1 /* -*- tab-width: 8; indent-tabs-mode: t -*-
2 * filling.c: An implementation of the Nikoli game fillomino.
3 * Copyright (C) 2007 Jonas Kölker. See LICENSE for the license.
8 * - use a typedef instead of int for numbers on the board
9 * + replace int with something else (signed short?)
10 * - the type should be signed (for -board[i] and -SENTINEL)
11 * - the type should be somewhat big: board[i] = i
12 * - Using shorts gives us 181x181 puzzles as upper bound.
14 * - in board generation, after having merged regions such that no
15 * more merges are necessary, try splitting (big) regions.
16 * + it seems that smaller regions make for better puzzles; see
17 * for instance the 7x7 puzzle in this file (grep for 7x7:).
19 * - symmetric hints (solo-style)
20 * + right now that means including _many_ hints, and the puzzles
21 * won't look any nicer. Not worth it (at the moment).
23 * - make the solver do recursion/backtracking.
24 * + This is for user-submitted puzzles, not for puzzle
25 * generation (on the other hand, never say never).
27 * - prove that only w=h=2 needs a special case
29 * - solo-like pencil marks?
31 * - a user says that the difficulty is unevenly distributed.
32 * + partition into levels? Will they be non-crap?
34 * - Allow square contents > 9?
35 * + I could use letters for digits (solo does this), but
36 * letters don't have numeric significance (normal people hate
37 * base36), which is relevant here (much more than in solo).
38 * + [click, 1, 0, enter] => [10 in clicked square]?
39 * + How much information is needed to solve? Does one need to
40 * know the algorithm by which the largest number is set?
42 * - eliminate puzzle instances with done chunks (1's in particular)?
43 * + that's what the qsort call is all about.
44 * + the 1's don't bother me that much.
45 * + but this takes a LONG time (not always possible)?
46 * - this may be affected by solver (lack of) quality.
47 * - weed them out by construction instead of post-cons check
48 * + but that interleaves make_board and new_game_desc: you
49 * have to alternate between changing the board and
50 * changing the hint set (instead of just creating the
51 * board once, then changing the hint set once -> done).
53 * - use binary search when discovering the minimal sovable point
54 * + profile to show a need (but when the solver gets slower...)
55 * + 7x9 @ .011s, 9x13 @ .075s, 17x13 @ .661s (all avg with n=100)
56 * + but the hints are independent, not linear, so... what?
69 static unsigned char verbose;
71 static void printv(const char *fmt, ...) {
82 /*****************************************************************************
83 * GAME CONFIGURATION AND PARAMETERS *
84 *****************************************************************************/
91 struct game_params params;
98 struct shared_state *shared;
99 int completed, cheated;
102 static const struct game_params filling_defaults[3] = {
103 {9, 7}, {13, 9}, {17, 13}
106 static game_params *default_params(void)
108 game_params *ret = snew(game_params);
110 *ret = filling_defaults[1]; /* struct copy */
115 static int game_fetch_preset(int i, char **name, game_params **params)
119 if (i < 0 || i >= lenof(filling_defaults)) return FALSE;
120 *params = snew(game_params);
121 **params = filling_defaults[i]; /* struct copy */
122 sprintf(buf, "%dx%d", filling_defaults[i].w, filling_defaults[i].h);
128 static void free_params(game_params *params)
133 static game_params *dup_params(const game_params *params)
135 game_params *ret = snew(game_params);
136 *ret = *params; /* struct copy */
140 static void decode_params(game_params *ret, char const *string)
142 ret->w = ret->h = atoi(string);
143 while (*string && isdigit((unsigned char) *string)) ++string;
144 if (*string == 'x') ret->h = atoi(++string);
147 static char *encode_params(const game_params *params, int full)
150 sprintf(buf, "%dx%d", params->w, params->h);
154 static config_item *game_configure(const game_params *params)
159 ret = snewn(3, config_item);
161 ret[0].name = "Width";
162 ret[0].type = C_STRING;
163 sprintf(buf, "%d", params->w);
164 ret[0].u.string.sval = dupstr(buf);
166 ret[1].name = "Height";
167 ret[1].type = C_STRING;
168 sprintf(buf, "%d", params->h);
169 ret[1].u.string.sval = dupstr(buf);
177 static game_params *custom_params(const config_item *cfg)
179 game_params *ret = snew(game_params);
181 ret->w = atoi(cfg[0].u.string.sval);
182 ret->h = atoi(cfg[1].u.string.sval);
187 static const char *validate_params(const game_params *params, int full)
189 if (params->w < 1) return "Width must be at least one";
190 if (params->h < 1) return "Height must be at least one";
195 /*****************************************************************************
196 * STRINGIFICATION OF GAME STATE *
197 *****************************************************************************/
201 /* Example of plaintext rendering:
202 * +---+---+---+---+---+---+---+
203 * | 6 | | | 2 | | | 2 |
204 * +---+---+---+---+---+---+---+
205 * | | 3 | | 6 | | 3 | |
206 * +---+---+---+---+---+---+---+
207 * | 3 | | | | | | 1 |
208 * +---+---+---+---+---+---+---+
209 * | | 2 | 3 | | 4 | 2 | |
210 * +---+---+---+---+---+---+---+
211 * | 2 | | | | | | 3 |
212 * +---+---+---+---+---+---+---+
213 * | | 5 | | 1 | | 4 | |
214 * +---+---+---+---+---+---+---+
215 * | 4 | | | 3 | | | 3 |
216 * +---+---+---+---+---+---+---+
218 * This puzzle instance is taken from the nikoli website
219 * Encoded (unsolved and solved), the strings are these:
220 * 7x7:6002002030603030000010230420200000305010404003003
221 * 7x7:6662232336663232331311235422255544325413434443313
223 static char *board_to_string(int *board, int w, int h) {
224 const int sz = w * h;
225 const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */
226 const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */
227 const int chlen = chw * chh;
228 char *repr = snewn(chlen + 1, char);
233 /* build the first line ("^(\+---){n}\+$") */
234 for (i = 0; i < w; ++i) {
241 repr[4*i + 1] = '\n';
243 /* ... and copy it onto the odd-numbered lines */
244 for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw);
246 /* build the second line ("^(\|\t){n}\|$") */
247 for (i = 0; i < w; ++i) {
248 repr[chw + 4*i + 0] = '|';
249 repr[chw + 4*i + 1] = ' ';
250 repr[chw + 4*i + 2] = ' ';
251 repr[chw + 4*i + 3] = ' ';
253 repr[chw + 4*i + 0] = '|';
254 repr[chw + 4*i + 1] = '\n';
256 /* ... and copy it onto the even-numbered lines */
257 for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw);
259 /* fill in the numbers */
260 for (i = 0; i < sz; ++i) {
263 if (board[i] == EMPTY) continue;
264 repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0';
271 static int game_can_format_as_text_now(const game_params *params)
276 static char *game_text_format(const game_state *state)
278 const int w = state->shared->params.w;
279 const int h = state->shared->params.h;
280 return board_to_string(state->board, w, h);
283 /*****************************************************************************
284 * GAME GENERATION AND SOLVER *
285 *****************************************************************************/
287 static const int dx[4] = {-1, 1, 0, 0};
288 static const int dy[4] = {0, 0, -1, 1};
297 /* Used internally by learn_bitmap_deductions; kept here to avoid
298 * mallocing/freeing them every time that function is called. */
299 int *bm, *bmdsf, *bmminsize;
302 static void print_board(int *board, int w, int h) {
304 char *repr = board_to_string(board, w, h);
305 printv("%s\n", repr);
310 static game_state *new_game(midend *, const game_params *, const char *);
311 static void free_game(game_state *);
315 static int mark_region(int *board, int w, int h, int i, int n, int m) {
320 for (j = 0; j < 4; ++j) {
321 const int x = (i % w) + dx[j], y = (i / w) + dy[j], ii = w*y + x;
322 if (x < 0 || x >= w || y < 0 || y >= h) continue;
323 if (board[ii] == m) return FALSE;
324 if (board[ii] != n) continue;
325 if (!mark_region(board, w, h, ii, n, m)) return FALSE;
330 static int region_size(int *board, int w, int h, int i) {
331 const int sz = w * h;
333 if (board[i] == 0) return 0;
335 mark_region(board, w, h, i, board[i], SENTINEL);
336 for (size = j = 0; j < sz; ++j) {
337 if (board[j] != -1) continue;
344 static void merge_ones(int *board, int w, int h)
346 const int sz = w * h;
347 const int maxsize = min(max(max(w, h), 3), 9);
351 for (i = 0; i < sz; ++i) {
352 if (board[i] != 1) continue;
354 for (j = 0; j < 4; ++j, board[i] = 1) {
355 const int x = (i % w) + dx[j], y = (i / w) + dy[j];
356 int oldsize, newsize, ok, ii = w*y + x;
357 if (x < 0 || x >= w || y < 0 || y >= h) continue;
358 if (board[ii] == maxsize) continue;
362 newsize = region_size(board, w, h, i);
364 if (newsize > maxsize) continue;
366 ok = mark_region(board, w, h, i, oldsize, newsize);
368 for (k = 0; k < sz; ++k)
370 board[k] = ok ? newsize : oldsize;
374 if (j < 4) change = TRUE;
379 /* generate a random valid board; uses validate_board. */
380 static void make_board(int *board, int w, int h, random_state *rs) {
381 const int sz = w * h;
383 /* w=h=2 is a special case which requires a number > max(w, h) */
384 /* TODO prove that this is the case ONLY for w=h=2. */
385 const int maxsize = min(max(max(w, h), 3), 9);
387 /* Note that if 1 in {w, h} then it's impossible to have a region
388 * of size > w*h, so the special case only affects w=h=2. */
396 /* I abuse the board variable: when generating the puzzle, it
397 * contains a shuffled list of numbers {0, ..., sz-1}. */
398 for (i = 0; i < sz; ++i) board[i] = i;
400 dsf = snewn(sz, int);
403 shuffle(board, sz, sizeof (int), rs);
406 change = FALSE; /* as long as the board potentially has errors */
407 for (i = 0; i < sz; ++i) {
408 const int square = dsf_canonify(dsf, board[i]);
409 const int size = dsf_size(dsf, square);
410 int merge = SENTINEL, min = maxsize - size + 1, error = FALSE;
411 int neighbour, neighbour_size, j;
413 for (j = 0; j < 4; ++j) {
414 const int x = (board[i] % w) + dx[j];
415 const int y = (board[i] / w) + dy[j];
416 if (x < 0 || x >= w || y < 0 || y >= h) continue;
418 neighbour = dsf_canonify(dsf, w*y + x);
419 if (square == neighbour) continue;
421 neighbour_size = dsf_size(dsf, neighbour);
422 if (size == neighbour_size) error = TRUE;
424 /* find the smallest neighbour to merge with, which
425 * wouldn't make the region too large. (This is
426 * guaranteed by the initial value of `min'.) */
427 if (neighbour_size < min) {
428 min = neighbour_size;
433 /* if this square is not in error, leave it be */
434 if (!error) continue;
436 /* if it is, but we can't fix it, retry the whole board.
437 * Maybe we could fix it by merging the conflicting
438 * neighbouring region(s) into some of their neighbours,
439 * but just restarting works out fine. */
440 if (merge == SENTINEL) goto retry;
442 /* merge with the smallest neighbouring workable region. */
443 dsf_merge(dsf, square, merge);
448 for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i);
449 merge_ones(board, w, h);
454 static void merge(int *dsf, int *connected, int a, int b) {
458 a = dsf_canonify(dsf, a);
459 b = dsf_canonify(dsf, b);
461 dsf_merge(dsf, a, b);
463 connected[a] = connected[b];
467 static void *memdup(const void *ptr, size_t len, size_t esz) {
468 void *dup = smalloc(len * esz);
470 memcpy(dup, ptr, len * esz);
474 static void expand(struct solver_state *s, int w, int h, int t, int f) {
477 assert(s->board[t] == EMPTY); /* expand to empty square */
478 assert(s->board[f] != EMPTY); /* expand from non-empty square */
480 "learn: expanding %d from (%d, %d) into (%d, %d)\n",
481 s->board[f], f % w, f / w, t % w, t / w);
482 s->board[t] = s->board[f];
483 for (j = 0; j < 4; ++j) {
484 const int x = (t % w) + dx[j];
485 const int y = (t / w) + dy[j];
486 const int idx = w*y + x;
487 if (x < 0 || x >= w || y < 0 || y >= h) continue;
488 if (s->board[idx] != s->board[t]) continue;
489 merge(s->dsf, s->connected, t, idx);
494 static void clear_count(int *board, int sz) {
496 for (i = 0; i < sz; ++i) {
497 if (board[i] >= 0) continue;
498 else if (board[i] == -SENTINEL) board[i] = EMPTY;
499 else board[i] = -board[i];
503 static void flood_count(int *board, int w, int h, int i, int n, int *c) {
504 const int sz = w * h;
507 if (board[i] == EMPTY) board[i] = -SENTINEL;
508 else if (board[i] == n) board[i] = -board[i];
511 if (--*c == 0) return;
513 for (k = 0; k < 4; ++k) {
514 const int x = (i % w) + dx[k];
515 const int y = (i / w) + dy[k];
516 const int idx = w*y + x;
517 if (x < 0 || x >= w || y < 0 || y >= h) continue;
518 flood_count(board, w, h, idx, n, c);
523 static int check_capacity(int *board, int w, int h, int i) {
525 flood_count(board, w, h, i, board[i], &n);
526 clear_count(board, w * h);
530 static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) {
535 for (j = 0; j < 4; ++j) {
536 const int x = (i % w) + dx[j];
537 const int y = (i / w) + dy[j];
538 const int idx = w*y + x;
541 if (x < 0 || x >= w || y < 0 || y >= h) continue;
542 if (board[idx] != n) continue;
543 root = dsf_canonify(dsf, idx);
544 for (m = 0; m < nhits && root != hits[m]; ++m);
545 if (m < nhits) continue;
546 printv("\t (%d, %d) contrib %d to size\n", x, y, dsf[root] >> 2);
547 size += dsf_size(dsf, root);
548 assert(dsf_size(dsf, root) >= 1);
549 hits[nhits++] = root;
555 * +---+---+---+---+---+---+---+
556 * | 6 | | | 2 | | | 2 |
557 * +---+---+---+---+---+---+---+
558 * | | 3 | | 6 | | 3 | |
559 * +---+---+---+---+---+---+---+
560 * | 3 | | | | | | 1 |
561 * +---+---+---+---+---+---+---+
562 * | | 2 | 3 | | 4 | 2 | |
563 * +---+---+---+---+---+---+---+
564 * | 2 | | | | | | 3 |
565 * +---+---+---+---+---+---+---+
566 * | | 5 | | 1 | | 4 | |
567 * +---+---+---+---+---+---+---+
568 * | 4 | | | 3 | | | 3 |
569 * +---+---+---+---+---+---+---+
572 /* Solving techniques:
574 * CONNECTED COMPONENT FORCED EXPANSION (too big):
575 * When a CC can only be expanded in one direction, because all the
576 * other ones would make the CC too big.
577 * +---+---+---+---+---+
578 * | 2 | 2 | | 2 | _ |
579 * +---+---+---+---+---+
581 * CONNECTED COMPONENT FORCED EXPANSION (too small):
582 * When a CC must include a particular square, because otherwise there
583 * would not be enough room to complete it. This includes squares not
584 * adjacent to the CC through learn_critical_square.
590 * When an empty square has no neighbouring empty squares and only a 1
591 * will go into the square (or other CCs would be too big).
596 * TODO: generalise DROPPING IN A ONE: find the size of the CC of
597 * empty squares and a list of all adjacent numbers. See if only one
598 * number in {1, ..., size} u {all adjacent numbers} is possible.
599 * Probably this is only effective for a CC size < n for some n (4?)
601 * TODO: backtracking.
604 static void filled_square(struct solver_state *s, int w, int h, int i) {
606 for (j = 0; j < 4; ++j) {
607 const int x = (i % w) + dx[j];
608 const int y = (i / w) + dy[j];
609 const int idx = w*y + x;
610 if (x < 0 || x >= w || y < 0 || y >= h) continue;
611 if (s->board[i] == s->board[idx])
612 merge(s->dsf, s->connected, i, idx);
616 static void init_solver_state(struct solver_state *s, int w, int h) {
617 const int sz = w * h;
622 for (i = 0; i < sz; ++i) s->connected[i] = i;
623 for (i = 0; i < sz; ++i)
624 if (s->board[i] == EMPTY) ++s->nempty;
625 else filled_square(s, w, h, i);
628 static int learn_expand_or_one(struct solver_state *s, int w, int h) {
629 const int sz = w * h;
635 for (i = 0; i < sz; ++i) {
639 if (s->board[i] != EMPTY) continue;
641 for (j = 0; j < 4; ++j) {
642 const int x = (i % w) + dx[j];
643 const int y = (i / w) + dy[j];
644 const int idx = w*y + x;
645 if (x < 0 || x >= w || y < 0 || y >= h) continue;
646 if (s->board[idx] == EMPTY) {
651 (s->board[idx] == 1 ||
652 (s->board[idx] >= expandsize(s->board, s->dsf, w, h,
655 if (dsf_size(s->dsf, idx) == s->board[idx]) continue;
656 assert(s->board[i] == EMPTY);
657 s->board[i] = -SENTINEL;
658 if (check_capacity(s->board, w, h, idx)) continue;
659 assert(s->board[i] == EMPTY);
660 printv("learn: expanding in one\n");
661 expand(s, w, h, i, idx);
667 printv("learn: one at (%d, %d)\n", i % w, i / w);
668 assert(s->board[i] == EMPTY);
678 static int learn_blocked_expansion(struct solver_state *s, int w, int h) {
679 const int sz = w * h;
684 /* for every connected component */
685 for (i = 0; i < sz; ++i) {
689 if (s->board[i] == EMPTY) continue;
690 j = dsf_canonify(s->dsf, i);
692 /* (but only for each connected component) */
693 if (i != j) continue;
695 /* (and not if it's already complete) */
696 if (dsf_size(s->dsf, j) == s->board[j]) continue;
698 /* for each square j _in_ the connected component */
701 printv(" looking at (%d, %d)\n", j % w, j / w);
703 /* for each neighbouring square (idx) */
704 for (k = 0; k < 4; ++k) {
705 const int x = (j % w) + dx[k];
706 const int y = (j / w) + dy[k];
707 const int idx = w*y + x;
712 if (x < 0 || x >= w || y < 0 || y >= h) continue;
713 if (s->board[idx] != EMPTY) continue;
714 if (exp == idx) continue;
715 printv("\ttrying to expand onto (%d, %d)\n", x, y);
717 /* find out the would-be size of the new connected
718 * component if we actually expanded into idx */
721 for (l = 0; l < 4; ++l) {
722 const int lx = x + dx[l];
723 const int ly = y + dy[l];
724 const int idxl = w*ly + lx;
727 if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
728 if (board[idxl] != board[j]) continue;
729 root = dsf_canonify(dsf, idxl);
730 for (m = 0; m < nhits && root != hits[m]; ++m);
731 if (m != nhits) continue;
732 // printv("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);
733 size += dsf_size(dsf, root);
734 assert(dsf_size(dsf, root) >= 1);
735 hits[nhits++] = root;
739 size = expandsize(s->board, s->dsf, w, h, idx, s->board[j]);
741 /* ... and see if that size is too big, or if we
742 * have other expansion candidates. Otherwise
743 * remember the (so far) only candidate. */
745 printv("\tthat would give a size of %d\n", size);
746 if (size > s->board[j]) continue;
747 /* printv("\tnow knowing %d expansions\n", nexpand + 1); */
748 if (exp != SENTINEL) goto next_i;
753 j = s->connected[j]; /* next square in the same CC */
754 assert(s->board[i] == s->board[j]);
756 /* end: for each square j _in_ the connected component */
758 if (exp == SENTINEL) continue;
759 printv("learning to expand\n");
760 expand(s, w, h, exp, i);
766 /* end: for each connected component */
770 static int learn_critical_square(struct solver_state *s, int w, int h) {
771 const int sz = w * h;
776 /* for each connected component */
777 for (i = 0; i < sz; ++i) {
779 if (s->board[i] == EMPTY) continue;
780 if (i != dsf_canonify(s->dsf, i)) continue;
781 slack = s->board[i] - dsf_size(s->dsf, i);
782 if (slack == 0) continue;
783 assert(s->board[i] != 1);
784 /* for each empty square */
785 for (j = 0; j < sz; ++j) {
786 if (s->board[j] == EMPTY) {
787 /* if it's too far away from the CC, don't bother */
788 int k = i, jx = j % w, jy = j / w;
790 int kx = k % w, ky = k / w;
791 if (abs(kx - jx) + abs(ky - jy) <= slack) break;
794 if (i == k) continue; /* not within range */
796 s->board[j] = -SENTINEL;
797 if (check_capacity(s->board, w, h, i)) continue;
798 /* if not expanding s->board[i] to s->board[j] implies
799 * that s->board[i] can't reach its full size, ... */
802 "learn: ds %d at (%d, %d) blocking (%d, %d)\n",
803 s->board[i], j % w, j / w, i % w, i / w);
805 s->board[j] = s->board[i];
806 filled_square(s, w, h, j);
814 static void print_bitmap(int *bitmap, int w, int h) {
817 for (y = 0; y < h; y++) {
818 for (x = 0; x < w; x++) {
819 printv(" %03x", bm[y*w+x]);
827 static int learn_bitmap_deductions(struct solver_state *s, int w, int h)
829 const int sz = w * h;
832 int *minsize = s->bmminsize;
837 * This function does deductions based on building up a bitmap
838 * which indicates the possible numbers that can appear in each
839 * grid square. If we can rule out all but one possibility for a
840 * particular square, then we've found out the value of that
841 * square. In particular, this is one of the few forms of
842 * deduction capable of inferring the existence of a 'ghost
843 * region', i.e. a region which has none of its squares filled in
846 * The reasoning goes like this. A currently unfilled square S can
847 * turn out to contain digit n in exactly two ways: either S is
848 * part of an n-region which also includes some currently known
849 * connected component of squares with n in, or S is part of an
850 * n-region separate from _all_ currently known connected
851 * components. If we can rule out both possibilities, then square
852 * S can't contain digit n at all.
854 * The former possibility: if there's a region of size n
855 * containing both S and some existing component C, then that
856 * means the distance from S to C must be small enough that C
857 * could be extended to include S without becoming too big. So we
858 * can do a breadth-first search out from all existing components
859 * with n in them, to identify all the squares which could be
860 * joined to any of them.
862 * The latter possibility: if there's a region of size n that
863 * doesn't contain _any_ existing component, then it also can't
864 * contain any square adjacent to an existing component either. So
865 * we can identify all the EMPTY squares not adjacent to any
866 * existing square with n in, and group them into connected
867 * components; then any component of size less than n is ruled
868 * out, because there wouldn't be room to create a completely new
871 * In fact we process these possibilities in the other order.
872 * First we find all the squares not adjacent to an existing
873 * square with n in; then we winnow those by removing too-small
874 * connected components, to get the set of squares which could
875 * possibly be part of a brand new n-region; and finally we do the
876 * breadth-first search to add in the set of squares which could
877 * possibly be added to some existing n-region.
881 * Start by initialising our bitmap to 'all numbers possible in
884 for (y = 0; y < h; y++)
885 for (x = 0; x < w; x++)
886 bm[y*w+x] = (1 << 10) - (1 << 1); /* bits 1,2,...,9 now set */
888 printv("initial bitmap:\n");
889 print_bitmap(bm, w, h);
893 * Now completely zero out the bitmap for squares that are already
894 * filled in (we aren't interested in those anyway). Also, for any
895 * filled square, eliminate its number from all its neighbours
896 * (because, as discussed above, the neighbours couldn't be part
897 * of a _new_ region with that number in it, and that's the case
898 * we consider first).
900 for (y = 0; y < h; y++) {
901 for (x = 0; x < w; x++) {
909 bm[i-1] &= ~(1 << n);
911 bm[i+1] &= ~(1 << n);
913 bm[i-w] &= ~(1 << n);
915 bm[i+w] &= ~(1 << n);
920 printv("bitmap after filled squares:\n");
921 print_bitmap(bm, w, h);
925 * Now, for each n, we separately find the connected components of
926 * squares for which n is still a possibility. Then discard any
927 * component of size < n, because that component is too small to
928 * have a completely new n-region in it.
930 for (n = 1; n <= 9; n++) {
934 for (y = 0; y < h; y++)
935 for (x = 0; x+1 < w; x++)
936 if (bm[y*w+x] & bm[y*w+(x+1)] & (1 << n))
937 dsf_merge(dsf, y*w+x, y*w+(x+1));
938 for (y = 0; y+1 < h; y++)
939 for (x = 0; x < w; x++)
940 if (bm[y*w+x] & bm[(y+1)*w+x] & (1 << n))
941 dsf_merge(dsf, y*w+x, (y+1)*w+x);
944 for (i = 0; i < sz; i++)
945 if ((bm[i] & (1 << n)) && dsf_size(dsf, i) < n)
949 printv("bitmap after winnowing small components:\n");
950 print_bitmap(bm, w, h);
954 * Now our bitmap includes every square which could be part of a
955 * completely new region, of any size. Extend it to include
956 * squares which could be part of an existing region.
958 for (n = 1; n <= 9; n++) {
960 * We're going to do a breadth-first search starting from
961 * existing connected components with cell value n, to find
962 * all cells they might possibly extend into.
964 * The quantity we compute, for each square, is 'minimum size
965 * that any existing CC would have to have if extended to
966 * include this square'. So squares already _in_ an existing
967 * CC are initialised to the size of that CC; then we search
968 * outwards using the rule that if a square's score is j, then
969 * its neighbours can't score more than j+1.
971 * Scores are capped at n+1, because if a square scores more
972 * than n then that's enough to know it can't possibly be
973 * reached by extending an existing region - we don't need to
974 * know exactly _how far_ out of reach it is.
976 for (i = 0; i < sz; i++) {
977 if (s->board[i] == n) {
978 /* Square is part of an existing CC. */
979 minsize[i] = dsf_size(s->dsf, i);
981 /* Otherwise, initialise to the maximum score n+1;
982 * we'll reduce this later if we find a neighbouring
983 * square with a lower score. */
988 for (j = 1; j < n; j++) {
990 * Find neighbours of cells scoring j, and set their score
993 * Doing the BFS this way means we need n passes over the
994 * grid, which isn't entirely optimal but it seems to be
995 * fast enough for the moment. This could probably be
996 * improved by keeping a linked-list queue of cells in
997 * some way, but I think you'd have to be a bit careful to
998 * insert things into the right place in the queue; this
999 * way is easier not to get wrong.
1001 for (y = 0; y < h; y++) {
1002 for (x = 0; x < w; x++) {
1004 if (minsize[i] == j) {
1005 if (x > 0 && minsize[i-1] > j+1)
1007 if (x+1 < w && minsize[i+1] > j+1)
1009 if (y > 0 && minsize[i-w] > j+1)
1011 if (y+1 < h && minsize[i+w] > j+1)
1019 * Now, every cell scoring at most n should have its 1<<n bit
1020 * in the bitmap reinstated, because we've found that it's
1021 * potentially reachable by extending an existing CC.
1023 for (i = 0; i < sz; i++)
1024 if (minsize[i] <= n)
1028 printv("bitmap after bfs:\n");
1029 print_bitmap(bm, w, h);
1033 * Now our bitmap is complete. Look for entries with only one bit
1034 * set; those are squares with only one possible number, in which
1035 * case we can fill that number in.
1037 for (i = 0; i < sz; i++) {
1038 if (bm[i] && !(bm[i] & (bm[i]-1))) { /* is bm[i] a power of two? */
1041 /* Integer log2, by simple binary search. */
1043 if (val >> 8) { val >>= 8; n += 8; }
1044 if (val >> 4) { val >>= 4; n += 4; }
1045 if (val >> 2) { val >>= 2; n += 2; }
1046 if (val >> 1) { val >>= 1; n += 1; }
1048 /* Double-check that we ended up with a sensible
1052 assert(bm[i] == (1 << n));
1054 if (s->board[i] == EMPTY) {
1055 printv("learn: %d is only possibility at (%d, %d)\n",
1058 filled_square(s, w, h, i);
1069 static int solver(const int *orig, int w, int h, char **solution) {
1070 const int sz = w * h;
1072 struct solver_state ss;
1073 ss.board = memdup(orig, sz, sizeof (int));
1074 ss.dsf = snew_dsf(sz); /* eqv classes: connected components */
1075 ss.connected = snewn(sz, int); /* connected[n] := n.next; */
1076 /* cyclic disjoint singly linked lists, same partitioning as dsf.
1077 * The lists lets you iterate over a partition given any member */
1078 ss.bm = snewn(sz, int);
1079 ss.bmdsf = snew_dsf(sz);
1080 ss.bmminsize = snewn(sz, int);
1082 printv("trying to solve this:\n");
1083 print_board(ss.board, w, h);
1085 init_solver_state(&ss, w, h);
1087 if (learn_blocked_expansion(&ss, w, h)) continue;
1088 if (learn_expand_or_one(&ss, w, h)) continue;
1089 if (learn_critical_square(&ss, w, h)) continue;
1090 if (learn_bitmap_deductions(&ss, w, h)) continue;
1092 } while (ss.nempty);
1094 printv("best guess:\n");
1095 print_board(ss.board, w, h);
1099 *solution = snewn(sz + 2, char);
1101 for (i = 0; i < sz; ++i) (*solution)[i + 1] = ss.board[i] + '0';
1102 (*solution)[sz + 1] = '\0';
1103 /* We don't need the \0 for execute_move (the only user)
1104 * I'm just being printf-friendly in case I wanna print */
1109 sfree(ss.connected);
1112 sfree(ss.bmminsize);
1117 static int *make_dsf(int *dsf, int *board, const int w, const int h) {
1118 const int sz = w * h;
1122 dsf = snew_dsf(w * h);
1124 dsf_init(dsf, w * h);
1126 for (i = 0; i < sz; ++i) {
1128 for (j = 0; j < 4; ++j) {
1129 const int x = (i % w) + dx[j];
1130 const int y = (i / w) + dy[j];
1131 const int k = w*y + x;
1132 if (x < 0 || x >= w || y < 0 || y >= h) continue;
1133 if (board[i] == board[k]) dsf_merge(dsf, i, k);
1139 static void minimize_clue_set(int *board, int w, int h, random_state *rs)
1141 const int sz = w * h;
1142 int *shuf = snewn(sz, int), i;
1145 for (i = 0; i < sz; ++i) shuf[i] = i;
1146 shuffle(shuf, sz, sizeof (int), rs);
1149 * First, try to eliminate an entire region at a time if possible,
1150 * because inferring the existence of a completely unclued region
1151 * is a particularly good aspect of this puzzle type and we want
1152 * to encourage it to happen.
1154 * Begin by identifying the regions as linked lists of cells using
1157 dsf = make_dsf(NULL, board, w, h);
1158 next = snewn(sz, int);
1159 for (i = 0; i < sz; ++i) {
1160 int j = dsf_canonify(dsf, i);
1162 /* First cell of a region; set next[i] = -1 to indicate
1166 /* Add this cell to a region which already has a
1167 * linked-list head, by pointing the canonical element j
1168 * at this one, and pointing this one in turn at wherever
1169 * j previously pointed. (This should end up with the
1170 * elements linked in the order 1,n,n-1,n-2,...,2, which
1171 * is a bit weird-looking, but any order is fine.)
1180 * Now loop over the grid cells in our shuffled order, and each
1181 * time we encounter a region for the first time, try to remove it
1182 * all. Then we set next[canonical index] to -2 rather than -1, to
1183 * mark it as already tried.
1185 * Doing this in a loop over _cells_, rather than extracting and
1186 * shuffling a list of _regions_, is intended to skew the
1187 * probabilities towards trying to remove larger regions first
1188 * (but without anything as crudely predictable as enforcing that
1189 * we _always_ process regions in descending size order). Region
1190 * removals might well be mutually exclusive, and larger ghost
1191 * regions are more interesting, so we want to bias towards them
1194 for (i = 0; i < sz; ++i) {
1195 int j = dsf_canonify(dsf, shuf[i]);
1196 if (next[j] != -2) {
1200 /* Blank out the whole thing. */
1201 for (k = j; k >= 0; k = next[k])
1204 if (!solver(board, w, h, NULL)) {
1205 /* Wasn't still solvable; reinstate it all */
1206 for (k = j; k >= 0; k = next[k])
1210 /* Either way, don't try this region again. */
1218 * Now go through individual cells, in the same shuffled order,
1219 * and try to remove each one by itself.
1221 for (i = 0; i < sz; ++i) {
1222 int tmp = board[shuf[i]];
1223 board[shuf[i]] = EMPTY;
1224 if (!solver(board, w, h, NULL)) board[shuf[i]] = tmp;
1230 static int encode_run(char *buffer, int run)
1233 for (; run > 26; run -= 26)
1236 buffer[i++] = 'a' - 1 + run;
1240 static char *new_game_desc(const game_params *params, random_state *rs,
1241 char **aux, int interactive)
1243 const int w = params->w, h = params->h, sz = w * h;
1244 int *board = snewn(sz, int), i, j, run;
1245 char *description = snewn(sz + 1, char);
1247 make_board(board, w, h, rs);
1248 minimize_clue_set(board, w, h, rs);
1250 for (run = j = i = 0; i < sz; ++i) {
1251 assert(board[i] >= 0);
1252 assert(board[i] < 10);
1253 if (board[i] == 0) {
1256 j += encode_run(description + j, run);
1258 description[j++] = board[i] + '0';
1261 j += encode_run(description + j, run);
1262 description[j++] = '\0';
1266 return sresize(description, j, char);
1269 static const char *validate_desc(const game_params *params, const char *desc)
1271 const int sz = params->w * params->h;
1272 const char m = '0' + max(max(params->w, params->h), 3);
1275 for (area = 0; *desc; ++desc) {
1276 if (*desc >= 'a' && *desc <= 'z') area += *desc - 'a' + 1;
1277 else if (*desc >= '0' && *desc <= m) ++area;
1279 static char s[] = "Invalid character '%""' in game description";
1280 int n = sprintf(s, "Invalid character '%1c' in game description",
1282 assert(n + 1 <= lenof(s)); /* +1 for the terminating NUL */
1285 if (area > sz) return "Too much data to fit in grid";
1287 return (area < sz) ? "Not enough data to fill grid" : NULL;
1290 static game_state *new_game(midend *me, const game_params *params,
1293 game_state *state = snew(game_state);
1294 int sz = params->w * params->h;
1297 state->cheated = state->completed = FALSE;
1298 state->shared = snew(struct shared_state);
1299 state->shared->refcnt = 1;
1300 state->shared->params = *params; /* struct copy */
1301 state->shared->clues = snewn(sz, int);
1303 for (i = 0; *desc; ++desc) {
1304 if (*desc >= 'a' && *desc <= 'z') {
1305 int j = *desc - 'a' + 1;
1306 assert(i + j <= sz);
1307 for (; j; --j) state->shared->clues[i++] = 0;
1308 } else state->shared->clues[i++] = *desc - '0';
1310 state->board = memdup(state->shared->clues, sz, sizeof (int));
1315 static game_state *dup_game(const game_state *state)
1317 const int sz = state->shared->params.w * state->shared->params.h;
1318 game_state *ret = snew(game_state);
1320 ret->board = memdup(state->board, sz, sizeof (int));
1321 ret->shared = state->shared;
1322 ret->cheated = state->cheated;
1323 ret->completed = state->completed;
1324 ++ret->shared->refcnt;
1329 static void free_game(game_state *state)
1332 sfree(state->board);
1333 if (--state->shared->refcnt == 0) {
1334 sfree(state->shared->clues);
1335 sfree(state->shared);
1340 static char *solve_game(const game_state *state, const game_state *currstate,
1341 const char *aux, const char **error)
1344 const int w = state->shared->params.w;
1345 const int h = state->shared->params.h;
1347 if (!solver(state->board, w, h, &new_aux))
1348 *error = "Sorry, I couldn't find a solution";
1354 /*****************************************************************************
1355 * USER INTERFACE STATE AND ACTION *
1356 *****************************************************************************/
1359 int *sel; /* w*h highlighted squares, or NULL */
1360 int cur_x, cur_y, cur_visible, keydragging;
1363 static game_ui *new_ui(const game_state *state)
1365 game_ui *ui = snew(game_ui);
1368 ui->cur_x = ui->cur_y = ui->cur_visible = ui->keydragging = 0;
1373 static void free_ui(game_ui *ui)
1380 static char *encode_ui(const game_ui *ui)
1385 static void decode_ui(game_ui *ui, const char *encoding)
1389 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1390 const game_state *newstate)
1392 /* Clear any selection */
1397 ui->keydragging = FALSE;
1400 #define PREFERRED_TILE_SIZE 32
1401 #define TILE_SIZE (ds->tilesize)
1402 #define BORDER (TILE_SIZE / 2)
1403 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1405 struct game_drawstate {
1406 struct game_params params;
1410 int *dsf_scratch, *border_scratch;
1413 static char *interpret_move(const game_state *state, game_ui *ui,
1414 const game_drawstate *ds,
1415 int x, int y, int button)
1417 const int w = state->shared->params.w;
1418 const int h = state->shared->params.h;
1420 const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1421 const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1429 button &= ~MOD_MASK;
1431 if (button == LEFT_BUTTON || button == LEFT_DRAG) {
1432 /* A left-click anywhere will clear the current selection. */
1433 if (button == LEFT_BUTTON) {
1439 if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
1441 ui->sel = snewn(w*h, int);
1442 memset(ui->sel, 0, w*h*sizeof(int));
1444 if (!state->shared->clues[w*ty+tx])
1445 ui->sel[w*ty+tx] = 1;
1447 ui->cur_visible = 0;
1451 if (IS_CURSOR_MOVE(button)) {
1452 ui->cur_visible = 1;
1453 move_cursor(button, &ui->cur_x, &ui->cur_y, w, h, 0);
1454 if (ui->keydragging) goto select_square;
1457 if (button == CURSOR_SELECT) {
1458 if (!ui->cur_visible) {
1459 ui->cur_visible = 1;
1462 ui->keydragging = !ui->keydragging;
1463 if (!ui->keydragging) return UI_UPDATE;
1467 ui->sel = snewn(w*h, int);
1468 memset(ui->sel, 0, w*h*sizeof(int));
1470 if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
1471 ui->sel[w*ui->cur_y + ui->cur_x] = 1;
1474 if (button == CURSOR_SELECT2) {
1475 if (!ui->cur_visible) {
1476 ui->cur_visible = 1;
1480 ui->sel = snewn(w*h, int);
1481 memset(ui->sel, 0, w*h*sizeof(int));
1483 ui->keydragging = FALSE;
1484 if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
1485 ui->sel[w*ui->cur_y + ui->cur_x] ^= 1;
1486 for (i = 0; i < w*h && !ui->sel[i]; i++);
1494 if (button == '\b' || button == 27) {
1497 ui->keydragging = FALSE;
1501 if (button < '0' || button > '9') return NULL;
1503 if (button > (w == 2 && h == 2 ? 3 : max(w, h))) return NULL;
1504 ui->keydragging = FALSE;
1506 for (i = 0; i < w*h; i++) {
1508 if ((ui->sel && ui->sel[i]) ||
1509 (!ui->sel && ui->cur_visible && (w*ui->cur_y+ui->cur_x) == i)) {
1510 if (state->shared->clues[i] != 0) continue; /* in case cursor is on clue */
1511 if (state->board[i] != button) {
1512 sprintf(buf, "%s%d", move ? "," : "", i);
1514 move = srealloc(move, strlen(move)+strlen(buf)+1);
1517 move = smalloc(strlen(buf)+1);
1525 sprintf(buf, "_%d", button);
1526 move = srealloc(move, strlen(move)+strlen(buf)+1);
1529 if (!ui->sel) return move ? move : NULL;
1532 /* Need to update UI at least, as we cleared the selection */
1533 return move ? move : UI_UPDATE;
1536 static game_state *execute_move(const game_state *state, const char *move)
1538 game_state *new_state = NULL;
1539 const int sz = state->shared->params.w * state->shared->params.h;
1543 new_state = dup_game(state);
1544 for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0';
1545 new_state->cheated = TRUE;
1548 char *endptr, *delim = strchr(move, '_');
1549 if (!delim) goto err;
1550 value = strtol(delim+1, &endptr, 0);
1551 if (*endptr || endptr == delim+1) goto err;
1552 if (value < 0 || value > 9) goto err;
1553 new_state = dup_game(state);
1555 const int i = strtol(move, &endptr, 0);
1556 if (endptr == move) goto err;
1557 if (i < 0 || i >= sz) goto err;
1558 new_state->board[i] = value;
1559 if (*endptr == '_') break;
1560 if (*endptr != ',') goto err;
1566 * Check for completion.
1568 if (!new_state->completed) {
1569 const int w = new_state->shared->params.w;
1570 const int h = new_state->shared->params.h;
1571 const int sz = w * h;
1572 int *dsf = make_dsf(NULL, new_state->board, w, h);
1574 for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i);
1577 new_state->completed = TRUE;
1583 if (new_state) free_game(new_state);
1587 /* ----------------------------------------------------------------------
1591 #define FLASH_TIME 0.4F
1593 #define COL_CLUE COL_GRID
1605 static void game_compute_size(const game_params *params, int tilesize,
1608 *x = (params->w + 1) * tilesize;
1609 *y = (params->h + 1) * tilesize;
1612 static void game_set_size(drawing *dr, game_drawstate *ds,
1613 const game_params *params, int tilesize)
1615 ds->tilesize = tilesize;
1618 static float *game_colours(frontend *fe, int *ncolours)
1620 float *ret = snewn(3 * NCOLOURS, float);
1622 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1624 ret[COL_GRID * 3 + 0] = 0.0F;
1625 ret[COL_GRID * 3 + 1] = 0.0F;
1626 ret[COL_GRID * 3 + 2] = 0.0F;
1628 ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
1629 ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1630 ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1632 ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0];
1633 ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1];
1634 ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2];
1636 ret[COL_CURSOR * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1637 ret[COL_CURSOR * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1638 ret[COL_CURSOR * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
1640 ret[COL_ERROR * 3 + 0] = 1.0F;
1641 ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1642 ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1644 ret[COL_USER * 3 + 0] = 0.0F;
1645 ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1646 ret[COL_USER * 3 + 2] = 0.0F;
1648 *ncolours = NCOLOURS;
1652 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1654 struct game_drawstate *ds = snew(struct game_drawstate);
1657 ds->tilesize = PREFERRED_TILE_SIZE;
1659 ds->params = state->shared->params;
1660 ds->v = snewn(ds->params.w * ds->params.h, int);
1661 ds->flags = snewn(ds->params.w * ds->params.h, int);
1662 for (i = 0; i < ds->params.w * ds->params.h; i++)
1663 ds->v[i] = ds->flags[i] = -1;
1664 ds->border_scratch = snewn(ds->params.w * ds->params.h, int);
1665 ds->dsf_scratch = NULL;
1670 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1674 sfree(ds->border_scratch);
1675 sfree(ds->dsf_scratch);
1679 #define BORDER_U 0x001
1680 #define BORDER_D 0x002
1681 #define BORDER_L 0x004
1682 #define BORDER_R 0x008
1683 #define BORDER_UR 0x010
1684 #define BORDER_DR 0x020
1685 #define BORDER_UL 0x040
1686 #define BORDER_DL 0x080
1687 #define HIGH_BG 0x100
1688 #define CORRECT_BG 0x200
1689 #define ERROR_BG 0x400
1690 #define USER_COL 0x800
1691 #define CURSOR_SQ 0x1000
1693 static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
1700 * Clip to the grid square.
1702 clip(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1703 TILE_SIZE, TILE_SIZE);
1709 BORDER + x*TILE_SIZE,
1710 BORDER + y*TILE_SIZE,
1713 (flags & HIGH_BG ? COL_HIGHLIGHT :
1714 flags & ERROR_BG ? COL_ERROR :
1715 flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
1718 * Draw the grid lines.
1720 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1721 BORDER + (x+1)*TILE_SIZE, BORDER + y*TILE_SIZE, COL_GRID);
1722 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1723 BORDER + x*TILE_SIZE, BORDER + (y+1)*TILE_SIZE, COL_GRID);
1733 (x + 1) * TILE_SIZE,
1734 (y + 1) * TILE_SIZE,
1737 ALIGN_VCENTRE | ALIGN_HCENTRE,
1738 flags & USER_COL ? COL_USER : COL_CLUE,
1743 * Draw bold lines around the borders.
1745 if (flags & BORDER_L)
1747 BORDER + x*TILE_SIZE + 1,
1748 BORDER + y*TILE_SIZE + 1,
1752 if (flags & BORDER_U)
1754 BORDER + x*TILE_SIZE + 1,
1755 BORDER + y*TILE_SIZE + 1,
1759 if (flags & BORDER_R)
1761 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1762 BORDER + y*TILE_SIZE + 1,
1766 if (flags & BORDER_D)
1768 BORDER + x*TILE_SIZE + 1,
1769 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1773 if (flags & BORDER_UL)
1775 BORDER + x*TILE_SIZE + 1,
1776 BORDER + y*TILE_SIZE + 1,
1780 if (flags & BORDER_UR)
1782 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1783 BORDER + y*TILE_SIZE + 1,
1787 if (flags & BORDER_DL)
1789 BORDER + x*TILE_SIZE + 1,
1790 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1794 if (flags & BORDER_DR)
1796 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1797 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1802 if (flags & CURSOR_SQ) {
1803 int coff = TILE_SIZE/8;
1804 draw_rect_outline(dr,
1805 BORDER + x*TILE_SIZE + coff,
1806 BORDER + y*TILE_SIZE + coff,
1815 BORDER + x*TILE_SIZE,
1816 BORDER + y*TILE_SIZE,
1821 static void draw_grid(drawing *dr, game_drawstate *ds, const game_state *state,
1822 const game_ui *ui, int flashy, int borders, int shading)
1824 const int w = state->shared->params.w;
1825 const int h = state->shared->params.h;
1830 * Build a dsf for the board in its current state, to use for
1831 * highlights and hints.
1833 ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h);
1836 * Work out where we're putting borders between the cells.
1838 for (y = 0; y < w*h; y++)
1839 ds->border_scratch[y] = 0;
1841 for (y = 0; y < h; y++)
1842 for (x = 0; x < w; x++) {
1846 for (dx = 0; dx <= 1; dx++) {
1851 if (x+dx >= w || y+dy >= h)
1854 v1 = state->board[y*w+x];
1855 v2 = state->board[(y+dy)*w+(x+dx)];
1856 s1 = dsf_size(ds->dsf_scratch, y*w+x);
1857 s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx));
1860 * We only ever draw a border between two cells if
1861 * they don't have the same contents.
1865 * But in that situation, we don't always draw
1866 * a border. We do if the two cells both
1867 * contain actual numbers...
1873 * ... or if at least one of them is a
1874 * completed or overfull omino.
1883 ds->border_scratch[y*w+x] |= (dx ? 1 : 2);
1888 * Actually do the drawing.
1890 for (y = 0; y < h; ++y)
1891 for (x = 0; x < w; ++x) {
1893 * Determine what we need to draw in this square.
1895 int i = y*w+x, v = state->board[i];
1898 if (flashy || !shading) {
1899 /* clear all background flags */
1900 } else if (ui && ui->sel && ui->sel[i]) {
1903 int size = dsf_size(ds->dsf_scratch, i);
1905 flags |= CORRECT_BG;
1909 int rt = dsf_canonify(ds->dsf_scratch, i), j;
1910 for (j = 0; j < w*h; ++j) {
1912 if (dsf_canonify(ds->dsf_scratch, j) != rt) continue;
1913 for (k = 0; k < 4; ++k) {
1914 const int xx = j % w + dx[k], yy = j / w + dy[k];
1915 if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
1916 state->board[yy*w + xx] == EMPTY)
1925 if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
1929 * Borders at the very edges of the grid are
1930 * independent of the `borders' flag.
1942 if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1))
1944 if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2))
1946 if (x == w-1 || (ds->border_scratch[y*w+x] & 1))
1948 if (y == h-1 || (ds->border_scratch[y*w+x] & 2))
1951 if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)]))
1953 if (y > 0 && x < w-1 &&
1954 ((ds->border_scratch[(y-1)*w+x] & 1) ||
1955 (ds->border_scratch[(y-1)*w+(x+1)] & 2)))
1957 if (y < h-1 && x > 0 &&
1958 ((ds->border_scratch[y*w+(x-1)] & 2) ||
1959 (ds->border_scratch[(y+1)*w+(x-1)] & 1)))
1961 if (y < h-1 && x < w-1 &&
1962 ((ds->border_scratch[y*w+(x+1)] & 2) ||
1963 (ds->border_scratch[(y+1)*w+x] & 1)))
1967 if (!state->shared->clues[y*w+x])
1970 if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) {
1971 draw_square(dr, ds, x, y, v, flags);
1973 ds->flags[y*w+x] = flags;
1978 static void game_redraw(drawing *dr, game_drawstate *ds,
1979 const game_state *oldstate, const game_state *state,
1980 int dir, const game_ui *ui,
1981 float animtime, float flashtime)
1983 const int w = state->shared->params.w;
1984 const int h = state->shared->params.h;
1988 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3);
1992 * The initial contents of the window are not guaranteed and
1993 * can vary with front ends. To be on the safe side, all games
1994 * should start by drawing a big background-colour rectangle
1995 * covering the whole window.
1997 draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
2001 * Smaller black rectangle which is the main grid.
2003 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
2004 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
2005 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
2008 draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
2013 draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE);
2016 static float game_anim_length(const game_state *oldstate,
2017 const game_state *newstate, int dir, game_ui *ui)
2022 static float game_flash_length(const game_state *oldstate,
2023 const game_state *newstate, int dir, game_ui *ui)
2027 assert(newstate->shared);
2028 assert(oldstate->shared == newstate->shared);
2029 if (!oldstate->completed && newstate->completed &&
2030 !oldstate->cheated && !newstate->cheated)
2035 static int game_status(const game_state *state)
2037 return state->completed ? +1 : 0;
2040 static int game_timing_state(const game_state *state, game_ui *ui)
2045 static void game_print_size(const game_params *params, float *x, float *y)
2050 * I'll use 6mm squares by default.
2052 game_compute_size(params, 600, &pw, &ph);
2057 static void game_print(drawing *dr, const game_state *state, int tilesize)
2059 const int w = state->shared->params.w;
2060 const int h = state->shared->params.h;
2063 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2064 game_drawstate *ds = game_new_drawstate(dr, state);
2065 game_set_size(dr, ds, NULL, tilesize);
2067 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
2068 c = print_mono_colour(dr, 0); assert(c == COL_GRID);
2069 c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT);
2070 c = print_mono_colour(dr, 1); assert(c == COL_CORRECT);
2071 c = print_mono_colour(dr, 1); assert(c == COL_ERROR);
2072 c = print_mono_colour(dr, 0); assert(c == COL_USER);
2077 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
2078 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
2079 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
2083 * We'll draw borders between the ominoes iff the grid is not
2084 * pristine. So scan it to see if it is.
2087 for (i = 0; i < w*h; i++)
2088 if (state->board[i] && !state->shared->clues[i])
2094 print_line_width(dr, TILE_SIZE / 64);
2095 draw_grid(dr, ds, state, NULL, FALSE, borders, FALSE);
2100 game_free_drawstate(dr, ds);
2104 #define thegame filling
2107 const struct game thegame = {
2108 "Filling", "games.filling", "filling",
2110 game_fetch_preset, NULL,
2115 TRUE, game_configure, custom_params,
2123 TRUE, game_can_format_as_text_now, game_text_format,
2131 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2134 game_free_drawstate,
2139 TRUE, FALSE, game_print_size, game_print,
2140 FALSE, /* wants_statusbar */
2141 FALSE, game_timing_state,
2142 REQUIRE_NUMPAD, /* flags */
2145 #ifdef STANDALONE_SOLVER /* solver? hah! */
2147 int main(int argc, char **argv) {
2149 game_params *params;
2154 for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc);
2155 if (*desc == '\0') {
2156 fprintf(stderr, "bad puzzle id: %s", par);
2162 params = snew(game_params);
2163 decode_params(params, par);
2164 state = new_game(NULL, params, desc);
2165 if (solver(state->board, params->w, params->h, NULL))
2166 printf("%s:%s: solvable\n", par, desc);
2168 printf("%s:%s: not solvable\n", par, desc);
2175 /* vim: set shiftwidth=4 tabstop=8: */