X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/4413ef0febdc131ec0ea3661fcd3466063b31494..7fb7e7c120bf5d4e2dba21f1a76ea98c51b5b818:/dominosa.c diff --git a/dominosa.c b/dominosa.c index f9d55d6..68422b7 100644 --- a/dominosa.c +++ b/dominosa.c @@ -109,8 +109,12 @@ static int game_fetch_preset(int i, char **name, game_params **params) switch (i) { case 0: n = 3; break; - case 1: n = 6; break; - case 2: n = 9; break; + case 1: n = 4; break; + case 2: n = 5; break; + case 3: n = 6; break; + case 4: n = 7; break; + case 5: n = 8; break; + case 6: n = 9; break; default: return FALSE; } @@ -546,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; /* @@ -586,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 @@ -1171,6 +941,11 @@ static char *solve_game(game_state *state, game_state *currstate, return ret; } +static int game_can_format_as_text_now(game_params *params) +{ + return TRUE; +} + static char *game_text_format(game_state *state) { return NULL; @@ -1439,7 +1214,7 @@ static void game_set_size(drawing *dr, game_drawstate *ds, ds->tilesize = tilesize; } -static float *game_colours(frontend *fe, game_state *state, int *ncolours) +static float *game_colours(frontend *fe, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); @@ -1682,11 +1457,6 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_wants_statusbar(void) -{ - return FALSE; -} - static int game_timing_state(game_state *state, game_ui *ui) { return TRUE; @@ -1700,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) @@ -1745,7 +1515,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) #endif const struct game thegame = { - "Dominosa", "games.dominosa", + "Dominosa", "games.dominosa", "dominosa", default_params, game_fetch_preset, decode_params, @@ -1760,7 +1530,7 @@ const struct game thegame = { dup_game, free_game, TRUE, solve_game, - FALSE, game_text_format, + FALSE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, @@ -1776,7 +1546,10 @@ const struct game thegame = { game_anim_length, game_flash_length, TRUE, FALSE, game_print_size, game_print, - game_wants_statusbar, + FALSE, /* wants_statusbar */ FALSE, game_timing_state, - 0, /* mouse_priorities */ + 0, /* flags */ }; + +/* vim: set shiftwidth=4 :set textwidth=80: */ +