X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=filling.c;h=3797e5c5ff94515879d857d2a6c7f3aef3f08d70;hb=3234912f921916a1b8da164fd61dc75579358577;hp=020906254f97c0756bed747d779163adc82ec5a2;hpb=c826fdc062af7d2e0ee0ca39a78eff9e529a2d56;p=sgt-puzzles.git diff --git a/filling.c b/filling.c index 0209062..3797e5c 100644 --- a/filling.c +++ b/filling.c @@ -11,13 +11,6 @@ * - the type should be somewhat big: board[i] = i * - Using shorts gives us 181x181 puzzles as upper bound. * - * - make a somewhat more clever solver - * + enable "ghost regions" of size > 1 - * - one can put an upper bound on the size of a ghost region - * by considering the board size and summing present hints. - * + for each square, for i=1..n, what is the distance to a region - * containing i? How full is the region? How is this useful? - * * - in board generation, after having merged regions such that no * more merges are necessary, try splitting (big) regions. * + it seems that smaller regions make for better puzzles; see @@ -91,7 +84,7 @@ static void printv(char *fmt, ...) { *****************************************************************************/ struct game_params { - int h, w; + int w, h; }; struct shared_state { @@ -106,7 +99,9 @@ struct game_state { int completed, cheated; }; -static const struct game_params filling_defaults[3] = {{7, 9}, {9, 13}, {13, 17}}; +static const struct game_params filling_defaults[3] = { + {9, 7}, {13, 9}, {17, 13} +}; static game_params *default_params(void) { @@ -124,7 +119,7 @@ static int game_fetch_preset(int i, char **name, game_params **params) if (i < 0 || i >= lenof(filling_defaults)) return FALSE; *params = snew(game_params); **params = filling_defaults[i]; /* struct copy */ - sprintf(buf, "%dx%d", filling_defaults[i].h, filling_defaults[i].w); + sprintf(buf, "%dx%d", filling_defaults[i].w, filling_defaults[i].h); *name = dupstr(buf); return TRUE; @@ -135,7 +130,7 @@ static void free_params(game_params *params) sfree(params); } -static game_params *dup_params(game_params *params) +static game_params *dup_params(const game_params *params) { game_params *ret = snew(game_params); *ret = *params; /* struct copy */ @@ -149,14 +144,14 @@ static void decode_params(game_params *ret, char const *string) if (*string == 'x') ret->h = atoi(++string); } -static char *encode_params(game_params *params, int full) +static char *encode_params(const game_params *params, int full) { char buf[64]; sprintf(buf, "%dx%d", params->w, params->h); return dupstr(buf); } -static config_item *game_configure(game_params *params) +static config_item *game_configure(const game_params *params) { config_item *ret; char buf[64]; @@ -183,7 +178,7 @@ static config_item *game_configure(game_params *params) return ret; } -static game_params *custom_params(config_item *cfg) +static game_params *custom_params(const config_item *cfg) { game_params *ret = snew(game_params); @@ -193,7 +188,7 @@ static game_params *custom_params(config_item *cfg) return ret; } -static char *validate_params(game_params *params, int full) +static char *validate_params(const game_params *params, int full) { if (params->w < 1) return "Width must be at least one"; if (params->h < 1) return "Height must be at least one"; @@ -277,12 +272,12 @@ static char *board_to_string(int *board, int w, int h) { return repr; } -static int game_can_format_as_text_now(game_params *params) +static int game_can_format_as_text_now(const game_params *params) { return TRUE; } -static char *game_text_format(game_state *state) +static char *game_text_format(const game_state *state) { const int w = state->shared->params.w; const int h = state->shared->params.h; @@ -302,6 +297,10 @@ struct solver_state int *board; int *connected; int nempty; + + /* Used internally by learn_bitmap_deductions; kept here to avoid + * mallocing/freeing them every time that function is called. */ + int *bm, *bmdsf, *bmminsize; }; static void print_board(int *board, int w, int h) { @@ -312,16 +311,78 @@ static void print_board(int *board, int w, int h) { } } -static game_state *new_game(midend *, game_params *, char *); +static game_state *new_game(midend *, const game_params *, const char *); static void free_game(game_state *); #define SENTINEL sz +static int mark_region(int *board, int w, int h, int i, int n, int m) { + int j; + + board[i] = -1; + + for (j = 0; j < 4; ++j) { + const int x = (i % w) + dx[j], y = (i / w) + dy[j], ii = w*y + x; + if (x < 0 || x >= w || y < 0 || y >= h) continue; + if (board[ii] == m) return FALSE; + if (board[ii] != n) continue; + if (!mark_region(board, w, h, ii, n, m)) return FALSE; + } + return TRUE; +} + +static int region_size(int *board, int w, int h, int i) { + const int sz = w * h; + int j, size, copy; + if (board[i] == 0) return 0; + copy = board[i]; + mark_region(board, w, h, i, board[i], SENTINEL); + for (size = j = 0; j < sz; ++j) { + if (board[j] != -1) continue; + ++size; + board[j] = copy; + } + return size; +} + +static void merge_ones(int *board, int w, int h) +{ + const int sz = w * h; + const int maxsize = min(max(max(w, h), 3), 9); + int i, j, k, change; + do { + change = FALSE; + for (i = 0; i < sz; ++i) { + if (board[i] != 1) continue; + + for (j = 0; j < 4; ++j, board[i] = 1) { + const int x = (i % w) + dx[j], y = (i / w) + dy[j]; + int oldsize, newsize, ok, ii = w*y + x; + if (x < 0 || x >= w || y < 0 || y >= h) continue; + if (board[ii] == maxsize) continue; + + oldsize = board[ii]; + board[i] = oldsize; + newsize = region_size(board, w, h, i); + + if (newsize > maxsize) continue; + + ok = mark_region(board, w, h, i, oldsize, newsize); + + for (k = 0; k < sz; ++k) + if (board[k] == -1) + board[k] = ok ? newsize : oldsize; + + if (ok) break; + } + if (j < 4) change = TRUE; + } + } while (change); +} + /* generate a random valid board; uses validate_board. */ static void make_board(int *board, int w, int h, random_state *rs) { - int *dsf; - - const unsigned int sz = w * h; + const int sz = w * h; /* w=h=2 is a special case which requires a number > max(w, h) */ /* TODO prove that this is the case ONLY for w=h=2. */ @@ -330,90 +391,74 @@ static void make_board(int *board, int w, int h, random_state *rs) { /* Note that if 1 in {w, h} then it's impossible to have a region * of size > w*h, so the special case only affects w=h=2. */ - int nboards = 0; - int i; + int i, change, *dsf; assert(w >= 1); assert(h >= 1); - assert(board); - dsf = snew_dsf(sz); /* implicit dsf_init */ - /* I abuse the board variable: when generating the puzzle, it - * contains a shuffled list of numbers {0, ..., nsq-1}. */ - for (i = 0; i < (int)sz; ++i) board[i] = i; - - while (1) { - int change; - ++nboards; - shuffle(board, sz, sizeof (int), rs); - /* while the board can in principle be fixed */ - do { - change = FALSE; - for (i = 0; i < (int)sz; ++i) { - int a = SENTINEL; - int b = SENTINEL; - int c = SENTINEL; - const int aa = dsf_canonify(dsf, board[i]); - int cc = sz; - int j; - for (j = 0; j < 4; ++j) { - const int x = (board[i] % w) + dx[j]; - const int y = (board[i] / w) + dy[j]; - int bb; - if (x < 0 || x >= w || y < 0 || y >= h) continue; - bb = dsf_canonify(dsf, w*y + x); - if (aa == bb) continue; - else if (dsf_size(dsf, aa) == dsf_size(dsf, bb)) { - a = aa; - b = bb; - c = cc; - } else if (cc == sz) c = cc = bb; - } - if (a != SENTINEL) { - a = dsf_canonify(dsf, a); - assert(a != dsf_canonify(dsf, b)); - if (c != sz) assert(a != dsf_canonify(dsf, c)); - dsf_merge(dsf, a, c == sz? b: c); - /* if repair impossible; make a new board */ - if (dsf_size(dsf, a) > maxsize) goto retry; - change = TRUE; - } - } - } while (change); + * contains a shuffled list of numbers {0, ..., sz-1}. */ + for (i = 0; i < sz; ++i) board[i] = i; - for (i = 0; i < (int)sz; ++i) board[i] = dsf_size(dsf, i); + dsf = snewn(sz, int); +retry: + dsf_init(dsf, sz); + shuffle(board, sz, sizeof (int), rs); - sfree(dsf); - printv("returning board number %d\n", nboards); - return; + do { + change = FALSE; /* as long as the board potentially has errors */ + for (i = 0; i < sz; ++i) { + const int square = dsf_canonify(dsf, board[i]); + const int size = dsf_size(dsf, square); + int merge = SENTINEL, min = maxsize - size + 1, error = FALSE; + int neighbour, neighbour_size, j; + + for (j = 0; j < 4; ++j) { + const int x = (board[i] % w) + dx[j]; + const int y = (board[i] / w) + dy[j]; + if (x < 0 || x >= w || y < 0 || y >= h) continue; - retry: - dsf_init(dsf, sz); - } - assert(FALSE); /* unreachable */ -} + neighbour = dsf_canonify(dsf, w*y + x); + if (square == neighbour) continue; -static int rhofree(int *hop, int start) { - int turtle = start, rabbit = hop[start]; - while (rabbit != turtle) { /* find a cycle */ - turtle = hop[turtle]; - rabbit = hop[hop[rabbit]]; - } - do { /* check that start is in the cycle */ - rabbit = hop[rabbit]; - if (start == rabbit) return 1; - } while (rabbit != turtle); - return 0; + neighbour_size = dsf_size(dsf, neighbour); + if (size == neighbour_size) error = TRUE; + + /* find the smallest neighbour to merge with, which + * wouldn't make the region too large. (This is + * guaranteed by the initial value of `min'.) */ + if (neighbour_size < min) { + min = neighbour_size; + merge = neighbour; + } + } + + /* if this square is not in error, leave it be */ + if (!error) continue; + + /* if it is, but we can't fix it, retry the whole board. + * Maybe we could fix it by merging the conflicting + * neighbouring region(s) into some of their neighbours, + * but just restarting works out fine. */ + if (merge == SENTINEL) goto retry; + + /* merge with the smallest neighbouring workable region. */ + dsf_merge(dsf, square, merge); + change = TRUE; + } + } while (change); + + for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i); + merge_ones(board, w, h); + + sfree(dsf); } static void merge(int *dsf, int *connected, int a, int b) { int c; assert(dsf); assert(connected); - assert(rhofree(connected, a)); - assert(rhofree(connected, b)); a = dsf_canonify(dsf, a); b = dsf_canonify(dsf, b); if (a == b) return; @@ -421,8 +466,6 @@ static void merge(int *dsf, int *connected, int a, int b) { c = connected[a]; connected[a] = connected[b]; connected[b] = c; - assert(rhofree(connected, a)); - assert(rhofree(connected, b)); } static void *memdup(const void *ptr, size_t len, size_t esz) { @@ -613,6 +656,7 @@ static int learn_expand_or_one(struct solver_state *s, int w, int h) { (s->board[idx] >= expandsize(s->board, s->dsf, w, h, i, s->board[idx])))) one = FALSE; + if (dsf_size(s->dsf, idx) == s->board[idx]) continue; assert(s->board[i] == EMPTY); s->board[i] = -SENTINEL; if (check_capacity(s->board, w, h, idx)) continue; @@ -735,14 +779,24 @@ static int learn_critical_square(struct solver_state *s, int w, int h) { /* for each connected component */ for (i = 0; i < sz; ++i) { - int j; + int j, slack; if (s->board[i] == EMPTY) continue; if (i != dsf_canonify(s->dsf, i)) continue; - if (dsf_size(s->dsf, i) == s->board[i]) continue; + slack = s->board[i] - dsf_size(s->dsf, i); + if (slack == 0) continue; assert(s->board[i] != 1); /* for each empty square */ for (j = 0; j < sz; ++j) { - if (s->board[j] != EMPTY) continue; + if (s->board[j] == EMPTY) { + /* if it's too far away from the CC, don't bother */ + int k = i, jx = j % w, jy = j / w; + do { + int kx = k % w, ky = k / w; + if (abs(kx - jx) + abs(ky - jy) <= slack) break; + k = s->connected[k]; + } while (i != k); + if (i == k) continue; /* not within range */ + } else continue; s->board[j] = -SENTINEL; if (check_capacity(s->board, w, h, i)) continue; /* if not expanding s->board[i] to s->board[j] implies @@ -760,6 +814,262 @@ static int learn_critical_square(struct solver_state *s, int w, int h) { return learn; } +#if 0 +static void print_bitmap(int *bitmap, int w, int h) { + if (verbose) { + int x, y; + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + printv(" %03x", bm[y*w+x]); + } + printv("\n"); + } + } +} +#endif + +static int learn_bitmap_deductions(struct solver_state *s, int w, int h) +{ + const int sz = w * h; + int *bm = s->bm; + int *dsf = s->bmdsf; + int *minsize = s->bmminsize; + int x, y, i, j, n; + int learn = FALSE; + + /* + * This function does deductions based on building up a bitmap + * which indicates the possible numbers that can appear in each + * grid square. If we can rule out all but one possibility for a + * particular square, then we've found out the value of that + * square. In particular, this is one of the few forms of + * deduction capable of inferring the existence of a 'ghost + * region', i.e. a region which has none of its squares filled in + * at all. + * + * The reasoning goes like this. A currently unfilled square S can + * turn out to contain digit n in exactly two ways: either S is + * part of an n-region which also includes some currently known + * connected component of squares with n in, or S is part of an + * n-region separate from _all_ currently known connected + * components. If we can rule out both possibilities, then square + * S can't contain digit n at all. + * + * The former possibility: if there's a region of size n + * containing both S and some existing component C, then that + * means the distance from S to C must be small enough that C + * could be extended to include S without becoming too big. So we + * can do a breadth-first search out from all existing components + * with n in them, to identify all the squares which could be + * joined to any of them. + * + * The latter possibility: if there's a region of size n that + * doesn't contain _any_ existing component, then it also can't + * contain any square adjacent to an existing component either. So + * we can identify all the EMPTY squares not adjacent to any + * existing square with n in, and group them into connected + * components; then any component of size less than n is ruled + * out, because there wouldn't be room to create a completely new + * n-region in it. + * + * In fact we process these possibilities in the other order. + * First we find all the squares not adjacent to an existing + * square with n in; then we winnow those by removing too-small + * connected components, to get the set of squares which could + * possibly be part of a brand new n-region; and finally we do the + * breadth-first search to add in the set of squares which could + * possibly be added to some existing n-region. + */ + + /* + * Start by initialising our bitmap to 'all numbers possible in + * all squares'. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + bm[y*w+x] = (1 << 10) - (1 << 1); /* bits 1,2,...,9 now set */ +#if 0 + printv("initial bitmap:\n"); + print_bitmap(bm, w, h); +#endif + + /* + * Now completely zero out the bitmap for squares that are already + * filled in (we aren't interested in those anyway). Also, for any + * filled square, eliminate its number from all its neighbours + * (because, as discussed above, the neighbours couldn't be part + * of a _new_ region with that number in it, and that's the case + * we consider first). + */ + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + i = y*w+x; + n = s->board[i]; + + if (n != EMPTY) { + bm[i] = 0; + + if (x > 0) + bm[i-1] &= ~(1 << n); + if (x+1 < w) + bm[i+1] &= ~(1 << n); + if (y > 0) + bm[i-w] &= ~(1 << n); + if (y+1 < h) + bm[i+w] &= ~(1 << n); + } + } + } +#if 0 + printv("bitmap after filled squares:\n"); + print_bitmap(bm, w, h); +#endif + + /* + * Now, for each n, we separately find the connected components of + * squares for which n is still a possibility. Then discard any + * component of size < n, because that component is too small to + * have a completely new n-region in it. + */ + for (n = 1; n <= 9; n++) { + dsf_init(dsf, sz); + + /* Build the dsf */ + for (y = 0; y < h; y++) + for (x = 0; x+1 < w; x++) + if (bm[y*w+x] & bm[y*w+(x+1)] & (1 << n)) + dsf_merge(dsf, y*w+x, y*w+(x+1)); + for (y = 0; y+1 < h; y++) + for (x = 0; x < w; x++) + if (bm[y*w+x] & bm[(y+1)*w+x] & (1 << n)) + dsf_merge(dsf, y*w+x, (y+1)*w+x); + + /* Query the dsf */ + for (i = 0; i < sz; i++) + if ((bm[i] & (1 << n)) && dsf_size(dsf, i) < n) + bm[i] &= ~(1 << n); + } +#if 0 + printv("bitmap after winnowing small components:\n"); + print_bitmap(bm, w, h); +#endif + + /* + * Now our bitmap includes every square which could be part of a + * completely new region, of any size. Extend it to include + * squares which could be part of an existing region. + */ + for (n = 1; n <= 9; n++) { + /* + * We're going to do a breadth-first search starting from + * existing connected components with cell value n, to find + * all cells they might possibly extend into. + * + * The quantity we compute, for each square, is 'minimum size + * that any existing CC would have to have if extended to + * include this square'. So squares already _in_ an existing + * CC are initialised to the size of that CC; then we search + * outwards using the rule that if a square's score is j, then + * its neighbours can't score more than j+1. + * + * Scores are capped at n+1, because if a square scores more + * than n then that's enough to know it can't possibly be + * reached by extending an existing region - we don't need to + * know exactly _how far_ out of reach it is. + */ + for (i = 0; i < sz; i++) { + if (s->board[i] == n) { + /* Square is part of an existing CC. */ + minsize[i] = dsf_size(s->dsf, i); + } else { + /* Otherwise, initialise to the maximum score n+1; + * we'll reduce this later if we find a neighbouring + * square with a lower score. */ + minsize[i] = n+1; + } + } + + for (j = 1; j < n; j++) { + /* + * Find neighbours of cells scoring j, and set their score + * to at most j+1. + * + * Doing the BFS this way means we need n passes over the + * grid, which isn't entirely optimal but it seems to be + * fast enough for the moment. This could probably be + * improved by keeping a linked-list queue of cells in + * some way, but I think you'd have to be a bit careful to + * insert things into the right place in the queue; this + * way is easier not to get wrong. + */ + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + i = y*w+x; + if (minsize[i] == j) { + if (x > 0 && minsize[i-1] > j+1) + minsize[i-1] = j+1; + if (x+1 < w && minsize[i+1] > j+1) + minsize[i+1] = j+1; + if (y > 0 && minsize[i-w] > j+1) + minsize[i-w] = j+1; + if (y+1 < h && minsize[i+w] > j+1) + minsize[i+w] = j+1; + } + } + } + } + + /* + * Now, every cell scoring at most n should have its 1<> 8) { val >>= 8; n += 8; } + if (val >> 4) { val >>= 4; n += 4; } + if (val >> 2) { val >>= 2; n += 2; } + if (val >> 1) { val >>= 1; n += 1; } + + /* Double-check that we ended up with a sensible + * answer. */ + assert(1 <= n); + assert(n <= 9); + assert(bm[i] == (1 << n)); + + if (s->board[i] == EMPTY) { + printv("learn: %d is only possibility at (%d, %d)\n", + n, i % w, i / w); + s->board[i] = n; + filled_square(s, w, h, i); + assert(s->nempty); + --s->nempty; + learn = TRUE; + } + } + } + + return learn; +} + static int solver(const int *orig, int w, int h, char **solution) { const int sz = w * h; @@ -769,6 +1079,9 @@ static int solver(const int *orig, int w, int h, char **solution) { ss.connected = snewn(sz, int); /* connected[n] := n.next; */ /* cyclic disjoint singly linked lists, same partitioning as dsf. * The lists lets you iterate over a partition given any member */ + ss.bm = snewn(sz, int); + ss.bmdsf = snew_dsf(sz); + ss.bmminsize = snewn(sz, int); printv("trying to solve this:\n"); print_board(ss.board, w, h); @@ -778,6 +1091,7 @@ static int solver(const int *orig, int w, int h, char **solution) { if (learn_blocked_expansion(&ss, w, h)) continue; if (learn_expand_or_one(&ss, w, h)) continue; if (learn_critical_square(&ss, w, h)) continue; + if (learn_bitmap_deductions(&ss, w, h)) continue; break; } while (ss.nempty); @@ -786,7 +1100,6 @@ static int solver(const int *orig, int w, int h, char **solution) { if (solution) { int i; - assert(*solution == NULL); *solution = snewn(sz + 2, char); **solution = 's'; for (i = 0; i < sz; ++i) (*solution)[i + 1] = ss.board[i] + '0'; @@ -798,6 +1111,9 @@ static int solver(const int *orig, int w, int h, char **solution) { sfree(ss.dsf); sfree(ss.board); sfree(ss.connected); + sfree(ss.bm); + sfree(ss.bmdsf); + sfree(ss.bmminsize); return !ss.nempty; } @@ -824,107 +1140,159 @@ static int *make_dsf(int *dsf, int *board, const int w, const int h) { return dsf; } -/* -static int filled(int *board, int *randomize, int k, int n) { - int i; - if (board == NULL) return FALSE; - if (randomize == NULL) return FALSE; - if (k > n) return FALSE; - for (i = 0; i < k; ++i) if (board[randomize[i]] == 0) return FALSE; - for (; i < n; ++i) if (board[randomize[i]] != 0) return FALSE; - return TRUE; -} -*/ +static void minimize_clue_set(int *board, int w, int h, random_state *rs) +{ + const int sz = w * h; + int *shuf = snewn(sz, int), i; + int *dsf, *next; -static int *g_board; -static int compare(const void *pa, const void *pb) { - if (!g_board) return 0; - return g_board[*(const int *)pb] - g_board[*(const int *)pa]; -} + for (i = 0; i < sz; ++i) shuf[i] = i; + shuffle(shuf, sz, sizeof (int), rs); -static void minimize_clue_set(int *board, int w, int h, int *randomize) { - const int sz = w * h; - int i; - int *board_cp = snewn(sz, int); - memcpy(board_cp, board, sz * sizeof (int)); + /* + * First, try to eliminate an entire region at a time if possible, + * because inferring the existence of a completely unclued region + * is a particularly good aspect of this puzzle type and we want + * to encourage it to happen. + * + * Begin by identifying the regions as linked lists of cells using + * the 'next' array. + */ + dsf = make_dsf(NULL, board, w, h); + next = snewn(sz, int); + for (i = 0; i < sz; ++i) { + int j = dsf_canonify(dsf, i); + if (i == j) { + /* First cell of a region; set next[i] = -1 to indicate + * end-of-list. */ + next[i] = -1; + } else { + /* Add this cell to a region which already has a + * linked-list head, by pointing the canonical element j + * at this one, and pointing this one in turn at wherever + * j previously pointed. (This should end up with the + * elements linked in the order 1,n,n-1,n-2,...,2, which + * is a bit weird-looking, but any order is fine.) + */ + assert(j < i); + next[i] = next[j]; + next[j] = i; + } + } - /* since more clues only helps and never hurts, one pass will do - * just fine: if we can remove clue n with k clues of index > n, - * we could have removed clue n with >= k clues of index > n. - * So an additional pass wouldn't do anything [use induction]. */ + /* + * Now loop over the grid cells in our shuffled order, and each + * time we encounter a region for the first time, try to remove it + * all. Then we set next[canonical index] to -2 rather than -1, to + * mark it as already tried. + * + * Doing this in a loop over _cells_, rather than extracting and + * shuffling a list of _regions_, is intended to skew the + * probabilities towards trying to remove larger regions first + * (but without anything as crudely predictable as enforcing that + * we _always_ process regions in descending size order). Region + * removals might well be mutually exclusive, and larger ghost + * regions are more interesting, so we want to bias towards them + * if we can. + */ for (i = 0; i < sz; ++i) { - if (board[randomize[i]] == EMPTY) continue; - board[randomize[i]] = EMPTY; - /* (rot.) symmetry tends to include _way_ too many hints */ - /* board[sz - randomize[i] - 1] = EMPTY; */ - if (!solver(board, w, h, NULL)) { - board[randomize[i]] = board_cp[randomize[i]]; - /* board[sz - randomize[i] - 1] = - board_cp[sz - randomize[i] - 1]; */ + int j = dsf_canonify(dsf, shuf[i]); + if (next[j] != -2) { + int tmp = board[j]; + int k; + + /* Blank out the whole thing. */ + for (k = j; k >= 0; k = next[k]) + board[k] = EMPTY; + + if (!solver(board, w, h, NULL)) { + /* Wasn't still solvable; reinstate it all */ + for (k = j; k >= 0; k = next[k]) + board[k] = tmp; + } + + /* Either way, don't try this region again. */ + next[j] = -2; } } + sfree(next); + sfree(dsf); - sfree(board_cp); + /* + * Now go through individual cells, in the same shuffled order, + * and try to remove each one by itself. + */ + for (i = 0; i < sz; ++i) { + int tmp = board[shuf[i]]; + board[shuf[i]] = EMPTY; + if (!solver(board, w, h, NULL)) board[shuf[i]] = tmp; + } + + sfree(shuf); } -static char *new_game_desc(game_params *params, random_state *rs, - char **aux, int interactive) +static int encode_run(char *buffer, int run) { - const int w = params->w; - const int h = params->h; - const int sz = w * h; - int *board = snewn(sz, int); - int *randomize = snewn(sz, int); - char *game_description = snewn(sz + 1, char); - int i; + int i = 0; + for (; run > 26; run -= 26) + buffer[i++] = 'z'; + if (run) + buffer[i++] = 'a' - 1 + run; + return i; +} - for (i = 0; i < sz; ++i) { - board[i] = EMPTY; - randomize[i] = i; - } +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, int interactive) +{ + const int w = params->w, h = params->h, sz = w * h; + int *board = snewn(sz, int), i, j, run; + char *description = snewn(sz + 1, char); make_board(board, w, h, rs); - g_board = board; - qsort(randomize, sz, sizeof (int), compare); - minimize_clue_set(board, w, h, randomize); + minimize_clue_set(board, w, h, rs); - for (i = 0; i < sz; ++i) { + for (run = j = i = 0; i < sz; ++i) { assert(board[i] >= 0); assert(board[i] < 10); - game_description[i] = board[i] + '0'; + if (board[i] == 0) { + ++run; + } else { + j += encode_run(description + j, run); + run = 0; + description[j++] = board[i] + '0'; + } } - game_description[sz] = '\0'; + j += encode_run(description + j, run); + description[j++] = '\0'; -/* - solver(board, w, h, aux); - print_board(board, w, h); -*/ - - sfree(randomize); sfree(board); - return game_description; + return sresize(description, j, char); } -static char *validate_desc(game_params *params, char *desc) +static char *validate_desc(const game_params *params, const char *desc) { - int i; const int sz = params->w * params->h; const char m = '0' + max(max(params->w, params->h), 3); - - printv("desc = '%s'; sz = %d\n", desc, sz); - - for (i = 0; desc[i] && i < sz; ++i) - if (!isdigit((unsigned char) *desc)) - return "non-digit in string"; - else if (desc[i] > m) - return "too large digit in string"; - if (desc[i]) return "string too long"; - else if (i < sz) return "string too short"; - return NULL; + int area; + + for (area = 0; *desc; ++desc) { + if (*desc >= 'a' && *desc <= 'z') area += *desc - 'a' + 1; + else if (*desc >= '0' && *desc <= m) ++area; + else { + static char s[] = "Invalid character '%""' in game description"; + int n = sprintf(s, "Invalid character '%1c' in game description", + *desc); + assert(n + 1 <= lenof(s)); /* +1 for the terminating NUL */ + return s; + } + if (area > sz) return "Too much data to fit in grid"; + } + return (area < sz) ? "Not enough data to fill grid" : NULL; } -static game_state *new_game(midend *me, game_params *params, char *desc) +static game_state *new_game(midend *me, const game_params *params, + const char *desc) { game_state *state = snew(game_state); int sz = params->w * params->h; @@ -935,13 +1303,20 @@ static game_state *new_game(midend *me, game_params *params, char *desc) state->shared->refcnt = 1; state->shared->params = *params; /* struct copy */ state->shared->clues = snewn(sz, int); - for (i = 0; i < sz; ++i) state->shared->clues[i] = desc[i] - '0'; + + for (i = 0; *desc; ++desc) { + if (*desc >= 'a' && *desc <= 'z') { + int j = *desc - 'a' + 1; + assert(i + j <= sz); + for (; j; --j) state->shared->clues[i++] = 0; + } else state->shared->clues[i++] = *desc - '0'; + } state->board = memdup(state->shared->clues, sz, sizeof (int)); return state; } -static game_state *dup_game(game_state *state) +static game_state *dup_game(const game_state *state) { const int sz = state->shared->params.w * state->shared->params.h; game_state *ret = snew(game_state); @@ -966,16 +1341,18 @@ static void free_game(game_state *state) sfree(state); } -static char *solve_game(game_state *state, game_state *currstate, - char *aux, char **error) +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) { if (aux == NULL) { const int w = state->shared->params.w; const int h = state->shared->params.h; - if (!solver(state->board, w, h, &aux)) + char *new_aux; + if (!solver(state->board, w, h, &new_aux)) *error = "Sorry, I couldn't find a solution"; + return new_aux; } - return aux; + return dupstr(aux); } /***************************************************************************** @@ -984,15 +1361,15 @@ static char *solve_game(game_state *state, game_state *currstate, struct game_ui { int *sel; /* w*h highlighted squares, or NULL */ - int cur_x, cur_y, cur_visible; + int cur_x, cur_y, cur_visible, keydragging; }; -static game_ui *new_ui(game_state *state) +static game_ui *new_ui(const game_state *state) { game_ui *ui = snew(game_ui); ui->sel = NULL; - ui->cur_x = ui->cur_y = ui->cur_visible = 0; + ui->cur_x = ui->cur_y = ui->cur_visible = ui->keydragging = 0; return ui; } @@ -1004,23 +1381,24 @@ static void free_ui(game_ui *ui) sfree(ui); } -static char *encode_ui(game_ui *ui) +static char *encode_ui(const game_ui *ui) { return NULL; } -static void decode_ui(game_ui *ui, char *encoding) +static void decode_ui(game_ui *ui, const char *encoding) { } -static void game_changed_state(game_ui *ui, game_state *oldstate, - game_state *newstate) +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) { /* Clear any selection */ if (ui->sel) { sfree(ui->sel); ui->sel = NULL; } + ui->keydragging = FALSE; } #define PREFERRED_TILE_SIZE 32 @@ -1036,7 +1414,8 @@ struct game_drawstate { int *dsf_scratch, *border_scratch; }; -static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, int x, int y, int button) { const int w = state->shared->params.w; @@ -1076,36 +1455,58 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, if (IS_CURSOR_MOVE(button)) { ui->cur_visible = 1; move_cursor(button, &ui->cur_x, &ui->cur_y, w, h, 0); + if (ui->keydragging) goto select_square; return ""; } - if (IS_CURSOR_SELECT(button)) { + if (button == CURSOR_SELECT) { if (!ui->cur_visible) { ui->cur_visible = 1; return ""; } + ui->keydragging = !ui->keydragging; + if (!ui->keydragging) return ""; + + select_square: if (!ui->sel) { ui->sel = snewn(w*h, int); memset(ui->sel, 0, w*h*sizeof(int)); } - if (state->shared->clues[w*ui->cur_y + ui->cur_x] == 0) - ui->sel[w*ui->cur_y + ui->cur_x] ^= 1; - return ""; + if (!state->shared->clues[w*ui->cur_y + ui->cur_x]) + ui->sel[w*ui->cur_y + ui->cur_x] = 1; + return ""; + } + if (button == CURSOR_SELECT2) { + if (!ui->cur_visible) { + ui->cur_visible = 1; + return ""; + } + if (!ui->sel) { + ui->sel = snewn(w*h, int); + memset(ui->sel, 0, w*h*sizeof(int)); + } + ui->keydragging = FALSE; + if (!state->shared->clues[w*ui->cur_y + ui->cur_x]) + ui->sel[w*ui->cur_y + ui->cur_x] ^= 1; + for (i = 0; i < w*h && !ui->sel[i]; i++); + if (i == w*h) { + sfree(ui->sel); + ui->sel = NULL; + } + return ""; } - switch (button) { - case ' ': - case '\r': - case '\n': - case '\b': - case '\177': - button = 0; - break; - default: - if (!isdigit(button)) return NULL; - button -= '0'; - if (button > (w == 2 && h == 2? 3: max(w, h))) return NULL; + if (button == '\b' || button == 27) { + sfree(ui->sel); + ui->sel = NULL; + ui->keydragging = FALSE; + return ""; } + if (button < '0' || button > '9') return NULL; + button -= '0'; + if (button > (w == 2 && h == 2 ? 3 : max(w, h))) return NULL; + ui->keydragging = FALSE; + for (i = 0; i < w*h; i++) { char buf[32]; if ((ui->sel && ui->sel[i]) || @@ -1136,9 +1537,9 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, return move ? move : ""; } -static game_state *execute_move(game_state *state, char *move) +static game_state *execute_move(const game_state *state, const char *move) { - game_state *new_state; + game_state *new_state = NULL; const int sz = state->shared->params.w * state->shared->params.h; if (*move == 's') { @@ -1149,18 +1550,18 @@ static game_state *execute_move(game_state *state, char *move) } else { int value; char *endptr, *delim = strchr(move, '_'); - if (!delim) return NULL; + if (!delim) goto err; value = strtol(delim+1, &endptr, 0); - if (*endptr || endptr == delim+1) return NULL; - if (value < 0 || value > 9) return NULL; + if (*endptr || endptr == delim+1) goto err; + if (value < 0 || value > 9) goto err; new_state = dup_game(state); while (*move) { const int i = strtol(move, &endptr, 0); - if (endptr == move) return NULL; - if (i < 0 || i >= sz) return NULL; + if (endptr == move) goto err; + if (i < 0 || i >= sz) goto err; new_state->board[i] = value; if (*endptr == '_') break; - if (*endptr != ',') return NULL; + if (*endptr != ',') goto err; move = endptr + 1; } } @@ -1181,6 +1582,10 @@ static game_state *execute_move(game_state *state, char *move) } return new_state; + +err: + if (new_state) free_game(new_state); + return NULL; } /* ---------------------------------------------------------------------- @@ -1201,7 +1606,7 @@ enum { NCOLOURS }; -static void game_compute_size(game_params *params, int tilesize, +static void game_compute_size(const game_params *params, int tilesize, int *x, int *y) { *x = (params->w + 1) * tilesize; @@ -1209,7 +1614,7 @@ static void game_compute_size(game_params *params, int tilesize, } static void game_set_size(drawing *dr, game_drawstate *ds, - game_params *params, int tilesize) + const game_params *params, int tilesize) { ds->tilesize = tilesize; } @@ -1248,7 +1653,7 @@ static float *game_colours(frontend *fe, int *ncolours) return ret; } -static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); int i; @@ -1417,8 +1822,8 @@ static void draw_square(drawing *dr, game_drawstate *ds, int x, int y, TILE_SIZE); } -static void draw_grid(drawing *dr, game_drawstate *ds, game_state *state, - game_ui *ui, int flashy, int borders, int shading) +static void draw_grid(drawing *dr, game_drawstate *ds, const game_state *state, + const game_ui *ui, int flashy, int borders, int shading) { const int w = state->shared->params.w; const int h = state->shared->params.h; @@ -1491,21 +1896,37 @@ static void draw_grid(drawing *dr, game_drawstate *ds, game_state *state, /* * Determine what we need to draw in this square. */ - int v = state->board[y*w+x]; + int i = y*w+x, v = state->board[i]; int flags = 0; if (flashy || !shading) { /* clear all background flags */ - } else if (ui->sel && ui->sel[y*w+x]) { + } else if (ui && ui->sel && ui->sel[i]) { flags |= HIGH_BG; } else if (v) { - int size = dsf_size(ds->dsf_scratch, y*w+x); + int size = dsf_size(ds->dsf_scratch, i); if (size == v) flags |= CORRECT_BG; else if (size > v) flags |= ERROR_BG; + else { + int rt = dsf_canonify(ds->dsf_scratch, i), j; + for (j = 0; j < w*h; ++j) { + int k; + if (dsf_canonify(ds->dsf_scratch, j) != rt) continue; + for (k = 0; k < 4; ++k) { + const int xx = j % w + dx[k], yy = j / w + dy[k]; + if (xx >= 0 && xx < w && yy >= 0 && yy < h && + state->board[yy*w + xx] == EMPTY) + goto noflag; + } + } + flags |= ERROR_BG; + noflag: + ; + } } - if (ui->cur_visible && x == ui->cur_x && y == ui->cur_y) + if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y) flags |= CURSOR_SQ; /* @@ -1558,8 +1979,9 @@ static void draw_grid(drawing *dr, game_drawstate *ds, game_state *state, } } -static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, - game_state *state, int dir, game_ui *ui, +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, float animtime, float flashtime) { const int w = state->shared->params.w; @@ -1595,14 +2017,14 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE); } -static float game_anim_length(game_state *oldstate, game_state *newstate, - int dir, game_ui *ui) +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { return 0.0F; } -static float game_flash_length(game_state *oldstate, game_state *newstate, - int dir, game_ui *ui) +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { assert(oldstate); assert(newstate); @@ -1614,12 +2036,17 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_timing_state(game_state *state, game_ui *ui) +static int game_status(const game_state *state) +{ + return state->completed ? +1 : 0; +} + +static int game_timing_state(const game_state *state, game_ui *ui) { return TRUE; } -static void game_print_size(game_params *params, float *x, float *y) +static void game_print_size(const game_params *params, float *x, float *y) { int pw, ph; @@ -1631,7 +2058,7 @@ static void game_print_size(game_params *params, float *x, float *y) *y = ph / 100.0F; } -static void game_print(drawing *dr, game_state *state, int tilesize) +static void game_print(drawing *dr, const game_state *state, int tilesize) { const int w = state->shared->params.w; const int h = state->shared->params.h; @@ -1712,6 +2139,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, TRUE, FALSE, game_print_size, game_print, FALSE, /* wants_statusbar */ FALSE, game_timing_state,