--- /dev/null
+/*
+ * laydomino.c: code for performing a domino (2x1 tile) layout of
+ * a given area of code.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include "puzzles.h"
+
+/*
+ * This function returns an array size w x h representing a grid:
+ * each grid[i] = j, where j is the other end of a 2x1 domino.
+ * If w*h is odd, one square will remain referring to itself.
+ */
+
+int *domino_layout(int w, int h, random_state *rs)
+{
+ int *grid, *grid2, *list;
+ int wh = w*h;
+
+ /*
+ * Allocate space in which to lay the grid out.
+ */
+ grid = snewn(wh, int);
+ grid2 = snewn(wh, int);
+ list = snewn(2*wh, int);
+
+ domino_layout_prealloc(w, h, rs, grid, grid2, list);
+
+ sfree(grid2);
+ sfree(list);
+
+ return grid;
+}
+
+/*
+ * As for domino_layout, but with preallocated buffers.
+ * grid and grid2 should be size w*h, and list size 2*w*h.
+ */
+void domino_layout_prealloc(int w, int h, random_state *rs,
+ int *grid, int *grid2, int *list)
+{
+ int i, j, k, m, wh = w*h, todo, done;
+
+ /*
+ * To begin with, set grid[i] = i for all i to indicate
+ * that all squares are currently singletons. Later we'll
+ * set grid[i] to be the index of the other end of the
+ * domino on i.
+ */
+ for (i = 0; i < wh; i++)
+ grid[i] = i;
+
+ /*
+ * Now prepare a list of the possible domino locations. There
+ * are w*(h-1) possible vertical locations, and (w-1)*h
+ * horizontal ones, for a total of 2*wh - h - w.
+ *
+ * I'm going to denote the vertical domino placement with
+ * its top in square i as 2*i, and the horizontal one with
+ * its left half in square i as 2*i+1.
+ */
+ k = 0;
+ for (j = 0; j < h-1; j++)
+ for (i = 0; i < w; i++)
+ list[k++] = 2 * (j*w+i); /* vertical positions */
+ for (j = 0; j < h; j++)
+ for (i = 0; i < w-1; i++)
+ list[k++] = 2 * (j*w+i) + 1; /* horizontal positions */
+ assert(k == 2*wh - h - w);
+
+ /*
+ * Shuffle the list.
+ */
+ shuffle(list, k, sizeof(*list), rs);
+
+ /*
+ * Work down the shuffled list, placing a domino everywhere
+ * we can.
+ */
+ for (i = 0; i < k; i++) {
+ int horiz, xy, xy2;
+
+ horiz = list[i] % 2;
+ xy = list[i] / 2;
+ xy2 = xy + (horiz ? 1 : w);
+
+ if (grid[xy] == xy && grid[xy2] == xy2) {
+ /*
+ * We can place this domino. Do so.
+ */
+ grid[xy] = xy2;
+ grid[xy2] = xy;
+ }
+ }
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("generated initial layout\n");
+#endif
+
+ /*
+ * Now we've placed as many dominoes as we can immediately
+ * manage. There will be squares remaining, but they'll be
+ * singletons. So loop round and deal with the singletons
+ * two by two.
+ */
+ while (1) {
+#ifdef GENERATION_DIAGNOSTICS
+ for (j = 0; j < h; j++) {
+ for (i = 0; i < w; i++) {
+ int xy = j*w+i;
+ int v = grid[xy];
+ int c = (v == xy+1 ? '[' : v == xy-1 ? ']' :
+ v == xy+w ? 'n' : v == xy-w ? 'U' : '.');
+ putchar(c);
+ }
+ putchar('\n');
+ }
+ putchar('\n');
+#endif
+
+ /*
+ * Our strategy is:
+ *
+ * First find a singleton square.
+ *
+ * Then breadth-first search out from the starting
+ * square. From that square (and any others we reach on
+ * the way), examine all four neighbours of the square.
+ * If one is an end of a domino, we move to the _other_
+ * end of that domino before looking at neighbours
+ * again. When we encounter another singleton on this
+ * search, stop.
+ *
+ * This will give us a path of adjacent squares such
+ * that all but the two ends are covered in dominoes.
+ * So we can now shuffle every domino on the path up by
+ * one.
+ *
+ * (Chessboard colours are mathematically important
+ * here: we always end up pairing each singleton with a
+ * singleton of the other colour. However, we never
+ * have to track this manually, since it's
+ * automatically taken care of by the fact that we
+ * always make an even number of orthogonal moves.)
+ */
+ k = 0;
+ for (j = 0; j < wh; j++) {
+ if (grid[j] == j) {
+ k++;
+ i = j; /* start BFS here. */
+ }
+ }
+ if (k == (wh % 2))
+ break; /* if area is even, we have no more singletons;
+ if area is odd, we have one singleton.
+ either way, we're done. */
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("starting b.f.s. at singleton %d\n", i);
+#endif
+ /*
+ * Set grid2 to -1 everywhere. It will hold our
+ * distance-from-start values, and also our
+ * backtracking data, during the b.f.s.
+ */
+ for (j = 0; j < wh; j++)
+ grid2[j] = -1;
+ grid2[i] = 0; /* starting square has distance zero */
+
+ /*
+ * Start our to-do list of squares. It'll live in
+ * `list'; since the b.f.s can cover every square at
+ * most once there is no need for it to be circular.
+ * We'll just have two counters tracking the end of the
+ * list and the squares we've already dealt with.
+ */
+ done = 0;
+ todo = 1;
+ list[0] = i;
+
+ /*
+ * Now begin the b.f.s. loop.
+ */
+ while (done < todo) {
+ int d[4], nd, x, y;
+
+ i = list[done++];
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("b.f.s. iteration from %d\n", i);
+#endif
+ x = i % w;
+ y = i / w;
+ nd = 0;
+ if (x > 0)
+ d[nd++] = i - 1;
+ if (x+1 < w)
+ d[nd++] = i + 1;
+ if (y > 0)
+ d[nd++] = i - w;
+ if (y+1 < h)
+ d[nd++] = i + w;
+ /*
+ * To avoid directional bias, process the
+ * neighbours of this square in a random order.
+ */
+ shuffle(d, nd, sizeof(*d), rs);
+
+ for (j = 0; j < nd; j++) {
+ k = d[j];
+ if (grid[k] == k) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("found neighbouring singleton %d\n", k);
+#endif
+ grid2[k] = i;
+ break; /* found a target singleton! */
+ }
+
+ /*
+ * We're moving through a domino here, so we
+ * have two entries in grid2 to fill with
+ * useful data. In grid[k] - the square
+ * adjacent to where we came from - I'm going
+ * to put the address _of_ the square we came
+ * from. In the other end of the domino - the
+ * square from which we will continue the
+ * search - I'm going to put the distance.
+ */
+ m = grid[k];
+
+ if (grid2[m] < 0 || grid2[m] > grid2[i]+1) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("found neighbouring domino %d/%d\n", k, m);
+#endif
+ grid2[m] = grid2[i]+1;
+ grid2[k] = i;
+ /*
+ * And since we've now visited a new
+ * domino, add m to the to-do list.
+ */
+ assert(todo < wh);
+ list[todo++] = m;
+ }
+ }
+
+ if (j < nd) {
+ i = k;
+#ifdef GENERATION_DIAGNOSTICS
+ printf("terminating b.f.s. loop, i = %d\n", i);
+#endif
+ break;
+ }
+
+ i = -1; /* just in case the loop terminates */
+ }
+
+ /*
+ * We expect this b.f.s. to have found us a target
+ * square.
+ */
+ assert(i >= 0);
+
+ /*
+ * Now we can follow the trail back to our starting
+ * singleton, re-laying dominoes as we go.
+ */
+ while (1) {
+ j = grid2[i];
+ assert(j >= 0 && j < wh);
+ k = grid[j];
+
+ grid[i] = j;
+ grid[j] = i;
+#ifdef GENERATION_DIAGNOSTICS
+ printf("filling in domino %d/%d (next %d)\n", i, j, k);
+#endif
+ if (j == k)
+ break; /* we've reached the other singleton */
+ i = k;
+ }
+#ifdef GENERATION_DIAGNOSTICS
+ printf("fixup path completed\n");
+#endif
+ }
+}
+
+/* vim: set shiftwidth=4 :set textwidth=80: */
+
~mdw / sgt / puzzles / blobdiff