+static void gen_grid(int w, int h, int nc, int *grid, random_state *rs)
+{
+ int wh = w*h, tc = nc+1;
+ int i, j, k, c, x, y, pos, n;
+ int *list, *grid2;
+ int ok, failures = 0;
+
+ /*
+ * We'll use `list' to track the possible places to put our
+ * next insertion. There are up to h places to insert in each
+ * column: in a column of height n there are n+1 places because
+ * we can insert at the very bottom or the very top, but a
+ * column of height h can't have anything at all inserted in it
+ * so we have up to h in each column. Likewise, with n columns
+ * present there are n+1 places to fit a new one in between but
+ * we can't insert a column if there are already w; so there
+ * are a maximum of w new columns too. Total is wh + w.
+ */
+ list = snewn(wh + w, int);
+ grid2 = snewn(wh, int);
+
+ do {
+ /*
+ * Start with two or three squares - depending on parity of w*h
+ * - of a random colour.
+ */
+ for (i = 0; i < wh; i++)
+ grid[i] = 0;
+ j = 2 + (wh % 2);
+ c = 1 + random_upto(rs, nc);
+ if (j <= w) {
+ for (i = 0; i < j; i++)
+ grid[(h-1)*w+i] = c;
+ } else {
+ assert(j <= h);
+ for (i = 0; i < j; i++)
+ grid[(h-1-i)*w] = c;
+ }
+
+ /*
+ * Now repeatedly insert a two-square blob in the grid, of
+ * whatever colour will go at the position we chose.
+ */
+ while (1) {
+ n = 0;
+
+ /*
+ * Build up a list of insertion points. Each point is
+ * encoded as y*w+x; insertion points between columns are
+ * encoded as h*w+x.
+ */
+
+ if (grid[wh - 1] == 0) {
+ /*
+ * The final column is empty, so we can insert new
+ * columns.
+ */
+ for (i = 0; i < w; i++) {
+ list[n++] = wh + i;
+ if (grid[(h-1)*w + i] == 0)
+ break;
+ }
+ }
+
+ /*
+ * Now look for places to insert within columns.
+ */
+ for (i = 0; i < w; i++) {
+ if (grid[(h-1)*w+i] == 0)
+ break; /* no more columns */
+
+ if (grid[i] != 0)
+ continue; /* this column is full */
+
+ for (j = h; j-- > 0 ;) {
+ list[n++] = j*w+i;
+ if (grid[j*w+i] == 0)
+ break; /* this column is exhausted */
+ }
+ }
+
+ if (n == 0)
+ break; /* we're done */
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("initial grid:\n");
+ {
+ int x,y;
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (grid[y*w+x] == 0)
+ printf("-");
+ else
+ printf("%d", grid[y*w+x]);
+ }
+ printf("\n");
+ }
+ }
+#endif
+
+ /*
+ * Now go through the list one element at a time in
+ * random order, and actually attempt to insert
+ * something there.
+ */
+ while (n-- > 0) {
+ int dirs[4], ndirs, dir;
+
+ i = random_upto(rs, n+1);
+ pos = list[i];
+ list[i] = list[n];
+
+ x = pos % w;
+ y = pos / w;
+
+ memcpy(grid2, grid, wh * sizeof(int));
+
+ if (y == h) {
+ /*
+ * Insert a column at position x.
+ */
+ for (i = w-1; i > x; i--)
+ for (j = 0; j < h; j++)
+ grid2[j*w+i] = grid2[j*w+(i-1)];
+ /*
+ * Clear the new column.
+ */
+ for (j = 0; j < h; j++)
+ grid2[j*w+x] = 0;
+ /*
+ * Decrement y so that our first square is actually
+ * inserted _in_ the grid rather than just below it.
+ */
+ y--;
+ }
+
+ /*
+ * Insert a square within column x at position y.
+ */
+ for (i = 0; i+1 <= y; i++)
+ grid2[i*w+x] = grid2[(i+1)*w+x];
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("trying at n=%d (%d,%d)\n", n, x, y);
+ grid2[y*w+x] = tc;
+ {
+ int x,y;
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (grid2[y*w+x] == 0)
+ printf("-");
+ else if (grid2[y*w+x] <= nc)
+ printf("%d", grid2[y*w+x]);
+ else
+ printf("*");
+ }
+ printf("\n");
+ }
+ }
+#endif
+
+ /*
+ * Pick our square colour so that it doesn't match any
+ * of its neighbours.
+ */
+ {
+ int wrongcol[4], nwrong = 0;
+
+ /*
+ * List the neighbouring colours.
+ */
+ if (x > 0)
+ wrongcol[nwrong++] = grid2[y*w+(x-1)];
+ if (x+1 < w)
+ wrongcol[nwrong++] = grid2[y*w+(x+1)];
+ if (y > 0)
+ wrongcol[nwrong++] = grid2[(y-1)*w+x];
+ if (y+1 < h)
+ wrongcol[nwrong++] = grid2[(y+1)*w+x];
+
+ /*
+ * Eliminate duplicates. We can afford a shoddy
+ * algorithm here because the problem size is
+ * bounded.
+ */
+ for (i = j = 0 ;; i++) {
+ int pos = -1, min = 0;
+ if (j > 0)
+ min = wrongcol[j-1];
+ for (k = i; k < nwrong; k++)
+ if (wrongcol[k] > min &&
+ (pos == -1 || wrongcol[k] < wrongcol[pos]))
+ pos = k;
+ if (pos >= 0) {
+ int v = wrongcol[pos];
+ wrongcol[pos] = wrongcol[j];
+ wrongcol[j++] = v;
+ } else
+ break;
+ }
+ nwrong = j;
+
+ /*
+ * If no colour will go here, stop trying.
+ */
+ if (nwrong == nc)
+ continue;
+
+ /*
+ * Otherwise, pick a colour from the remaining
+ * ones.
+ */
+ c = 1 + random_upto(rs, nc - nwrong);
+ for (i = 0; i < nwrong; i++) {
+ if (c >= wrongcol[i])
+ c++;
+ else
+ break;
+ }
+ }
+
+ /*
+ * Place the new square.
+ *
+ * Although I've _chosen_ the new region's colour
+ * (so that we can check adjacency), I'm going to
+ * actually place it as an invalid colour (tc)
+ * until I'm sure it's viable. This is so that I
+ * can conveniently check that I really have made a
+ * _valid_ inverse move later on.
+ */
+#ifdef GENERATION_DIAGNOSTICS
+ printf("picked colour %d\n", c);
+#endif
+ grid2[y*w+x] = tc;
+
+ /*
+ * Now attempt to extend it in one of three ways: left,
+ * right or up.
+ */
+ ndirs = 0;
+ if (x > 0 &&
+ grid2[y*w+(x-1)] != c &&
+ grid2[x-1] == 0 &&
+ (y+1 >= h || grid2[(y+1)*w+(x-1)] != c) &&
+ (y+1 >= h || grid2[(y+1)*w+(x-1)] != 0) &&
+ (x <= 1 || grid2[y*w+(x-2)] != c))
+ dirs[ndirs++] = -1; /* left */
+ if (x+1 < w &&
+ grid2[y*w+(x+1)] != c &&
+ grid2[x+1] == 0 &&
+ (y+1 >= h || grid2[(y+1)*w+(x+1)] != c) &&
+ (y+1 >= h || grid2[(y+1)*w+(x+1)] != 0) &&
+ (x+2 >= w || grid2[y*w+(x+2)] != c))
+ dirs[ndirs++] = +1; /* right */
+ if (y > 0 &&
+ grid2[x] == 0 &&
+ (x <= 0 || grid2[(y-1)*w+(x-1)] != c) &&
+ (x+1 >= w || grid2[(y-1)*w+(x+1)] != c)) {
+ /*
+ * We add this possibility _twice_, so that the
+ * probability of placing a vertical domino is
+ * about the same as that of a horizontal. This
+ * should yield less bias in the generated
+ * grids.
+ */
+ dirs[ndirs++] = 0; /* up */
+ dirs[ndirs++] = 0; /* up */
+ }
+
+ if (ndirs == 0)
+ continue;
+
+ dir = dirs[random_upto(rs, ndirs)];
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("picked dir %d\n", dir);
+#endif
+
+ /*
+ * Insert a square within column (x+dir) at position y.
+ */
+ for (i = 0; i+1 <= y; i++)
+ grid2[i*w+x+dir] = grid2[(i+1)*w+x+dir];
+ grid2[y*w+x+dir] = tc;
+
+ /*
+ * See if we've divided the remaining grid squares
+ * into sub-areas. If so, we need every sub-area to
+ * have an even area or we won't be able to
+ * complete generation.
+ *
+ * If the height is odd and not all columns are
+ * present, we can increase the area of a subarea
+ * by adding a new column in it, so in that
+ * situation we don't mind having as many odd
+ * subareas as there are spare columns.
+ *
+ * If the height is even, we can't fix it at all.
+ */
+ {
+ int nerrs = 0, nfix = 0;
+ k = 0; /* current subarea size */
+ for (i = 0; i < w; i++) {
+ if (grid2[(h-1)*w+i] == 0) {
+ if (h % 2)
+ nfix++;
+ continue;
+ }
+ for (j = 0; j < h && grid2[j*w+i] == 0; j++);
+ assert(j < h);
+ if (j == 0) {
+ /*
+ * End of previous subarea.
+ */
+ if (k % 2)
+ nerrs++;
+ k = 0;
+ } else {
+ k += j;
+ }
+ }
+ if (k % 2)
+ nerrs++;
+ if (nerrs > nfix)
+ continue; /* try a different placement */
+ }
+
+ /*
+ * We've made a move. Verify that it is a valid
+ * move and that if made it would indeed yield the
+ * previous grid state. The criteria are:
+ *
+ * (a) removing all the squares of colour tc (and
+ * shuffling the columns up etc) from grid2
+ * would yield grid
+ * (b) no square of colour tc is adjacent to one
+ * of colour c
+ * (c) all the squares of colour tc form a single
+ * connected component
+ *
+ * We verify the latter property at the same time
+ * as checking that removing all the tc squares
+ * would yield the previous grid. Then we colour
+ * the tc squares in colour c by breadth-first
+ * search, which conveniently permits us to test
+ * that they're all connected.
+ */
+ {
+ int x1, x2, y1, y2;
+ int ok = TRUE;
+ int fillstart = -1, ntc = 0;
+
+#ifdef GENERATION_DIAGNOSTICS
+ {
+ int x,y;
+ printf("testing move (new, old):\n");
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (grid2[y*w+x] == 0)
+ printf("-");
+ else if (grid2[y*w+x] <= nc)
+ printf("%d", grid2[y*w+x]);
+ else
+ printf("*");
+ }
+ printf(" ");
+ for (x = 0; x < w; x++) {
+ if (grid[y*w+x] == 0)
+ printf("-");
+ else
+ printf("%d", grid[y*w+x]);
+ }
+ printf("\n");
+ }
+ }
+#endif