From: simon Date: Sat, 18 Aug 2007 10:07:29 +0000 (+0000) Subject: A piece of library code which constructs a random division of a X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/commitdiff_plain/11d273f702540eb5b003836f96f2537c74b94064 A piece of library code which constructs a random division of a rectangle into equally sized ominoes. I have a couple of potential applications for this, but none I've actually implemented yet, so for the moment it's living in `unfinished'. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@7690 cda61777-01e9-0310-a592-d414129be87e --- diff --git a/unfinished/divvy.c b/unfinished/divvy.c new file mode 100644 index 0000000..9e6805d --- /dev/null +++ b/unfinished/divvy.c @@ -0,0 +1,533 @@ +/* + * Library code to divide up a rectangle into a number of equally + * sized ominoes, in a random fashion. + * + * Could use this for generating solved grids of + * http://www.nikoli.co.jp/ja/puzzles/block_puzzle/ + * or for generating the playfield for Jigsaw Sudoku. + */ + +#include +#include +#include +#include + +#include "puzzles.h" + +/* + * Subroutine which implements a function used in computing both + * whether a square can safely be added to an omino, and whether + * it can safely be removed. + * + * We enumerate the eight squares 8-adjacent to this one, in + * cyclic order. We go round that loop and count the number of + * times we find a square owned by the target omino next to one + * not owned by it. We then return success iff that count is 2. + * + * When adding a square to an omino, this is precisely the + * criterion which tells us that adding the square won't leave a + * hole in the middle of the omino. (There's no explicit + * requirement in the statement of our problem that the ominoes be + * simply connected, but we do know they must be all of equal size + * and so it's clear that we must avoid leaving holes, since a + * hole would necessarily be smaller than the maximum omino size.) + * + * When removing a square from an omino, the _same_ criterion + * tells us that removing the square won't disconnect the omino. + */ +static int addremcommon(int w, int h, int x, int y, int *own, int val) +{ + int neighbours[8]; + int dir, count; + + for (dir = 0; dir < 8; dir++) { + int dx = ((dir & 3) == 2 ? 0 : dir > 2 && dir < 6 ? +1 : -1); + int dy = ((dir & 3) == 0 ? 0 : dir < 4 ? -1 : +1); + int sx = x+dx, sy = y+dy; + + if (sx < 0 || sx >= w || sy < 0 || sy >= h) + neighbours[dir] = -1; /* outside the grid */ + else + neighbours[dir] = own[sy*w+sx]; + } + + /* + * To begin with, check 4-adjacency. + */ + if (neighbours[0] != val && neighbours[2] != val && + neighbours[4] != val && neighbours[6] != val) + return FALSE; + + count = 0; + + for (dir = 0; dir < 8; dir++) { + int next = (dir + 1) & 7; + int gotthis = (neighbours[dir] == val); + int gotnext = (neighbours[next] == val); + + if (gotthis != gotnext) + count++; + } + + return (count == 2); +} + +/* + * w and h are the dimensions of the rectangle. + * + * k is the size of the required ominoes. (So k must divide w*h, + * of course.) + * + * The returned result is a w*h-sized dsf. + * + * In both of the above suggested use cases, the user would + * probably want w==h==k, but that isn't a requirement. + */ +int *divvy_rectangle(int w, int h, int k, random_state *rs) +{ + int *order, *queue, *tmp, *own, *sizes, *addable, *removable, *retdsf; + int wh = w*h; + int i, j, n, x, y, qhead, qtail; + + n = wh / k; + assert(wh == k*n); + + order = snewn(wh, int); + tmp = snewn(wh, int); + own = snewn(wh, int); + sizes = snewn(n, int); + queue = snewn(n, int); + addable = snewn(wh*4, int); + removable = snewn(wh, int); + + /* + * Permute the grid squares into a random order, which will be + * used for iterating over the grid whenever we need to search + * for something. This prevents directional bias and arranges + * for the answer to be non-deterministic. + */ + for (i = 0; i < wh; i++) + order[i] = i; + shuffle(order, wh, sizeof(*order), rs); + + /* + * Begin by choosing a starting square at random for each + * omino. + */ + for (i = 0; i < wh; i++) { + own[i] = -1; + } + for (i = 0; i < n; i++) { + own[order[i]] = i; + sizes[i] = 1; + } + + /* + * Now repeatedly pick a random omino which isn't already at + * the target size, and find a way to expand it by one. This + * may involve stealing a square from another omino, in which + * case we then re-expand that omino, forming a chain of + * square-stealing which terminates in an as yet unclaimed + * square. Hence every successful iteration around this loop + * causes the number of unclaimed squares to drop by one, and + * so the process is bounded in duration. + */ + while (1) { + +#ifdef DIVVY_DIAGNOSTICS + { + int x, y; + printf("Top of loop. Current grid:\n"); + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) + printf("%3d", own[y*w+x]); + printf("\n"); + } + } +#endif + + /* + * Go over the grid and figure out which squares can + * safely be added to, or removed from, each omino. We + * don't take account of other ominoes in this process, so + * we will often end up knowing that a square can be + * poached from one omino by another. + * + * For each square, there may be up to four ominoes to + * which it can be added (those to which it is + * 4-adjacent). + */ + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int yx = y*w+x; + int curr = own[yx]; + int dir; + + if (curr < 0) { + removable[yx] = 0; /* can't remove if it's not owned! */ + } else { + /* + * See if this square can be removed from its + * omino without disconnecting it. + */ + removable[yx] = addremcommon(w, h, x, y, own, curr); + } + + for (dir = 0; dir < 4; dir++) { + int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0); + int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0); + int sx = x + dx, sy = y + dy; + int syx = sy*w+sx; + + addable[yx*4+dir] = -1; + + if (sx < 0 || sx >= w || sy < 0 || sy >= h) + continue; /* no omino here! */ + if (own[syx] < 0) + continue; /* also no omino here */ + if (own[syx] == own[yx]) + continue; /* we already got one */ + if (!addremcommon(w, h, x, y, own, own[syx])) + continue; /* would non-simply connect the omino */ + + addable[yx*4+dir] = own[syx]; + } + } + } + + for (i = j = 0; i < n; i++) + if (sizes[i] < k) + tmp[j++] = i; + if (j == 0) + break; /* all ominoes are complete! */ + j = tmp[random_upto(rs, j)]; + + /* + * So we're trying to expand omino j. We breadth-first + * search out from j across the space of ominoes. + * + * For bfs purposes, we use two elements of tmp per omino: + * tmp[2*i+0] tells us which omino we got to i from, and + * tmp[2*i+1] numbers the grid square that omino stole + * from us. + * + * This requires that wh (the size of tmp) is at least 2n, + * i.e. k is at least 2. There would have been nothing to + * stop a user calling this function with k=1, but if they + * did then we wouldn't have got to _here_ in the code - + * we would have noticed above that all ominoes were + * already at their target sizes, and terminated :-) + */ + assert(wh >= 2*n); + for (i = 0; i < n; i++) + tmp[2*i] = tmp[2*i+1] = -1; + qhead = qtail = 0; + queue[qtail++] = j; + tmp[2*j] = tmp[2*j+1] = -2; /* special value: `starting point' */ + + while (qhead < qtail) { + int tmpsq; + + j = queue[qhead]; + + /* + * We wish to expand omino j. However, we might have + * got here by omino j having a square stolen from it, + * so first of all we must temporarily mark that + * square as not belonging to j, so that our adjacency + * calculations don't assume j _does_ belong to us. + */ + tmpsq = tmp[2*j+1]; + if (tmpsq >= 0) { + assert(own[tmpsq] == j); + own[tmpsq] = -1; + } + + /* + * OK. Now begin by seeing if we can find any + * unclaimed square into which we can expand omino j. + * If we find one, the entire bfs terminates. + */ + for (i = 0; i < wh; i++) { + int dir; + + if (own[order[i]] >= 0) + continue; /* this square is claimed */ + for (dir = 0; dir < 4; dir++) + if (addable[order[i]*4+dir] == j) { + /* + * We know this square is addable to this + * omino with the grid in the state it had + * at the top of the loop. However, we + * must now check that it's _still_ + * addable to this omino when the omino is + * missing a square. To do this it's only + * necessary to re-check addremcommon. +~|~ */ + if (!addremcommon(w, h, order[i]%w, order[i]/w, + own, j)) + continue; + break; + } + if (dir == 4) + continue; /* we can't add this square to j */ + break; /* got one! */ + } + if (i < wh) { + i = order[i]; + + /* + * We are done. We can add square i to omino j, + * and then backtrack along the trail in tmp + * moving squares between ominoes, ending up + * expanding our starting omino by one. + */ + while (1) { + own[i] = j; + if (tmp[2*j] == -2) + break; + i = tmp[2*j+1]; + j = tmp[2*j]; + } + + /* + * Increment the size of the starting omino. + */ + sizes[j]++; + + /* + * Terminate the bfs loop. + */ + break; + } + + /* + * If we get here, we haven't been able to expand + * omino j into an unclaimed square. So now we begin + * to investigate expanding it into squares which are + * claimed by ominoes the bfs has not yet visited. + */ + for (i = 0; i < wh; i++) { + int dir, nj; + + nj = own[order[i]]; + if (nj < 0 || tmp[2*nj] != -1) + continue; /* unclaimed, or owned by wrong omino */ + if (!removable[order[i]]) + continue; /* its omino won't let it go */ + + for (dir = 0; dir < 4; dir++) + if (addable[order[i]*4+dir] == j) { + /* + * As above, re-check addremcommon. + */ + if (!addremcommon(w, h, order[i]%w, order[i]/w, + own, j)) + continue; + + /* + * We have found a square we can use to + * expand omino j, at the expense of the + * as-yet unvisited omino nj. So add this + * to the bfs queue. + */ + assert(qtail < n); + queue[qtail++] = nj; + tmp[2*nj] = j; + tmp[2*nj+1] = order[i]; + + /* + * Now terminate the loop over dir, to + * ensure we don't accidentally add the + * same omino twice to the queue. + */ + break; + } + } + + /* + * Restore the temporarily removed square. + */ + if (tmpsq >= 0) + own[tmpsq] = j; + + /* + * Advance the queue head. + */ + qhead++; + } + + if (qhead == qtail) { + /* + * We have finished the bfs and not found any way to + * expand omino j. Panic, and return failure. + * + * FIXME: or should we loop over all ominoes before we + * give up? + */ + retdsf = NULL; + goto cleanup; + } + } + + /* + * Construct the output dsf. + */ + for (i = 0; i < wh; i++) { + assert(own[i] >= 0 && own[i] < n); + tmp[own[i]] = i; + } + retdsf = snew_dsf(wh); + for (i = 0; i < wh; i++) { + dsf_merge(retdsf, i, tmp[own[i]]); + } + + /* + * Construct the output dsf a different way, to verify that + * the ominoes really are k-ominoes and we haven't + * accidentally split one into two disconnected pieces. + */ + dsf_init(tmp, wh); + for (y = 0; y < h; y++) + for (x = 0; x+1 < w; x++) + if (own[y*w+x] == own[y*w+(x+1)]) + dsf_merge(tmp, y*w+x, y*w+(x+1)); + for (x = 0; x < w; x++) + for (y = 0; y+1 < h; y++) + if (own[y*w+x] == own[(y+1)*w+x]) + dsf_merge(tmp, y*w+x, (y+1)*w+x); + for (i = 0; i < wh; i++) { + j = dsf_canonify(retdsf, i); + assert(dsf_canonify(tmp, j) == dsf_canonify(tmp, i)); + } + + cleanup: + + /* + * Free our temporary working space. + */ + sfree(order); + sfree(tmp); + sfree(own); + sfree(sizes); + sfree(queue); + sfree(addable); + sfree(removable); + + /* + * And we're done. + */ + return retdsf; +} + +#ifdef TESTMODE + +/* + * gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c + * + * or to debug + * + * gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c + */ + +int main(int argc, char **argv) +{ + int *dsf; + int i, successes; + int w = 9, h = 4, k = 6, tries = 100; + random_state *rs; + + rs = random_new("123456", 6); + + if (argc > 1) + w = atoi(argv[1]); + if (argc > 2) + h = atoi(argv[2]); + if (argc > 3) + k = atoi(argv[3]); + if (argc > 4) + tries = atoi(argv[4]); + + successes = 0; + for (i = 0; i < tries; i++) { + dsf = divvy_rectangle(w, h, k, rs); + if (dsf) { + int x, y; + + successes++; + + for (y = 0; y <= 2*h; y++) { + for (x = 0; x <= 2*w; x++) { + int miny = y/2 - 1, maxy = y/2; + int minx = x/2 - 1, maxx = x/2; + int classes[4], tx, ty; + for (ty = 0; ty < 2; ty++) + for (tx = 0; tx < 2; tx++) { + int cx = minx+tx, cy = miny+ty; + if (cx < 0 || cx >= w || cy < 0 || cy >= h) + classes[ty*2+tx] = -1; + else + classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx); + } + switch (y%2 * 2 + x%2) { + case 0: /* corner */ + /* + * Cases for the corner: + * + * - if all four surrounding squares + * belong to the same omino, we print a + * space. + * + * - if the top two are the same and the + * bottom two are the same, we print a + * horizontal line. + * + * - if the left two are the same and the + * right two are the same, we print a + * vertical line. + * + * - otherwise, we print a cross. + */ + if (classes[0] == classes[1] && + classes[1] == classes[2] && + classes[2] == classes[3]) + printf(" "); + else if (classes[0] == classes[1] && + classes[2] == classes[3]) + printf("-"); + else if (classes[0] == classes[2] && + classes[1] == classes[3]) + printf("|"); + else + printf("+"); + break; + case 1: /* horiz edge */ + if (classes[1] == classes[3]) + printf(" "); + else + printf("--"); + break; + case 2: /* vert edge */ + if (classes[2] == classes[3]) + printf(" "); + else + printf("|"); + break; + case 3: /* square centre */ + printf(" "); + break; + } + } + printf("\n"); + } + printf("\n"); + sfree(dsf); + } + } + + printf("%d successes out of %d tries\n", successes, tries); + + return 0; +} + +#endif