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 char?)
10 * - the type should be signed (I use -board[i] temporarily)
11 * - problems are small (<= 9?): type can be char?
13 * - make a somewhat more clever solver
15 * - make the solver do recursion/backtracking.
16 * + This is for user-submitted puzzles, not for puzzle
17 * generation (on the other hand, never say never).
19 * - prove that only w=h=2 needs a special case
21 * - solo-like pencil marks?
23 * - speed up generation of puzzles of size >= 11x11
25 * - Allow square contents > 9?
26 * + I could use letters for digits (solo does this), but
27 * letters don't have numeric significance (normal people hate
28 * base36), which is relevant here (much more than in solo).
29 * + How much information is needed to solve? Does one need to
30 * know the algorithm by which the largest number is set?
32 * - eliminate puzzle instances with done chunks (1's in particular)?
33 * + that's what the qsort call is all about.
34 * + the 1's don't bother me that much.
35 * + but this takes a LONG time (not always possible)?
36 * - this may be affected by solver (lack of) quality.
37 * - weed them out by construction instead of post-cons check
38 * + but that interleaves make_board and new_game_desc: you
39 * have to alternate between changing the board and
40 * changing the hint set (instead of just creating the
41 * board once, then changing the hint set once -> done).
43 * - use binary search when discovering the minimal sovable point
44 * + profile to show a need (but when the solver gets slower...)
45 * + avg 0.1s per 9x9, which _is_ human-patience noticable.
62 struct game_params params;
69 struct shared_state *shared;
70 int completed, cheated;
73 static const struct game_params defaults[3] = {{5, 5}, {7, 7}, {9, 9}};
75 static game_params *default_params(void)
77 game_params *ret = snew(game_params);
79 *ret = defaults[1]; /* struct copy */
84 static int game_fetch_preset(int i, char **name, game_params **params)
88 if (i < 0 || i >= lenof(defaults)) return FALSE;
89 *params = snew(game_params);
90 **params = defaults[i]; /* struct copy */
91 sprintf(buf, "%dx%d", defaults[i].w, defaults[i].h);
97 static void free_params(game_params *params)
102 static game_params *dup_params(game_params *params)
104 game_params *ret = snew(game_params);
105 *ret = *params; /* struct copy */
109 static void decode_params(game_params *ret, char const *string)
111 ret->w = ret->h = atoi(string);
112 while (*string && isdigit((unsigned char) *string)) ++string;
113 if (*string == 'x') ret->h = atoi(++string);
116 static char *encode_params(game_params *params, int full)
119 sprintf(buf, "%dx%d", params->w, params->h);
123 static config_item *game_configure(game_params *params)
128 ret = snewn(3, config_item);
130 ret[0].name = "Width";
131 ret[0].type = C_STRING;
132 sprintf(buf, "%d", params->w);
133 ret[0].sval = dupstr(buf);
136 ret[1].name = "Height";
137 ret[1].type = C_STRING;
138 sprintf(buf, "%d", params->h);
139 ret[1].sval = dupstr(buf);
150 static game_params *custom_params(config_item *cfg)
152 game_params *ret = snew(game_params);
154 ret->w = atoi(cfg[0].sval);
155 ret->h = atoi(cfg[1].sval);
160 static char *validate_params(game_params *params, int full)
162 if (params->w < 1) return "Width must be at least one";
163 if (params->h < 1) return "Height must be at least one";
168 /*****************************************************************************
169 * STRINGIFICATION OF GAME STATE *
170 *****************************************************************************/
174 /* Example of plaintext rendering:
175 * +---+---+---+---+---+---+---+
176 * | 6 | | | 2 | | | 2 |
177 * +---+---+---+---+---+---+---+
178 * | | 3 | | 6 | | 3 | |
179 * +---+---+---+---+---+---+---+
180 * | 3 | | | | | | 1 |
181 * +---+---+---+---+---+---+---+
182 * | | 2 | 3 | | 4 | 2 | |
183 * +---+---+---+---+---+---+---+
184 * | 2 | | | | | | 3 |
185 * +---+---+---+---+---+---+---+
186 * | | 5 | | 1 | | 4 | |
187 * +---+---+---+---+---+---+---+
188 * | 4 | | | 3 | | | 3 |
189 * +---+---+---+---+---+---+---+
191 * This puzzle instance is taken from the nikoli website
192 * Encoded (unsolved and solved), the strings are these:
193 * 7x7:6002002030603030000010230420200000305010404003003
194 * 7x7:6662232336663232331311235422255544325413434443313
196 static char *board_to_string(int *board, int w, int h) {
197 const int sz = w * h;
198 const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */
199 const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */
200 const int chlen = chw * chh;
201 char *repr = snewn(chlen + 1, char);
206 /* build the first line ("^(\+---){n}\+$") */
207 for (i = 0; i < w; ++i) {
214 repr[4*i + 1] = '\n';
216 /* ... and copy it onto the odd-numbered lines */
217 for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw);
219 /* build the second line ("^(\|\t){n}\|$") */
220 for (i = 0; i < w; ++i) {
221 repr[chw + 4*i + 0] = '|';
222 repr[chw + 4*i + 1] = ' ';
223 repr[chw + 4*i + 2] = ' ';
224 repr[chw + 4*i + 3] = ' ';
226 repr[chw + 4*i + 0] = '|';
227 repr[chw + 4*i + 1] = '\n';
229 /* ... and copy it onto the even-numbered lines */
230 for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw);
232 /* fill in the numbers */
233 for (i = 0; i < sz; ++i) {
236 if (board[i] == EMPTY) continue;
237 repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0';
244 static char *game_text_format(game_state *state)
246 const int w = state->shared->params.w;
247 const int h = state->shared->params.h;
248 return board_to_string(state->board, w, h);
251 /*****************************************************************************
252 * GAME GENERATION AND SOLVER *
253 *****************************************************************************/
255 static const int dx[4] = {-1, 1, 0, 0};
256 static const int dy[4] = {0, 0, -1, 1};
259 static void print_board(int *board, int w, int h) {
260 char *repr = board_to_string(board, w, h);
268 /* determines whether a board (in dsf form) is valid. If possible,
269 * return a conflicting pair in *a and *b and a non-*b neighbour of *a
270 * in *c. If not possible, leave them unmodified. */
272 validate_board(int *dsf, int w, int h, int *sq, int *a, int *b, int *c) {
273 const int sz = w * h;
275 assert(*a == SENTINEL);
276 assert(*b == SENTINEL);
277 assert(*c == SENTINEL);
278 for (i = 0; i < sz && *a == sz; ++i) {
279 const int aa = dsf_canonify(dsf, sq[i]);
282 for (j = 0; j < 4; ++j) {
283 const int x = (sq[i] % w) + dx[j];
284 const int y = (sq[i] / w) + dy[j];
286 if (x < 0 || x >= w || y < 0 || y >= h) continue;
287 bb = dsf_canonify(dsf, w*y + x);
288 if (aa == bb) continue;
289 else if (dsf_size(dsf, aa) == dsf_size(dsf, bb)) {
293 } else if (cc == sz) *c = cc = bb;
298 static game_state *new_game(midend *, game_params *, char *);
299 static void free_game(game_state *);
301 /* generate a random valid board; uses validate_board. */
302 static void make_board(int *board, int w, int h, random_state *rs) {
305 const unsigned int sz = w * h;
307 /* w=h=2 is a special case which requires a number > max(w, h) */
308 /* TODO prove that this is the case ONLY for w=h=2. */
309 const int maxsize = min(max(max(w, h), 3), 9);
311 /* Note that if 1 in {w, h} then it's impossible to have a region
312 * of size > w*h, so the special case only affects w=h=2. */
323 dsf = snew_dsf(sz); /* implicit dsf_init */
325 /* I abuse the board variable: when generating the puzzle, it
326 * contains a shuffled list of numbers {0, ..., nsq-1}. */
327 for (i = 0; i < sz; ++i) board[i] = i;
331 shuffle(board, sz, sizeof (int), rs);
332 /* while the board can in principle be fixed */
337 validate_board(dsf, w, h, board, &a, &b, &c);
338 if (a == SENTINEL /* meaning the board is valid */) {
340 for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i);
342 /* printf("returning board number %d\n", nboards); */
345 /* try to repair the invalid board */
346 a = dsf_canonify(dsf, a);
347 assert(a != dsf_canonify(dsf, b));
348 if (c != sz) assert(a != dsf_canonify(dsf, c));
349 dsf_merge(dsf, a, c == sz? b: c);
350 /* if repair impossible; make a new board */
351 if (dsf_size(dsf, a) > maxsize) break;
354 dsf_init(dsf, sz); /* re-init the dsf */
356 assert(FALSE); /* unreachable */
359 static int rhofree(int *hop, int start) {
360 int turtle = start, rabbit = hop[start];
361 while (rabbit != turtle) { /* find a cycle */
362 turtle = hop[turtle];
363 rabbit = hop[hop[rabbit]];
365 do { /* check that start is in the cycle */
366 rabbit = hop[rabbit];
367 if (start == rabbit) return 1;
368 } while (rabbit != turtle);
372 static void merge(int *dsf, int *connected, int a, int b) {
376 assert(rhofree(connected, a));
377 assert(rhofree(connected, b));
378 a = dsf_canonify(dsf, a);
379 b = dsf_canonify(dsf, b);
381 dsf_merge(dsf, a, b);
383 connected[a] = connected[b];
385 assert(rhofree(connected, a));
386 assert(rhofree(connected, b));
389 static void *memdup(const void *ptr, size_t len, size_t esz) {
390 void *dup = smalloc(len * esz);
392 memcpy(dup, ptr, len * esz);
396 static void expand(int *board, int *connected, int *dsf, int w, int h,
397 int dst, int src, int *empty, int *learn) {
404 assert(board[dst] == EMPTY);
405 assert(board[src] != EMPTY);
406 board[dst] = board[src];
407 for (j = 0; j < 4; ++j) {
408 const int x = (dst % w) + dx[j];
409 const int y = (dst / w) + dy[j];
410 const int idx = w*y + x;
411 if (x < 0 || x >= w || y < 0 || y >= h) continue;
412 if (board[idx] != board[dst]) continue;
413 merge(dsf, connected, dst, idx);
415 /* printf("set board[%d] = board[%d], which is %d; size(%d) = %d\n", dst, src, board[src], src, dsf[dsf_canonify(dsf, src)] >> 2); */
420 static void flood(int *board, int w, int h, int i, int n) {
421 const int sz = w * h;
424 if (board[i] == EMPTY) board[i] = -SENTINEL;
425 else if (board[i] == n) board[i] = -board[i];
428 for (k = 0; k < 4; ++k) {
429 const int x = (i % w) + dx[k];
430 const int y = (i / w) + dy[k];
431 const int idx = w*y + x;
432 if (x < 0 || x >= w || y < 0 || y >= h) continue;
433 flood(board, w, h, idx, n);
437 static int count_and_clear(int *board, int sz) {
440 for (i = 0; i < sz; ++i) {
441 if (board[i] >= 0) continue;
443 if (board[i] == -SENTINEL) board[i] = EMPTY;
444 else board[i] = -board[i];
449 static int count(int *board, int w, int h, int i) {
450 flood(board, w, h, i, board[i]);
451 return count_and_clear(board, w * h);
454 static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) {
459 for (j = 0; j < 4; ++j) {
460 const int x = (i % w) + dx[j];
461 const int y = (i / w) + dy[j];
462 const int idx = w*y + x;
465 if (x < 0 || x >= w || y < 0 || y >= h) continue;
466 if (board[idx] != n) continue;
467 root = dsf_canonify(dsf, idx);
468 for (m = 0; m < nhits && root != hits[m]; ++m);
469 if (m < nhits) continue;
470 /* printf("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2); */
471 size += dsf_size(dsf, root);
472 assert(dsf_size(dsf, root) >= 1);
473 hits[nhits++] = root;
479 * +---+---+---+---+---+---+---+
480 * | 6 | | | 2 | | | 2 |
481 * +---+---+---+---+---+---+---+
482 * | | 3 | | 6 | | 3 | |
483 * +---+---+---+---+---+---+---+
484 * | 3 | | | | | | 1 |
485 * +---+---+---+---+---+---+---+
486 * | | 2 | 3 | | 4 | 2 | |
487 * +---+---+---+---+---+---+---+
488 * | 2 | | | | | | 3 |
489 * +---+---+---+---+---+---+---+
490 * | | 5 | | 1 | | 4 | |
491 * +---+---+---+---+---+---+---+
492 * | 4 | | | 3 | | | 3 |
493 * +---+---+---+---+---+---+---+
496 /* Solving techniques:
498 * CONNECTED COMPONENT FORCED EXPANSION (too big):
499 * When a CC can only be expanded in one direction, because all the
500 * other ones would make the CC too big.
501 * +---+---+---+---+---+
502 * | 2 | 2 | | 2 | _ |
503 * +---+---+---+---+---+
505 * CONNECTED COMPONENT FORCED EXPANSION (too small):
506 * When a CC must include a particular square, because otherwise there
507 * would not be enough room to complete it.
513 * When an empty square has no neighbouring empty squares and only a 1
514 * will go into the square (or other CCs would be too big).
519 * TODO: generalise DROPPING IN A ONE: find the size of the CC of
520 * empty squares and a list of all adjacent numbers. See if only one
521 * number in {1, ..., size} u {all adjacent numbers} is possible.
522 * Probably this is only effective for a CC size < n for some n (4?)
524 * TODO: backtracking.
526 #define EXPAND(a, b)\
527 expand(board, connected, dsf, w, h, a, b, &nempty, &learn)
529 static int solver(const int *orig, int w, int h, char **solution) {
530 const int sz = w * h;
532 int *board = memdup(orig, sz, sizeof (int));
533 int *dsf = snew_dsf(sz); /* eqv classes: connected components */
534 int *connected = snewn(sz, int); /* connected[n] := n.next; */
535 /* cyclic disjoint singly linked lists, same partitioning as dsf.
536 * The lists lets you iterate over a partition given any member */
543 for (i = 0; i < sz; i++) connected[i] = i;
545 for (i = 0; i < sz; ++i) {
547 if (board[i] == EMPTY) ++nempty;
548 else for (j = 0; j < 4; ++j) {
549 const int x = (i % w) + dx[j];
550 const int y = (i / w) + dy[j];
551 const int idx = w*y + x;
552 if (x < 0 || x >= w || y < 0 || y >= h) continue;
553 if (board[i] == board[idx]) merge(dsf, connected, i, idx);
557 /* puts("trying to solve this:");
558 print_board(board, w, h); */
560 /* TODO: refactor this code, it's too long */
565 /* for every connected component */
566 for (i = 0; i < sz; ++i) {
570 /* If the component consists of empty squares */
571 if (board[i] == EMPTY) {
574 for (k = 0; k < 4; ++k) {
575 const int x = (i % w) + dx[k];
576 const int y = (i / w) + dy[k];
577 const int idx = w*y + x;
579 if (x < 0 || x >= w || y < 0 || y >= h) continue;
580 if (board[idx] == EMPTY) {
586 (board[idx] >= expandsize(board, dsf, w, h,
589 assert(board[i] == EMPTY);
590 board[i] = -SENTINEL;
591 n = count(board, w, h, idx);
592 assert(board[i] == EMPTY);
593 if (n >= board[idx]) continue;
598 assert(board[i] == EMPTY);
606 /* printf("expanding blob of (%d, %d)\n", i % w, i / w); */
608 j = dsf_canonify(dsf, i);
610 /* (but only for each connected component) */
611 if (i != j) continue;
613 /* (and not if it's already complete) */
614 if (dsf_size(dsf, j) == board[j]) continue;
616 /* for each square j _in_ the connected component */
619 /* printf(" looking at (%d, %d)\n", j % w, j / w); */
621 /* for each neighbouring square (idx) */
622 for (k = 0; k < 4; ++k) {
623 const int x = (j % w) + dx[k];
624 const int y = (j / w) + dy[k];
625 const int idx = w*y + x;
630 if (x < 0 || x >= w || y < 0 || y >= h) continue;
631 if (board[idx] != EMPTY) continue;
632 if (exp == idx) continue;
633 /* printf("\ttrying to expand onto (%d, %d)\n", x, y); */
635 /* find out the would-be size of the new connected
636 * component if we actually expanded into idx */
639 for (l = 0; l < 4; ++l) {
640 const int lx = x + dx[l];
641 const int ly = y + dy[l];
642 const int idxl = w*ly + lx;
645 if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
646 if (board[idxl] != board[j]) continue;
647 root = dsf_canonify(dsf, idxl);
648 for (m = 0; m < nhits && root != hits[m]; ++m);
649 if (m != nhits) continue;
650 // printf("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);
651 size += dsf_size(dsf, root);
652 assert(dsf_size(dsf, root) >= 1);
653 hits[nhits++] = root;
657 size = expandsize(board, dsf, w, h, idx, board[j]);
659 /* ... and see if that size is too big, or if we
660 * have other expansion candidates. Otherwise
661 * remember the (so far) only candidate. */
663 /* printf("\tthat would give a size of %d\n", size); */
664 if (size > board[j]) continue;
665 /* printf("\tnow knowing %d expansions\n", nexpand + 1); */
666 if (exp != SENTINEL) goto next_i;
671 j = connected[j]; /* next square in the same CC */
672 assert(board[i] == board[j]);
674 /* end: for each square j _in_ the connected component */
676 if (exp == SENTINEL) continue;
677 /* printf("expand b: %d -> %d\n", i, exp); */
683 /* end: for each connected component */
684 } while (learn && nempty);
686 /* puts("best guess:");
687 print_board(board, w, h); */
691 assert(*solution == NULL);
692 *solution = snewn(sz + 2, char);
694 for (i = 0; i < sz; ++i) (*solution)[i + 1] = board[i] + '0';
695 (*solution)[sz + 1] = '\0';
696 /* We don't need the \0 for execute_move (the only user)
697 * I'm just being printf-friendly in case I wanna print */
707 static int *make_dsf(int *dsf, int *board, const int w, const int h) {
708 const int sz = w * h;
712 dsf = snew_dsf(w * h);
714 dsf_init(dsf, w * h);
716 for (i = 0; i < sz; ++i) {
718 for (j = 0; j < 4; ++j) {
719 const int x = (i % w) + dx[j];
720 const int y = (i / w) + dy[j];
721 const int k = w*y + x;
722 if (x < 0 || x >= w || y < 0 || y >= h) continue;
723 if (board[i] == board[k]) dsf_merge(dsf, i, k);
730 static int filled(int *board, int *randomize, int k, int n) {
732 if (board == NULL) return FALSE;
733 if (randomize == NULL) return FALSE;
734 if (k > n) return FALSE;
735 for (i = 0; i < k; ++i) if (board[randomize[i]] == 0) return FALSE;
736 for (; i < n; ++i) if (board[randomize[i]] != 0) return FALSE;
742 static int compare(const void *pa, const void *pb) {
743 if (!g_board) return 0;
744 return g_board[*(const int *)pb] - g_board[*(const int *)pa];
747 static char *new_game_desc(game_params *params, random_state *rs,
748 char **aux, int interactive)
750 const int w = params->w;
751 const int h = params->h;
752 const int sz = w * h;
753 int *board = snewn(sz, int);
754 int *randomize = snewn(sz, int);
755 int *solver_board = snewn(sz, int);
756 char *game_description = snewn(sz + 1, char);
759 for (i = 0; i < sz; ++i) {
764 make_board(board, w, h, rs);
765 memcpy(solver_board, board, sz * sizeof (int));
768 qsort(randomize, sz, sizeof (int), compare);
770 /* since more clues only helps and never hurts, one pass will do
771 * just fine: if we can remove clue n with k clues of index > n,
772 * we could have removed clue n with >= k clues of index > n.
773 * So an additional pass wouldn't do anything [use induction]. */
774 for (i = 0; i < sz; ++i) {
775 solver_board[randomize[i]] = EMPTY;
776 if (!solver(solver_board, w, h, NULL))
777 solver_board[randomize[i]] = board[randomize[i]];
780 for (i = 0; i < sz; ++i) {
781 assert(solver_board[i] >= 0);
782 assert(solver_board[i] < 10);
783 game_description[i] = solver_board[i] + '0';
785 game_description[sz] = '\0';
788 solver(solver_board, w, h, aux);
789 print_board(solver_board, w, h);
796 return game_description;
799 static char *validate_desc(game_params *params, char *desc)
802 const int sz = params->w * params->h;
803 const char m = '0' + max(max(params->w, params->h), 3);
805 /* printf("desc = '%s'; sz = %d\n", desc, sz); */
807 for (i = 0; desc[i] && i < sz; ++i)
808 if (!isdigit((unsigned char) *desc))
809 return "non-digit in string";
810 else if (desc[i] > m)
811 return "too large digit in string";
812 if (desc[i]) return "string too long";
813 else if (i < sz) return "string too short";
817 static game_state *new_game(midend *me, game_params *params, char *desc)
819 game_state *state = snew(game_state);
820 int sz = params->w * params->h;
823 state->cheated = state->completed = FALSE;
824 state->shared = snew(struct shared_state);
825 state->shared->refcnt = 1;
826 state->shared->params = *params; /* struct copy */
827 state->shared->clues = snewn(sz, int);
828 for (i = 0; i < sz; ++i) state->shared->clues[i] = desc[i] - '0';
829 state->board = memdup(state->shared->clues, sz, sizeof (int));
834 static game_state *dup_game(game_state *state)
836 const int sz = state->shared->params.w * state->shared->params.h;
837 game_state *ret = snew(game_state);
839 ret->board = memdup(state->board, sz, sizeof (int));
840 ret->shared = state->shared;
841 ret->cheated = state->cheated;
842 ret->completed = state->completed;
843 ++ret->shared->refcnt;
848 static void free_game(game_state *state)
852 if (--state->shared->refcnt == 0) {
853 sfree(state->shared->clues);
854 sfree(state->shared);
859 static char *solve_game(game_state *state, game_state *currstate,
860 char *aux, char **error)
863 const int w = state->shared->params.w;
864 const int h = state->shared->params.h;
865 if (!solver(state->board, w, h, &aux))
866 *error = "Sorry, I couldn't find a solution";
871 /*****************************************************************************
872 * USER INTERFACE STATE AND ACTION *
873 *****************************************************************************/
876 int x, y; /* highlighted square, or (-1, -1) if none */
879 static game_ui *new_ui(game_state *state)
881 game_ui *ui = snew(game_ui);
888 static void free_ui(game_ui *ui)
893 static char *encode_ui(game_ui *ui)
898 static void decode_ui(game_ui *ui, char *encoding)
902 static void game_changed_state(game_ui *ui, game_state *oldstate,
903 game_state *newstate)
907 #define PREFERRED_TILE_SIZE 32
908 #define TILE_SIZE (ds->tilesize)
909 #define BORDER (TILE_SIZE / 2)
910 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
912 struct game_drawstate {
913 struct game_params params;
917 int *dsf_scratch, *border_scratch;
920 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
921 int x, int y, int button)
923 const int w = state->shared->params.w;
924 const int h = state->shared->params.h;
926 const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
927 const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
934 if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
935 if (button == LEFT_BUTTON) {
936 if ((tx == ui->x && ty == ui->y) || state->shared->clues[w*ty+tx])
938 else ui->x = tx, ui->y = ty;
939 return ""; /* redraw */
943 assert((ui->x == -1) == (ui->y == -1));
944 if (ui->x == -1) return NULL;
945 assert(state->shared->clues[w*ui->y + ui->x] == 0);
956 if (!isdigit(button)) return NULL;
958 if (button > (w == 2 && h == 2? 3: max(w, h))) return NULL;
962 const int i = w*ui->y + ui->x;
965 if (state->board[i] == button) {
966 return ""; /* no change - just update ui */
968 sprintf(buf, "%d_%d", i, button);
974 static game_state *execute_move(game_state *state, char *move)
976 game_state *new_state;
977 const int sz = state->shared->params.w * state->shared->params.h;
981 new_state = dup_game(state);
982 for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0';
983 new_state->cheated = TRUE;
986 const int i = strtol(move, &endptr, 0);
988 if (endptr == move) return NULL;
989 if (*endptr != '_') return NULL;
991 value = strtol(move, &endptr, 0);
992 if (endptr == move) return NULL;
993 if (*endptr != '\0') return NULL;
994 if (i < 0 || i >= sz || value < 0 || value > 9) return NULL;
995 new_state = dup_game(state);
996 new_state->board[i] = value;
1000 * Check for completion.
1002 if (!new_state->completed) {
1003 const int w = new_state->shared->params.w;
1004 const int h = new_state->shared->params.h;
1005 const int sz = w * h;
1006 int *dsf = make_dsf(NULL, new_state->board, w, h);
1008 for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i);
1011 new_state->completed = TRUE;
1017 /* ----------------------------------------------------------------------
1021 #define FLASH_TIME 0.4F
1023 #define COL_CLUE COL_GRID
1034 static void game_compute_size(game_params *params, int tilesize,
1037 *x = (params->w + 1) * tilesize;
1038 *y = (params->h + 1) * tilesize;
1041 static void game_set_size(drawing *dr, game_drawstate *ds,
1042 game_params *params, int tilesize)
1044 ds->tilesize = tilesize;
1047 static float *game_colours(frontend *fe, int *ncolours)
1049 float *ret = snewn(3 * NCOLOURS, float);
1051 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1053 ret[COL_GRID * 3 + 0] = 0.0F;
1054 ret[COL_GRID * 3 + 1] = 0.0F;
1055 ret[COL_GRID * 3 + 2] = 0.0F;
1057 ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
1058 ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1059 ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1061 ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0];
1062 ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1];
1063 ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2];
1065 ret[COL_ERROR * 3 + 0] = 1.0F;
1066 ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1067 ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1069 ret[COL_USER * 3 + 0] = 0.0F;
1070 ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1071 ret[COL_USER * 3 + 2] = 0.0F;
1073 *ncolours = NCOLOURS;
1077 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1079 struct game_drawstate *ds = snew(struct game_drawstate);
1082 ds->tilesize = PREFERRED_TILE_SIZE;
1084 ds->params = state->shared->params;
1085 ds->v = snewn(ds->params.w * ds->params.h, int);
1086 ds->flags = snewn(ds->params.w * ds->params.h, int);
1087 for (i = 0; i < ds->params.w * ds->params.h; i++)
1088 ds->v[i] = ds->flags[i] = -1;
1089 ds->border_scratch = snewn(ds->params.w * ds->params.h, int);
1090 ds->dsf_scratch = NULL;
1095 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1099 sfree(ds->border_scratch);
1100 sfree(ds->dsf_scratch);
1104 #define BORDER_U 0x001
1105 #define BORDER_D 0x002
1106 #define BORDER_L 0x004
1107 #define BORDER_R 0x008
1108 #define BORDER_UR 0x010
1109 #define BORDER_DR 0x020
1110 #define BORDER_UL 0x040
1111 #define BORDER_DL 0x080
1112 #define CURSOR_BG 0x100
1113 #define CORRECT_BG 0x200
1114 #define ERROR_BG 0x400
1115 #define USER_COL 0x800
1117 static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
1124 * Clip to the grid square.
1126 clip(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1127 TILE_SIZE, TILE_SIZE);
1133 BORDER + x*TILE_SIZE,
1134 BORDER + y*TILE_SIZE,
1137 (flags & CURSOR_BG ? COL_HIGHLIGHT :
1138 flags & ERROR_BG ? COL_ERROR :
1139 flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
1142 * Draw the grid lines.
1144 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1145 BORDER + (x+1)*TILE_SIZE, BORDER + y*TILE_SIZE, COL_GRID);
1146 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1147 BORDER + x*TILE_SIZE, BORDER + (y+1)*TILE_SIZE, COL_GRID);
1157 (x + 1) * TILE_SIZE,
1158 (y + 1) * TILE_SIZE,
1161 ALIGN_VCENTRE | ALIGN_HCENTRE,
1162 flags & USER_COL ? COL_USER : COL_CLUE,
1167 * Draw bold lines around the borders.
1169 if (flags & BORDER_L)
1171 BORDER + x*TILE_SIZE + 1,
1172 BORDER + y*TILE_SIZE + 1,
1176 if (flags & BORDER_U)
1178 BORDER + x*TILE_SIZE + 1,
1179 BORDER + y*TILE_SIZE + 1,
1183 if (flags & BORDER_R)
1185 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1186 BORDER + y*TILE_SIZE + 1,
1190 if (flags & BORDER_D)
1192 BORDER + x*TILE_SIZE + 1,
1193 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1197 if (flags & BORDER_UL)
1199 BORDER + x*TILE_SIZE + 1,
1200 BORDER + y*TILE_SIZE + 1,
1204 if (flags & BORDER_UR)
1206 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1207 BORDER + y*TILE_SIZE + 1,
1211 if (flags & BORDER_DL)
1213 BORDER + x*TILE_SIZE + 1,
1214 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1218 if (flags & BORDER_DR)
1220 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1221 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1229 BORDER + x*TILE_SIZE,
1230 BORDER + y*TILE_SIZE,
1235 static void draw_grid(drawing *dr, game_drawstate *ds, game_state *state,
1236 game_ui *ui, int flashy, int borders, int shading)
1238 const int w = state->shared->params.w;
1239 const int h = state->shared->params.h;
1244 * Build a dsf for the board in its current state, to use for
1245 * highlights and hints.
1247 ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h);
1250 * Work out where we're putting borders between the cells.
1252 for (y = 0; y < w*h; y++)
1253 ds->border_scratch[y] = 0;
1255 for (y = 0; y < h; y++)
1256 for (x = 0; x < w; x++) {
1260 for (dx = 0; dx <= 1; dx++) {
1265 if (x+dx >= w || y+dy >= h)
1268 v1 = state->board[y*w+x];
1269 v2 = state->board[(y+dy)*w+(x+dx)];
1270 s1 = dsf_size(ds->dsf_scratch, y*w+x);
1271 s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx));
1274 * We only ever draw a border between two cells if
1275 * they don't have the same contents.
1279 * But in that situation, we don't always draw
1280 * a border. We do if the two cells both
1281 * contain actual numbers...
1287 * ... or if at least one of them is a
1288 * completed or overfull omino.
1297 ds->border_scratch[y*w+x] |= (dx ? 1 : 2);
1302 * Actually do the drawing.
1304 for (y = 0; y < h; ++y)
1305 for (x = 0; x < w; ++x) {
1307 * Determine what we need to draw in this square.
1309 int v = state->board[y*w+x];
1312 if (flashy || !shading) {
1313 /* clear all background flags */
1314 } else if (x == ui->x && y == ui->y) {
1317 int size = dsf_size(ds->dsf_scratch, y*w+x);
1319 flags |= CORRECT_BG;
1325 * Borders at the very edges of the grid are
1326 * independent of the `borders' flag.
1338 if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1))
1340 if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2))
1342 if (x == w-1 || (ds->border_scratch[y*w+x] & 1))
1344 if (y == h-1 || (ds->border_scratch[y*w+x] & 2))
1347 if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)]))
1349 if (y > 0 && x < w-1 &&
1350 ((ds->border_scratch[(y-1)*w+x] & 1) ||
1351 (ds->border_scratch[(y-1)*w+(x+1)] & 2)))
1353 if (y < h-1 && x > 0 &&
1354 ((ds->border_scratch[y*w+(x-1)] & 2) ||
1355 (ds->border_scratch[(y+1)*w+(x-1)] & 1)))
1357 if (y < h-1 && x < w-1 &&
1358 ((ds->border_scratch[y*w+(x+1)] & 2) ||
1359 (ds->border_scratch[(y+1)*w+x] & 1)))
1363 if (!state->shared->clues[y*w+x])
1366 if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) {
1367 draw_square(dr, ds, x, y, v, flags);
1369 ds->flags[y*w+x] = flags;
1374 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1375 game_state *state, int dir, game_ui *ui,
1376 float animtime, float flashtime)
1378 const int w = state->shared->params.w;
1379 const int h = state->shared->params.h;
1383 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3);
1387 * The initial contents of the window are not guaranteed and
1388 * can vary with front ends. To be on the safe side, all games
1389 * should start by drawing a big background-colour rectangle
1390 * covering the whole window.
1392 draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
1396 * Smaller black rectangle which is the main grid.
1398 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1399 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1400 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1403 draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
1408 draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE);
1411 static float game_anim_length(game_state *oldstate, game_state *newstate,
1412 int dir, game_ui *ui)
1417 static float game_flash_length(game_state *oldstate, game_state *newstate,
1418 int dir, game_ui *ui)
1422 assert(newstate->shared);
1423 assert(oldstate->shared == newstate->shared);
1424 if (!oldstate->completed && newstate->completed &&
1425 !oldstate->cheated && !newstate->cheated)
1430 static int game_timing_state(game_state *state, game_ui *ui)
1435 static void game_print_size(game_params *params, float *x, float *y)
1440 * I'll use 6mm squares by default.
1442 game_compute_size(params, 600, &pw, &ph);
1447 static void game_print(drawing *dr, game_state *state, int tilesize)
1449 const int w = state->shared->params.w;
1450 const int h = state->shared->params.h;
1453 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1454 game_drawstate *ds = game_new_drawstate(dr, state);
1455 game_set_size(dr, ds, NULL, tilesize);
1457 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1458 c = print_mono_colour(dr, 0); assert(c == COL_GRID);
1459 c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT);
1460 c = print_mono_colour(dr, 1); assert(c == COL_CORRECT);
1461 c = print_mono_colour(dr, 1); assert(c == COL_ERROR);
1462 c = print_mono_colour(dr, 0); assert(c == COL_USER);
1467 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1468 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1469 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1473 * We'll draw borders between the ominoes iff the grid is not
1474 * pristine. So scan it to see if it is.
1477 for (i = 0; i < w*h; i++)
1478 if (state->board[i] && !state->shared->clues[i])
1484 print_line_width(dr, TILE_SIZE / 64);
1485 draw_grid(dr, ds, state, NULL, FALSE, borders, FALSE);
1490 game_free_drawstate(dr, ds);
1494 #define thegame filling
1497 const struct game thegame = {
1498 "Filling", "games.filling", "filling",
1505 TRUE, game_configure, custom_params,
1513 TRUE, game_text_format,
1521 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1524 game_free_drawstate,
1528 TRUE, FALSE, game_print_size, game_print,
1529 FALSE, /* wants_statusbar */
1530 FALSE, game_timing_state,
1531 REQUIRE_NUMPAD, /* flags */
1534 #ifdef STANDALONE_SOLVER /* solver? hah! */
1536 int main(int argc, char **argv) {
1538 game_params *params;
1543 for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc);
1544 if (*desc == '\0') {
1545 fprintf(stderr, "bad puzzle id: %s", par);
1551 params = snew(game_params);
1552 decode_params(params, par);
1553 state = new_game(NULL, params, desc);
1554 if (solver(state->board, params->w, params->h, NULL))
1555 printf("%s:%s: solvable\n", par, desc);
1557 printf("%s:%s: not solvable\n", par, desc);