ref: cc54c09413a08ea150fd8cc6706ed61ccc8ce47e
parent: 2842817eda5892783a8287b8d32d1b3baeb11dc8
author: Simon Tatham <anakin@pobox.com>
date: Sat Aug 18 06:07:29 EDT 2007
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'. [originally from svn r7690]
--- /dev/null
+++ b/unfinished/divvy.c
@@ -1,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 <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stddef.h>
+
+#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