+ /*
+ * 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 */
+
+ /*
+ * Shuffle the list.
+ */
+ shuffle(list, n, sizeof(*list), rs);
+
+#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 and
+ * actually attempt to insert something there.
+ */
+ while (n-- > 0) {
+ int dirs[4], ndirs, dir;
+
+ pos = 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
+
+ for (x1 = x2 = 0; x2 < w; x2++) {
+ int usedcol = FALSE;
+
+ for (y1 = y2 = h-1; y2 >= 0; y2--) {
+ if (grid2[y2*w+x2] == tc) {
+ ntc++;
+ if (fillstart == -1)
+ fillstart = y2*w+x2;
+ if ((y2+1 < h && grid2[(y2+1)*w+x2] == c) ||
+ (y2-1 >= 0 && grid2[(y2-1)*w+x2] == c) ||
+ (x2+1 < w && grid2[y2*w+x2+1] == c) ||
+ (x2-1 >= 0 && grid2[y2*w+x2-1] == c)) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("adjacency failure at %d,%d\n",
+ x2, y2);
+#endif
+ ok = FALSE;
+ }
+ continue;
+ }
+ if (grid2[y2*w+x2] == 0)
+ break;
+ usedcol = TRUE;
+ if (grid2[y2*w+x2] != grid[y1*w+x1]) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("matching failure at %d,%d vs %d,%d\n",
+ x2, y2, x1, y1);
+#endif
+ ok = FALSE;
+ }
+ y1--;
+ }
+
+ /*
+ * If we've reached the top of the column
+ * in grid2, verify that we've also reached
+ * the top of the column in `grid'.
+ */
+ if (usedcol) {
+ while (y1 >= 0) {
+ if (grid[y1*w+x1] != 0) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("junk at column top (%d,%d)\n",
+ x1, y1);
+#endif
+ ok = FALSE;
+ }
+ y1--;
+ }
+ }
+
+ if (!ok)
+ break;
+
+ if (usedcol)
+ x1++;
+ }
+
+ if (!ok) {
+ assert(!"This should never happen");
+
+ /*
+ * If this game is compiled NDEBUG so that
+ * the assertion doesn't bring it to a
+ * crashing halt, the only thing we can do
+ * is to give up, loop round again, and
+ * hope to randomly avoid making whatever
+ * type of move just caused this failure.
+ */
+ continue;
+ }
+
+ /*
+ * Now use bfs to fill in the tc section as
+ * colour c. We use `list' to store the set of
+ * squares we have to process.
+ */
+ i = j = 0;
+ assert(fillstart >= 0);
+ list[i++] = fillstart;
+#ifdef OUTPUT_SOLUTION
+ printf("M");
+#endif
+ while (j < i) {
+ k = list[j];
+ x = k % w;
+ y = k / w;
+#ifdef OUTPUT_SOLUTION
+ printf("%s%d", j ? "," : "", k);
+#endif
+ j++;
+
+ assert(grid2[k] == tc);
+ grid2[k] = c;
+
+ if (x > 0 && grid2[k-1] == tc)
+ list[i++] = k-1;
+ if (x+1 < w && grid2[k+1] == tc)
+ list[i++] = k+1;
+ if (y > 0 && grid2[k-w] == tc)
+ list[i++] = k-w;
+ if (y+1 < h && grid2[k+w] == tc)
+ list[i++] = k+w;
+ }
+#ifdef OUTPUT_SOLUTION
+ printf("\n");
+#endif
+
+ /*
+ * Check that we've filled the same number of
+ * tc squares as we originally found.
+ */
+ assert(j == ntc);
+ }
+
+ memcpy(grid, grid2, wh * sizeof(int));
+
+ break; /* done it! */
+ }
+
+#ifdef GENERATION_DIAGNOSTICS
+ {
+ int x,y;
+ printf("n=%d\n", n);
+ 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
+
+ if (n < 0)
+ break;
+ }
+
+ ok = TRUE;
+ for (i = 0; i < wh; i++)
+ if (grid[i] == 0) {
+ ok = FALSE;
+ failures++;
+#if defined GENERATION_DIAGNOSTICS || defined SHOW_INCOMPLETE
+ {
+ int x,y;
+ printf("incomplete grid:\n");
+ 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
+ break;
+ }
+
+ } while (!ok);
+
+#if defined GENERATION_DIAGNOSTICS || defined COUNT_FAILURES
+ printf("%d failures\n", failures);
+#endif
+#ifdef GENERATION_DIAGNOSTICS
+ {
+ int x,y;
+ printf("final grid:\n");
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ printf("%d", grid[y*w+x]);
+ }
+ printf("\n");
+ }
+ }
+#endif
+
+ sfree(grid2);
+ sfree(list);
+}
+
+/*
+ * Not-guaranteed-soluble grid generator; kept as a legacy, and in
+ * case someone finds the slightly odd quality of the guaranteed-
+ * soluble grids to be aesthetically displeasing or finds its CPU
+ * utilisation to be excessive.
+ */
+static void gen_grid_random(int w, int h, int nc, int *grid, random_state *rs)