From 4700b8499251fc0361d522cbdcade99d9c08e8bb Mon Sep 17 00:00:00 2001 From: simon Date: Mon, 2 Mar 2009 19:45:59 +0000 Subject: [PATCH] Patch from James H to abstract out of Dominosa the code which randomly generates a tiling of a rectangle with dominoes, since he wants to reuse that function in another puzzle. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@8488 cda61777-01e9-0310-a592-d414129be87e --- dominosa.R | 8 +- dominosa.c | 245 ++------------------------------------------------ laydomino.c | 291 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ puzzles.h | 6 ++ 4 files changed, 309 insertions(+), 241 deletions(-) create mode 100644 laydomino.c diff --git a/dominosa.R b/dominosa.R index 252bff8..2282653 100644 --- a/dominosa.R +++ b/dominosa.R @@ -1,10 +1,12 @@ # -*- makefile -*- -dominosa : [X] GTK COMMON dominosa dominosa-icon|no-icon +DOMINOSA_EXTRA = laydomino -dominosa : [G] WINDOWS COMMON dominosa dominosa.res|noicon.res +dominosa : [X] GTK COMMON dominosa DOMINOSA_EXTRA dominosa-icon|no-icon -ALL += dominosa[COMBINED] +dominosa : [G] WINDOWS COMMON dominosa DOMINOSA_EXTRA dominosa.res|noicon.res + +ALL += dominosa[COMBINED] DOMINOSA_EXTRA !begin gtk GAMES += dominosa diff --git a/dominosa.c b/dominosa.c index bd170dc..68422b7 100644 --- a/dominosa.c +++ b/dominosa.c @@ -550,7 +550,7 @@ static char *new_game_desc(game_params *params, random_state *rs, { int n = params->n, w = n+2, h = n+1, wh = w*h; int *grid, *grid2, *list; - int i, j, k, m, todo, done, len; + int i, j, k, len; char *ret; /* @@ -590,241 +590,7 @@ static char *new_game_desc(game_params *params, random_state *rs, */ do { - /* - * 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.) - */ - for (i = 0; i < wh; i++) - if (grid[i] == i) - break; - if (i == wh) - break; /* no more singletons; 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 - } + domino_layout_prealloc(w, h, rs, grid, grid2, list); /* * Now we have a complete layout covering the whole @@ -1704,8 +1470,8 @@ static void game_print_size(game_params *params, float *x, float *y) * I'll use 6mm squares by default. */ game_compute_size(params, 600, &pw, &ph); - *x = pw / 100.0; - *y = ph / 100.0; + *x = pw / 100.0F; + *y = ph / 100.0F; } static void game_print(drawing *dr, game_state *state, int tilesize) @@ -1784,3 +1550,6 @@ const struct game thegame = { FALSE, game_timing_state, 0, /* flags */ }; + +/* vim: set shiftwidth=4 :set textwidth=80: */ + 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: */ + diff --git a/puzzles.h b/puzzles.h index 0e0cf97..69476ae 100644 --- a/puzzles.h +++ b/puzzles.h @@ -339,6 +339,12 @@ void dsf_merge(int *dsf, int v1, int v2); void dsf_init(int *dsf, int len); /* + * laydomino.c + */ +int *domino_layout(int w, int h, random_state *rs); +void domino_layout_prealloc(int w, int h, random_state *rs, + int *grid, int *grid2, int *list); +/* * version.c */ extern char ver[]; -- 2.11.0