X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/2705d3741495f136d9d092d873f9b1c803ba1d8f..95c76d7c0c76081ab4f389aa1bb7667ee08c99eb:/slant.c diff --git a/slant.c b/slant.c index ebc5bbb..fc47209 100644 --- a/slant.c +++ b/slant.c @@ -24,6 +24,7 @@ #include #include +#include #include #include #include @@ -273,6 +274,30 @@ struct solver_scratch { signed char *slashval; /* + * Stores possible v-shapes. This array is w by h in size, but + * not every bit of every entry is meaningful. The bits mean: + * + * - bit 0 for a square means that that square and the one to + * its right might form a v-shape between them + * - bit 1 for a square means that that square and the one to + * its right might form a ^-shape between them + * - bit 2 for a square means that that square and the one + * below it might form a >-shape between them + * - bit 3 for a square means that that square and the one + * below it might form a <-shape between them + * + * Any starting 1 or 3 clue rules out four bits in this array + * immediately; a 2 clue propagates any ruled-out bit past it + * (if the two squares on one side of a 2 cannot be a v-shape, + * then neither can the two on the other side be the same + * v-shape); we can rule out further bits during play using + * partially filled 2 clues; whenever a pair of squares is + * known not to be _either_ kind of v-shape, we can mark them + * as equivalent. + */ + unsigned char *vbitmap; + + /* * Useful to have this information automatically passed to * solver subroutines. (This pointer is not dynamically * allocated by new_scratch and free_scratch.) @@ -289,11 +314,13 @@ static struct solver_scratch *new_scratch(int w, int h) ret->border = snewn(W*H, unsigned char); ret->equiv = snewn(w*h, int); ret->slashval = snewn(w*h, signed char); + ret->vbitmap = snewn(w*h, unsigned char); return ret; } static void free_scratch(struct solver_scratch *sc) { + sfree(sc->vbitmap); sfree(sc->slashval); sfree(sc->equiv); sfree(sc->border); @@ -388,6 +415,36 @@ static void fill_square(int w, int h, int x, int y, int v, } } +static int vbitmap_clear(int w, int h, struct solver_scratch *sc, + int x, int y, int vbits, char *reason, ...) +{ + int done_something = FALSE; + int vbit; + + for (vbit = 1; vbit <= 8; vbit <<= 1) + if (vbits & sc->vbitmap[y*w+x] & vbit) { + done_something = TRUE; +#ifdef SOLVER_DIAGNOSTICS + if (verbose) { + va_list ap; + + printf("ruling out %c shape at (%d,%d)-(%d,%d) (", + "!v^!>!!!<"[vbit], x, y, + x+((vbit&0x3)!=0), y+((vbit&0xC)!=0)); + + va_start(ap, reason); + vprintf(reason, ap); + va_end(ap); + + printf(")\n"); + } +#endif + sc->vbitmap[y*w+x] &= ~vbit; + } + + return done_something; +} + /* * Solver. Returns 0 for impossibility, 1 for success, 2 for * ambiguity or failure to converge. @@ -411,15 +468,13 @@ static int slant_solve(int w, int h, const signed char *clues, * Establish a disjoint set forest for tracking connectedness * between grid points. */ - for (i = 0; i < W*H; i++) - sc->connected[i] = i; /* initially all distinct */ + dsf_init(sc->connected, W*H); /* * Establish a disjoint set forest for tracking which squares * are known to slant in the same direction. */ - for (i = 0; i < w*h; i++) - sc->equiv[i] = i; /* initially all distinct */ + dsf_init(sc->equiv, w*h); /* * Clear the slashval array. @@ -427,7 +482,12 @@ static int slant_solve(int w, int h, const signed char *clues, memset(sc->slashval, 0, w*h); /* - * Initialise the `exits' and `border' arrays. Theses is used + * Set up the vbitmap array. Initially all types of v are possible. + */ + memset(sc->vbitmap, 0xF, w*h); + + /* + * Initialise the `exits' and `border' arrays. These are used * to do second-order loop avoidance: the dual of the no loops * constraint is that every point must be somehow connected to * the border of the grid (otherwise there would be a solid @@ -454,69 +514,6 @@ static int slant_solve(int w, int h, const signed char *clues, } /* - * Make a one-off preliminary pass over the grid looking for - * starting-point arrangements. The ones we need to spot are: - * - * - two adjacent 1s in the centre of the grid imply that each - * one's single line points towards the other. (If either 1 - * were connected on the far side, the two squares shared - * between the 1s would both link to the other 1 as a - * consequence of neither linking to the first.) Thus, we - * can fill in the four squares around them. - * - * - dually, two adjacent 3s imply that each one's _non_-line - * points towards the other. - * - * - if the pair of 1s and 3s is not _adjacent_ but is - * separated by one or more 2s, the reasoning still applies. - * - * This is more advanced than just spotting obvious starting - * squares such as central 4s and edge 2s, so we disable it on - * DIFF_EASY. - * - * (I don't like this loop; it feels grubby to me. My - * mathematical intuition feels there ought to be some more - * general deductive form which contains this loop as a special - * case, but I can't bring it to mind right now.) - */ - if (difficulty > DIFF_EASY) { - for (y = 1; y+1 < H; y++) - for (x = 1; x+1 < W; x++) { - int v = clues[y*W+x], s, x2, y2, dx, dy; - if (v != 1 && v != 3) - continue; - /* Slash value of the square up and left of (x,y). */ - s = (v == 1 ? +1 : -1); - - /* Look in each direction once. */ - for (dy = 0; dy < 2; dy++) { - dx = 1 - dy; - x2 = x+dx; - y2 = y+dy; - if (x2+1 >= W || y2+1 >= H) - continue; /* too close to the border */ - while (x2+dx+1 < W && y2+dy+1 < H && clues[y2*W+x2] == 2) - x2 += dx, y2 += dy; - if (clues[y2*W+x2] == v) { -#ifdef SOLVER_DIAGNOSTICS - if (verbose) - printf("found adjacent %ds at %d,%d and %d,%d\n", - v, x, y, x2, y2); -#endif - fill_square(w, h, x-1, y-1, s, soln, - sc->connected, sc); - fill_square(w, h, x-1+dy, y-1+dx, -s, soln, - sc->connected, sc); - fill_square(w, h, x2, y2, s, soln, - sc->connected, sc); - fill_square(w, h, x2-dy, y2-dx, -s, soln, - sc->connected, sc); - } - } - } - } - - /* * Repeatedly try to deduce something until we can't. */ do { @@ -837,6 +834,147 @@ static int slant_solve(int w, int h, const signed char *clues, } } + if (done_something) + continue; + + /* + * Now see what we can do with the vbitmap array. All + * vbitmap deductions are disabled at Easy level. + */ + if (difficulty <= DIFF_EASY) + continue; + + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int s, c; + + /* + * Any line already placed in a square must rule + * out any type of v which contradicts it. + */ + if ((s = soln[y*w+x]) != 0) { + if (x > 0) + done_something |= + vbitmap_clear(w, h, sc, x-1, y, (s < 0 ? 0x1 : 0x2), + "contradicts known edge at (%d,%d)",x,y); + if (x+1 < w) + done_something |= + vbitmap_clear(w, h, sc, x, y, (s < 0 ? 0x2 : 0x1), + "contradicts known edge at (%d,%d)",x,y); + if (y > 0) + done_something |= + vbitmap_clear(w, h, sc, x, y-1, (s < 0 ? 0x4 : 0x8), + "contradicts known edge at (%d,%d)",x,y); + if (y+1 < h) + done_something |= + vbitmap_clear(w, h, sc, x, y, (s < 0 ? 0x8 : 0x4), + "contradicts known edge at (%d,%d)",x,y); + } + + /* + * If both types of v are ruled out for a pair of + * adjacent squares, mark them as equivalent. + */ + if (x+1 < w && !(sc->vbitmap[y*w+x] & 0x3)) { + int n1 = y*w+x, n2 = y*w+(x+1); + if (dsf_canonify(sc->equiv, n1) != + dsf_canonify(sc->equiv, n2)) { + dsf_merge(sc->equiv, n1, n2); + done_something = TRUE; +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("(%d,%d) and (%d,%d) must be equivalent" + " because both v-shapes are ruled out\n", + x, y, x+1, y); +#endif + } + } + if (y+1 < h && !(sc->vbitmap[y*w+x] & 0xC)) { + int n1 = y*w+x, n2 = (y+1)*w+x; + if (dsf_canonify(sc->equiv, n1) != + dsf_canonify(sc->equiv, n2)) { + dsf_merge(sc->equiv, n1, n2); + done_something = TRUE; +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("(%d,%d) and (%d,%d) must be equivalent" + " because both v-shapes are ruled out\n", + x, y, x, y+1); +#endif + } + } + + /* + * The remaining work in this loop only works + * around non-edge clue points. + */ + if (y == 0 || x == 0) + continue; + if ((c = clues[y*W+x]) < 0) + continue; + + /* + * x,y marks a clue point not on the grid edge. See + * if this clue point allows us to rule out any v + * shapes. + */ + + if (c == 1) { + /* + * A 1 clue can never have any v shape pointing + * at it. + */ + done_something |= + vbitmap_clear(w, h, sc, x-1, y-1, 0x5, + "points at 1 clue at (%d,%d)", x, y); + done_something |= + vbitmap_clear(w, h, sc, x-1, y, 0x2, + "points at 1 clue at (%d,%d)", x, y); + done_something |= + vbitmap_clear(w, h, sc, x, y-1, 0x8, + "points at 1 clue at (%d,%d)", x, y); + } else if (c == 3) { + /* + * A 3 clue can never have any v shape pointing + * away from it. + */ + done_something |= + vbitmap_clear(w, h, sc, x-1, y-1, 0xA, + "points away from 3 clue at (%d,%d)", x, y); + done_something |= + vbitmap_clear(w, h, sc, x-1, y, 0x1, + "points away from 3 clue at (%d,%d)", x, y); + done_something |= + vbitmap_clear(w, h, sc, x, y-1, 0x4, + "points away from 3 clue at (%d,%d)", x, y); + } else if (c == 2) { + /* + * If a 2 clue has any kind of v ruled out on + * one side of it, the same v is ruled out on + * the other side. + */ + done_something |= + vbitmap_clear(w, h, sc, x-1, y-1, + (sc->vbitmap[(y )*w+(x-1)] & 0x3) ^ 0x3, + "propagated by 2 clue at (%d,%d)", x, y); + done_something |= + vbitmap_clear(w, h, sc, x-1, y-1, + (sc->vbitmap[(y-1)*w+(x )] & 0xC) ^ 0xC, + "propagated by 2 clue at (%d,%d)", x, y); + done_something |= + vbitmap_clear(w, h, sc, x-1, y, + (sc->vbitmap[(y-1)*w+(x-1)] & 0x3) ^ 0x3, + "propagated by 2 clue at (%d,%d)", x, y); + done_something |= + vbitmap_clear(w, h, sc, x, y-1, + (sc->vbitmap[(y-1)*w+(x-1)] & 0xC) ^ 0xC, + "propagated by 2 clue at (%d,%d)", x, y); + } + +#undef CLEARBITS + + } + } while (done_something); /* @@ -866,9 +1004,7 @@ static void slant_generate(int w, int h, signed char *soln, random_state *rs) * Establish a disjoint set forest for tracking connectedness * between grid points. */ - connected = snewn(W*H, int); - for (i = 0; i < W*H; i++) - connected[i] = i; /* initially all distinct */ + connected = snew_dsf(W*H); /* * Prepare a list of the squares in the grid, and fill them in @@ -1249,8 +1385,7 @@ static int check_completion(game_state *state) * edge is visited at most twice. */ dsf = state->clues->tmpdsf; - for (i = 0; i < W*H; i++) - dsf[i] = i; /* initially all distinct */ + dsf_init(dsf, W*H); for (y = 0; y < h; y++) for (x = 0; x < w; x++) { int i1, i2; @@ -1707,7 +1842,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); @@ -1970,11 +2105,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; @@ -2056,7 +2186,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) #endif const struct game thegame = { - "Slant", "games.slant", + "Slant", "games.slant", "slant", default_params, game_fetch_preset, decode_params, @@ -2087,7 +2217,7 @@ 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, /* flags */ };