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 * - make a somewhat more clever solver
15 * + enable "ghost regions" of size > 1
16 * - one can put an upper bound on the size of a ghost region
17 * by considering the board size and summing present hints.
18 * + for each square, for i=1..n, what is the distance to a region
19 * containing i? How full is the region? How is this useful?
21 * - in board generation, after having merged regions such that no
22 * more merges are necessary, try splitting (big) regions.
23 * + it seems that smaller regions make for better puzzles; see
24 * for instance the 7x7 puzzle in this file (grep for 7x7:).
26 * - symmetric hints (solo-style)
27 * + right now that means including _many_ hints, and the puzzles
28 * won't look any nicer. Not worth it (at the moment).
30 * - make the solver do recursion/backtracking.
31 * + This is for user-submitted puzzles, not for puzzle
32 * generation (on the other hand, never say never).
34 * - prove that only w=h=2 needs a special case
36 * - solo-like pencil marks?
38 * - a user says that the difficulty is unevenly distributed.
39 * + partition into levels? Will they be non-crap?
41 * - Allow square contents > 9?
42 * + I could use letters for digits (solo does this), but
43 * letters don't have numeric significance (normal people hate
44 * base36), which is relevant here (much more than in solo).
45 * + [click, 1, 0, enter] => [10 in clicked square]?
46 * + How much information is needed to solve? Does one need to
47 * know the algorithm by which the largest number is set?
49 * - eliminate puzzle instances with done chunks (1's in particular)?
50 * + that's what the qsort call is all about.
51 * + the 1's don't bother me that much.
52 * + but this takes a LONG time (not always possible)?
53 * - this may be affected by solver (lack of) quality.
54 * - weed them out by construction instead of post-cons check
55 * + but that interleaves make_board and new_game_desc: you
56 * have to alternate between changing the board and
57 * changing the hint set (instead of just creating the
58 * board once, then changing the hint set once -> done).
60 * - use binary search when discovering the minimal sovable point
61 * + profile to show a need (but when the solver gets slower...)
62 * + 7x9 @ .011s, 9x13 @ .075s, 17x13 @ .661s (all avg with n=100)
63 * + but the hints are independent, not linear, so... what?
76 static unsigned char verbose;
78 static void printv(char *fmt, ...) {
89 /*****************************************************************************
90 * GAME CONFIGURATION AND PARAMETERS *
91 *****************************************************************************/
98 struct game_params params;
105 struct shared_state *shared;
106 int completed, cheated;
109 static const struct game_params filling_defaults[3] = {
110 {9, 7}, {13, 9}, {17, 13}
113 static game_params *default_params(void)
115 game_params *ret = snew(game_params);
117 *ret = filling_defaults[1]; /* struct copy */
122 static int game_fetch_preset(int i, char **name, game_params **params)
126 if (i < 0 || i >= lenof(filling_defaults)) return FALSE;
127 *params = snew(game_params);
128 **params = filling_defaults[i]; /* struct copy */
129 sprintf(buf, "%dx%d", filling_defaults[i].w, filling_defaults[i].h);
135 static void free_params(game_params *params)
140 static game_params *dup_params(const game_params *params)
142 game_params *ret = snew(game_params);
143 *ret = *params; /* struct copy */
147 static void decode_params(game_params *ret, char const *string)
149 ret->w = ret->h = atoi(string);
150 while (*string && isdigit((unsigned char) *string)) ++string;
151 if (*string == 'x') ret->h = atoi(++string);
154 static char *encode_params(const game_params *params, int full)
157 sprintf(buf, "%dx%d", params->w, params->h);
161 static config_item *game_configure(const game_params *params)
166 ret = snewn(3, config_item);
168 ret[0].name = "Width";
169 ret[0].type = C_STRING;
170 sprintf(buf, "%d", params->w);
171 ret[0].sval = dupstr(buf);
174 ret[1].name = "Height";
175 ret[1].type = C_STRING;
176 sprintf(buf, "%d", params->h);
177 ret[1].sval = dupstr(buf);
188 static game_params *custom_params(const config_item *cfg)
190 game_params *ret = snew(game_params);
192 ret->w = atoi(cfg[0].sval);
193 ret->h = atoi(cfg[1].sval);
198 static char *validate_params(const game_params *params, int full)
200 if (params->w < 1) return "Width must be at least one";
201 if (params->h < 1) return "Height must be at least one";
206 /*****************************************************************************
207 * STRINGIFICATION OF GAME STATE *
208 *****************************************************************************/
212 /* Example of plaintext rendering:
213 * +---+---+---+---+---+---+---+
214 * | 6 | | | 2 | | | 2 |
215 * +---+---+---+---+---+---+---+
216 * | | 3 | | 6 | | 3 | |
217 * +---+---+---+---+---+---+---+
218 * | 3 | | | | | | 1 |
219 * +---+---+---+---+---+---+---+
220 * | | 2 | 3 | | 4 | 2 | |
221 * +---+---+---+---+---+---+---+
222 * | 2 | | | | | | 3 |
223 * +---+---+---+---+---+---+---+
224 * | | 5 | | 1 | | 4 | |
225 * +---+---+---+---+---+---+---+
226 * | 4 | | | 3 | | | 3 |
227 * +---+---+---+---+---+---+---+
229 * This puzzle instance is taken from the nikoli website
230 * Encoded (unsolved and solved), the strings are these:
231 * 7x7:6002002030603030000010230420200000305010404003003
232 * 7x7:6662232336663232331311235422255544325413434443313
234 static char *board_to_string(int *board, int w, int h) {
235 const int sz = w * h;
236 const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */
237 const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */
238 const int chlen = chw * chh;
239 char *repr = snewn(chlen + 1, char);
244 /* build the first line ("^(\+---){n}\+$") */
245 for (i = 0; i < w; ++i) {
252 repr[4*i + 1] = '\n';
254 /* ... and copy it onto the odd-numbered lines */
255 for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw);
257 /* build the second line ("^(\|\t){n}\|$") */
258 for (i = 0; i < w; ++i) {
259 repr[chw + 4*i + 0] = '|';
260 repr[chw + 4*i + 1] = ' ';
261 repr[chw + 4*i + 2] = ' ';
262 repr[chw + 4*i + 3] = ' ';
264 repr[chw + 4*i + 0] = '|';
265 repr[chw + 4*i + 1] = '\n';
267 /* ... and copy it onto the even-numbered lines */
268 for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw);
270 /* fill in the numbers */
271 for (i = 0; i < sz; ++i) {
274 if (board[i] == EMPTY) continue;
275 repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0';
282 static int game_can_format_as_text_now(const game_params *params)
287 static char *game_text_format(const game_state *state)
289 const int w = state->shared->params.w;
290 const int h = state->shared->params.h;
291 return board_to_string(state->board, w, h);
294 /*****************************************************************************
295 * GAME GENERATION AND SOLVER *
296 *****************************************************************************/
298 static const int dx[4] = {-1, 1, 0, 0};
299 static const int dy[4] = {0, 0, -1, 1};
309 static void print_board(int *board, int w, int h) {
311 char *repr = board_to_string(board, w, h);
312 printv("%s\n", repr);
317 static game_state *new_game(midend *, const game_params *, const char *);
318 static void free_game(game_state *);
322 static int mark_region(int *board, int w, int h, int i, int n, int m) {
327 for (j = 0; j < 4; ++j) {
328 const int x = (i % w) + dx[j], y = (i / w) + dy[j], ii = w*y + x;
329 if (x < 0 || x >= w || y < 0 || y >= h) continue;
330 if (board[ii] == m) return FALSE;
331 if (board[ii] != n) continue;
332 if (!mark_region(board, w, h, ii, n, m)) return FALSE;
337 static int region_size(int *board, int w, int h, int i) {
338 const int sz = w * h;
340 if (board[i] == 0) return 0;
342 mark_region(board, w, h, i, board[i], SENTINEL);
343 for (size = j = 0; j < sz; ++j) {
344 if (board[j] != -1) continue;
351 static void merge_ones(int *board, int w, int h)
353 const int sz = w * h;
354 const int maxsize = min(max(max(w, h), 3), 9);
358 for (i = 0; i < sz; ++i) {
359 if (board[i] != 1) continue;
361 for (j = 0; j < 4; ++j, board[i] = 1) {
362 const int x = (i % w) + dx[j], y = (i / w) + dy[j];
363 int oldsize, newsize, ok, ii = w*y + x;
364 if (x < 0 || x >= w || y < 0 || y >= h) continue;
365 if (board[ii] == maxsize) continue;
369 newsize = region_size(board, w, h, i);
371 if (newsize > maxsize) continue;
373 ok = mark_region(board, w, h, i, oldsize, newsize);
375 for (k = 0; k < sz; ++k)
377 board[k] = ok ? newsize : oldsize;
381 if (j < 4) change = TRUE;
386 /* generate a random valid board; uses validate_board. */
387 static void make_board(int *board, int w, int h, random_state *rs) {
388 const int sz = w * h;
390 /* w=h=2 is a special case which requires a number > max(w, h) */
391 /* TODO prove that this is the case ONLY for w=h=2. */
392 const int maxsize = min(max(max(w, h), 3), 9);
394 /* Note that if 1 in {w, h} then it's impossible to have a region
395 * of size > w*h, so the special case only affects w=h=2. */
403 /* I abuse the board variable: when generating the puzzle, it
404 * contains a shuffled list of numbers {0, ..., sz-1}. */
405 for (i = 0; i < sz; ++i) board[i] = i;
407 dsf = snewn(sz, int);
410 shuffle(board, sz, sizeof (int), rs);
413 change = FALSE; /* as long as the board potentially has errors */
414 for (i = 0; i < sz; ++i) {
415 const int square = dsf_canonify(dsf, board[i]);
416 const int size = dsf_size(dsf, square);
417 int merge = SENTINEL, min = maxsize - size + 1, error = FALSE;
418 int neighbour, neighbour_size, j;
420 for (j = 0; j < 4; ++j) {
421 const int x = (board[i] % w) + dx[j];
422 const int y = (board[i] / w) + dy[j];
423 if (x < 0 || x >= w || y < 0 || y >= h) continue;
425 neighbour = dsf_canonify(dsf, w*y + x);
426 if (square == neighbour) continue;
428 neighbour_size = dsf_size(dsf, neighbour);
429 if (size == neighbour_size) error = TRUE;
431 /* find the smallest neighbour to merge with, which
432 * wouldn't make the region too large. (This is
433 * guaranteed by the initial value of `min'.) */
434 if (neighbour_size < min) {
435 min = neighbour_size;
440 /* if this square is not in error, leave it be */
441 if (!error) continue;
443 /* if it is, but we can't fix it, retry the whole board.
444 * Maybe we could fix it by merging the conflicting
445 * neighbouring region(s) into some of their neighbours,
446 * but just restarting works out fine. */
447 if (merge == SENTINEL) goto retry;
449 /* merge with the smallest neighbouring workable region. */
450 dsf_merge(dsf, square, merge);
455 for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i);
456 merge_ones(board, w, h);
461 static void merge(int *dsf, int *connected, int a, int b) {
465 a = dsf_canonify(dsf, a);
466 b = dsf_canonify(dsf, b);
468 dsf_merge(dsf, a, b);
470 connected[a] = connected[b];
474 static void *memdup(const void *ptr, size_t len, size_t esz) {
475 void *dup = smalloc(len * esz);
477 memcpy(dup, ptr, len * esz);
481 static void expand(struct solver_state *s, int w, int h, int t, int f) {
484 assert(s->board[t] == EMPTY); /* expand to empty square */
485 assert(s->board[f] != EMPTY); /* expand from non-empty square */
487 "learn: expanding %d from (%d, %d) into (%d, %d)\n",
488 s->board[f], f % w, f / w, t % w, t / w);
489 s->board[t] = s->board[f];
490 for (j = 0; j < 4; ++j) {
491 const int x = (t % w) + dx[j];
492 const int y = (t / w) + dy[j];
493 const int idx = w*y + x;
494 if (x < 0 || x >= w || y < 0 || y >= h) continue;
495 if (s->board[idx] != s->board[t]) continue;
496 merge(s->dsf, s->connected, t, idx);
501 static void clear_count(int *board, int sz) {
503 for (i = 0; i < sz; ++i) {
504 if (board[i] >= 0) continue;
505 else if (board[i] == -SENTINEL) board[i] = EMPTY;
506 else board[i] = -board[i];
510 static void flood_count(int *board, int w, int h, int i, int n, int *c) {
511 const int sz = w * h;
514 if (board[i] == EMPTY) board[i] = -SENTINEL;
515 else if (board[i] == n) board[i] = -board[i];
518 if (--*c == 0) return;
520 for (k = 0; k < 4; ++k) {
521 const int x = (i % w) + dx[k];
522 const int y = (i / w) + dy[k];
523 const int idx = w*y + x;
524 if (x < 0 || x >= w || y < 0 || y >= h) continue;
525 flood_count(board, w, h, idx, n, c);
530 static int check_capacity(int *board, int w, int h, int i) {
532 flood_count(board, w, h, i, board[i], &n);
533 clear_count(board, w * h);
537 static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) {
542 for (j = 0; j < 4; ++j) {
543 const int x = (i % w) + dx[j];
544 const int y = (i / w) + dy[j];
545 const int idx = w*y + x;
548 if (x < 0 || x >= w || y < 0 || y >= h) continue;
549 if (board[idx] != n) continue;
550 root = dsf_canonify(dsf, idx);
551 for (m = 0; m < nhits && root != hits[m]; ++m);
552 if (m < nhits) continue;
553 printv("\t (%d, %d) contrib %d to size\n", x, y, dsf[root] >> 2);
554 size += dsf_size(dsf, root);
555 assert(dsf_size(dsf, root) >= 1);
556 hits[nhits++] = root;
562 * +---+---+---+---+---+---+---+
563 * | 6 | | | 2 | | | 2 |
564 * +---+---+---+---+---+---+---+
565 * | | 3 | | 6 | | 3 | |
566 * +---+---+---+---+---+---+---+
567 * | 3 | | | | | | 1 |
568 * +---+---+---+---+---+---+---+
569 * | | 2 | 3 | | 4 | 2 | |
570 * +---+---+---+---+---+---+---+
571 * | 2 | | | | | | 3 |
572 * +---+---+---+---+---+---+---+
573 * | | 5 | | 1 | | 4 | |
574 * +---+---+---+---+---+---+---+
575 * | 4 | | | 3 | | | 3 |
576 * +---+---+---+---+---+---+---+
579 /* Solving techniques:
581 * CONNECTED COMPONENT FORCED EXPANSION (too big):
582 * When a CC can only be expanded in one direction, because all the
583 * other ones would make the CC too big.
584 * +---+---+---+---+---+
585 * | 2 | 2 | | 2 | _ |
586 * +---+---+---+---+---+
588 * CONNECTED COMPONENT FORCED EXPANSION (too small):
589 * When a CC must include a particular square, because otherwise there
590 * would not be enough room to complete it. This includes squares not
591 * adjacent to the CC through learn_critical_square.
597 * When an empty square has no neighbouring empty squares and only a 1
598 * will go into the square (or other CCs would be too big).
603 * TODO: generalise DROPPING IN A ONE: find the size of the CC of
604 * empty squares and a list of all adjacent numbers. See if only one
605 * number in {1, ..., size} u {all adjacent numbers} is possible.
606 * Probably this is only effective for a CC size < n for some n (4?)
608 * TODO: backtracking.
611 static void filled_square(struct solver_state *s, int w, int h, int i) {
613 for (j = 0; j < 4; ++j) {
614 const int x = (i % w) + dx[j];
615 const int y = (i / w) + dy[j];
616 const int idx = w*y + x;
617 if (x < 0 || x >= w || y < 0 || y >= h) continue;
618 if (s->board[i] == s->board[idx])
619 merge(s->dsf, s->connected, i, idx);
623 static void init_solver_state(struct solver_state *s, int w, int h) {
624 const int sz = w * h;
629 for (i = 0; i < sz; ++i) s->connected[i] = i;
630 for (i = 0; i < sz; ++i)
631 if (s->board[i] == EMPTY) ++s->nempty;
632 else filled_square(s, w, h, i);
635 static int learn_expand_or_one(struct solver_state *s, int w, int h) {
636 const int sz = w * h;
642 for (i = 0; i < sz; ++i) {
646 if (s->board[i] != EMPTY) continue;
648 for (j = 0; j < 4; ++j) {
649 const int x = (i % w) + dx[j];
650 const int y = (i / w) + dy[j];
651 const int idx = w*y + x;
652 if (x < 0 || x >= w || y < 0 || y >= h) continue;
653 if (s->board[idx] == EMPTY) {
658 (s->board[idx] == 1 ||
659 (s->board[idx] >= expandsize(s->board, s->dsf, w, h,
662 if (dsf_size(s->dsf, idx) == s->board[idx]) continue;
663 assert(s->board[i] == EMPTY);
664 s->board[i] = -SENTINEL;
665 if (check_capacity(s->board, w, h, idx)) continue;
666 assert(s->board[i] == EMPTY);
667 printv("learn: expanding in one\n");
668 expand(s, w, h, i, idx);
674 printv("learn: one at (%d, %d)\n", i % w, i / w);
675 assert(s->board[i] == EMPTY);
685 static int learn_blocked_expansion(struct solver_state *s, int w, int h) {
686 const int sz = w * h;
691 /* for every connected component */
692 for (i = 0; i < sz; ++i) {
696 if (s->board[i] == EMPTY) continue;
697 j = dsf_canonify(s->dsf, i);
699 /* (but only for each connected component) */
700 if (i != j) continue;
702 /* (and not if it's already complete) */
703 if (dsf_size(s->dsf, j) == s->board[j]) continue;
705 /* for each square j _in_ the connected component */
708 printv(" looking at (%d, %d)\n", j % w, j / w);
710 /* for each neighbouring square (idx) */
711 for (k = 0; k < 4; ++k) {
712 const int x = (j % w) + dx[k];
713 const int y = (j / w) + dy[k];
714 const int idx = w*y + x;
719 if (x < 0 || x >= w || y < 0 || y >= h) continue;
720 if (s->board[idx] != EMPTY) continue;
721 if (exp == idx) continue;
722 printv("\ttrying to expand onto (%d, %d)\n", x, y);
724 /* find out the would-be size of the new connected
725 * component if we actually expanded into idx */
728 for (l = 0; l < 4; ++l) {
729 const int lx = x + dx[l];
730 const int ly = y + dy[l];
731 const int idxl = w*ly + lx;
734 if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
735 if (board[idxl] != board[j]) continue;
736 root = dsf_canonify(dsf, idxl);
737 for (m = 0; m < nhits && root != hits[m]; ++m);
738 if (m != nhits) continue;
739 // printv("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);
740 size += dsf_size(dsf, root);
741 assert(dsf_size(dsf, root) >= 1);
742 hits[nhits++] = root;
746 size = expandsize(s->board, s->dsf, w, h, idx, s->board[j]);
748 /* ... and see if that size is too big, or if we
749 * have other expansion candidates. Otherwise
750 * remember the (so far) only candidate. */
752 printv("\tthat would give a size of %d\n", size);
753 if (size > s->board[j]) continue;
754 /* printv("\tnow knowing %d expansions\n", nexpand + 1); */
755 if (exp != SENTINEL) goto next_i;
760 j = s->connected[j]; /* next square in the same CC */
761 assert(s->board[i] == s->board[j]);
763 /* end: for each square j _in_ the connected component */
765 if (exp == SENTINEL) continue;
766 printv("learning to expand\n");
767 expand(s, w, h, exp, i);
773 /* end: for each connected component */
777 static int learn_critical_square(struct solver_state *s, int w, int h) {
778 const int sz = w * h;
783 /* for each connected component */
784 for (i = 0; i < sz; ++i) {
786 if (s->board[i] == EMPTY) continue;
787 if (i != dsf_canonify(s->dsf, i)) continue;
788 slack = s->board[i] - dsf_size(s->dsf, i);
789 if (slack == 0) continue;
790 assert(s->board[i] != 1);
791 /* for each empty square */
792 for (j = 0; j < sz; ++j) {
793 if (s->board[j] == EMPTY) {
794 /* if it's too far away from the CC, don't bother */
795 int k = i, jx = j % w, jy = j / w;
797 int kx = k % w, ky = k / w;
798 if (abs(kx - jx) + abs(ky - jy) <= slack) break;
801 if (i == k) continue; /* not within range */
803 s->board[j] = -SENTINEL;
804 if (check_capacity(s->board, w, h, i)) continue;
805 /* if not expanding s->board[i] to s->board[j] implies
806 * that s->board[i] can't reach its full size, ... */
809 "learn: ds %d at (%d, %d) blocking (%d, %d)\n",
810 s->board[i], j % w, j / w, i % w, i / w);
812 s->board[j] = s->board[i];
813 filled_square(s, w, h, j);
820 static int solver(const int *orig, int w, int h, char **solution) {
821 const int sz = w * h;
823 struct solver_state ss;
824 ss.board = memdup(orig, sz, sizeof (int));
825 ss.dsf = snew_dsf(sz); /* eqv classes: connected components */
826 ss.connected = snewn(sz, int); /* connected[n] := n.next; */
827 /* cyclic disjoint singly linked lists, same partitioning as dsf.
828 * The lists lets you iterate over a partition given any member */
830 printv("trying to solve this:\n");
831 print_board(ss.board, w, h);
833 init_solver_state(&ss, w, h);
835 if (learn_blocked_expansion(&ss, w, h)) continue;
836 if (learn_expand_or_one(&ss, w, h)) continue;
837 if (learn_critical_square(&ss, w, h)) continue;
841 printv("best guess:\n");
842 print_board(ss.board, w, h);
846 *solution = snewn(sz + 2, char);
848 for (i = 0; i < sz; ++i) (*solution)[i + 1] = ss.board[i] + '0';
849 (*solution)[sz + 1] = '\0';
850 /* We don't need the \0 for execute_move (the only user)
851 * I'm just being printf-friendly in case I wanna print */
861 static int *make_dsf(int *dsf, int *board, const int w, const int h) {
862 const int sz = w * h;
866 dsf = snew_dsf(w * h);
868 dsf_init(dsf, w * h);
870 for (i = 0; i < sz; ++i) {
872 for (j = 0; j < 4; ++j) {
873 const int x = (i % w) + dx[j];
874 const int y = (i / w) + dy[j];
875 const int k = w*y + x;
876 if (x < 0 || x >= w || y < 0 || y >= h) continue;
877 if (board[i] == board[k]) dsf_merge(dsf, i, k);
883 static void minimize_clue_set(int *board, int w, int h, random_state *rs)
885 const int sz = w * h;
886 int *shuf = snewn(sz, int), i;
888 for (i = 0; i < sz; ++i) shuf[i] = i;
889 shuffle(shuf, sz, sizeof (int), rs);
891 /* the solver is monotone, so a second pass is superfluous. */
892 for (i = 0; i < sz; ++i) {
893 int tmp = board[shuf[i]];
894 board[shuf[i]] = EMPTY;
895 if (!solver(board, w, h, NULL)) board[shuf[i]] = tmp;
901 static int encode_run(char *buffer, int run)
904 for (; run > 26; run -= 26)
907 buffer[i++] = 'a' - 1 + run;
911 static char *new_game_desc(const game_params *params, random_state *rs,
912 char **aux, int interactive)
914 const int w = params->w, h = params->h, sz = w * h;
915 int *board = snewn(sz, int), i, j, run;
916 char *description = snewn(sz + 1, char);
918 make_board(board, w, h, rs);
919 minimize_clue_set(board, w, h, rs);
921 for (run = j = i = 0; i < sz; ++i) {
922 assert(board[i] >= 0);
923 assert(board[i] < 10);
927 j += encode_run(description + j, run);
929 description[j++] = board[i] + '0';
932 j += encode_run(description + j, run);
933 description[j++] = '\0';
937 return sresize(description, j, char);
940 static char *validate_desc(const game_params *params, const char *desc)
942 const int sz = params->w * params->h;
943 const char m = '0' + max(max(params->w, params->h), 3);
946 for (area = 0; *desc; ++desc) {
947 if (*desc >= 'a' && *desc <= 'z') area += *desc - 'a' + 1;
948 else if (*desc >= '0' && *desc <= m) ++area;
950 static char s[] = "Invalid character '%""' in game description";
951 int n = sprintf(s, "Invalid character '%1c' in game description",
953 assert(n + 1 <= lenof(s)); /* +1 for the terminating NUL */
956 if (area > sz) return "Too much data to fit in grid";
958 return (area < sz) ? "Not enough data to fill grid" : NULL;
961 static game_state *new_game(midend *me, const game_params *params,
964 game_state *state = snew(game_state);
965 int sz = params->w * params->h;
968 state->cheated = state->completed = FALSE;
969 state->shared = snew(struct shared_state);
970 state->shared->refcnt = 1;
971 state->shared->params = *params; /* struct copy */
972 state->shared->clues = snewn(sz, int);
974 for (i = 0; *desc; ++desc) {
975 if (*desc >= 'a' && *desc <= 'z') {
976 int j = *desc - 'a' + 1;
978 for (; j; --j) state->shared->clues[i++] = 0;
979 } else state->shared->clues[i++] = *desc - '0';
981 state->board = memdup(state->shared->clues, sz, sizeof (int));
986 static game_state *dup_game(const game_state *state)
988 const int sz = state->shared->params.w * state->shared->params.h;
989 game_state *ret = snew(game_state);
991 ret->board = memdup(state->board, sz, sizeof (int));
992 ret->shared = state->shared;
993 ret->cheated = state->cheated;
994 ret->completed = state->completed;
995 ++ret->shared->refcnt;
1000 static void free_game(game_state *state)
1003 sfree(state->board);
1004 if (--state->shared->refcnt == 0) {
1005 sfree(state->shared->clues);
1006 sfree(state->shared);
1011 static char *solve_game(const game_state *state, const game_state *currstate,
1012 const char *aux, char **error)
1015 const int w = state->shared->params.w;
1016 const int h = state->shared->params.h;
1018 if (!solver(state->board, w, h, &new_aux))
1019 *error = "Sorry, I couldn't find a solution";
1025 /*****************************************************************************
1026 * USER INTERFACE STATE AND ACTION *
1027 *****************************************************************************/
1030 int *sel; /* w*h highlighted squares, or NULL */
1031 int cur_x, cur_y, cur_visible, keydragging;
1034 static game_ui *new_ui(const game_state *state)
1036 game_ui *ui = snew(game_ui);
1039 ui->cur_x = ui->cur_y = ui->cur_visible = ui->keydragging = 0;
1044 static void free_ui(game_ui *ui)
1051 static char *encode_ui(const game_ui *ui)
1056 static void decode_ui(game_ui *ui, const char *encoding)
1060 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1061 const game_state *newstate)
1063 /* Clear any selection */
1068 ui->keydragging = FALSE;
1071 #define PREFERRED_TILE_SIZE 32
1072 #define TILE_SIZE (ds->tilesize)
1073 #define BORDER (TILE_SIZE / 2)
1074 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1076 struct game_drawstate {
1077 struct game_params params;
1081 int *dsf_scratch, *border_scratch;
1084 static char *interpret_move(const game_state *state, game_ui *ui,
1085 const game_drawstate *ds,
1086 int x, int y, int button)
1088 const int w = state->shared->params.w;
1089 const int h = state->shared->params.h;
1091 const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1092 const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1100 button &= ~MOD_MASK;
1102 if (button == LEFT_BUTTON || button == LEFT_DRAG) {
1103 /* A left-click anywhere will clear the current selection. */
1104 if (button == LEFT_BUTTON) {
1110 if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
1112 ui->sel = snewn(w*h, int);
1113 memset(ui->sel, 0, w*h*sizeof(int));
1115 if (!state->shared->clues[w*ty+tx])
1116 ui->sel[w*ty+tx] = 1;
1118 ui->cur_visible = 0;
1119 return ""; /* redraw */
1122 if (IS_CURSOR_MOVE(button)) {
1123 ui->cur_visible = 1;
1124 move_cursor(button, &ui->cur_x, &ui->cur_y, w, h, 0);
1125 if (ui->keydragging) goto select_square;
1128 if (button == CURSOR_SELECT) {
1129 if (!ui->cur_visible) {
1130 ui->cur_visible = 1;
1133 ui->keydragging = !ui->keydragging;
1134 if (!ui->keydragging) return "";
1138 ui->sel = snewn(w*h, int);
1139 memset(ui->sel, 0, w*h*sizeof(int));
1141 if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
1142 ui->sel[w*ui->cur_y + ui->cur_x] = 1;
1145 if (button == CURSOR_SELECT2) {
1146 if (!ui->cur_visible) {
1147 ui->cur_visible = 1;
1151 ui->sel = snewn(w*h, int);
1152 memset(ui->sel, 0, w*h*sizeof(int));
1154 ui->keydragging = FALSE;
1155 if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
1156 ui->sel[w*ui->cur_y + ui->cur_x] ^= 1;
1157 for (i = 0; i < w*h && !ui->sel[i]; i++);
1165 if (button == '\b' || button == 27) {
1168 ui->keydragging = FALSE;
1172 if (button < '0' || button > '9') return NULL;
1174 if (button > (w == 2 && h == 2 ? 3 : max(w, h))) return NULL;
1175 ui->keydragging = FALSE;
1177 for (i = 0; i < w*h; i++) {
1179 if ((ui->sel && ui->sel[i]) ||
1180 (!ui->sel && ui->cur_visible && (w*ui->cur_y+ui->cur_x) == i)) {
1181 if (state->shared->clues[i] != 0) continue; /* in case cursor is on clue */
1182 if (state->board[i] != button) {
1183 sprintf(buf, "%s%d", move ? "," : "", i);
1185 move = srealloc(move, strlen(move)+strlen(buf)+1);
1188 move = smalloc(strlen(buf)+1);
1196 sprintf(buf, "_%d", button);
1197 move = srealloc(move, strlen(move)+strlen(buf)+1);
1200 if (!ui->sel) return move ? move : NULL;
1203 /* Need to update UI at least, as we cleared the selection */
1204 return move ? move : "";
1207 static game_state *execute_move(const game_state *state, const char *move)
1209 game_state *new_state = NULL;
1210 const int sz = state->shared->params.w * state->shared->params.h;
1214 new_state = dup_game(state);
1215 for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0';
1216 new_state->cheated = TRUE;
1219 char *endptr, *delim = strchr(move, '_');
1220 if (!delim) goto err;
1221 value = strtol(delim+1, &endptr, 0);
1222 if (*endptr || endptr == delim+1) goto err;
1223 if (value < 0 || value > 9) goto err;
1224 new_state = dup_game(state);
1226 const int i = strtol(move, &endptr, 0);
1227 if (endptr == move) goto err;
1228 if (i < 0 || i >= sz) goto err;
1229 new_state->board[i] = value;
1230 if (*endptr == '_') break;
1231 if (*endptr != ',') goto err;
1237 * Check for completion.
1239 if (!new_state->completed) {
1240 const int w = new_state->shared->params.w;
1241 const int h = new_state->shared->params.h;
1242 const int sz = w * h;
1243 int *dsf = make_dsf(NULL, new_state->board, w, h);
1245 for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i);
1248 new_state->completed = TRUE;
1254 if (new_state) free_game(new_state);
1258 /* ----------------------------------------------------------------------
1262 #define FLASH_TIME 0.4F
1264 #define COL_CLUE COL_GRID
1276 static void game_compute_size(const game_params *params, int tilesize,
1279 *x = (params->w + 1) * tilesize;
1280 *y = (params->h + 1) * tilesize;
1283 static void game_set_size(drawing *dr, game_drawstate *ds,
1284 const game_params *params, int tilesize)
1286 ds->tilesize = tilesize;
1289 static float *game_colours(frontend *fe, int *ncolours)
1291 float *ret = snewn(3 * NCOLOURS, float);
1293 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1295 ret[COL_GRID * 3 + 0] = 0.0F;
1296 ret[COL_GRID * 3 + 1] = 0.0F;
1297 ret[COL_GRID * 3 + 2] = 0.0F;
1299 ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
1300 ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1301 ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1303 ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0];
1304 ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1];
1305 ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2];
1307 ret[COL_CURSOR * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1308 ret[COL_CURSOR * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1309 ret[COL_CURSOR * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
1311 ret[COL_ERROR * 3 + 0] = 1.0F;
1312 ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1313 ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1315 ret[COL_USER * 3 + 0] = 0.0F;
1316 ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1317 ret[COL_USER * 3 + 2] = 0.0F;
1319 *ncolours = NCOLOURS;
1323 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1325 struct game_drawstate *ds = snew(struct game_drawstate);
1328 ds->tilesize = PREFERRED_TILE_SIZE;
1330 ds->params = state->shared->params;
1331 ds->v = snewn(ds->params.w * ds->params.h, int);
1332 ds->flags = snewn(ds->params.w * ds->params.h, int);
1333 for (i = 0; i < ds->params.w * ds->params.h; i++)
1334 ds->v[i] = ds->flags[i] = -1;
1335 ds->border_scratch = snewn(ds->params.w * ds->params.h, int);
1336 ds->dsf_scratch = NULL;
1341 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1345 sfree(ds->border_scratch);
1346 sfree(ds->dsf_scratch);
1350 #define BORDER_U 0x001
1351 #define BORDER_D 0x002
1352 #define BORDER_L 0x004
1353 #define BORDER_R 0x008
1354 #define BORDER_UR 0x010
1355 #define BORDER_DR 0x020
1356 #define BORDER_UL 0x040
1357 #define BORDER_DL 0x080
1358 #define HIGH_BG 0x100
1359 #define CORRECT_BG 0x200
1360 #define ERROR_BG 0x400
1361 #define USER_COL 0x800
1362 #define CURSOR_SQ 0x1000
1364 static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
1371 * Clip to the grid square.
1373 clip(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1374 TILE_SIZE, TILE_SIZE);
1380 BORDER + x*TILE_SIZE,
1381 BORDER + y*TILE_SIZE,
1384 (flags & HIGH_BG ? COL_HIGHLIGHT :
1385 flags & ERROR_BG ? COL_ERROR :
1386 flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
1389 * Draw the grid lines.
1391 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1392 BORDER + (x+1)*TILE_SIZE, BORDER + y*TILE_SIZE, COL_GRID);
1393 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1394 BORDER + x*TILE_SIZE, BORDER + (y+1)*TILE_SIZE, COL_GRID);
1404 (x + 1) * TILE_SIZE,
1405 (y + 1) * TILE_SIZE,
1408 ALIGN_VCENTRE | ALIGN_HCENTRE,
1409 flags & USER_COL ? COL_USER : COL_CLUE,
1414 * Draw bold lines around the borders.
1416 if (flags & BORDER_L)
1418 BORDER + x*TILE_SIZE + 1,
1419 BORDER + y*TILE_SIZE + 1,
1423 if (flags & BORDER_U)
1425 BORDER + x*TILE_SIZE + 1,
1426 BORDER + y*TILE_SIZE + 1,
1430 if (flags & BORDER_R)
1432 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1433 BORDER + y*TILE_SIZE + 1,
1437 if (flags & BORDER_D)
1439 BORDER + x*TILE_SIZE + 1,
1440 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1444 if (flags & BORDER_UL)
1446 BORDER + x*TILE_SIZE + 1,
1447 BORDER + y*TILE_SIZE + 1,
1451 if (flags & BORDER_UR)
1453 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1454 BORDER + y*TILE_SIZE + 1,
1458 if (flags & BORDER_DL)
1460 BORDER + x*TILE_SIZE + 1,
1461 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1465 if (flags & BORDER_DR)
1467 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1468 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1473 if (flags & CURSOR_SQ) {
1474 int coff = TILE_SIZE/8;
1475 draw_rect_outline(dr,
1476 BORDER + x*TILE_SIZE + coff,
1477 BORDER + y*TILE_SIZE + coff,
1486 BORDER + x*TILE_SIZE,
1487 BORDER + y*TILE_SIZE,
1492 static void draw_grid(drawing *dr, game_drawstate *ds, const game_state *state,
1493 const game_ui *ui, int flashy, int borders, int shading)
1495 const int w = state->shared->params.w;
1496 const int h = state->shared->params.h;
1501 * Build a dsf for the board in its current state, to use for
1502 * highlights and hints.
1504 ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h);
1507 * Work out where we're putting borders between the cells.
1509 for (y = 0; y < w*h; y++)
1510 ds->border_scratch[y] = 0;
1512 for (y = 0; y < h; y++)
1513 for (x = 0; x < w; x++) {
1517 for (dx = 0; dx <= 1; dx++) {
1522 if (x+dx >= w || y+dy >= h)
1525 v1 = state->board[y*w+x];
1526 v2 = state->board[(y+dy)*w+(x+dx)];
1527 s1 = dsf_size(ds->dsf_scratch, y*w+x);
1528 s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx));
1531 * We only ever draw a border between two cells if
1532 * they don't have the same contents.
1536 * But in that situation, we don't always draw
1537 * a border. We do if the two cells both
1538 * contain actual numbers...
1544 * ... or if at least one of them is a
1545 * completed or overfull omino.
1554 ds->border_scratch[y*w+x] |= (dx ? 1 : 2);
1559 * Actually do the drawing.
1561 for (y = 0; y < h; ++y)
1562 for (x = 0; x < w; ++x) {
1564 * Determine what we need to draw in this square.
1566 int i = y*w+x, v = state->board[i];
1569 if (flashy || !shading) {
1570 /* clear all background flags */
1571 } else if (ui && ui->sel && ui->sel[i]) {
1574 int size = dsf_size(ds->dsf_scratch, i);
1576 flags |= CORRECT_BG;
1580 int rt = dsf_canonify(ds->dsf_scratch, i), j;
1581 for (j = 0; j < w*h; ++j) {
1583 if (dsf_canonify(ds->dsf_scratch, j) != rt) continue;
1584 for (k = 0; k < 4; ++k) {
1585 const int xx = j % w + dx[k], yy = j / w + dy[k];
1586 if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
1587 state->board[yy*w + xx] == EMPTY)
1596 if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
1600 * Borders at the very edges of the grid are
1601 * independent of the `borders' flag.
1613 if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1))
1615 if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2))
1617 if (x == w-1 || (ds->border_scratch[y*w+x] & 1))
1619 if (y == h-1 || (ds->border_scratch[y*w+x] & 2))
1622 if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)]))
1624 if (y > 0 && x < w-1 &&
1625 ((ds->border_scratch[(y-1)*w+x] & 1) ||
1626 (ds->border_scratch[(y-1)*w+(x+1)] & 2)))
1628 if (y < h-1 && x > 0 &&
1629 ((ds->border_scratch[y*w+(x-1)] & 2) ||
1630 (ds->border_scratch[(y+1)*w+(x-1)] & 1)))
1632 if (y < h-1 && x < w-1 &&
1633 ((ds->border_scratch[y*w+(x+1)] & 2) ||
1634 (ds->border_scratch[(y+1)*w+x] & 1)))
1638 if (!state->shared->clues[y*w+x])
1641 if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) {
1642 draw_square(dr, ds, x, y, v, flags);
1644 ds->flags[y*w+x] = flags;
1649 static void game_redraw(drawing *dr, game_drawstate *ds,
1650 const game_state *oldstate, const game_state *state,
1651 int dir, const game_ui *ui,
1652 float animtime, float flashtime)
1654 const int w = state->shared->params.w;
1655 const int h = state->shared->params.h;
1659 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3);
1663 * The initial contents of the window are not guaranteed and
1664 * can vary with front ends. To be on the safe side, all games
1665 * should start by drawing a big background-colour rectangle
1666 * covering the whole window.
1668 draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
1672 * Smaller black rectangle which is the main grid.
1674 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1675 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1676 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1679 draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
1684 draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE);
1687 static float game_anim_length(const game_state *oldstate,
1688 const game_state *newstate, int dir, game_ui *ui)
1693 static float game_flash_length(const game_state *oldstate,
1694 const game_state *newstate, int dir, game_ui *ui)
1698 assert(newstate->shared);
1699 assert(oldstate->shared == newstate->shared);
1700 if (!oldstate->completed && newstate->completed &&
1701 !oldstate->cheated && !newstate->cheated)
1706 static int game_status(const game_state *state)
1708 return state->completed ? +1 : 0;
1711 static int game_timing_state(const game_state *state, game_ui *ui)
1716 static void game_print_size(const game_params *params, float *x, float *y)
1721 * I'll use 6mm squares by default.
1723 game_compute_size(params, 600, &pw, &ph);
1728 static void game_print(drawing *dr, const game_state *state, int tilesize)
1730 const int w = state->shared->params.w;
1731 const int h = state->shared->params.h;
1734 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1735 game_drawstate *ds = game_new_drawstate(dr, state);
1736 game_set_size(dr, ds, NULL, tilesize);
1738 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1739 c = print_mono_colour(dr, 0); assert(c == COL_GRID);
1740 c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT);
1741 c = print_mono_colour(dr, 1); assert(c == COL_CORRECT);
1742 c = print_mono_colour(dr, 1); assert(c == COL_ERROR);
1743 c = print_mono_colour(dr, 0); assert(c == COL_USER);
1748 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1749 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1750 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1754 * We'll draw borders between the ominoes iff the grid is not
1755 * pristine. So scan it to see if it is.
1758 for (i = 0; i < w*h; i++)
1759 if (state->board[i] && !state->shared->clues[i])
1765 print_line_width(dr, TILE_SIZE / 64);
1766 draw_grid(dr, ds, state, NULL, FALSE, borders, FALSE);
1771 game_free_drawstate(dr, ds);
1775 #define thegame filling
1778 const struct game thegame = {
1779 "Filling", "games.filling", "filling",
1786 TRUE, game_configure, custom_params,
1794 TRUE, game_can_format_as_text_now, game_text_format,
1802 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1805 game_free_drawstate,
1810 TRUE, FALSE, game_print_size, game_print,
1811 FALSE, /* wants_statusbar */
1812 FALSE, game_timing_state,
1813 REQUIRE_NUMPAD, /* flags */
1816 #ifdef STANDALONE_SOLVER /* solver? hah! */
1818 int main(int argc, char **argv) {
1820 game_params *params;
1825 for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc);
1826 if (*desc == '\0') {
1827 fprintf(stderr, "bad puzzle id: %s", par);
1833 params = snew(game_params);
1834 decode_params(params, par);
1835 state = new_game(NULL, params, desc);
1836 if (solver(state->board, params->w, params->h, NULL))
1837 printf("%s:%s: solvable\n", par, desc);
1839 printf("%s:%s: not solvable\n", par, desc);
1846 /* vim: set shiftwidth=4 tabstop=8: */