X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/f52166e6af5dfc34f1acb7239939c69e0c35944a..4700b8499251fc0361d522cbdcade99d9c08e8bb:/laydomino.c diff --git a/laydomino.c b/laydomino.c new file mode 100644 index 0000000..cead5d5 --- /dev/null +++ b/laydomino.c @@ -0,0 +1,291 @@ +/* + * laydomino.c: code for performing a domino (2x1 tile) layout of + * a given area of code. + */ + +#include +#include +#include + +#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: */ +