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, ...) {
87 /*****************************************************************************
88 * GAME CONFIGURATION AND PARAMETERS *
89 *****************************************************************************/
96 struct game_params params;
103 struct shared_state *shared;
104 int completed, cheated;
107 static const struct game_params defaults[3] = {{7, 9}, {9, 13}, {13, 17}};
109 static game_params *default_params(void)
111 game_params *ret = snew(game_params);
113 *ret = defaults[1]; /* struct copy */
118 static int game_fetch_preset(int i, char **name, game_params **params)
122 if (i < 0 || i >= lenof(defaults)) return FALSE;
123 *params = snew(game_params);
124 **params = defaults[i]; /* struct copy */
125 sprintf(buf, "%dx%d", defaults[i].h, defaults[i].w);
131 static void free_params(game_params *params)
136 static game_params *dup_params(game_params *params)
138 game_params *ret = snew(game_params);
139 *ret = *params; /* struct copy */
143 static void decode_params(game_params *ret, char const *string)
145 ret->w = ret->h = atoi(string);
146 while (*string && isdigit((unsigned char) *string)) ++string;
147 if (*string == 'x') ret->h = atoi(++string);
150 static char *encode_params(game_params *params, int full)
153 sprintf(buf, "%dx%d", params->w, params->h);
157 static config_item *game_configure(game_params *params)
162 ret = snewn(3, config_item);
164 ret[0].name = "Width";
165 ret[0].type = C_STRING;
166 sprintf(buf, "%d", params->w);
167 ret[0].sval = dupstr(buf);
170 ret[1].name = "Height";
171 ret[1].type = C_STRING;
172 sprintf(buf, "%d", params->h);
173 ret[1].sval = dupstr(buf);
184 static game_params *custom_params(config_item *cfg)
186 game_params *ret = snew(game_params);
188 ret->w = atoi(cfg[0].sval);
189 ret->h = atoi(cfg[1].sval);
194 static char *validate_params(game_params *params, int full)
196 if (params->w < 1) return "Width must be at least one";
197 if (params->h < 1) return "Height must be at least one";
202 /*****************************************************************************
203 * STRINGIFICATION OF GAME STATE *
204 *****************************************************************************/
208 /* Example of plaintext rendering:
209 * +---+---+---+---+---+---+---+
210 * | 6 | | | 2 | | | 2 |
211 * +---+---+---+---+---+---+---+
212 * | | 3 | | 6 | | 3 | |
213 * +---+---+---+---+---+---+---+
214 * | 3 | | | | | | 1 |
215 * +---+---+---+---+---+---+---+
216 * | | 2 | 3 | | 4 | 2 | |
217 * +---+---+---+---+---+---+---+
218 * | 2 | | | | | | 3 |
219 * +---+---+---+---+---+---+---+
220 * | | 5 | | 1 | | 4 | |
221 * +---+---+---+---+---+---+---+
222 * | 4 | | | 3 | | | 3 |
223 * +---+---+---+---+---+---+---+
225 * This puzzle instance is taken from the nikoli website
226 * Encoded (unsolved and solved), the strings are these:
227 * 7x7:6002002030603030000010230420200000305010404003003
228 * 7x7:6662232336663232331311235422255544325413434443313
230 static char *board_to_string(int *board, int w, int h) {
231 const int sz = w * h;
232 const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */
233 const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */
234 const int chlen = chw * chh;
235 char *repr = snewn(chlen + 1, char);
240 /* build the first line ("^(\+---){n}\+$") */
241 for (i = 0; i < w; ++i) {
248 repr[4*i + 1] = '\n';
250 /* ... and copy it onto the odd-numbered lines */
251 for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw);
253 /* build the second line ("^(\|\t){n}\|$") */
254 for (i = 0; i < w; ++i) {
255 repr[chw + 4*i + 0] = '|';
256 repr[chw + 4*i + 1] = ' ';
257 repr[chw + 4*i + 2] = ' ';
258 repr[chw + 4*i + 3] = ' ';
260 repr[chw + 4*i + 0] = '|';
261 repr[chw + 4*i + 1] = '\n';
263 /* ... and copy it onto the even-numbered lines */
264 for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw);
266 /* fill in the numbers */
267 for (i = 0; i < sz; ++i) {
270 if (board[i] == EMPTY) continue;
271 repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0';
278 static int game_can_format_as_text_now(game_params *params)
283 static char *game_text_format(game_state *state)
285 const int w = state->shared->params.w;
286 const int h = state->shared->params.h;
287 return board_to_string(state->board, w, h);
290 /*****************************************************************************
291 * GAME GENERATION AND SOLVER *
292 *****************************************************************************/
294 static const int dx[4] = {-1, 1, 0, 0};
295 static const int dy[4] = {0, 0, -1, 1};
305 static void print_board(int *board, int w, int h) {
307 char *repr = board_to_string(board, w, h);
308 printv("%s\n", repr);
313 static game_state *new_game(midend *, game_params *, char *);
314 static void free_game(game_state *);
318 /* generate a random valid board; uses validate_board. */
319 static void make_board(int *board, int w, int h, random_state *rs) {
322 const unsigned int sz = w * h;
324 /* w=h=2 is a special case which requires a number > max(w, h) */
325 /* TODO prove that this is the case ONLY for w=h=2. */
326 const int maxsize = min(max(max(w, h), 3), 9);
328 /* Note that if 1 in {w, h} then it's impossible to have a region
329 * of size > w*h, so the special case only affects w=h=2. */
339 dsf = snew_dsf(sz); /* implicit dsf_init */
341 /* I abuse the board variable: when generating the puzzle, it
342 * contains a shuffled list of numbers {0, ..., nsq-1}. */
343 for (i = 0; i < sz; ++i) board[i] = i;
348 shuffle(board, sz, sizeof (int), rs);
349 /* while the board can in principle be fixed */
352 for (i = 0; i < sz; ++i) {
356 const int aa = dsf_canonify(dsf, board[i]);
359 for (j = 0; j < 4; ++j) {
360 const int x = (board[i] % w) + dx[j];
361 const int y = (board[i] / w) + dy[j];
363 if (x < 0 || x >= w || y < 0 || y >= h) continue;
364 bb = dsf_canonify(dsf, w*y + x);
365 if (aa == bb) continue;
366 else if (dsf_size(dsf, aa) == dsf_size(dsf, bb)) {
370 } else if (cc == sz) c = cc = bb;
373 a = dsf_canonify(dsf, a);
374 assert(a != dsf_canonify(dsf, b));
375 if (c != sz) assert(a != dsf_canonify(dsf, c));
376 dsf_merge(dsf, a, c == sz? b: c);
377 /* if repair impossible; make a new board */
378 if (dsf_size(dsf, a) > maxsize) goto retry;
384 for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i);
387 printv("returning board number %d\n", nboards);
393 assert(FALSE); /* unreachable */
396 static int rhofree(int *hop, int start) {
397 int turtle = start, rabbit = hop[start];
398 while (rabbit != turtle) { /* find a cycle */
399 turtle = hop[turtle];
400 rabbit = hop[hop[rabbit]];
402 do { /* check that start is in the cycle */
403 rabbit = hop[rabbit];
404 if (start == rabbit) return 1;
405 } while (rabbit != turtle);
409 static void merge(int *dsf, int *connected, int a, int b) {
413 assert(rhofree(connected, a));
414 assert(rhofree(connected, b));
415 a = dsf_canonify(dsf, a);
416 b = dsf_canonify(dsf, b);
418 dsf_merge(dsf, a, b);
420 connected[a] = connected[b];
422 assert(rhofree(connected, a));
423 assert(rhofree(connected, b));
426 static void *memdup(const void *ptr, size_t len, size_t esz) {
427 void *dup = smalloc(len * esz);
429 memcpy(dup, ptr, len * esz);
433 static void expand(struct solver_state *s, int w, int h, int t, int f) {
436 assert(s->board[t] == EMPTY); /* expand to empty square */
437 assert(s->board[f] != EMPTY); /* expand from non-empty square */
439 "learn: expanding %d from (%d, %d) into (%d, %d)\n",
440 s->board[f], f % w, f / w, t % w, t / w);
441 s->board[t] = s->board[f];
442 for (j = 0; j < 4; ++j) {
443 const int x = (t % w) + dx[j];
444 const int y = (t / w) + dy[j];
445 const int idx = w*y + x;
446 if (x < 0 || x >= w || y < 0 || y >= h) continue;
447 if (s->board[idx] != s->board[t]) continue;
448 merge(s->dsf, s->connected, t, idx);
453 static void clear_count(int *board, int sz) {
455 for (i = 0; i < sz; ++i) {
456 if (board[i] >= 0) continue;
457 else if (board[i] == -SENTINEL) board[i] = EMPTY;
458 else board[i] = -board[i];
462 static void flood_count(int *board, int w, int h, int i, int n, int *c) {
463 const int sz = w * h;
466 if (board[i] == EMPTY) board[i] = -SENTINEL;
467 else if (board[i] == n) board[i] = -board[i];
470 if (--*c == 0) return;
472 for (k = 0; k < 4; ++k) {
473 const int x = (i % w) + dx[k];
474 const int y = (i / w) + dy[k];
475 const int idx = w*y + x;
476 if (x < 0 || x >= w || y < 0 || y >= h) continue;
477 flood_count(board, w, h, idx, n, c);
482 static int check_capacity(int *board, int w, int h, int i) {
484 flood_count(board, w, h, i, board[i], &n);
485 clear_count(board, w * h);
489 static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) {
494 for (j = 0; j < 4; ++j) {
495 const int x = (i % w) + dx[j];
496 const int y = (i / w) + dy[j];
497 const int idx = w*y + x;
500 if (x < 0 || x >= w || y < 0 || y >= h) continue;
501 if (board[idx] != n) continue;
502 root = dsf_canonify(dsf, idx);
503 for (m = 0; m < nhits && root != hits[m]; ++m);
504 if (m < nhits) continue;
505 printv("\t (%d, %d) contrib %d to size\n", x, y, dsf[root] >> 2);
506 size += dsf_size(dsf, root);
507 assert(dsf_size(dsf, root) >= 1);
508 hits[nhits++] = root;
514 * +---+---+---+---+---+---+---+
515 * | 6 | | | 2 | | | 2 |
516 * +---+---+---+---+---+---+---+
517 * | | 3 | | 6 | | 3 | |
518 * +---+---+---+---+---+---+---+
519 * | 3 | | | | | | 1 |
520 * +---+---+---+---+---+---+---+
521 * | | 2 | 3 | | 4 | 2 | |
522 * +---+---+---+---+---+---+---+
523 * | 2 | | | | | | 3 |
524 * +---+---+---+---+---+---+---+
525 * | | 5 | | 1 | | 4 | |
526 * +---+---+---+---+---+---+---+
527 * | 4 | | | 3 | | | 3 |
528 * +---+---+---+---+---+---+---+
531 /* Solving techniques:
533 * CONNECTED COMPONENT FORCED EXPANSION (too big):
534 * When a CC can only be expanded in one direction, because all the
535 * other ones would make the CC too big.
536 * +---+---+---+---+---+
537 * | 2 | 2 | | 2 | _ |
538 * +---+---+---+---+---+
540 * CONNECTED COMPONENT FORCED EXPANSION (too small):
541 * When a CC must include a particular square, because otherwise there
542 * would not be enough room to complete it. This includes squares not
543 * adjacent to the CC through learn_critical_square.
549 * When an empty square has no neighbouring empty squares and only a 1
550 * will go into the square (or other CCs would be too big).
555 * TODO: generalise DROPPING IN A ONE: find the size of the CC of
556 * empty squares and a list of all adjacent numbers. See if only one
557 * number in {1, ..., size} u {all adjacent numbers} is possible.
558 * Probably this is only effective for a CC size < n for some n (4?)
560 * TODO: backtracking.
563 static void filled_square(struct solver_state *s, int w, int h, int i) {
565 for (j = 0; j < 4; ++j) {
566 const int x = (i % w) + dx[j];
567 const int y = (i / w) + dy[j];
568 const int idx = w*y + x;
569 if (x < 0 || x >= w || y < 0 || y >= h) continue;
570 if (s->board[i] == s->board[idx])
571 merge(s->dsf, s->connected, i, idx);
575 static void init_solver_state(struct solver_state *s, int w, int h) {
576 const int sz = w * h;
581 for (i = 0; i < sz; ++i) s->connected[i] = i;
582 for (i = 0; i < sz; ++i)
583 if (s->board[i] == EMPTY) ++s->nempty;
584 else filled_square(s, w, h, i);
587 static int learn_expand_or_one(struct solver_state *s, int w, int h) {
588 const int sz = w * h;
594 for (i = 0; i < sz; ++i) {
598 if (s->board[i] != EMPTY) continue;
600 for (j = 0; j < 4; ++j) {
601 const int x = (i % w) + dx[j];
602 const int y = (i / w) + dy[j];
603 const int idx = w*y + x;
604 if (x < 0 || x >= w || y < 0 || y >= h) continue;
605 if (s->board[idx] == EMPTY) {
610 (s->board[idx] == 1 ||
611 (s->board[idx] >= expandsize(s->board, s->dsf, w, h,
614 assert(s->board[i] == EMPTY);
615 s->board[i] = -SENTINEL;
616 if (check_capacity(s->board, w, h, idx)) continue;
617 assert(s->board[i] == EMPTY);
618 printv("learn: expanding in one\n");
619 expand(s, w, h, i, idx);
625 printv("learn: one at (%d, %d)\n", i % w, i / w);
626 assert(s->board[i] == EMPTY);
636 static int learn_blocked_expansion(struct solver_state *s, int w, int h) {
637 const int sz = w * h;
642 /* for every connected component */
643 for (i = 0; i < sz; ++i) {
647 if (s->board[i] == EMPTY) continue;
648 j = dsf_canonify(s->dsf, i);
650 /* (but only for each connected component) */
651 if (i != j) continue;
653 /* (and not if it's already complete) */
654 if (dsf_size(s->dsf, j) == s->board[j]) continue;
656 /* for each square j _in_ the connected component */
659 printv(" looking at (%d, %d)\n", j % w, j / w);
661 /* for each neighbouring square (idx) */
662 for (k = 0; k < 4; ++k) {
663 const int x = (j % w) + dx[k];
664 const int y = (j / w) + dy[k];
665 const int idx = w*y + x;
670 if (x < 0 || x >= w || y < 0 || y >= h) continue;
671 if (s->board[idx] != EMPTY) continue;
672 if (exp == idx) continue;
673 printv("\ttrying to expand onto (%d, %d)\n", x, y);
675 /* find out the would-be size of the new connected
676 * component if we actually expanded into idx */
679 for (l = 0; l < 4; ++l) {
680 const int lx = x + dx[l];
681 const int ly = y + dy[l];
682 const int idxl = w*ly + lx;
685 if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
686 if (board[idxl] != board[j]) continue;
687 root = dsf_canonify(dsf, idxl);
688 for (m = 0; m < nhits && root != hits[m]; ++m);
689 if (m != nhits) continue;
690 // printv("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);
691 size += dsf_size(dsf, root);
692 assert(dsf_size(dsf, root) >= 1);
693 hits[nhits++] = root;
697 size = expandsize(s->board, s->dsf, w, h, idx, s->board[j]);
699 /* ... and see if that size is too big, or if we
700 * have other expansion candidates. Otherwise
701 * remember the (so far) only candidate. */
703 printv("\tthat would give a size of %d\n", size);
704 if (size > s->board[j]) continue;
705 /* printv("\tnow knowing %d expansions\n", nexpand + 1); */
706 if (exp != SENTINEL) goto next_i;
711 j = s->connected[j]; /* next square in the same CC */
712 assert(s->board[i] == s->board[j]);
714 /* end: for each square j _in_ the connected component */
716 if (exp == SENTINEL) continue;
717 printv("learning to expand\n");
718 expand(s, w, h, exp, i);
724 /* end: for each connected component */
728 static int learn_critical_square(struct solver_state *s, int w, int h) {
729 const int sz = w * h;
734 /* for each connected component */
735 for (i = 0; i < sz; ++i) {
737 if (s->board[i] == EMPTY) continue;
738 if (i != dsf_canonify(s->dsf, i)) continue;
739 if (dsf_size(s->dsf, i) == s->board[i]) continue;
740 assert(s->board[i] != 1);
741 /* for each empty square */
742 for (j = 0; j < sz; ++j) {
743 if (s->board[j] != EMPTY) continue;
744 s->board[j] = -SENTINEL;
745 if (check_capacity(s->board, w, h, i)) continue;
746 /* if not expanding s->board[i] to s->board[j] implies
747 * that s->board[i] can't reach its full size, ... */
750 "learn: ds %d at (%d, %d) blocking (%d, %d)\n",
751 s->board[i], j % w, j / w, i % w, i / w);
753 s->board[j] = s->board[i];
754 filled_square(s, w, h, j);
761 static int solver(const int *orig, int w, int h, char **solution) {
762 const int sz = w * h;
764 struct solver_state ss;
765 ss.board = memdup(orig, sz, sizeof (int));
766 ss.dsf = snew_dsf(sz); /* eqv classes: connected components */
767 ss.connected = snewn(sz, int); /* connected[n] := n.next; */
768 /* cyclic disjoint singly linked lists, same partitioning as dsf.
769 * The lists lets you iterate over a partition given any member */
771 printv("trying to solve this:\n");
772 print_board(ss.board, w, h);
774 init_solver_state(&ss, w, h);
776 if (learn_blocked_expansion(&ss, w, h)) continue;
777 if (learn_expand_or_one(&ss, w, h)) continue;
778 if (learn_critical_square(&ss, w, h)) continue;
782 printv("best guess:\n");
783 print_board(ss.board, w, h);
787 assert(*solution == NULL);
788 *solution = snewn(sz + 2, char);
790 for (i = 0; i < sz; ++i) (*solution)[i + 1] = ss.board[i] + '0';
791 (*solution)[sz + 1] = '\0';
792 /* We don't need the \0 for execute_move (the only user)
793 * I'm just being printf-friendly in case I wanna print */
803 static int *make_dsf(int *dsf, int *board, const int w, const int h) {
804 const int sz = w * h;
808 dsf = snew_dsf(w * h);
810 dsf_init(dsf, w * h);
812 for (i = 0; i < sz; ++i) {
814 for (j = 0; j < 4; ++j) {
815 const int x = (i % w) + dx[j];
816 const int y = (i / w) + dy[j];
817 const int k = w*y + x;
818 if (x < 0 || x >= w || y < 0 || y >= h) continue;
819 if (board[i] == board[k]) dsf_merge(dsf, i, k);
826 static int filled(int *board, int *randomize, int k, int n) {
828 if (board == NULL) return FALSE;
829 if (randomize == NULL) return FALSE;
830 if (k > n) return FALSE;
831 for (i = 0; i < k; ++i) if (board[randomize[i]] == 0) return FALSE;
832 for (; i < n; ++i) if (board[randomize[i]] != 0) return FALSE;
838 static int compare(const void *pa, const void *pb) {
839 if (!g_board) return 0;
840 return g_board[*(const int *)pb] - g_board[*(const int *)pa];
843 static void minimize_clue_set(int *board, int w, int h, int *randomize) {
844 const int sz = w * h;
846 int *board_cp = snewn(sz, int);
847 memcpy(board_cp, board, sz * sizeof (int));
849 /* since more clues only helps and never hurts, one pass will do
850 * just fine: if we can remove clue n with k clues of index > n,
851 * we could have removed clue n with >= k clues of index > n.
852 * So an additional pass wouldn't do anything [use induction]. */
853 for (i = 0; i < sz; ++i) {
854 if (board[randomize[i]] == EMPTY) continue;
855 board[randomize[i]] = EMPTY;
856 /* (rot.) symmetry tends to include _way_ too many hints */
857 /* board[sz - randomize[i] - 1] = EMPTY; */
858 if (!solver(board, w, h, NULL)) {
859 board[randomize[i]] = board_cp[randomize[i]];
860 /* board[sz - randomize[i] - 1] =
861 board_cp[sz - randomize[i] - 1]; */
868 static char *new_game_desc(game_params *params, random_state *rs,
869 char **aux, int interactive)
871 const int w = params->w;
872 const int h = params->h;
873 const int sz = w * h;
874 int *board = snewn(sz, int);
875 int *randomize = snewn(sz, int);
876 char *game_description = snewn(sz + 1, char);
879 for (i = 0; i < sz; ++i) {
884 make_board(board, w, h, rs);
886 qsort(randomize, sz, sizeof (int), compare);
887 minimize_clue_set(board, w, h, randomize);
889 for (i = 0; i < sz; ++i) {
890 assert(board[i] >= 0);
891 assert(board[i] < 10);
892 game_description[i] = board[i] + '0';
894 game_description[sz] = '\0';
897 solver(board, w, h, aux);
898 print_board(board, w, h);
904 return game_description;
907 static char *validate_desc(game_params *params, char *desc)
910 const int sz = params->w * params->h;
911 const char m = '0' + max(max(params->w, params->h), 3);
913 printv("desc = '%s'; sz = %d\n", desc, sz);
915 for (i = 0; desc[i] && i < sz; ++i)
916 if (!isdigit((unsigned char) *desc))
917 return "non-digit in string";
918 else if (desc[i] > m)
919 return "too large digit in string";
920 if (desc[i]) return "string too long";
921 else if (i < sz) return "string too short";
925 static game_state *new_game(midend *me, game_params *params, char *desc)
927 game_state *state = snew(game_state);
928 int sz = params->w * params->h;
931 state->cheated = state->completed = FALSE;
932 state->shared = snew(struct shared_state);
933 state->shared->refcnt = 1;
934 state->shared->params = *params; /* struct copy */
935 state->shared->clues = snewn(sz, int);
936 for (i = 0; i < sz; ++i) state->shared->clues[i] = desc[i] - '0';
937 state->board = memdup(state->shared->clues, sz, sizeof (int));
942 static game_state *dup_game(game_state *state)
944 const int sz = state->shared->params.w * state->shared->params.h;
945 game_state *ret = snew(game_state);
947 ret->board = memdup(state->board, sz, sizeof (int));
948 ret->shared = state->shared;
949 ret->cheated = state->cheated;
950 ret->completed = state->completed;
951 ++ret->shared->refcnt;
956 static void free_game(game_state *state)
960 if (--state->shared->refcnt == 0) {
961 sfree(state->shared->clues);
962 sfree(state->shared);
967 static char *solve_game(game_state *state, game_state *currstate,
968 char *aux, char **error)
971 const int w = state->shared->params.w;
972 const int h = state->shared->params.h;
973 if (!solver(state->board, w, h, &aux))
974 *error = "Sorry, I couldn't find a solution";
979 /*****************************************************************************
980 * USER INTERFACE STATE AND ACTION *
981 *****************************************************************************/
984 int *sel; /* w*h highlighted squares, or NULL */
987 static game_ui *new_ui(game_state *state)
989 game_ui *ui = snew(game_ui);
996 static void free_ui(game_ui *ui)
1003 static char *encode_ui(game_ui *ui)
1008 static void decode_ui(game_ui *ui, char *encoding)
1012 static void game_changed_state(game_ui *ui, game_state *oldstate,
1013 game_state *newstate)
1015 /* Clear any selection */
1022 #define PREFERRED_TILE_SIZE 32
1023 #define TILE_SIZE (ds->tilesize)
1024 #define BORDER (TILE_SIZE / 2)
1025 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1027 struct game_drawstate {
1028 struct game_params params;
1032 int *dsf_scratch, *border_scratch;
1035 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1036 int x, int y, int button)
1038 const int w = state->shared->params.w;
1039 const int h = state->shared->params.h;
1041 const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1042 const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1050 button &= ~MOD_MASK;
1052 if (button == LEFT_BUTTON || button == LEFT_DRAG) {
1053 /* A left-click anywhere will clear the current selection. */
1054 if (button == LEFT_BUTTON) {
1060 if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
1062 ui->sel = snewn(w*h, int);
1063 memset(ui->sel, 0, w*h*sizeof(int));
1065 if (!state->shared->clues[w*ty+tx])
1066 ui->sel[w*ty+tx] = 1;
1068 return ""; /* redraw */
1071 if (!ui->sel) return NULL;
1082 if (!isdigit(button)) return NULL;
1084 if (button > (w == 2 && h == 2? 3: max(w, h))) return NULL;
1087 for (i = 0; i < w*h; i++) {
1090 assert(state->shared->clues[i] == 0);
1091 if (state->board[i] != button) {
1092 sprintf(buf, "%s%d", move ? "," : "", i);
1094 move = srealloc(move, strlen(move)+strlen(buf)+1);
1097 move = smalloc(strlen(buf)+1);
1105 sprintf(buf, "_%d", button);
1106 move = srealloc(move, strlen(move)+strlen(buf)+1);
1111 /* Need to update UI at least, as we cleared the selection */
1112 return move ? move : "";
1115 static game_state *execute_move(game_state *state, char *move)
1117 game_state *new_state;
1118 const int sz = state->shared->params.w * state->shared->params.h;
1122 new_state = dup_game(state);
1123 for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0';
1124 new_state->cheated = TRUE;
1127 char *endptr, *delim = strchr(move, '_');
1128 if (!delim) return NULL;
1129 value = strtol(delim+1, &endptr, 0);
1130 if (*endptr || endptr == delim+1) return NULL;
1131 if (value < 0 || value > 9) return NULL;
1132 new_state = dup_game(state);
1134 const int i = strtol(move, &endptr, 0);
1135 if (endptr == move) return NULL;
1136 if (i < 0 || i >= sz) return NULL;
1137 new_state->board[i] = value;
1138 if (*endptr == '_') break;
1139 if (*endptr != ',') return NULL;
1145 * Check for completion.
1147 if (!new_state->completed) {
1148 const int w = new_state->shared->params.w;
1149 const int h = new_state->shared->params.h;
1150 const int sz = w * h;
1151 int *dsf = make_dsf(NULL, new_state->board, w, h);
1153 for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i);
1156 new_state->completed = TRUE;
1162 /* ----------------------------------------------------------------------
1166 #define FLASH_TIME 0.4F
1168 #define COL_CLUE COL_GRID
1179 static void game_compute_size(game_params *params, int tilesize,
1182 *x = (params->w + 1) * tilesize;
1183 *y = (params->h + 1) * tilesize;
1186 static void game_set_size(drawing *dr, game_drawstate *ds,
1187 game_params *params, int tilesize)
1189 ds->tilesize = tilesize;
1192 static float *game_colours(frontend *fe, int *ncolours)
1194 float *ret = snewn(3 * NCOLOURS, float);
1196 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1198 ret[COL_GRID * 3 + 0] = 0.0F;
1199 ret[COL_GRID * 3 + 1] = 0.0F;
1200 ret[COL_GRID * 3 + 2] = 0.0F;
1202 ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
1203 ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1204 ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1206 ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0];
1207 ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1];
1208 ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2];
1210 ret[COL_ERROR * 3 + 0] = 1.0F;
1211 ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1212 ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1214 ret[COL_USER * 3 + 0] = 0.0F;
1215 ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1216 ret[COL_USER * 3 + 2] = 0.0F;
1218 *ncolours = NCOLOURS;
1222 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1224 struct game_drawstate *ds = snew(struct game_drawstate);
1227 ds->tilesize = PREFERRED_TILE_SIZE;
1229 ds->params = state->shared->params;
1230 ds->v = snewn(ds->params.w * ds->params.h, int);
1231 ds->flags = snewn(ds->params.w * ds->params.h, int);
1232 for (i = 0; i < ds->params.w * ds->params.h; i++)
1233 ds->v[i] = ds->flags[i] = -1;
1234 ds->border_scratch = snewn(ds->params.w * ds->params.h, int);
1235 ds->dsf_scratch = NULL;
1240 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1244 sfree(ds->border_scratch);
1245 sfree(ds->dsf_scratch);
1249 #define BORDER_U 0x001
1250 #define BORDER_D 0x002
1251 #define BORDER_L 0x004
1252 #define BORDER_R 0x008
1253 #define BORDER_UR 0x010
1254 #define BORDER_DR 0x020
1255 #define BORDER_UL 0x040
1256 #define BORDER_DL 0x080
1257 #define CURSOR_BG 0x100
1258 #define CORRECT_BG 0x200
1259 #define ERROR_BG 0x400
1260 #define USER_COL 0x800
1262 static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
1269 * Clip to the grid square.
1271 clip(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1272 TILE_SIZE, TILE_SIZE);
1278 BORDER + x*TILE_SIZE,
1279 BORDER + y*TILE_SIZE,
1282 (flags & CURSOR_BG ? COL_HIGHLIGHT :
1283 flags & ERROR_BG ? COL_ERROR :
1284 flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
1287 * Draw the grid lines.
1289 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1290 BORDER + (x+1)*TILE_SIZE, BORDER + y*TILE_SIZE, COL_GRID);
1291 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1292 BORDER + x*TILE_SIZE, BORDER + (y+1)*TILE_SIZE, COL_GRID);
1302 (x + 1) * TILE_SIZE,
1303 (y + 1) * TILE_SIZE,
1306 ALIGN_VCENTRE | ALIGN_HCENTRE,
1307 flags & USER_COL ? COL_USER : COL_CLUE,
1312 * Draw bold lines around the borders.
1314 if (flags & BORDER_L)
1316 BORDER + x*TILE_SIZE + 1,
1317 BORDER + y*TILE_SIZE + 1,
1321 if (flags & BORDER_U)
1323 BORDER + x*TILE_SIZE + 1,
1324 BORDER + y*TILE_SIZE + 1,
1328 if (flags & BORDER_R)
1330 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1331 BORDER + y*TILE_SIZE + 1,
1335 if (flags & BORDER_D)
1337 BORDER + x*TILE_SIZE + 1,
1338 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1342 if (flags & BORDER_UL)
1344 BORDER + x*TILE_SIZE + 1,
1345 BORDER + y*TILE_SIZE + 1,
1349 if (flags & BORDER_UR)
1351 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1352 BORDER + y*TILE_SIZE + 1,
1356 if (flags & BORDER_DL)
1358 BORDER + x*TILE_SIZE + 1,
1359 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1363 if (flags & BORDER_DR)
1365 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1366 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1374 BORDER + x*TILE_SIZE,
1375 BORDER + y*TILE_SIZE,
1380 static void draw_grid(drawing *dr, game_drawstate *ds, game_state *state,
1381 game_ui *ui, int flashy, int borders, int shading)
1383 const int w = state->shared->params.w;
1384 const int h = state->shared->params.h;
1389 * Build a dsf for the board in its current state, to use for
1390 * highlights and hints.
1392 ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h);
1395 * Work out where we're putting borders between the cells.
1397 for (y = 0; y < w*h; y++)
1398 ds->border_scratch[y] = 0;
1400 for (y = 0; y < h; y++)
1401 for (x = 0; x < w; x++) {
1405 for (dx = 0; dx <= 1; dx++) {
1410 if (x+dx >= w || y+dy >= h)
1413 v1 = state->board[y*w+x];
1414 v2 = state->board[(y+dy)*w+(x+dx)];
1415 s1 = dsf_size(ds->dsf_scratch, y*w+x);
1416 s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx));
1419 * We only ever draw a border between two cells if
1420 * they don't have the same contents.
1424 * But in that situation, we don't always draw
1425 * a border. We do if the two cells both
1426 * contain actual numbers...
1432 * ... or if at least one of them is a
1433 * completed or overfull omino.
1442 ds->border_scratch[y*w+x] |= (dx ? 1 : 2);
1447 * Actually do the drawing.
1449 for (y = 0; y < h; ++y)
1450 for (x = 0; x < w; ++x) {
1452 * Determine what we need to draw in this square.
1454 int v = state->board[y*w+x];
1457 if (flashy || !shading) {
1458 /* clear all background flags */
1459 } else if (ui->sel && ui->sel[y*w+x]) {
1462 int size = dsf_size(ds->dsf_scratch, y*w+x);
1464 flags |= CORRECT_BG;
1470 * Borders at the very edges of the grid are
1471 * independent of the `borders' flag.
1483 if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1))
1485 if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2))
1487 if (x == w-1 || (ds->border_scratch[y*w+x] & 1))
1489 if (y == h-1 || (ds->border_scratch[y*w+x] & 2))
1492 if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)]))
1494 if (y > 0 && x < w-1 &&
1495 ((ds->border_scratch[(y-1)*w+x] & 1) ||
1496 (ds->border_scratch[(y-1)*w+(x+1)] & 2)))
1498 if (y < h-1 && x > 0 &&
1499 ((ds->border_scratch[y*w+(x-1)] & 2) ||
1500 (ds->border_scratch[(y+1)*w+(x-1)] & 1)))
1502 if (y < h-1 && x < w-1 &&
1503 ((ds->border_scratch[y*w+(x+1)] & 2) ||
1504 (ds->border_scratch[(y+1)*w+x] & 1)))
1508 if (!state->shared->clues[y*w+x])
1511 if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) {
1512 draw_square(dr, ds, x, y, v, flags);
1514 ds->flags[y*w+x] = flags;
1519 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1520 game_state *state, int dir, game_ui *ui,
1521 float animtime, float flashtime)
1523 const int w = state->shared->params.w;
1524 const int h = state->shared->params.h;
1528 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3);
1532 * The initial contents of the window are not guaranteed and
1533 * can vary with front ends. To be on the safe side, all games
1534 * should start by drawing a big background-colour rectangle
1535 * covering the whole window.
1537 draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
1541 * Smaller black rectangle which is the main grid.
1543 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1544 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1545 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1548 draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
1553 draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE);
1556 static float game_anim_length(game_state *oldstate, game_state *newstate,
1557 int dir, game_ui *ui)
1562 static float game_flash_length(game_state *oldstate, game_state *newstate,
1563 int dir, game_ui *ui)
1567 assert(newstate->shared);
1568 assert(oldstate->shared == newstate->shared);
1569 if (!oldstate->completed && newstate->completed &&
1570 !oldstate->cheated && !newstate->cheated)
1575 static int game_timing_state(game_state *state, game_ui *ui)
1580 static void game_print_size(game_params *params, float *x, float *y)
1585 * I'll use 6mm squares by default.
1587 game_compute_size(params, 600, &pw, &ph);
1592 static void game_print(drawing *dr, game_state *state, int tilesize)
1594 const int w = state->shared->params.w;
1595 const int h = state->shared->params.h;
1598 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1599 game_drawstate *ds = game_new_drawstate(dr, state);
1600 game_set_size(dr, ds, NULL, tilesize);
1602 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1603 c = print_mono_colour(dr, 0); assert(c == COL_GRID);
1604 c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT);
1605 c = print_mono_colour(dr, 1); assert(c == COL_CORRECT);
1606 c = print_mono_colour(dr, 1); assert(c == COL_ERROR);
1607 c = print_mono_colour(dr, 0); assert(c == COL_USER);
1612 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1613 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1614 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1618 * We'll draw borders between the ominoes iff the grid is not
1619 * pristine. So scan it to see if it is.
1622 for (i = 0; i < w*h; i++)
1623 if (state->board[i] && !state->shared->clues[i])
1629 print_line_width(dr, TILE_SIZE / 64);
1630 draw_grid(dr, ds, state, NULL, FALSE, borders, FALSE);
1635 game_free_drawstate(dr, ds);
1639 #define thegame filling
1642 const struct game thegame = {
1643 "Filling", "games.filling", "filling",
1650 TRUE, game_configure, custom_params,
1658 TRUE, game_can_format_as_text_now, game_text_format,
1666 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1669 game_free_drawstate,
1673 TRUE, FALSE, game_print_size, game_print,
1674 FALSE, /* wants_statusbar */
1675 FALSE, game_timing_state,
1676 REQUIRE_NUMPAD, /* flags */
1679 #ifdef STANDALONE_SOLVER /* solver? hah! */
1681 int main(int argc, char **argv) {
1683 game_params *params;
1688 for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc);
1689 if (*desc == '\0') {
1690 fprintf(stderr, "bad puzzle id: %s", par);
1696 params = snew(game_params);
1697 decode_params(params, par);
1698 state = new_game(NULL, params, desc);
1699 if (solver(state->board, params->w, params->h, NULL))
1700 printf("%s:%s: solvable\n", par, desc);
1702 printf("%s:%s: not solvable\n", par, desc);