X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/ab3620809e311adb62a7e5e71fa30961a8103c64..e94d848e651d6f60607753a29ff62d1fb7337198:/solo.c diff --git a/solo.c b/solo.c index 916742f..165e683 100644 --- a/solo.c +++ b/solo.c @@ -327,6 +327,8 @@ static char *validate_params(game_params *params, int full) return "Both dimensions must be at least 2"; if (params->c > ORDER_MAX || params->r > ORDER_MAX) return "Dimensions greater than "STR(ORDER_MAX)" are not supported"; + if ((params->c * params->r) > 36) + return "Unable to support more than 36 distinct symbols in a puzzle"; return NULL; } @@ -529,8 +531,8 @@ static int solver_elim(struct solver_usage *usage, int start, int step if (!usage->grid[YUNTRANS(y)*cr+x]) { #ifdef STANDALONE_SOLVER if (solver_show_working) { - printf("%*s", solver_recurse_depth*4, ""); va_list ap; + printf("%*s", solver_recurse_depth*4, ""); va_start(ap, fmt); vprintf(fmt, ap); va_end(ap); @@ -544,8 +546,8 @@ static int solver_elim(struct solver_usage *usage, int start, int step } else if (m == 0) { #ifdef STANDALONE_SOLVER if (solver_show_working) { - printf("%*s", solver_recurse_depth*4, ""); va_list ap; + printf("%*s", solver_recurse_depth*4, ""); va_start(ap, fmt); vprintf(fmt, ap); va_end(ap); @@ -598,8 +600,8 @@ static int solver_intersect(struct solver_usage *usage, int px, py, pn; if (!ret) { - printf("%*s", solver_recurse_depth*4, ""); va_list ap; + printf("%*s", solver_recurse_depth*4, ""); va_start(ap, fmt); vprintf(fmt, ap); va_end(ap); @@ -732,9 +734,9 @@ static int solver_set(struct solver_usage *usage, if (rows > n - count) { #ifdef STANDALONE_SOLVER if (solver_show_working) { + va_list ap; printf("%*s", solver_recurse_depth*4, ""); - va_list ap; va_start(ap, fmt); vprintf(fmt, ap); va_end(ap); @@ -776,9 +778,9 @@ static int solver_set(struct solver_usage *usage, int px, py, pn; if (!progress) { + va_list ap; printf("%*s", solver_recurse_depth*4, ""); - va_list ap; va_start(ap, fmt); vprintf(fmt, ap); va_end(ap); @@ -843,7 +845,7 @@ static void solver_free_scratch(struct solver_scratch *scratch) sfree(scratch); } -static int solver(int c, int r, digit *grid, random_state *rs, int maxdiff) +static int solver(int c, int r, digit *grid, int maxdiff) { struct solver_usage *usage; struct solver_scratch *scratch; @@ -1119,11 +1121,10 @@ static int solver(int c, int r, digit *grid, random_state *rs, int maxdiff) * possible. */ if (maxdiff >= DIFF_RECURSIVE) { - int best, bestcount, bestnumber; + int best, bestcount; best = -1; bestcount = cr+1; - bestnumber = 0; for (y = 0; y < cr; y++) for (x = 0; x < cr; x++) @@ -1147,14 +1148,7 @@ static int solver(int c, int r, digit *grid, random_state *rs, int maxdiff) if (count < bestcount) { bestcount = count; - bestnumber = 0; - } - - if (count == bestcount) { - bestnumber++; - if (bestnumber == 1 || - (rs && random_upto(rs, bestnumber) == 0)) - best = y*cr+x; + best = y*cr+x; } } @@ -1193,18 +1187,6 @@ static int solver(int c, int r, digit *grid, random_state *rs, int maxdiff) } #endif - /* Now shuffle the list. */ - if (rs) { - for (i = j; i > 1; i--) { - int p = random_upto(rs, i); - if (p != i-1) { - int t = list[p]; - list[p] = list[i-1]; - list[i-1] = t; - } - } - } - /* * And step along the list, recursing back into the * main solver at every stage. @@ -1222,7 +1204,7 @@ static int solver(int c, int r, digit *grid, random_state *rs, int maxdiff) solver_recurse_depth++; #endif - ret = solver(c, r, outgrid, rs, maxdiff); + ret = solver(c, r, outgrid, maxdiff); #ifdef STANDALONE_SOLVER solver_recurse_depth--; @@ -1421,17 +1403,8 @@ static int gridgen_real(struct gridgen_usage *usage, digit *grid) digits[j++] = n+1; } - if (usage->rs) { - /* shuffle */ - for (i = j; i > 1; i--) { - int p = random_upto(usage->rs, i); - if (p != i-1) { - int t = digits[p]; - digits[p] = digits[i-1]; - digits[i-1] = t; - } - } - } + if (usage->rs) + shuffle(digits, j, sizeof(*digits), usage->rs); /* And finally, go through the digit list and actually recurse. */ ret = FALSE; @@ -1701,8 +1674,8 @@ static char *new_game_desc(game_params *params, random_state *rs, int nlocs; char *desc; int coords[16], ncoords; - int *symmclasses, nsymmclasses; - int maxdiff, recursing; + int maxdiff; + int x, y, i, j; /* * Adjust the maximum difficulty level to be consistent with @@ -1719,31 +1692,6 @@ static char *new_game_desc(game_params *params, random_state *rs, grid2 = snewn(area, digit); /* - * Find the set of equivalence classes of squares permitted - * by the selected symmetry. We do this by enumerating all - * the grid squares which have no symmetric companion - * sorting lower than themselves. - */ - nsymmclasses = 0; - symmclasses = snewn(cr * cr, int); - { - int x, y; - - for (y = 0; y < cr; y++) - for (x = 0; x < cr; x++) { - int i = y*cr+x; - int j; - - ncoords = symmetries(params, x, y, coords, params->symm); - for (j = 0; j < ncoords; j++) - if (coords[2*j+1]*cr+coords[2*j] < i) - break; - if (j == ncoords) - symmclasses[nsymmclasses++] = i; - } - } - - /* * Loop until we get a grid of the required difficulty. This is * nasty, but it seems to be unpleasantly hard to generate * difficult grids otherwise. @@ -1775,80 +1723,64 @@ static char *new_game_desc(game_params *params, random_state *rs, * Now we have a solved grid, start removing things from it * while preserving solubility. */ - recursing = FALSE; - while (1) { - int x, y, i, j; - /* - * Iterate over the grid and enumerate all the filled - * squares we could empty. - */ - nlocs = 0; + /* + * Find the set of equivalence classes of squares permitted + * by the selected symmetry. We do this by enumerating all + * the grid squares which have no symmetric companion + * sorting lower than themselves. + */ + nlocs = 0; + for (y = 0; y < cr; y++) + for (x = 0; x < cr; x++) { + int i = y*cr+x; + int j; - for (i = 0; i < nsymmclasses; i++) { - x = symmclasses[i] % cr; - y = symmclasses[i] / cr; - if (grid[y*cr+x]) { + ncoords = symmetries(params, x, y, coords, params->symm); + for (j = 0; j < ncoords; j++) + if (coords[2*j+1]*cr+coords[2*j] < i) + break; + if (j == ncoords) { locs[nlocs].x = x; locs[nlocs].y = y; nlocs++; } } - /* - * Now shuffle that list. - */ - for (i = nlocs; i > 1; i--) { - int p = random_upto(rs, i); - if (p != i-1) { - struct xy t = locs[p]; - locs[p] = locs[i-1]; - locs[i-1] = t; - } - } - - /* - * Now loop over the shuffled list and, for each element, - * see whether removing that element (and its reflections) - * from the grid will still leave the grid soluble by - * solver. - */ - for (i = 0; i < nlocs; i++) { - int ret; + /* + * Now shuffle that list. + */ + shuffle(locs, nlocs, sizeof(*locs), rs); - x = locs[i].x; - y = locs[i].y; + /* + * Now loop over the shuffled list and, for each element, + * see whether removing that element (and its reflections) + * from the grid will still leave the grid soluble. + */ + for (i = 0; i < nlocs; i++) { + int ret; - memcpy(grid2, grid, area); - ncoords = symmetries(params, x, y, coords, params->symm); - for (j = 0; j < ncoords; j++) - grid2[coords[2*j+1]*cr+coords[2*j]] = 0; + x = locs[i].x; + y = locs[i].y; - ret = solver(c, r, grid2, NULL, maxdiff); - if (ret != DIFF_IMPOSSIBLE && ret != DIFF_AMBIGUOUS) { - for (j = 0; j < ncoords; j++) - grid[coords[2*j+1]*cr+coords[2*j]] = 0; - break; - } - } + memcpy(grid2, grid, area); + ncoords = symmetries(params, x, y, coords, params->symm); + for (j = 0; j < ncoords; j++) + grid2[coords[2*j+1]*cr+coords[2*j]] = 0; - if (i == nlocs) { - /* - * There was nothing we could remove without - * destroying solvability. Give up. - */ - break; + ret = solver(c, r, grid2, maxdiff); + if (ret != DIFF_IMPOSSIBLE && ret != DIFF_AMBIGUOUS) { + for (j = 0; j < ncoords; j++) + grid[coords[2*j+1]*cr+coords[2*j]] = 0; } } memcpy(grid2, grid, area); - } while (solver(c, r, grid2, NULL, maxdiff) < maxdiff); + } while (solver(c, r, grid2, maxdiff) < maxdiff); sfree(grid2); sfree(locs); - sfree(symmclasses); - /* * Now we have the grid as it will be presented to the user. * Encode it in a game desc. @@ -2016,7 +1948,7 @@ static char *solve_game(game_state *state, game_state *currstate, grid = snewn(cr*cr, digit); memcpy(grid, state->grid, cr*cr); - solve_ret = solver(c, r, grid, NULL, DIFF_RECURSIVE); + solve_ret = solver(c, r, grid, DIFF_RECURSIVE); *error = NULL; @@ -2599,7 +2531,7 @@ static int game_wants_statusbar(void) return FALSE; } -static int game_timing_state(game_state *state) +static int game_timing_state(game_state *state, game_ui *ui) { return TRUE; } @@ -2666,6 +2598,8 @@ unsigned long random_bits(random_state *state, int bits) { assert(!"Shouldn't get randomness"); return 0; } unsigned long random_upto(random_state *state, unsigned long limit) { assert(!"Shouldn't get randomness"); return 0; } +void shuffle(void *array, int nelts, int eltsize, random_state *rs) +{ assert(!"Shouldn't get randomness"); } void fatal(char *fmt, ...) { @@ -2724,7 +2658,7 @@ int main(int argc, char **argv) } s = new_game(NULL, p, desc); - ret = solver(p->c, p->r, s->grid, NULL, DIFF_RECURSIVE); + ret = solver(p->c, p->r, s->grid, DIFF_RECURSIVE); if (grade) { printf("Difficulty rating: %s\n", ret==DIFF_BLOCK ? "Trivial (blockwise positional elimination only)":