X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=flood.c;h=f97de2fa7cf5b7885eb59ec2a128c0e561da7153;hb=3ce69e84cad15844282d691fa03e711c5353c05e;hp=42dc56ecf40b4d0dc58781fcce2748bf9bbe5d43;hpb=201b32983b5cd1f904da3614ee9136cfeec59818;p=sgt-puzzles.git diff --git a/flood.c b/flood.c index 42dc56e..f97de2f 100644 --- a/flood.c +++ b/flood.c @@ -27,6 +27,7 @@ #include #include +#include #include #include #include @@ -80,30 +81,36 @@ static game_params *default_params(void) return ret; } -static const struct game_params flood_presets[] = { - {12, 12, 6, 5}, - {12, 12, 6, 2}, - {12, 12, 6, 0}, - {16, 16, 6, 5}, - {16, 16, 6, 2}, - {16, 16, 6, 0}, +static const struct { + struct game_params preset; + const char *name; +} flood_presets[] = { + /* Default 12x12 size, three difficulty levels. */ + {{12, 12, 6, 5}, "12x12 Easy"}, + {{12, 12, 6, 2}, "12x12 Medium"}, + {{12, 12, 6, 0}, "12x12 Hard"}, + /* Larger puzzles, leaving off Easy in the expectation that people + * wanting a bigger grid will have played it enough to find Easy + * easy. */ + {{16, 16, 6, 2}, "16x16 Medium"}, + {{16, 16, 6, 0}, "16x16 Hard"}, + /* A couple of different colour counts. It seems generally not too + * hard with fewer colours (probably because fewer choices), so no + * extra moves for these modes. */ + {{12, 12, 3, 0}, "12x12, 3 colours"}, + {{12, 12, 4, 0}, "12x12, 4 colours"}, }; static int game_fetch_preset(int i, char **name, game_params **params) { game_params *ret; - char str[80]; if (i < 0 || i >= lenof(flood_presets)) return FALSE; ret = snew(game_params); - *ret = flood_presets[i]; - - sprintf(str, "%dx%d, %d colours, %d extra moves", - ret->w, ret->h, ret->colours, ret->leniency); - - *name = dupstr(str); + *ret = flood_presets[i].preset; + *name = dupstr(flood_presets[i].name); *params = ret; return TRUE; } @@ -215,21 +222,54 @@ static char *validate_params(const game_params *params, int full) return NULL; } +#if 0 +/* + * Bodge to permit varying the recursion depth for testing purposes. + +To test two Floods against each other: + +paste <(./flood.1 --generate 100 12x12c6m0#12345 | cut -f2 -d,) <(./flood.2 --generate 100 12x12c6m0#12345 | cut -f2 -d,) | awk '{print $2-$1}' | sort -n | uniq -c | awk '{print $2,$1}' | tee z + +and then run gnuplot and plot "z". + + */ +static int rdepth = 0; +#define RECURSION_DEPTH (rdepth) +void check_recursion_depth(void) +{ + if (!rdepth) { + const char *depthstr = getenv("FLOOD_DEPTH"); + rdepth = depthstr ? atoi(depthstr) : 1; + rdepth = rdepth > 0 ? rdepth : 1; + } +} +#else +/* + * Last time I empirically checked this, depth 3 was a noticeable + * improvement on 2, but 4 only negligibly better than 3. + */ +#define RECURSION_DEPTH 3 +#define check_recursion_depth() (void)0 +#endif + struct solver_scratch { int *queue[2]; int *dist; - char *grid, *grid2, *sparegrid; + char *grid, *grid2; + char *rgrids; }; static struct solver_scratch *new_scratch(int w, int h) { + int wh = w*h; struct solver_scratch *scratch = snew(struct solver_scratch); - scratch->queue[0] = snewn(w*h, int); - scratch->queue[1] = snewn(w*h, int); - scratch->dist = snewn(w*h, int); - scratch->grid = snewn(w*h, char); - scratch->grid2 = snewn(w*h, char); - scratch->sparegrid = snewn(w*h, char); + check_recursion_depth(); + scratch->queue[0] = snewn(wh, int); + scratch->queue[1] = snewn(wh, int); + scratch->dist = snewn(wh, int); + scratch->grid = snewn(wh, char); + scratch->grid2 = snewn(wh, char); + scratch->rgrids = snewn(wh * RECURSION_DEPTH, char); return scratch; } @@ -240,16 +280,24 @@ static void free_scratch(struct solver_scratch *scratch) sfree(scratch->dist); sfree(scratch->grid); sfree(scratch->grid2); - sfree(scratch->sparegrid); + sfree(scratch->rgrids); sfree(scratch); } #if 0 /* Diagnostic routines you can uncomment if you need them */ -void dump_grid(int w, int h, const char *grid, const char *title) +void dump_grid(int w, int h, const char *grid, const char *titlefmt, ...) { int x, y; - printf("%s:\n", title ? title : "Grid"); + if (titlefmt) { + va_list ap; + va_start(ap, titlefmt); + vprintf(titlefmt, ap); + va_end(ap); + printf(":\n"); + } else { + printf("Grid:\n"); + } for (y = 0; y < h; y++) { printf(" "); for (x = 0; x < w; x++) { @@ -259,10 +307,18 @@ void dump_grid(int w, int h, const char *grid, const char *title) } } -void dump_dist(int w, int h, const int *dists, const char *title) +void dump_dist(int w, int h, const int *dists, const char *titlefmt, ...) { int x, y; - printf("%s:\n", title ? title : "Distances"); + if (titlefmt) { + va_list ap; + va_start(ap, titlefmt); + vprintf(titlefmt, ap); + va_end(ap); + printf(":\n"); + } else { + printf("Distances:\n"); + } for (y = 0; y < h; y++) { printf(" "); for (x = 0; x < w; x++) { @@ -275,10 +331,12 @@ void dump_dist(int w, int h, const int *dists, const char *title) /* * Search a grid to find the most distant square(s). Return their - * distance and the number of them. + * distance and the number of them, and also the number of squares in + * the current controlled set (i.e. at distance zero). */ static void search(int w, int h, char *grid, int x0, int y0, - struct solver_scratch *scratch, int *rdist, int *rnumber) + struct solver_scratch *scratch, + int *rdist, int *rnumber, int *rcontrol) { int wh = w*h; int i, qcurr, qhead, qtail, qnext, currdist, remaining; @@ -298,6 +356,8 @@ static void search(int w, int h, char *grid, int x0, int y0, while (1) { if (qtail == qhead) { /* Switch queues. */ + if (currdist == 0) + *rcontrol = qhead; currdist++; qcurr ^= 1; /* switch queues */ qhead = qnext; @@ -345,6 +405,8 @@ static void search(int w, int h, char *grid, int x0, int y0, *rdist = currdist; *rnumber = qhead; + if (currdist == 0) + *rcontrol = qhead; } /* @@ -382,65 +444,105 @@ static void fill(int w, int h, char *grid, int x0, int y0, char newcolour, } } +/* + * Detect a completed grid. + */ +static int completed(int w, int h, char *grid) +{ + int wh = w*h; + int i; + + for (i = 1; i < wh; i++) + if (grid[i] != grid[0]) + return FALSE; + + return TRUE; +} + /* * Try out every possible move on a grid, and choose whichever one * reduced the result of search() by the most. */ -static char choosemove(int w, int h, char *grid, int x0, int y0, - int maxmove, struct solver_scratch *scratch) +static char choosemove_recurse(int w, int h, char *grid, int x0, int y0, + int maxmove, struct solver_scratch *scratch, + int depth, int *rbestdist, int *rbestnumber, int *rbestcontrol) { int wh = w*h; char move, bestmove; - int dist, number, bestdist, bestnumber; + int dist, number, control, bestdist, bestnumber, bestcontrol; + char *tmpgrid; + + assert(0 <= depth && depth < RECURSION_DEPTH); + tmpgrid = scratch->rgrids + depth*wh; bestdist = wh + 1; bestnumber = 0; + bestcontrol = 0; bestmove = -1; #if 0 - dump_grid(w, h, grid, "before choosemove"); + dump_grid(w, h, grid, "before choosemove_recurse %d", depth); #endif for (move = 0; move < maxmove; move++) { - char buf[256]; - sprintf(buf, "after move %d", move); if (grid[y0*w+x0] == move) continue; - memcpy(scratch->sparegrid, grid, wh * sizeof(*grid)); - fill(w, h, scratch->sparegrid, x0, y0, move, scratch->queue[0]); + memcpy(tmpgrid, grid, wh * sizeof(*grid)); + fill(w, h, tmpgrid, x0, y0, move, scratch->queue[0]); + if (completed(w, h, tmpgrid)) { + /* + * A move that wins is immediately the best, so stop + * searching. Record what depth of recursion that happened + * at, so that higher levels will choose a move that gets + * to a winning position sooner. + */ + *rbestdist = -1; + *rbestnumber = depth; + *rbestcontrol = wh; + return move; + } + if (depth < RECURSION_DEPTH-1) { + choosemove_recurse(w, h, tmpgrid, x0, y0, maxmove, scratch, + depth+1, &dist, &number, &control); + } else { #if 0 - dump_grid(w, h, scratch->sparegrid, buf); + dump_grid(w, h, tmpgrid, "after move %d at depth %d", + move, depth); #endif - search(w, h, scratch->sparegrid, x0, y0, scratch, &dist, &number); + search(w, h, tmpgrid, x0, y0, scratch, &dist, &number, &control); #if 0 - dump_dist(w, h, scratch->dist, buf); - printf("move %d: %d at %d\n", move, number, dist); + dump_dist(w, h, scratch->dist, "after move %d at depth %d", + move, depth); + printf("move %d at depth %d: %d at %d\n", + depth, move, number, dist); #endif - if (dist < bestdist || (dist == bestdist && number < bestnumber)) { + } + if (dist < bestdist || + (dist == bestdist && + (number < bestnumber || + (number == bestnumber && + (control > bestcontrol))))) { bestdist = dist; bestnumber = number; + bestcontrol = control; bestmove = move; } } #if 0 - printf("best was %d\n", bestmove); + printf("best at depth %d was %d (%d at %d, %d controlled)\n", + depth, bestmove, bestnumber, bestdist, bestcontrol); #endif + *rbestdist = bestdist; + *rbestnumber = bestnumber; + *rbestcontrol = bestcontrol; return bestmove; } - -/* - * Detect a completed grid. - */ -static int completed(int w, int h, char *grid) +static char choosemove(int w, int h, char *grid, int x0, int y0, + int maxmove, struct solver_scratch *scratch) { - int wh = w*h; - int i; - - for (i = 1; i < wh; i++) - if (grid[i] != grid[0]) - return FALSE; - - return TRUE; + int tmp0, tmp1, tmp2; + return choosemove_recurse(w, h, grid, x0, y0, maxmove, scratch, + 0, &tmp0, &tmp1, &tmp2); } static char *new_game_desc(const game_params *params, random_state *rs, @@ -464,6 +566,7 @@ static char *new_game_desc(const game_params *params, random_state *rs, */ memcpy(scratch->grid2, scratch->grid, wh * sizeof(*scratch->grid2)); moves = 0; + check_recursion_depth(); while (!completed(w, h, scratch->grid2)) { char move = choosemove(w, h, scratch->grid2, FILLX, FILLY, params->colours, scratch); @@ -506,7 +609,7 @@ static char *validate_desc(const game_params *params, const char *desc) c = 10 + (c - 'A'); else return "Bad character in grid description"; - if (c < 0 || c >= params->colours) + if ((unsigned)c >= params->colours) return "Colour out of range in grid description"; } if (*desc != ',') @@ -594,8 +697,10 @@ static char *solve_game(const game_state *state, const game_state *currstate, char buf[256]; struct solver_scratch *scratch; - if (currstate->complete) + if (currstate->complete) { + *error = "Puzzle is already solved"; return NULL; + } /* * Find the best solution our solver can give. @@ -604,6 +709,7 @@ static char *solve_game(const game_state *state, const game_state *currstate, nmoves = 0; scratch = new_scratch(w, h); memcpy(scratch->grid2, currstate->grid, wh * sizeof(*scratch->grid2)); + check_recursion_depth(); while (!completed(w, h, scratch->grid2)) { char move = choosemove(w, h, scratch->grid2, FILLX, FILLY, currstate->colours, scratch);