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.
63 struct game_params params
;
70 struct shared_state
*shared
;
71 int completed
, cheated
;
74 static const struct game_params defaults
[3] = {{5, 5}, {7, 7}, {9, 9}};
76 static game_params
*default_params(void)
78 game_params
*ret
= snew(game_params
);
80 *ret
= defaults
[1]; /* struct copy */
85 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
89 if (i
< 0 || i
>= lenof(defaults
)) return FALSE
;
90 *params
= snew(game_params
);
91 **params
= defaults
[i
]; /* struct copy */
92 sprintf(buf
, "%dx%d", defaults
[i
].w
, defaults
[i
].h
);
98 static void free_params(game_params
*params
)
103 static game_params
*dup_params(game_params
*params
)
105 game_params
*ret
= snew(game_params
);
106 *ret
= *params
; /* struct copy */
110 static void decode_params(game_params
*ret
, char const *string
)
112 ret
->w
= ret
->h
= atoi(string
);
113 while (*string
&& isdigit((unsigned char) *string
)) ++string
;
114 if (*string
== 'x') ret
->h
= atoi(++string
);
117 static char *encode_params(game_params
*params
, int full
)
120 sprintf(buf
, "%dx%d", params
->w
, params
->h
);
124 static config_item
*game_configure(game_params
*params
)
129 ret
= snewn(3, config_item
);
131 ret
[0].name
= "Width";
132 ret
[0].type
= C_STRING
;
133 sprintf(buf
, "%d", params
->w
);
134 ret
[0].sval
= dupstr(buf
);
137 ret
[1].name
= "Height";
138 ret
[1].type
= C_STRING
;
139 sprintf(buf
, "%d", params
->h
);
140 ret
[1].sval
= dupstr(buf
);
151 static game_params
*custom_params(config_item
*cfg
)
153 game_params
*ret
= snew(game_params
);
155 ret
->w
= atoi(cfg
[0].sval
);
156 ret
->h
= atoi(cfg
[1].sval
);
161 static char *validate_params(game_params
*params
, int full
)
163 if (params
->w
< 1) return "Width must be at least one";
164 if (params
->h
< 1) return "Height must be at least one";
169 /*****************************************************************************
170 * STRINGIFICATION OF GAME STATE *
171 *****************************************************************************/
175 /* Example of plaintext rendering:
176 * +---+---+---+---+---+---+---+
177 * | 6 | | | 2 | | | 2 |
178 * +---+---+---+---+---+---+---+
179 * | | 3 | | 6 | | 3 | |
180 * +---+---+---+---+---+---+---+
181 * | 3 | | | | | | 1 |
182 * +---+---+---+---+---+---+---+
183 * | | 2 | 3 | | 4 | 2 | |
184 * +---+---+---+---+---+---+---+
185 * | 2 | | | | | | 3 |
186 * +---+---+---+---+---+---+---+
187 * | | 5 | | 1 | | 4 | |
188 * +---+---+---+---+---+---+---+
189 * | 4 | | | 3 | | | 3 |
190 * +---+---+---+---+---+---+---+
192 * This puzzle instance is taken from the nikoli website
193 * Encoded (unsolved and solved), the strings are these:
194 * 7x7:6002002030603030000010230420200000305010404003003
195 * 7x7:6662232336663232331311235422255544325413434443313
197 static char *board_to_string(int *board
, int w
, int h
) {
198 const int sz
= w
* h
;
199 const int chw
= (4*w
+ 2); /* +2 for trailing '+' and '\n' */
200 const int chh
= (2*h
+ 1); /* +1: n fence segments, n+1 posts */
201 const int chlen
= chw
* chh
;
202 char *repr
= snewn(chlen
+ 1, char);
207 /* build the first line ("^(\+---){n}\+$") */
208 for (i
= 0; i
< w
; ++i
) {
215 repr
[4*i
+ 1] = '\n';
217 /* ... and copy it onto the odd-numbered lines */
218 for (i
= 0; i
< h
; ++i
) memcpy(repr
+ (2*i
+ 2) * chw
, repr
, chw
);
220 /* build the second line ("^(\|\t){n}\|$") */
221 for (i
= 0; i
< w
; ++i
) {
222 repr
[chw
+ 4*i
+ 0] = '|';
223 repr
[chw
+ 4*i
+ 1] = ' ';
224 repr
[chw
+ 4*i
+ 2] = ' ';
225 repr
[chw
+ 4*i
+ 3] = ' ';
227 repr
[chw
+ 4*i
+ 0] = '|';
228 repr
[chw
+ 4*i
+ 1] = '\n';
230 /* ... and copy it onto the even-numbered lines */
231 for (i
= 1; i
< h
; ++i
) memcpy(repr
+ (2*i
+ 1) * chw
, repr
+ chw
, chw
);
233 /* fill in the numbers */
234 for (i
= 0; i
< sz
; ++i
) {
237 if (board
[i
] == EMPTY
) continue;
238 repr
[chw
*(2*y
+ 1) + (4*x
+ 2)] = board
[i
] + '0';
245 static char *game_text_format(game_state
*state
)
247 const int w
= state
->shared
->params
.w
;
248 const int h
= state
->shared
->params
.h
;
249 return board_to_string(state
->board
, w
, h
);
252 /*****************************************************************************
253 * GAME GENERATION AND SOLVER *
254 *****************************************************************************/
256 static const int dx
[4] = {-1, 1, 0, 0};
257 static const int dy
[4] = {0, 0, -1, 1};
260 static void print_board(int *board, int w, int h) {
261 char *repr = board_to_string(board, w, h);
269 /* determines whether a board (in dsf form) is valid. If possible,
270 * return a conflicting pair in *a and *b and a non-*b neighbour of *a
271 * in *c. If not possible, leave them unmodified. */
273 validate_board(int *dsf
, int w
, int h
, int *sq
, int *a
, int *b
, int *c
) {
274 const int sz
= w
* h
;
276 assert(*a
== SENTINEL
);
277 assert(*b
== SENTINEL
);
278 assert(*c
== SENTINEL
);
279 for (i
= 0; i
< sz
&& *a
== sz
; ++i
) {
280 const int aa
= dsf_canonify(dsf
, sq
[i
]);
283 for (j
= 0; j
< 4; ++j
) {
284 const int x
= (sq
[i
] % w
) + dx
[j
];
285 const int y
= (sq
[i
] / w
) + dy
[j
];
287 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
) continue;
288 bb
= dsf_canonify(dsf
, w
*y
+ x
);
289 if (aa
== bb
) continue;
290 else if (dsf_size(dsf
, aa
) == dsf_size(dsf
, bb
)) {
294 } else if (cc
== sz
) *c
= cc
= bb
;
299 static game_state
*new_game(midend
*, game_params
*, char *);
300 static void free_game(game_state
*);
302 /* generate a random valid board; uses validate_board. */
303 void make_board(int *board
, int w
, int h
, random_state
*rs
) {
306 const unsigned int sz
= w
* h
;
308 /* w=h=2 is a special case which requires a number > max(w, h) */
309 /* TODO prove that this is the case ONLY for w=h=2. */
310 const int maxsize
= min(max(max(w
, h
), 3), 9);
312 /* Note that if 1 in {w, h} then it's impossible to have a region
313 * of size > w*h, so the special case only affects w=h=2. */
324 dsf
= snew_dsf(sz
); /* implicit dsf_init */
326 /* I abuse the board variable: when generating the puzzle, it
327 * contains a shuffled list of numbers {0, ..., nsq-1}. */
328 for (i
= 0; i
< sz
; ++i
) board
[i
] = i
;
332 shuffle(board
, sz
, sizeof (int), rs
);
333 /* while the board can in principle be fixed */
338 validate_board(dsf
, w
, h
, board
, &a
, &b
, &c
);
339 if (a
== SENTINEL
/* meaning the board is valid */) {
341 for (i
= 0; i
< sz
; ++i
) board
[i
] = dsf_size(dsf
, i
);
343 /* printf("returning board number %d\n", nboards); */
346 /* try to repair the invalid board */
347 a
= dsf_canonify(dsf
, a
);
348 assert(a
!= dsf_canonify(dsf
, b
));
349 if (c
!= sz
) assert(a
!= dsf_canonify(dsf
, c
));
350 dsf_merge(dsf
, a
, c
== sz? b
: c
);
351 /* if repair impossible; make a new board */
352 if (dsf_size(dsf
, a
) > maxsize
) break;
355 dsf_init(dsf
, sz
); /* re-init the dsf */
357 assert(FALSE
); /* unreachable */
360 static int rhofree(int *hop
, int start
) {
361 int turtle
= start
, rabbit
= hop
[start
];
362 while (rabbit
!= turtle
) { /* find a cycle */
363 turtle
= hop
[turtle
];
364 rabbit
= hop
[hop
[rabbit
]];
366 do { /* check that start is in the cycle */
367 rabbit
= hop
[rabbit
];
368 if (start
== rabbit
) return 1;
369 } while (rabbit
!= turtle
);
373 static void merge(int *dsf
, int *connected
, int a
, int b
) {
377 assert(rhofree(connected
, a
));
378 assert(rhofree(connected
, b
));
379 a
= dsf_canonify(dsf
, a
);
380 b
= dsf_canonify(dsf
, b
);
382 dsf_merge(dsf
, a
, b
);
384 connected
[a
] = connected
[b
];
386 assert(rhofree(connected
, a
));
387 assert(rhofree(connected
, b
));
390 static void *memdup(const void *ptr
, size_t len
, size_t esz
) {
391 void *dup
= smalloc(len
* esz
);
393 memcpy(dup
, ptr
, len
* esz
);
397 static void expand(int *board
, int *connected
, int *dsf
, int w
, int h
,
398 int dst
, int src
, int *empty
, int *learn
) {
405 assert(board
[dst
] == EMPTY
);
406 assert(board
[src
] != EMPTY
);
407 board
[dst
] = board
[src
];
408 for (j
= 0; j
< 4; ++j
) {
409 const int x
= (dst
% w
) + dx
[j
];
410 const int y
= (dst
/ w
) + dy
[j
];
411 const int idx
= w
*y
+ x
;
412 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
) continue;
413 if (board
[idx
] != board
[dst
]) continue;
414 merge(dsf
, connected
, dst
, idx
);
416 /* printf("set board[%d] = board[%d], which is %d; size(%d) = %d\n", dst, src, board[src], src, dsf[dsf_canonify(dsf, src)] >> 2); */
421 static void flood(int *board
, int w
, int h
, int i
, int n
) {
422 const int sz
= w
* h
;
425 if (board
[i
] == EMPTY
) board
[i
] = -SENTINEL
;
426 else if (board
[i
] == n
) board
[i
] = -board
[i
];
429 for (k
= 0; k
< 4; ++k
) {
430 const int x
= (i
% w
) + dx
[k
];
431 const int y
= (i
/ w
) + dy
[k
];
432 const int idx
= w
*y
+ x
;
433 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
) continue;
434 flood(board
, w
, h
, idx
, n
);
438 static int count_and_clear(int *board
, int sz
) {
441 for (i
= 0; i
< sz
; ++i
) {
442 if (board
[i
] >= 0) continue;
444 if (board
[i
] == -SENTINEL
) board
[i
] = EMPTY
;
445 else board
[i
] = -board
[i
];
450 static int count(int *board
, int w
, int h
, int i
) {
451 flood(board
, w
, h
, i
, board
[i
]);
452 return count_and_clear(board
, w
* h
);
455 static int expandsize(const int *board
, int *dsf
, int w
, int h
, int i
, int n
) {
460 for (j
= 0; j
< 4; ++j
) {
461 const int x
= (i
% w
) + dx
[j
];
462 const int y
= (i
/ w
) + dy
[j
];
463 const int idx
= w
*y
+ x
;
466 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
) continue;
467 if (board
[idx
] != n
) continue;
468 root
= dsf_canonify(dsf
, idx
);
469 for (m
= 0; m
< nhits
&& root
!= hits
[m
]; ++m
);
470 if (m
< nhits
) continue;
471 /* printf("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2); */
472 size
+= dsf_size(dsf
, root
);
473 assert(dsf_size(dsf
, root
) >= 1);
474 hits
[nhits
++] = root
;
480 * +---+---+---+---+---+---+---+
481 * | 6 | | | 2 | | | 2 |
482 * +---+---+---+---+---+---+---+
483 * | | 3 | | 6 | | 3 | |
484 * +---+---+---+---+---+---+---+
485 * | 3 | | | | | | 1 |
486 * +---+---+---+---+---+---+---+
487 * | | 2 | 3 | | 4 | 2 | |
488 * +---+---+---+---+---+---+---+
489 * | 2 | | | | | | 3 |
490 * +---+---+---+---+---+---+---+
491 * | | 5 | | 1 | | 4 | |
492 * +---+---+---+---+---+---+---+
493 * | 4 | | | 3 | | | 3 |
494 * +---+---+---+---+---+---+---+
497 /* Solving techniques:
499 * CONNECTED COMPONENT FORCED EXPANSION (too big):
500 * When a CC can only be expanded in one direction, because all the
501 * other ones would make the CC too big.
502 * +---+---+---+---+---+
503 * | 2 | 2 | | 2 | _ |
504 * +---+---+---+---+---+
506 * CONNECTED COMPONENT FORCED EXPANSION (too small):
507 * When a CC must include a particular square, because otherwise there
508 * would not be enough room to complete it.
514 * When an empty square has no neighbouring empty squares and only a 1
515 * will go into the square (or other CCs would be too big).
520 * TODO: generalise DROPPING IN A ONE: find the size of the CC of
521 * empty squares and a list of all adjacent numbers. See if only one
522 * number in {1, ..., size} u {all adjacent numbers} is possible.
523 * Probably this is only effective for a CC size < n for some n (4?)
525 * TODO: backtracking.
527 #define EXPAND(a, b)\
528 expand(board, connected, dsf, w, h, a, b, &nempty, &learn)
530 static int solver(const int *orig
, int w
, int h
, char **solution
) {
531 const int sz
= w
* h
;
533 int *board
= memdup(orig
, sz
, sizeof (int));
534 int *dsf
= snew_dsf(sz
); /* eqv classes: connected components */
535 int *connected
= snewn(sz
, int); /* connected[n] := n.next; */
536 /* cyclic disjoint singly linked lists, same partitioning as dsf.
537 * The lists lets you iterate over a partition given any member */
544 for (i
= 0; i
< sz
; i
++) connected
[i
] = i
;
546 for (i
= 0; i
< sz
; ++i
) {
548 if (board
[i
] == EMPTY
) ++nempty
;
549 else for (j
= 0; j
< 4; ++j
) {
550 const int x
= (i
% w
) + dx
[j
];
551 const int y
= (i
/ w
) + dy
[j
];
552 const int idx
= w
*y
+ x
;
553 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
) continue;
554 if (board
[i
] == board
[idx
]) merge(dsf
, connected
, i
, idx
);
558 /* puts("trying to solve this:");
559 print_board(board, w, h); */
561 /* TODO: refactor this code, it's too long */
566 /* for every connected component */
567 for (i
= 0; i
< sz
; ++i
) {
571 /* If the component consists of empty squares */
572 if (board
[i
] == EMPTY
) {
575 for (k
= 0; k
< 4; ++k
) {
576 const int x
= (i
% w
) + dx
[k
];
577 const int y
= (i
/ w
) + dy
[k
];
578 const int idx
= w
*y
+ x
;
580 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
) continue;
581 if (board
[idx
] == EMPTY
) {
587 (board
[idx
] >= expandsize(board
, dsf
, w
, h
,
590 assert(board
[i
] == EMPTY
);
591 board
[i
] = -SENTINEL
;
592 n
= count(board
, w
, h
, idx
);
593 assert(board
[i
] == EMPTY
);
594 if (n
>= board
[idx
]) continue;
599 assert(board
[i
] == EMPTY
);
607 /* printf("expanding blob of (%d, %d)\n", i % w, i / w); */
609 j
= dsf_canonify(dsf
, i
);
611 /* (but only for each connected component) */
612 if (i
!= j
) continue;
614 /* (and not if it's already complete) */
615 if (dsf_size(dsf
, j
) == board
[j
]) continue;
617 /* for each square j _in_ the connected component */
620 /* printf(" looking at (%d, %d)\n", j % w, j / w); */
622 /* for each neighbouring square (idx) */
623 for (k
= 0; k
< 4; ++k
) {
624 const int x
= (j
% w
) + dx
[k
];
625 const int y
= (j
/ w
) + dy
[k
];
626 const int idx
= w
*y
+ x
;
631 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
) continue;
632 if (board
[idx
] != EMPTY
) continue;
633 if (exp
== idx
) continue;
634 /* printf("\ttrying to expand onto (%d, %d)\n", x, y); */
636 /* find out the would-be size of the new connected
637 * component if we actually expanded into idx */
640 for (l = 0; l < 4; ++l) {
641 const int lx = x + dx[l];
642 const int ly = y + dy[l];
643 const int idxl = w*ly + lx;
646 if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
647 if (board[idxl] != board[j]) continue;
648 root = dsf_canonify(dsf, idxl);
649 for (m = 0; m < nhits && root != hits[m]; ++m);
650 if (m != nhits) continue;
651 // printf("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);
652 size += dsf_size(dsf, root);
653 assert(dsf_size(dsf, root) >= 1);
654 hits[nhits++] = root;
658 size
= expandsize(board
, dsf
, w
, h
, idx
, board
[j
]);
660 /* ... and see if that size is too big, or if we
661 * have other expansion candidates. Otherwise
662 * remember the (so far) only candidate. */
664 /* printf("\tthat would give a size of %d\n", size); */
665 if (size
> board
[j
]) continue;
666 /* printf("\tnow knowing %d expansions\n", nexpand + 1); */
667 if (exp
!= SENTINEL
) goto next_i
;
672 j
= connected
[j
]; /* next square in the same CC */
673 assert(board
[i
] == board
[j
]);
675 /* end: for each square j _in_ the connected component */
677 if (exp
== SENTINEL
) continue;
678 /* printf("expand b: %d -> %d\n", i, exp); */
684 /* end: for each connected component */
685 } while (learn
&& nempty
);
687 /* puts("best guess:");
688 print_board(board, w, h); */
692 assert(*solution
== NULL
);
693 *solution
= snewn(sz
+ 2, char);
695 for (i
= 0; i
< sz
; ++i
) (*solution
)[i
+ 1] = board
[i
] + '0';
696 (*solution
)[sz
+ 1] = '\0';
697 /* We don't need the \0 for execute_move (the only user)
698 * I'm just being printf-friendly in case I wanna print */
708 static int *make_dsf(int *dsf
, int *board
, const int w
, const int h
) {
709 const int sz
= w
* h
;
713 dsf
= snew_dsf(w
* h
);
715 dsf_init(dsf
, w
* h
);
717 for (i
= 0; i
< sz
; ++i
) {
719 for (j
= 0; j
< 4; ++j
) {
720 const int x
= (i
% w
) + dx
[j
];
721 const int y
= (i
/ w
) + dy
[j
];
722 const int k
= w
*y
+ x
;
723 if (x
< 0 || x
>= w
|| y
< 0 || y
>= h
) continue;
724 if (board
[i
] == board
[k
]) dsf_merge(dsf
, i
, k
);
731 static int filled(int *board, int *randomize, int k, int n) {
733 if (board == NULL) return FALSE;
734 if (randomize == NULL) return FALSE;
735 if (k > n) return FALSE;
736 for (i = 0; i < k; ++i) if (board[randomize[i]] == 0) return FALSE;
737 for (; i < n; ++i) if (board[randomize[i]] != 0) return FALSE;
743 static int compare(const void *pa
, const void *pb
) {
744 if (!g_board
) return 0;
745 return g_board
[*(const int *)pb
] - g_board
[*(const int *)pa
];
748 static char *new_game_desc(game_params
*params
, random_state
*rs
,
749 char **aux
, int interactive
)
751 const int w
= params
->w
;
752 const int h
= params
->h
;
753 const int sz
= w
* h
;
754 int *board
= snewn(sz
, int);
755 int *randomize
= snewn(sz
, int);
756 int *solver_board
= snewn(sz
, int);
757 char *game_description
= snewn(sz
+ 1, char);
760 for (i
= 0; i
< sz
; ++i
) {
765 make_board(board
, w
, h
, rs
);
766 memcpy(solver_board
, board
, sz
* sizeof (int));
769 qsort(randomize
, sz
, sizeof (int), compare
);
771 /* since more clues only helps and never hurts, one pass will do
772 * just fine: if we can remove clue n with k clues of index > n,
773 * we could have removed clue n with >= k clues of index > n.
774 * So an additional pass wouldn't do anything [use induction]. */
775 for (i
= 0; i
< sz
; ++i
) {
776 solver_board
[randomize
[i
]] = EMPTY
;
777 if (!solver(solver_board
, w
, h
, NULL
))
778 solver_board
[randomize
[i
]] = board
[randomize
[i
]];
781 for (i
= 0; i
< sz
; ++i
) {
782 assert(solver_board
[i
] >= 0);
783 assert(solver_board
[i
] < 10);
784 game_description
[i
] = solver_board
[i
] + '0';
786 game_description
[sz
] = '\0';
789 solver(solver_board, w, h, aux);
790 print_board(solver_board, w, h);
797 return game_description
;
800 static char *validate_desc(game_params
*params
, char *desc
)
803 const int sz
= params
->w
* params
->h
;
804 const char m
= '0' + max(max(params
->w
, params
->h
), 3);
806 /* printf("desc = '%s'; sz = %d\n", desc, sz); */
808 for (i
= 0; desc
[i
] && i
< sz
; ++i
)
809 if (!isdigit((unsigned char) *desc
))
810 return "non-digit in string";
811 else if (desc
[i
] > m
)
812 return "too large digit in string";
813 if (desc
[i
]) return "string too long";
814 else if (i
< sz
) return "string too short";
818 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
820 game_state
*state
= snew(game_state
);
821 int sz
= params
->w
* params
->h
;
824 state
->cheated
= state
->completed
= FALSE
;
825 state
->shared
= snew(struct shared_state
);
826 state
->shared
->refcnt
= 1;
827 state
->shared
->params
= *params
; /* struct copy */
828 state
->shared
->clues
= snewn(sz
, int);
829 for (i
= 0; i
< sz
; ++i
) state
->shared
->clues
[i
] = desc
[i
] - '0';
830 state
->board
= memdup(state
->shared
->clues
, sz
, sizeof (int));
835 static game_state
*dup_game(game_state
*state
)
837 const int sz
= state
->shared
->params
.w
* state
->shared
->params
.h
;
838 game_state
*ret
= snew(game_state
);
840 ret
->board
= memdup(state
->board
, sz
, sizeof (int));
841 ret
->shared
= state
->shared
;
842 ret
->cheated
= state
->cheated
;
843 ret
->completed
= state
->completed
;
844 ++ret
->shared
->refcnt
;
849 static void free_game(game_state
*state
)
853 if (--state
->shared
->refcnt
== 0) {
854 sfree(state
->shared
->clues
);
855 sfree(state
->shared
);
860 static char *solve_game(game_state
*state
, game_state
*currstate
,
861 char *aux
, char **error
)
864 const int w
= state
->shared
->params
.w
;
865 const int h
= state
->shared
->params
.h
;
866 if (!solver(state
->board
, w
, h
, &aux
))
867 *error
= "Sorry, I couldn't find a solution";
872 /*****************************************************************************
873 * USER INTERFACE STATE AND ACTION *
874 *****************************************************************************/
877 int x
, y
; /* highlighted square, or (-1, -1) if none */
880 static game_ui
*new_ui(game_state
*state
)
882 game_ui
*ui
= snew(game_ui
);
889 static void free_ui(game_ui
*ui
)
894 static char *encode_ui(game_ui
*ui
)
899 static void decode_ui(game_ui
*ui
, char *encoding
)
903 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
904 game_state
*newstate
)
908 #define PREFERRED_TILE_SIZE 32
909 #define TILE_SIZE (ds->tilesize)
910 #define BORDER (TILE_SIZE / 2)
911 #define BORDER_WIDTH (TILE_SIZE / 32)
913 struct game_drawstate
{
914 struct game_params params
;
918 int *dsf_scratch
, *border_scratch
;
921 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
922 int x
, int y
, int button
)
924 const int w
= state
->shared
->params
.w
;
925 const int h
= state
->shared
->params
.h
;
927 const int tx
= (x
+ TILE_SIZE
- BORDER
) / TILE_SIZE
- 1;
928 const int ty
= (y
+ TILE_SIZE
- BORDER
) / TILE_SIZE
- 1;
935 if (tx
>= 0 && tx
< w
&& ty
>= 0 && ty
< h
) {
936 if (button
== LEFT_BUTTON
) {
937 if ((tx
== ui
->x
&& ty
== ui
->y
) || state
->shared
->clues
[w
*ty
+tx
])
939 else ui
->x
= tx
, ui
->y
= ty
;
940 return ""; /* redraw */
944 assert((ui
->x
== -1) == (ui
->y
== -1));
945 if (ui
->x
== -1) return NULL
;
946 assert(state
->shared
->clues
[w
*ui
->y
+ ui
->x
] == 0);
957 if (!isdigit(button
)) return NULL
;
959 if (button
> (w
== 2 && h
== 2?
3: max(w
, h
))) return NULL
;
963 const int i
= w
*ui
->y
+ ui
->x
;
966 if (state
->board
[i
] == button
) {
967 return ""; /* no change - just update ui */
969 sprintf(buf
, "%d_%d", i
, button
);
975 static game_state
*execute_move(game_state
*state
, char *move
)
977 game_state
*new_state
;
980 const int sz
= state
->shared
->params
.w
* state
->shared
->params
.h
;
982 new_state
= dup_game(state
);
983 for (++move
; i
< sz
; ++i
) new_state
->board
[i
] = move
[i
] - '0';
984 new_state
->cheated
= TRUE
;
987 const int i
= strtol(move
, &endptr
, errno
= 0);
989 if (errno
== ERANGE
) return NULL
;
990 if (endptr
== move
) return NULL
;
991 if (*endptr
!= '_') return NULL
;
993 value
= strtol(move
, &endptr
, 0);
994 if (endptr
== move
) return NULL
;
995 if (*endptr
!= '\0') return NULL
;
996 new_state
= dup_game(state
);
997 new_state
->board
[i
] = value
;
1001 * Check for completion.
1003 if (!new_state
->completed
) {
1004 const int w
= new_state
->shared
->params
.w
;
1005 const int h
= new_state
->shared
->params
.h
;
1006 const int sz
= w
* h
;
1007 int *dsf
= make_dsf(NULL
, new_state
->board
, w
, h
);
1009 for (i
= 0; i
< sz
&& new_state
->board
[i
] == dsf_size(dsf
, i
); ++i
);
1012 new_state
->completed
= TRUE
;
1018 /* ----------------------------------------------------------------------
1022 #define FLASH_TIME 0.4F
1024 #define COL_CLUE COL_GRID
1035 static void game_compute_size(game_params
*params
, int tilesize
,
1038 *x
= (params
->w
+ 1) * tilesize
;
1039 *y
= (params
->h
+ 1) * tilesize
;
1042 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1043 game_params
*params
, int tilesize
)
1045 ds
->tilesize
= tilesize
;
1048 static float *game_colours(frontend
*fe
, int *ncolours
)
1050 float *ret
= snewn(3 * NCOLOURS
, float);
1052 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1054 ret
[COL_GRID
* 3 + 0] = 0.0F
;
1055 ret
[COL_GRID
* 3 + 1] = 0.0F
;
1056 ret
[COL_GRID
* 3 + 2] = 0.0F
;
1058 ret
[COL_HIGHLIGHT
* 3 + 0] = 0.85F
* ret
[COL_BACKGROUND
* 3 + 0];
1059 ret
[COL_HIGHLIGHT
* 3 + 1] = 0.85F
* ret
[COL_BACKGROUND
* 3 + 1];
1060 ret
[COL_HIGHLIGHT
* 3 + 2] = 0.85F
* ret
[COL_BACKGROUND
* 3 + 2];
1062 ret
[COL_CORRECT
* 3 + 0] = 0.9F
* ret
[COL_BACKGROUND
* 3 + 0];
1063 ret
[COL_CORRECT
* 3 + 1] = 0.9F
* ret
[COL_BACKGROUND
* 3 + 1];
1064 ret
[COL_CORRECT
* 3 + 2] = 0.9F
* ret
[COL_BACKGROUND
* 3 + 2];
1066 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
1067 ret
[COL_ERROR
* 3 + 1] = 0.85F
* ret
[COL_BACKGROUND
* 3 + 1];
1068 ret
[COL_ERROR
* 3 + 2] = 0.85F
* ret
[COL_BACKGROUND
* 3 + 2];
1070 ret
[COL_USER
* 3 + 0] = 0.0F
;
1071 ret
[COL_USER
* 3 + 1] = 0.6F
* ret
[COL_BACKGROUND
* 3 + 1];
1072 ret
[COL_USER
* 3 + 2] = 0.0F
;
1074 *ncolours
= NCOLOURS
;
1078 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1080 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1083 ds
->tilesize
= PREFERRED_TILE_SIZE
;
1085 ds
->params
= state
->shared
->params
;
1086 ds
->v
= snewn(ds
->params
.w
* ds
->params
.h
, int);
1087 ds
->flags
= snewn(ds
->params
.w
* ds
->params
.h
, int);
1088 for (i
= 0; i
< ds
->params
.w
* ds
->params
.h
; i
++)
1089 ds
->v
[i
] = ds
->flags
[i
] = -1;
1090 ds
->border_scratch
= snewn(ds
->params
.w
* ds
->params
.h
, int);
1091 ds
->dsf_scratch
= NULL
;
1096 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1100 sfree(ds
->border_scratch
);
1101 sfree(ds
->dsf_scratch
);
1105 #define BORDER_U 0x001
1106 #define BORDER_D 0x002
1107 #define BORDER_L 0x004
1108 #define BORDER_R 0x008
1109 #define BORDER_UR 0x010
1110 #define BORDER_DR 0x020
1111 #define BORDER_UL 0x040
1112 #define BORDER_DL 0x080
1113 #define CURSOR_BG 0x100
1114 #define CORRECT_BG 0x200
1115 #define ERROR_BG 0x400
1116 #define USER_COL 0x800
1118 static void draw_square(drawing
*dr
, game_drawstate
*ds
, int x
, int y
,
1125 * Clip to the grid square.
1127 clip(dr
, BORDER
+ x
*TILE_SIZE
, BORDER
+ y
*TILE_SIZE
,
1128 TILE_SIZE
, TILE_SIZE
);
1134 BORDER
+ x
*TILE_SIZE
,
1135 BORDER
+ y
*TILE_SIZE
,
1138 (flags
& CURSOR_BG ? COL_HIGHLIGHT
:
1139 flags
& ERROR_BG ? COL_ERROR
:
1140 flags
& CORRECT_BG ? COL_CORRECT
: COL_BACKGROUND
));
1143 * Draw the grid lines.
1145 draw_line(dr
, BORDER
+ x
*TILE_SIZE
, BORDER
+ y
*TILE_SIZE
,
1146 BORDER
+ (x
+1)*TILE_SIZE
, BORDER
+ y
*TILE_SIZE
, COL_GRID
);
1147 draw_line(dr
, BORDER
+ x
*TILE_SIZE
, BORDER
+ y
*TILE_SIZE
,
1148 BORDER
+ x
*TILE_SIZE
, BORDER
+ (y
+1)*TILE_SIZE
, COL_GRID
);
1158 (x
+ 1) * TILE_SIZE
,
1159 (y
+ 1) * TILE_SIZE
,
1162 ALIGN_VCENTRE
| ALIGN_HCENTRE
,
1163 flags
& USER_COL ? COL_USER
: COL_CLUE
,
1168 * Draw bold lines around the borders.
1170 if (flags
& BORDER_L
)
1172 BORDER
+ x
*TILE_SIZE
+ 1,
1173 BORDER
+ y
*TILE_SIZE
+ 1,
1177 if (flags
& BORDER_U
)
1179 BORDER
+ x
*TILE_SIZE
+ 1,
1180 BORDER
+ y
*TILE_SIZE
+ 1,
1184 if (flags
& BORDER_R
)
1186 BORDER
+ (x
+1)*TILE_SIZE
- BORDER_WIDTH
,
1187 BORDER
+ y
*TILE_SIZE
+ 1,
1191 if (flags
& BORDER_D
)
1193 BORDER
+ x
*TILE_SIZE
+ 1,
1194 BORDER
+ (y
+1)*TILE_SIZE
- BORDER_WIDTH
,
1198 if (flags
& BORDER_UL
)
1200 BORDER
+ x
*TILE_SIZE
+ 1,
1201 BORDER
+ y
*TILE_SIZE
+ 1,
1205 if (flags
& BORDER_UR
)
1207 BORDER
+ (x
+1)*TILE_SIZE
- BORDER_WIDTH
,
1208 BORDER
+ y
*TILE_SIZE
+ 1,
1212 if (flags
& BORDER_DL
)
1214 BORDER
+ x
*TILE_SIZE
+ 1,
1215 BORDER
+ (y
+1)*TILE_SIZE
- BORDER_WIDTH
,
1219 if (flags
& BORDER_DR
)
1221 BORDER
+ (x
+1)*TILE_SIZE
- BORDER_WIDTH
,
1222 BORDER
+ (y
+1)*TILE_SIZE
- BORDER_WIDTH
,
1230 BORDER
+ x
*TILE_SIZE
,
1231 BORDER
+ y
*TILE_SIZE
,
1236 static void draw_grid(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
1237 game_ui
*ui
, int flashy
, int borders
, int shading
)
1239 const int w
= state
->shared
->params
.w
;
1240 const int h
= state
->shared
->params
.h
;
1245 * Build a dsf for the board in its current state, to use for
1246 * highlights and hints.
1248 ds
->dsf_scratch
= make_dsf(ds
->dsf_scratch
, state
->board
, w
, h
);
1251 * Work out where we're putting borders between the cells.
1253 for (y
= 0; y
< w
*h
; y
++)
1254 ds
->border_scratch
[y
] = 0;
1256 for (y
= 0; y
< h
; y
++)
1257 for (x
= 0; x
< w
; x
++) {
1261 for (dx
= 0; dx
<= 1; dx
++) {
1266 if (x
+dx
>= w
|| y
+dy
>= h
)
1269 v1
= state
->board
[y
*w
+x
];
1270 v2
= state
->board
[(y
+dy
)*w
+(x
+dx
)];
1271 s1
= dsf_size(ds
->dsf_scratch
, y
*w
+x
);
1272 s2
= dsf_size(ds
->dsf_scratch
, (y
+dy
)*w
+(x
+dx
));
1275 * We only ever draw a border between two cells if
1276 * they don't have the same contents.
1280 * But in that situation, we don't always draw
1281 * a border. We do if the two cells both
1282 * contain actual numbers...
1288 * ... or if at least one of them is a
1289 * completed or overfull omino.
1298 ds
->border_scratch
[y
*w
+x
] |= (dx ?
1 : 2);
1303 * Actually do the drawing.
1305 for (y
= 0; y
< h
; ++y
)
1306 for (x
= 0; x
< w
; ++x
) {
1308 * Determine what we need to draw in this square.
1310 int v
= state
->board
[y
*w
+x
];
1313 if (flashy
|| !shading
) {
1314 /* clear all background flags */
1315 } else if (x
== ui
->x
&& y
== ui
->y
) {
1318 int size
= dsf_size(ds
->dsf_scratch
, y
*w
+x
);
1320 flags
|= CORRECT_BG
;
1326 * Borders at the very edges of the grid are
1327 * independent of the `borders' flag.
1339 if (x
== 0 || (ds
->border_scratch
[y
*w
+(x
-1)] & 1))
1341 if (y
== 0 || (ds
->border_scratch
[(y
-1)*w
+x
] & 2))
1343 if (x
== w
-1 || (ds
->border_scratch
[y
*w
+x
] & 1))
1345 if (y
== h
-1 || (ds
->border_scratch
[y
*w
+x
] & 2))
1348 if (y
> 0 && x
> 0 && (ds
->border_scratch
[(y
-1)*w
+(x
-1)]))
1350 if (y
> 0 && x
< w
-1 &&
1351 ((ds
->border_scratch
[(y
-1)*w
+x
] & 1) ||
1352 (ds
->border_scratch
[(y
-1)*w
+(x
+1)] & 2)))
1354 if (y
< h
-1 && x
> 0 &&
1355 ((ds
->border_scratch
[y
*w
+(x
-1)] & 2) ||
1356 (ds
->border_scratch
[(y
+1)*w
+(x
-1)] & 1)))
1358 if (y
< h
-1 && x
< w
-1 &&
1359 ((ds
->border_scratch
[y
*w
+(x
+1)] & 2) ||
1360 (ds
->border_scratch
[(y
+1)*w
+x
] & 1)))
1364 if (!state
->shared
->clues
[y
*w
+x
])
1367 if (ds
->v
[y
*w
+x
] != v
|| ds
->flags
[y
*w
+x
] != flags
) {
1368 draw_square(dr
, ds
, x
, y
, v
, flags
);
1370 ds
->flags
[y
*w
+x
] = flags
;
1375 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1376 game_state
*state
, int dir
, game_ui
*ui
,
1377 float animtime
, float flashtime
)
1379 const int w
= state
->shared
->params
.w
;
1380 const int h
= state
->shared
->params
.h
;
1384 (flashtime
<= FLASH_TIME
/3 || flashtime
>= FLASH_TIME
*2/3);
1388 * The initial contents of the window are not guaranteed and
1389 * can vary with front ends. To be on the safe side, all games
1390 * should start by drawing a big background-colour rectangle
1391 * covering the whole window.
1393 draw_rect(dr
, 0, 0, 10*ds
->tilesize
, 10*ds
->tilesize
, COL_BACKGROUND
);
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,
1406 draw_grid(dr
, ds
, state
, ui
, flashy
, TRUE
, TRUE
);
1409 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1410 int dir
, game_ui
*ui
)
1415 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1416 int dir
, game_ui
*ui
)
1420 assert(newstate
->shared
);
1421 assert(oldstate
->shared
== newstate
->shared
);
1422 if (!oldstate
->completed
&& newstate
->completed
&&
1423 !oldstate
->cheated
&& !newstate
->cheated
)
1428 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1433 static void game_print_size(game_params
*params
, float *x
, float *y
)
1438 * I'll use 6mm squares by default.
1440 game_compute_size(params
, 600, &pw
, &ph
);
1445 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1447 const int w
= state
->shared
->params
.w
;
1448 const int h
= state
->shared
->params
.h
;
1451 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1452 game_drawstate
*ds
= game_new_drawstate(dr
, state
);
1453 game_set_size(dr
, ds
, NULL
, tilesize
);
1455 c
= print_mono_colour(dr
, 1); assert(c
== COL_BACKGROUND
);
1456 c
= print_mono_colour(dr
, 0); assert(c
== COL_GRID
);
1457 c
= print_mono_colour(dr
, 1); assert(c
== COL_HIGHLIGHT
);
1458 c
= print_mono_colour(dr
, 1); assert(c
== COL_CORRECT
);
1459 c
= print_mono_colour(dr
, 1); assert(c
== COL_ERROR
);
1460 c
= print_mono_colour(dr
, 0); assert(c
== COL_USER
);
1465 draw_rect(dr
, BORDER
- BORDER_WIDTH
, BORDER
- BORDER_WIDTH
,
1466 w
*TILE_SIZE
+ 2*BORDER_WIDTH
+ 1,
1467 h
*TILE_SIZE
+ 2*BORDER_WIDTH
+ 1,
1471 * We'll draw borders between the ominoes iff the grid is not
1472 * pristine. So scan it to see if it is.
1475 for (i
= 0; i
< w
*h
; i
++)
1476 if (state
->board
[i
] && !state
->shared
->clues
[i
])
1482 print_line_width(dr
, TILE_SIZE
/ 64);
1483 draw_grid(dr
, ds
, state
, NULL
, FALSE
, borders
, FALSE
);
1488 game_free_drawstate(dr
, ds
);
1492 #define thegame filling
1495 const struct game thegame
= {
1496 "Filling", "games.filling", "filling",
1503 TRUE
, game_configure
, custom_params
,
1511 TRUE
, game_text_format
,
1519 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1522 game_free_drawstate
,
1526 TRUE
, FALSE
, game_print_size
, game_print
,
1527 FALSE
, /* wants_statusbar */
1528 FALSE
, game_timing_state
,
1532 #ifdef STANDALONE_SOLVER /* solver? hah! */
1534 int main(int argc
, char **argv
) {
1536 game_params
*params
;
1541 for (par
= desc
= *argv
; *desc
!= '\0' && *desc
!= ':'; ++desc
);
1542 if (*desc
== '\0') {
1543 fprintf(stderr
, "bad puzzle id: %s", par
);
1549 params
= snew(game_params
);
1550 decode_params(params
, par
);
1551 state
= new_game(NULL
, params
, desc
);
1552 if (solver(state
->board
, params
->w
, params
->h
, NULL
))
1553 printf("%s:%s: solvable\n", par
, desc
);
1555 printf("%s:%s: not solvable\n", par
, desc
);