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
);