X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/fdb3b29aacf3f9d0bf16c816ba2ec959e6518bd3..92efb79dde200c6197ea25c4648e324f35a58021:/solo.c diff --git a/solo.c b/solo.c index b85edeb..c6d39eb 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; } @@ -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. @@ -1926,7 +1858,7 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -static game_state *new_game(midend_data *me, game_params *params, char *desc) +static game_state *new_game(midend *me, game_params *params, char *desc) { game_state *state = snew(game_state); int c = params->c, r = params->r, cr = c*r, area = cr * cr; @@ -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; @@ -2320,8 +2252,8 @@ static void game_compute_size(game_params *params, int tilesize, *y = SIZE(params->c * params->r); } -static void game_set_size(game_drawstate *ds, game_params *params, - int tilesize) +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) { ds->tilesize = tilesize; } @@ -2360,7 +2292,7 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) return ret; } -static game_drawstate *game_new_drawstate(game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); int c = state->c, r = state->r, cr = c*r; @@ -2380,7 +2312,7 @@ static game_drawstate *game_new_drawstate(game_state *state) return ds; } -static void game_free_drawstate(game_drawstate *ds) +static void game_free_drawstate(drawing *dr, game_drawstate *ds) { sfree(ds->hl); sfree(ds->pencil); @@ -2389,7 +2321,7 @@ static void game_free_drawstate(game_drawstate *ds) sfree(ds); } -static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, +static void draw_number(drawing *dr, game_drawstate *ds, game_state *state, int x, int y, int hl) { int c = state->c, r = state->r, cr = c*r; @@ -2419,10 +2351,10 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, if ((y+1) % c) ch++; - clip(fe, cx, cy, cw, ch); + clip(dr, cx, cy, cw, ch); /* background needs erasing */ - draw_rect(fe, cx, cy, cw, ch, (hl & 15) == 1 ? COL_HIGHLIGHT : COL_BACKGROUND); + draw_rect(dr, cx, cy, cw, ch, (hl & 15) == 1 ? COL_HIGHLIGHT : COL_BACKGROUND); /* pencil-mode highlight */ if ((hl & 15) == 2) { @@ -2433,7 +2365,7 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, coords[3] = cy; coords[4] = cx; coords[5] = cy+ch/2; - draw_polygon(fe, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); + draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); } /* new number needs drawing? */ @@ -2442,7 +2374,7 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, str[0] = state->grid[y*cr+x] + '0'; if (str[0] > '9') str[0] += 'a' - ('9'+1); - draw_text(fe, tx + TILE_SIZE/2, ty + TILE_SIZE/2, + draw_text(dr, tx + TILE_SIZE/2, ty + TILE_SIZE/2, FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE, state->immutable[y*cr+x] ? COL_CLUE : (hl & 16) ? COL_ERROR : COL_USER, str); } else { @@ -2477,7 +2409,7 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, str[0] = i + '1'; if (str[0] > '9') str[0] += 'a' - ('9'+1); - draw_text(fe, tx + (4*dx+3) * TILE_SIZE / (4*pw+2), + draw_text(dr, tx + (4*dx+3) * TILE_SIZE / (4*pw+2), ty + (4*dy+3) * TILE_SIZE / (4*ph+2), FONT_VARIABLE, fontsize, ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str); @@ -2485,16 +2417,16 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, } } - unclip(fe); + unclip(dr); - draw_update(fe, cx, cy, cw, ch); + draw_update(dr, cx, cy, cw, ch); ds->grid[y*cr+x] = state->grid[y*cr+x]; memcpy(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr); ds->hl[y*cr+x] = hl; } -static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, game_state *state, int dir, game_ui *ui, float animtime, float flashtime) { @@ -2508,19 +2440,19 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, * all games should start by drawing a big * background-colour rectangle covering the whole window. */ - draw_rect(fe, 0, 0, SIZE(cr), SIZE(cr), COL_BACKGROUND); + draw_rect(dr, 0, 0, SIZE(cr), SIZE(cr), COL_BACKGROUND); /* * Draw the grid. */ for (x = 0; x <= cr; x++) { int thick = (x % r ? 0 : 1); - draw_rect(fe, BORDER + x*TILE_SIZE - thick, BORDER-1, + draw_rect(dr, BORDER + x*TILE_SIZE - thick, BORDER-1, 1+2*thick, cr*TILE_SIZE+3, COL_GRID); } for (y = 0; y <= cr; y++) { int thick = (y % c ? 0 : 1); - draw_rect(fe, BORDER-1, BORDER + y*TILE_SIZE - thick, + draw_rect(dr, BORDER-1, BORDER + y*TILE_SIZE - thick, cr*TILE_SIZE+3, 1+2*thick, COL_GRID); } } @@ -2566,7 +2498,7 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, (ds->entered_items[((x/r)+(y/c)*c)*cr+d-1] & 32))) highlight |= 16; - draw_number(fe, ds, state, x, y, highlight); + draw_number(dr, ds, state, x, y, highlight); } } @@ -2574,7 +2506,7 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, * Update the _entire_ grid if necessary. */ if (!ds->started) { - draw_update(fe, 0, 0, SIZE(cr), SIZE(cr)); + draw_update(dr, 0, 0, SIZE(cr), SIZE(cr)); ds->started = TRUE; } } @@ -2599,11 +2531,73 @@ 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; } +static void game_print_size(game_params *params, float *x, float *y) +{ + int pw, ph; + + /* + * I'll use 9mm squares by default. They should be quite big + * for this game, because players will want to jot down no end + * of pencil marks in the squares. + */ + game_compute_size(params, 900, &pw, &ph); + *x = pw / 100.0; + *y = ph / 100.0; +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ + int c = state->c, r = state->r, cr = c*r; + int ink = print_mono_colour(dr, 0); + int x, y; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + ads.tilesize = tilesize; + + /* + * Border. + */ + print_line_width(dr, 3 * TILE_SIZE / 40); + draw_rect_outline(dr, BORDER, BORDER, cr*TILE_SIZE, cr*TILE_SIZE, ink); + + /* + * Grid. + */ + for (x = 1; x < cr; x++) { + print_line_width(dr, (x % r ? 1 : 3) * TILE_SIZE / 40); + draw_line(dr, BORDER+x*TILE_SIZE, BORDER, + BORDER+x*TILE_SIZE, BORDER+cr*TILE_SIZE, ink); + } + for (y = 1; y < cr; y++) { + print_line_width(dr, (y % c ? 1 : 3) * TILE_SIZE / 40); + draw_line(dr, BORDER, BORDER+y*TILE_SIZE, + BORDER+cr*TILE_SIZE, BORDER+y*TILE_SIZE, ink); + } + + /* + * Numbers. + */ + for (y = 0; y < cr; y++) + for (x = 0; x < cr; x++) + if (state->grid[y*cr+x]) { + char str[2]; + str[1] = '\0'; + str[0] = state->grid[y*cr+x] + '0'; + if (str[0] > '9') + str[0] += 'a' - ('9'+1); + draw_text(dr, BORDER + x*TILE_SIZE + TILE_SIZE/2, + BORDER + y*TILE_SIZE + TILE_SIZE/2, + FONT_VARIABLE, TILE_SIZE/2, + ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); + } +} + #ifdef COMBINED #define thegame solo #endif @@ -2639,6 +2633,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + TRUE, FALSE, game_print_size, game_print, game_wants_statusbar, FALSE, game_timing_state, 0, /* mouse_priorities */ @@ -2651,21 +2646,26 @@ const struct game thegame = { */ void frontend_default_colour(frontend *fe, float *output) {} -void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize, +void draw_text(drawing *dr, int x, int y, int fonttype, int fontsize, int align, int colour, char *text) {} -void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {} -void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {} -void draw_polygon(frontend *fe, int *coords, int npoints, +void draw_rect(drawing *dr, int x, int y, int w, int h, int colour) {} +void draw_rect_outline(drawing *dr, int x, int y, int w, int h, int colour) {} +void draw_line(drawing *dr, int x1, int y1, int x2, int y2, int colour) {} +void draw_polygon(drawing *dr, int *coords, int npoints, int fillcolour, int outlinecolour) {} -void clip(frontend *fe, int x, int y, int w, int h) {} -void unclip(frontend *fe) {} -void start_draw(frontend *fe) {} -void draw_update(frontend *fe, int x, int y, int w, int h) {} -void end_draw(frontend *fe) {} +void clip(drawing *dr, int x, int y, int w, int h) {} +void unclip(drawing *dr) {} +void start_draw(drawing *dr) {} +void draw_update(drawing *dr, int x, int y, int w, int h) {} +void end_draw(drawing *dr) {} +int print_mono_colour(drawing *dr, int grey) { return 0; } +void print_line_width(drawing *dr, int width) {} 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 +2724,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)":