diff options
author | Franklin Wei <git@fwei.tk> | 2017-04-29 18:21:56 -0400 |
---|---|---|
committer | Franklin Wei <git@fwei.tk> | 2017-04-29 18:24:42 -0400 |
commit | 881746789a489fad85aae8317555f73dbe261556 (patch) | |
tree | cec2946362c4698c8db3c10f3242ef546c2c22dd /apps/plugins/puzzles/src/filling.c | |
parent | 03dd4b92be7dcd5c8ab06da3810887060e06abd5 (diff) | |
download | rockbox-881746789a489fad85aae8317555f73dbe261556.tar.gz rockbox-881746789a489fad85aae8317555f73dbe261556.zip |
puzzles: refactor and resync with upstream
This brings puzzles up-to-date with upstream revision
2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made
by me, including cursor-only Untangle and some compilation fixes
remain. Upstream code has been moved to its separate subdirectory and
future syncs can be done by simply copying over the new sources.
Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804
Diffstat (limited to 'apps/plugins/puzzles/src/filling.c')
-rw-r--r-- | apps/plugins/puzzles/src/filling.c | 2179 |
1 files changed, 2179 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/filling.c b/apps/plugins/puzzles/src/filling.c new file mode 100644 index 0000000000..d8d0c8cbb0 --- /dev/null +++ b/apps/plugins/puzzles/src/filling.c | |||
@@ -0,0 +1,2179 @@ | |||
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. | ||
4 | */ | ||
5 | |||
6 | /* TODO: | ||
7 | * | ||
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. | ||
13 | * | ||
14 | * - in board generation, after having merged regions such that no | ||
15 | * more merges are necessary, try splitting (big) regions. | ||
16 | * + it seems that smaller regions make for better puzzles; see | ||
17 | * for instance the 7x7 puzzle in this file (grep for 7x7:). | ||
18 | * | ||
19 | * - symmetric hints (solo-style) | ||
20 | * + right now that means including _many_ hints, and the puzzles | ||
21 | * won't look any nicer. Not worth it (at the moment). | ||
22 | * | ||
23 | * - make the solver do recursion/backtracking. | ||
24 | * + This is for user-submitted puzzles, not for puzzle | ||
25 | * generation (on the other hand, never say never). | ||
26 | * | ||
27 | * - prove that only w=h=2 needs a special case | ||
28 | * | ||
29 | * - solo-like pencil marks? | ||
30 | * | ||
31 | * - a user says that the difficulty is unevenly distributed. | ||
32 | * + partition into levels? Will they be non-crap? | ||
33 | * | ||
34 | * - Allow square contents > 9? | ||
35 | * + I could use letters for digits (solo does this), but | ||
36 | * letters don't have numeric significance (normal people hate | ||
37 | * base36), which is relevant here (much more than in solo). | ||
38 | * + [click, 1, 0, enter] => [10 in clicked square]? | ||
39 | * + How much information is needed to solve? Does one need to | ||
40 | * know the algorithm by which the largest number is set? | ||
41 | * | ||
42 | * - eliminate puzzle instances with done chunks (1's in particular)? | ||
43 | * + that's what the qsort call is all about. | ||
44 | * + the 1's don't bother me that much. | ||
45 | * + but this takes a LONG time (not always possible)? | ||
46 | * - this may be affected by solver (lack of) quality. | ||
47 | * - weed them out by construction instead of post-cons check | ||
48 | * + but that interleaves make_board and new_game_desc: you | ||
49 | * have to alternate between changing the board and | ||
50 | * changing the hint set (instead of just creating the | ||
51 | * board once, then changing the hint set once -> done). | ||
52 | * | ||
53 | * - use binary search when discovering the minimal sovable point | ||
54 | * + profile to show a need (but when the solver gets slower...) | ||
55 | * + 7x9 @ .011s, 9x13 @ .075s, 17x13 @ .661s (all avg with n=100) | ||
56 | * + but the hints are independent, not linear, so... what? | ||
57 | */ | ||
58 | |||
59 | #include <assert.h> | ||
60 | #include <ctype.h> | ||
61 | #include <math.h> | ||
62 | #include <stdarg.h> | ||
63 | #include <stdio.h> | ||
64 | #include <stdlib.h> | ||
65 | #include <string.h> | ||
66 | |||
67 | #include "puzzles.h" | ||
68 | |||
69 | static unsigned char verbose; | ||
70 | |||
71 | static void printv(char *fmt, ...) { | ||
72 | #ifndef PALM | ||
73 | if (verbose) { | ||
74 | va_list va; | ||
75 | va_start(va, fmt); | ||
76 | vprintf(fmt, va); | ||
77 | va_end(va); | ||
78 | } | ||
79 | #endif | ||
80 | } | ||
81 | |||
82 | /***************************************************************************** | ||
83 | * GAME CONFIGURATION AND PARAMETERS * | ||
84 | *****************************************************************************/ | ||
85 | |||
86 | struct game_params { | ||
87 | int w, h; | ||
88 | }; | ||
89 | |||
90 | struct shared_state { | ||
91 | struct game_params params; | ||
92 | int *clues; | ||
93 | int refcnt; | ||
94 | }; | ||
95 | |||
96 | struct game_state { | ||
97 | int *board; | ||
98 | struct shared_state *shared; | ||
99 | int completed, cheated; | ||
100 | }; | ||
101 | |||
102 | static const struct game_params filling_defaults[3] = { | ||
103 | {9, 7}, {13, 9}, {17, 13} | ||
104 | }; | ||
105 | |||
106 | static game_params *default_params(void) | ||
107 | { | ||
108 | game_params *ret = snew(game_params); | ||
109 | |||
110 | *ret = filling_defaults[1]; /* struct copy */ | ||
111 | |||
112 | return ret; | ||
113 | } | ||
114 | |||
115 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
116 | { | ||
117 | char buf[64]; | ||
118 | |||
119 | if (i < 0 || i >= lenof(filling_defaults)) return FALSE; | ||
120 | *params = snew(game_params); | ||
121 | **params = filling_defaults[i]; /* struct copy */ | ||
122 | sprintf(buf, "%dx%d", filling_defaults[i].w, filling_defaults[i].h); | ||
123 | *name = dupstr(buf); | ||
124 | |||
125 | return TRUE; | ||
126 | } | ||
127 | |||
128 | static void free_params(game_params *params) | ||
129 | { | ||
130 | sfree(params); | ||
131 | } | ||
132 | |||
133 | static game_params *dup_params(const game_params *params) | ||
134 | { | ||
135 | game_params *ret = snew(game_params); | ||
136 | *ret = *params; /* struct copy */ | ||
137 | return ret; | ||
138 | } | ||
139 | |||
140 | static void decode_params(game_params *ret, char const *string) | ||
141 | { | ||
142 | ret->w = ret->h = atoi(string); | ||
143 | while (*string && isdigit((unsigned char) *string)) ++string; | ||
144 | if (*string == 'x') ret->h = atoi(++string); | ||
145 | } | ||
146 | |||
147 | static char *encode_params(const game_params *params, int full) | ||
148 | { | ||
149 | char buf[64]; | ||
150 | sprintf(buf, "%dx%d", params->w, params->h); | ||
151 | return dupstr(buf); | ||
152 | } | ||
153 | |||
154 | static config_item *game_configure(const game_params *params) | ||
155 | { | ||
156 | config_item *ret; | ||
157 | char buf[64]; | ||
158 | |||
159 | ret = snewn(3, config_item); | ||
160 | |||
161 | ret[0].name = "Width"; | ||
162 | ret[0].type = C_STRING; | ||
163 | sprintf(buf, "%d", params->w); | ||
164 | ret[0].sval = dupstr(buf); | ||
165 | ret[0].ival = 0; | ||
166 | |||
167 | ret[1].name = "Height"; | ||
168 | ret[1].type = C_STRING; | ||
169 | sprintf(buf, "%d", params->h); | ||
170 | ret[1].sval = dupstr(buf); | ||
171 | ret[1].ival = 0; | ||
172 | |||
173 | ret[2].name = NULL; | ||
174 | ret[2].type = C_END; | ||
175 | ret[2].sval = NULL; | ||
176 | ret[2].ival = 0; | ||
177 | |||
178 | return ret; | ||
179 | } | ||
180 | |||
181 | static game_params *custom_params(const config_item *cfg) | ||
182 | { | ||
183 | game_params *ret = snew(game_params); | ||
184 | |||
185 | ret->w = atoi(cfg[0].sval); | ||
186 | ret->h = atoi(cfg[1].sval); | ||
187 | |||
188 | return ret; | ||
189 | } | ||
190 | |||
191 | static char *validate_params(const game_params *params, int full) | ||
192 | { | ||
193 | if (params->w < 1) return "Width must be at least one"; | ||
194 | if (params->h < 1) return "Height must be at least one"; | ||
195 | |||
196 | return NULL; | ||
197 | } | ||
198 | |||
199 | /***************************************************************************** | ||
200 | * STRINGIFICATION OF GAME STATE * | ||
201 | *****************************************************************************/ | ||
202 | |||
203 | #define EMPTY 0 | ||
204 | |||
205 | /* Example of plaintext rendering: | ||
206 | * +---+---+---+---+---+---+---+ | ||
207 | * | 6 | | | 2 | | | 2 | | ||
208 | * +---+---+---+---+---+---+---+ | ||
209 | * | | 3 | | 6 | | 3 | | | ||
210 | * +---+---+---+---+---+---+---+ | ||
211 | * | 3 | | | | | | 1 | | ||
212 | * +---+---+---+---+---+---+---+ | ||
213 | * | | 2 | 3 | | 4 | 2 | | | ||
214 | * +---+---+---+---+---+---+---+ | ||
215 | * | 2 | | | | | | 3 | | ||
216 | * +---+---+---+---+---+---+---+ | ||
217 | * | | 5 | | 1 | | 4 | | | ||
218 | * +---+---+---+---+---+---+---+ | ||
219 | * | 4 | | | 3 | | | 3 | | ||
220 | * +---+---+---+---+---+---+---+ | ||
221 | * | ||
222 | * This puzzle instance is taken from the nikoli website | ||
223 | * Encoded (unsolved and solved), the strings are these: | ||
224 | * 7x7:6002002030603030000010230420200000305010404003003 | ||
225 | * 7x7:6662232336663232331311235422255544325413434443313 | ||
226 | */ | ||
227 | static char *board_to_string(int *board, int w, int h) { | ||
228 | const int sz = w * h; | ||
229 | const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */ | ||
230 | const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */ | ||
231 | const int chlen = chw * chh; | ||
232 | char *repr = snewn(chlen + 1, char); | ||
233 | int i; | ||
234 | |||
235 | assert(board); | ||
236 | |||
237 | /* build the first line ("^(\+---){n}\+$") */ | ||
238 | for (i = 0; i < w; ++i) { | ||
239 | repr[4*i + 0] = '+'; | ||
240 | repr[4*i + 1] = '-'; | ||
241 | repr[4*i + 2] = '-'; | ||
242 | repr[4*i + 3] = '-'; | ||
243 | } | ||
244 | repr[4*i + 0] = '+'; | ||
245 | repr[4*i + 1] = '\n'; | ||
246 | |||
247 | /* ... and copy it onto the odd-numbered lines */ | ||
248 | for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw); | ||
249 | |||
250 | /* build the second line ("^(\|\t){n}\|$") */ | ||
251 | for (i = 0; i < w; ++i) { | ||
252 | repr[chw + 4*i + 0] = '|'; | ||
253 | repr[chw + 4*i + 1] = ' '; | ||
254 | repr[chw + 4*i + 2] = ' '; | ||
255 | repr[chw + 4*i + 3] = ' '; | ||
256 | } | ||
257 | repr[chw + 4*i + 0] = '|'; | ||
258 | repr[chw + 4*i + 1] = '\n'; | ||
259 | |||
260 | /* ... and copy it onto the even-numbered lines */ | ||
261 | for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw); | ||
262 | |||
263 | /* fill in the numbers */ | ||
264 | for (i = 0; i < sz; ++i) { | ||
265 | const int x = i % w; | ||
266 | const int y = i / w; | ||
267 | if (board[i] == EMPTY) continue; | ||
268 | repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0'; | ||
269 | } | ||
270 | |||
271 | repr[chlen] = '\0'; | ||
272 | return repr; | ||
273 | } | ||
274 | |||
275 | static int game_can_format_as_text_now(const game_params *params) | ||
276 | { | ||
277 | return TRUE; | ||
278 | } | ||
279 | |||
280 | static char *game_text_format(const game_state *state) | ||
281 | { | ||
282 | const int w = state->shared->params.w; | ||
283 | const int h = state->shared->params.h; | ||
284 | return board_to_string(state->board, w, h); | ||
285 | } | ||
286 | |||
287 | /***************************************************************************** | ||
288 | * GAME GENERATION AND SOLVER * | ||
289 | *****************************************************************************/ | ||
290 | |||
291 | static const int dx[4] = {-1, 1, 0, 0}; | ||
292 | static const int dy[4] = {0, 0, -1, 1}; | ||
293 | |||
294 | struct solver_state | ||
295 | { | ||
296 | int *dsf; | ||
297 | int *board; | ||
298 | int *connected; | ||
299 | int nempty; | ||
300 | |||
301 | /* Used internally by learn_bitmap_deductions; kept here to avoid | ||
302 | * mallocing/freeing them every time that function is called. */ | ||
303 | int *bm, *bmdsf, *bmminsize; | ||
304 | }; | ||
305 | |||
306 | static void print_board(int *board, int w, int h) { | ||
307 | if (verbose) { | ||
308 | char *repr = board_to_string(board, w, h); | ||
309 | printv("%s\n", repr); | ||
310 | free(repr); | ||
311 | } | ||
312 | } | ||
313 | |||
314 | static game_state *new_game(midend *, const game_params *, const char *); | ||
315 | static void free_game(game_state *); | ||
316 | |||
317 | #define SENTINEL sz | ||
318 | |||
319 | static int mark_region(int *board, int w, int h, int i, int n, int m) { | ||
320 | int j; | ||
321 | |||
322 | board[i] = -1; | ||
323 | |||
324 | for (j = 0; j < 4; ++j) { | ||
325 | const int x = (i % w) + dx[j], y = (i / w) + dy[j], ii = w*y + x; | ||
326 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
327 | if (board[ii] == m) return FALSE; | ||
328 | if (board[ii] != n) continue; | ||
329 | if (!mark_region(board, w, h, ii, n, m)) return FALSE; | ||
330 | } | ||
331 | return TRUE; | ||
332 | } | ||
333 | |||
334 | static int region_size(int *board, int w, int h, int i) { | ||
335 | const int sz = w * h; | ||
336 | int j, size, copy; | ||
337 | if (board[i] == 0) return 0; | ||
338 | copy = board[i]; | ||
339 | mark_region(board, w, h, i, board[i], SENTINEL); | ||
340 | for (size = j = 0; j < sz; ++j) { | ||
341 | if (board[j] != -1) continue; | ||
342 | ++size; | ||
343 | board[j] = copy; | ||
344 | } | ||
345 | return size; | ||
346 | } | ||
347 | |||
348 | static void merge_ones(int *board, int w, int h) | ||
349 | { | ||
350 | const int sz = w * h; | ||
351 | const int maxsize = min(max(max(w, h), 3), 9); | ||
352 | int i, j, k, change; | ||
353 | do { | ||
354 | change = FALSE; | ||
355 | for (i = 0; i < sz; ++i) { | ||
356 | if (board[i] != 1) continue; | ||
357 | |||
358 | for (j = 0; j < 4; ++j, board[i] = 1) { | ||
359 | const int x = (i % w) + dx[j], y = (i / w) + dy[j]; | ||
360 | int oldsize, newsize, ok, ii = w*y + x; | ||
361 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
362 | if (board[ii] == maxsize) continue; | ||
363 | |||
364 | oldsize = board[ii]; | ||
365 | board[i] = oldsize; | ||
366 | newsize = region_size(board, w, h, i); | ||
367 | |||
368 | if (newsize > maxsize) continue; | ||
369 | |||
370 | ok = mark_region(board, w, h, i, oldsize, newsize); | ||
371 | |||
372 | for (k = 0; k < sz; ++k) | ||
373 | if (board[k] == -1) | ||
374 | board[k] = ok ? newsize : oldsize; | ||
375 | |||
376 | if (ok) break; | ||
377 | } | ||
378 | if (j < 4) change = TRUE; | ||
379 | } | ||
380 | } while (change); | ||
381 | } | ||
382 | |||
383 | /* generate a random valid board; uses validate_board. */ | ||
384 | static void make_board(int *board, int w, int h, random_state *rs) { | ||
385 | const int sz = w * h; | ||
386 | |||
387 | /* w=h=2 is a special case which requires a number > max(w, h) */ | ||
388 | /* TODO prove that this is the case ONLY for w=h=2. */ | ||
389 | const int maxsize = min(max(max(w, h), 3), 9); | ||
390 | |||
391 | /* Note that if 1 in {w, h} then it's impossible to have a region | ||
392 | * of size > w*h, so the special case only affects w=h=2. */ | ||
393 | |||
394 | int i, change, *dsf; | ||
395 | |||
396 | assert(w >= 1); | ||
397 | assert(h >= 1); | ||
398 | assert(board); | ||
399 | |||
400 | /* I abuse the board variable: when generating the puzzle, it | ||
401 | * contains a shuffled list of numbers {0, ..., sz-1}. */ | ||
402 | for (i = 0; i < sz; ++i) board[i] = i; | ||
403 | |||
404 | dsf = snewn(sz, int); | ||
405 | retry: | ||
406 | dsf_init(dsf, sz); | ||
407 | shuffle(board, sz, sizeof (int), rs); | ||
408 | |||
409 | do { | ||
410 | change = FALSE; /* as long as the board potentially has errors */ | ||
411 | for (i = 0; i < sz; ++i) { | ||
412 | const int square = dsf_canonify(dsf, board[i]); | ||
413 | const int size = dsf_size(dsf, square); | ||
414 | int merge = SENTINEL, min = maxsize - size + 1, error = FALSE; | ||
415 | int neighbour, neighbour_size, j; | ||
416 | |||
417 | for (j = 0; j < 4; ++j) { | ||
418 | const int x = (board[i] % w) + dx[j]; | ||
419 | const int y = (board[i] / w) + dy[j]; | ||
420 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
421 | |||
422 | neighbour = dsf_canonify(dsf, w*y + x); | ||
423 | if (square == neighbour) continue; | ||
424 | |||
425 | neighbour_size = dsf_size(dsf, neighbour); | ||
426 | if (size == neighbour_size) error = TRUE; | ||
427 | |||
428 | /* find the smallest neighbour to merge with, which | ||
429 | * wouldn't make the region too large. (This is | ||
430 | * guaranteed by the initial value of `min'.) */ | ||
431 | if (neighbour_size < min) { | ||
432 | min = neighbour_size; | ||
433 | merge = neighbour; | ||
434 | } | ||
435 | } | ||
436 | |||
437 | /* if this square is not in error, leave it be */ | ||
438 | if (!error) continue; | ||
439 | |||
440 | /* if it is, but we can't fix it, retry the whole board. | ||
441 | * Maybe we could fix it by merging the conflicting | ||
442 | * neighbouring region(s) into some of their neighbours, | ||
443 | * but just restarting works out fine. */ | ||
444 | if (merge == SENTINEL) goto retry; | ||
445 | |||
446 | /* merge with the smallest neighbouring workable region. */ | ||
447 | dsf_merge(dsf, square, merge); | ||
448 | change = TRUE; | ||
449 | } | ||
450 | } while (change); | ||
451 | |||
452 | for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i); | ||
453 | merge_ones(board, w, h); | ||
454 | |||
455 | sfree(dsf); | ||
456 | } | ||
457 | |||
458 | static void merge(int *dsf, int *connected, int a, int b) { | ||
459 | int c; | ||
460 | assert(dsf); | ||
461 | assert(connected); | ||
462 | a = dsf_canonify(dsf, a); | ||
463 | b = dsf_canonify(dsf, b); | ||
464 | if (a == b) return; | ||
465 | dsf_merge(dsf, a, b); | ||
466 | c = connected[a]; | ||
467 | connected[a] = connected[b]; | ||
468 | connected[b] = c; | ||
469 | } | ||
470 | |||
471 | static void *memdup(const void *ptr, size_t len, size_t esz) { | ||
472 | void *dup = smalloc(len * esz); | ||
473 | assert(ptr); | ||
474 | memcpy(dup, ptr, len * esz); | ||
475 | return dup; | ||
476 | } | ||
477 | |||
478 | static void expand(struct solver_state *s, int w, int h, int t, int f) { | ||
479 | int j; | ||
480 | assert(s); | ||
481 | assert(s->board[t] == EMPTY); /* expand to empty square */ | ||
482 | assert(s->board[f] != EMPTY); /* expand from non-empty square */ | ||
483 | printv( | ||
484 | "learn: expanding %d from (%d, %d) into (%d, %d)\n", | ||
485 | s->board[f], f % w, f / w, t % w, t / w); | ||
486 | s->board[t] = s->board[f]; | ||
487 | for (j = 0; j < 4; ++j) { | ||
488 | const int x = (t % w) + dx[j]; | ||
489 | const int y = (t / w) + dy[j]; | ||
490 | const int idx = w*y + x; | ||
491 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
492 | if (s->board[idx] != s->board[t]) continue; | ||
493 | merge(s->dsf, s->connected, t, idx); | ||
494 | } | ||
495 | --s->nempty; | ||
496 | } | ||
497 | |||
498 | static void clear_count(int *board, int sz) { | ||
499 | int i; | ||
500 | for (i = 0; i < sz; ++i) { | ||
501 | if (board[i] >= 0) continue; | ||
502 | else if (board[i] == -SENTINEL) board[i] = EMPTY; | ||
503 | else board[i] = -board[i]; | ||
504 | } | ||
505 | } | ||
506 | |||
507 | static void flood_count(int *board, int w, int h, int i, int n, int *c) { | ||
508 | const int sz = w * h; | ||
509 | int k; | ||
510 | |||
511 | if (board[i] == EMPTY) board[i] = -SENTINEL; | ||
512 | else if (board[i] == n) board[i] = -board[i]; | ||
513 | else return; | ||
514 | |||
515 | if (--*c == 0) return; | ||
516 | |||
517 | for (k = 0; k < 4; ++k) { | ||
518 | const int x = (i % w) + dx[k]; | ||
519 | const int y = (i / w) + dy[k]; | ||
520 | const int idx = w*y + x; | ||
521 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
522 | flood_count(board, w, h, idx, n, c); | ||
523 | if (*c == 0) return; | ||
524 | } | ||
525 | } | ||
526 | |||
527 | static int check_capacity(int *board, int w, int h, int i) { | ||
528 | int n = board[i]; | ||
529 | flood_count(board, w, h, i, board[i], &n); | ||
530 | clear_count(board, w * h); | ||
531 | return n == 0; | ||
532 | } | ||
533 | |||
534 | static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) { | ||
535 | int j; | ||
536 | int nhits = 0; | ||
537 | int hits[4]; | ||
538 | int size = 1; | ||
539 | for (j = 0; j < 4; ++j) { | ||
540 | const int x = (i % w) + dx[j]; | ||
541 | const int y = (i / w) + dy[j]; | ||
542 | const int idx = w*y + x; | ||
543 | int root; | ||
544 | int m; | ||
545 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
546 | if (board[idx] != n) continue; | ||
547 | root = dsf_canonify(dsf, idx); | ||
548 | for (m = 0; m < nhits && root != hits[m]; ++m); | ||
549 | if (m < nhits) continue; | ||
550 | printv("\t (%d, %d) contrib %d to size\n", x, y, dsf[root] >> 2); | ||
551 | size += dsf_size(dsf, root); | ||
552 | assert(dsf_size(dsf, root) >= 1); | ||
553 | hits[nhits++] = root; | ||
554 | } | ||
555 | return size; | ||
556 | } | ||
557 | |||
558 | /* | ||
559 | * +---+---+---+---+---+---+---+ | ||
560 | * | 6 | | | 2 | | | 2 | | ||
561 | * +---+---+---+---+---+---+---+ | ||
562 | * | | 3 | | 6 | | 3 | | | ||
563 | * +---+---+---+---+---+---+---+ | ||
564 | * | 3 | | | | | | 1 | | ||
565 | * +---+---+---+---+---+---+---+ | ||
566 | * | | 2 | 3 | | 4 | 2 | | | ||
567 | * +---+---+---+---+---+---+---+ | ||
568 | * | 2 | | | | | | 3 | | ||
569 | * +---+---+---+---+---+---+---+ | ||
570 | * | | 5 | | 1 | | 4 | | | ||
571 | * +---+---+---+---+---+---+---+ | ||
572 | * | 4 | | | 3 | | | 3 | | ||
573 | * +---+---+---+---+---+---+---+ | ||
574 | */ | ||
575 | |||
576 | /* Solving techniques: | ||
577 | * | ||
578 | * CONNECTED COMPONENT FORCED EXPANSION (too big): | ||
579 | * When a CC can only be expanded in one direction, because all the | ||
580 | * other ones would make the CC too big. | ||
581 | * +---+---+---+---+---+ | ||
582 | * | 2 | 2 | | 2 | _ | | ||
583 | * +---+---+---+---+---+ | ||
584 | * | ||
585 | * CONNECTED COMPONENT FORCED EXPANSION (too small): | ||
586 | * When a CC must include a particular square, because otherwise there | ||
587 | * would not be enough room to complete it. This includes squares not | ||
588 | * adjacent to the CC through learn_critical_square. | ||
589 | * +---+---+ | ||
590 | * | 2 | _ | | ||
591 | * +---+---+ | ||
592 | * | ||
593 | * DROPPING IN A ONE: | ||
594 | * When an empty square has no neighbouring empty squares and only a 1 | ||
595 | * will go into the square (or other CCs would be too big). | ||
596 | * +---+---+---+ | ||
597 | * | 2 | 2 | _ | | ||
598 | * +---+---+---+ | ||
599 | * | ||
600 | * TODO: generalise DROPPING IN A ONE: find the size of the CC of | ||
601 | * empty squares and a list of all adjacent numbers. See if only one | ||
602 | * number in {1, ..., size} u {all adjacent numbers} is possible. | ||
603 | * Probably this is only effective for a CC size < n for some n (4?) | ||
604 | * | ||
605 | * TODO: backtracking. | ||
606 | */ | ||
607 | |||
608 | static void filled_square(struct solver_state *s, int w, int h, int i) { | ||
609 | int j; | ||
610 | for (j = 0; j < 4; ++j) { | ||
611 | const int x = (i % w) + dx[j]; | ||
612 | const int y = (i / w) + dy[j]; | ||
613 | const int idx = w*y + x; | ||
614 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
615 | if (s->board[i] == s->board[idx]) | ||
616 | merge(s->dsf, s->connected, i, idx); | ||
617 | } | ||
618 | } | ||
619 | |||
620 | static void init_solver_state(struct solver_state *s, int w, int h) { | ||
621 | const int sz = w * h; | ||
622 | int i; | ||
623 | assert(s); | ||
624 | |||
625 | s->nempty = 0; | ||
626 | for (i = 0; i < sz; ++i) s->connected[i] = i; | ||
627 | for (i = 0; i < sz; ++i) | ||
628 | if (s->board[i] == EMPTY) ++s->nempty; | ||
629 | else filled_square(s, w, h, i); | ||
630 | } | ||
631 | |||
632 | static int learn_expand_or_one(struct solver_state *s, int w, int h) { | ||
633 | const int sz = w * h; | ||
634 | int i; | ||
635 | int learn = FALSE; | ||
636 | |||
637 | assert(s); | ||
638 | |||
639 | for (i = 0; i < sz; ++i) { | ||
640 | int j; | ||
641 | int one = TRUE; | ||
642 | |||
643 | if (s->board[i] != EMPTY) continue; | ||
644 | |||
645 | for (j = 0; j < 4; ++j) { | ||
646 | const int x = (i % w) + dx[j]; | ||
647 | const int y = (i / w) + dy[j]; | ||
648 | const int idx = w*y + x; | ||
649 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
650 | if (s->board[idx] == EMPTY) { | ||
651 | one = FALSE; | ||
652 | continue; | ||
653 | } | ||
654 | if (one && | ||
655 | (s->board[idx] == 1 || | ||
656 | (s->board[idx] >= expandsize(s->board, s->dsf, w, h, | ||
657 | i, s->board[idx])))) | ||
658 | one = FALSE; | ||
659 | if (dsf_size(s->dsf, idx) == s->board[idx]) continue; | ||
660 | assert(s->board[i] == EMPTY); | ||
661 | s->board[i] = -SENTINEL; | ||
662 | if (check_capacity(s->board, w, h, idx)) continue; | ||
663 | assert(s->board[i] == EMPTY); | ||
664 | printv("learn: expanding in one\n"); | ||
665 | expand(s, w, h, i, idx); | ||
666 | learn = TRUE; | ||
667 | break; | ||
668 | } | ||
669 | |||
670 | if (j == 4 && one) { | ||
671 | printv("learn: one at (%d, %d)\n", i % w, i / w); | ||
672 | assert(s->board[i] == EMPTY); | ||
673 | s->board[i] = 1; | ||
674 | assert(s->nempty); | ||
675 | --s->nempty; | ||
676 | learn = TRUE; | ||
677 | } | ||
678 | } | ||
679 | return learn; | ||
680 | } | ||
681 | |||
682 | static int learn_blocked_expansion(struct solver_state *s, int w, int h) { | ||
683 | const int sz = w * h; | ||
684 | int i; | ||
685 | int learn = FALSE; | ||
686 | |||
687 | assert(s); | ||
688 | /* for every connected component */ | ||
689 | for (i = 0; i < sz; ++i) { | ||
690 | int exp = SENTINEL; | ||
691 | int j; | ||
692 | |||
693 | if (s->board[i] == EMPTY) continue; | ||
694 | j = dsf_canonify(s->dsf, i); | ||
695 | |||
696 | /* (but only for each connected component) */ | ||
697 | if (i != j) continue; | ||
698 | |||
699 | /* (and not if it's already complete) */ | ||
700 | if (dsf_size(s->dsf, j) == s->board[j]) continue; | ||
701 | |||
702 | /* for each square j _in_ the connected component */ | ||
703 | do { | ||
704 | int k; | ||
705 | printv(" looking at (%d, %d)\n", j % w, j / w); | ||
706 | |||
707 | /* for each neighbouring square (idx) */ | ||
708 | for (k = 0; k < 4; ++k) { | ||
709 | const int x = (j % w) + dx[k]; | ||
710 | const int y = (j / w) + dy[k]; | ||
711 | const int idx = w*y + x; | ||
712 | int size; | ||
713 | /* int l; | ||
714 | int nhits = 0; | ||
715 | int hits[4]; */ | ||
716 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
717 | if (s->board[idx] != EMPTY) continue; | ||
718 | if (exp == idx) continue; | ||
719 | printv("\ttrying to expand onto (%d, %d)\n", x, y); | ||
720 | |||
721 | /* find out the would-be size of the new connected | ||
722 | * component if we actually expanded into idx */ | ||
723 | /* | ||
724 | size = 1; | ||
725 | for (l = 0; l < 4; ++l) { | ||
726 | const int lx = x + dx[l]; | ||
727 | const int ly = y + dy[l]; | ||
728 | const int idxl = w*ly + lx; | ||
729 | int root; | ||
730 | int m; | ||
731 | if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue; | ||
732 | if (board[idxl] != board[j]) continue; | ||
733 | root = dsf_canonify(dsf, idxl); | ||
734 | for (m = 0; m < nhits && root != hits[m]; ++m); | ||
735 | if (m != nhits) continue; | ||
736 | // printv("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2); | ||
737 | size += dsf_size(dsf, root); | ||
738 | assert(dsf_size(dsf, root) >= 1); | ||
739 | hits[nhits++] = root; | ||
740 | } | ||
741 | */ | ||
742 | |||
743 | size = expandsize(s->board, s->dsf, w, h, idx, s->board[j]); | ||
744 | |||
745 | /* ... and see if that size is too big, or if we | ||
746 | * have other expansion candidates. Otherwise | ||
747 | * remember the (so far) only candidate. */ | ||
748 | |||
749 | printv("\tthat would give a size of %d\n", size); | ||
750 | if (size > s->board[j]) continue; | ||
751 | /* printv("\tnow knowing %d expansions\n", nexpand + 1); */ | ||
752 | if (exp != SENTINEL) goto next_i; | ||
753 | assert(exp != idx); | ||
754 | exp = idx; | ||
755 | } | ||
756 | |||
757 | j = s->connected[j]; /* next square in the same CC */ | ||
758 | assert(s->board[i] == s->board[j]); | ||
759 | } while (j != i); | ||
760 | /* end: for each square j _in_ the connected component */ | ||
761 | |||
762 | if (exp == SENTINEL) continue; | ||
763 | printv("learning to expand\n"); | ||
764 | expand(s, w, h, exp, i); | ||
765 | learn = TRUE; | ||
766 | |||
767 | next_i: | ||
768 | ; | ||
769 | } | ||
770 | /* end: for each connected component */ | ||
771 | return learn; | ||
772 | } | ||
773 | |||
774 | static int learn_critical_square(struct solver_state *s, int w, int h) { | ||
775 | const int sz = w * h; | ||
776 | int i; | ||
777 | int learn = FALSE; | ||
778 | assert(s); | ||
779 | |||
780 | /* for each connected component */ | ||
781 | for (i = 0; i < sz; ++i) { | ||
782 | int j, slack; | ||
783 | if (s->board[i] == EMPTY) continue; | ||
784 | if (i != dsf_canonify(s->dsf, i)) continue; | ||
785 | slack = s->board[i] - dsf_size(s->dsf, i); | ||
786 | if (slack == 0) continue; | ||
787 | assert(s->board[i] != 1); | ||
788 | /* for each empty square */ | ||
789 | for (j = 0; j < sz; ++j) { | ||
790 | if (s->board[j] == EMPTY) { | ||
791 | /* if it's too far away from the CC, don't bother */ | ||
792 | int k = i, jx = j % w, jy = j / w; | ||
793 | do { | ||
794 | int kx = k % w, ky = k / w; | ||
795 | if (abs(kx - jx) + abs(ky - jy) <= slack) break; | ||
796 | k = s->connected[k]; | ||
797 | } while (i != k); | ||
798 | if (i == k) continue; /* not within range */ | ||
799 | } else continue; | ||
800 | s->board[j] = -SENTINEL; | ||
801 | if (check_capacity(s->board, w, h, i)) continue; | ||
802 | /* if not expanding s->board[i] to s->board[j] implies | ||
803 | * that s->board[i] can't reach its full size, ... */ | ||
804 | assert(s->nempty); | ||
805 | printv( | ||
806 | "learn: ds %d at (%d, %d) blocking (%d, %d)\n", | ||
807 | s->board[i], j % w, j / w, i % w, i / w); | ||
808 | --s->nempty; | ||
809 | s->board[j] = s->board[i]; | ||
810 | filled_square(s, w, h, j); | ||
811 | learn = TRUE; | ||
812 | } | ||
813 | } | ||
814 | return learn; | ||
815 | } | ||
816 | |||
817 | #if 0 | ||
818 | static void print_bitmap(int *bitmap, int w, int h) { | ||
819 | if (verbose) { | ||
820 | int x, y; | ||
821 | for (y = 0; y < h; y++) { | ||
822 | for (x = 0; x < w; x++) { | ||
823 | printv(" %03x", bm[y*w+x]); | ||
824 | } | ||
825 | printv("\n"); | ||
826 | } | ||
827 | } | ||
828 | } | ||
829 | #endif | ||
830 | |||
831 | static int learn_bitmap_deductions(struct solver_state *s, int w, int h) | ||
832 | { | ||
833 | const int sz = w * h; | ||
834 | int *bm = s->bm; | ||
835 | int *dsf = s->bmdsf; | ||
836 | int *minsize = s->bmminsize; | ||
837 | int x, y, i, j, n; | ||
838 | int learn = FALSE; | ||
839 | |||
840 | /* | ||
841 | * This function does deductions based on building up a bitmap | ||
842 | * which indicates the possible numbers that can appear in each | ||
843 | * grid square. If we can rule out all but one possibility for a | ||
844 | * particular square, then we've found out the value of that | ||
845 | * square. In particular, this is one of the few forms of | ||
846 | * deduction capable of inferring the existence of a 'ghost | ||
847 | * region', i.e. a region which has none of its squares filled in | ||
848 | * at all. | ||
849 | * | ||
850 | * The reasoning goes like this. A currently unfilled square S can | ||
851 | * turn out to contain digit n in exactly two ways: either S is | ||
852 | * part of an n-region which also includes some currently known | ||
853 | * connected component of squares with n in, or S is part of an | ||
854 | * n-region separate from _all_ currently known connected | ||
855 | * components. If we can rule out both possibilities, then square | ||
856 | * S can't contain digit n at all. | ||
857 | * | ||
858 | * The former possibility: if there's a region of size n | ||
859 | * containing both S and some existing component C, then that | ||
860 | * means the distance from S to C must be small enough that C | ||
861 | * could be extended to include S without becoming too big. So we | ||
862 | * can do a breadth-first search out from all existing components | ||
863 | * with n in them, to identify all the squares which could be | ||
864 | * joined to any of them. | ||
865 | * | ||
866 | * The latter possibility: if there's a region of size n that | ||
867 | * doesn't contain _any_ existing component, then it also can't | ||
868 | * contain any square adjacent to an existing component either. So | ||
869 | * we can identify all the EMPTY squares not adjacent to any | ||
870 | * existing square with n in, and group them into connected | ||
871 | * components; then any component of size less than n is ruled | ||
872 | * out, because there wouldn't be room to create a completely new | ||
873 | * n-region in it. | ||
874 | * | ||
875 | * In fact we process these possibilities in the other order. | ||
876 | * First we find all the squares not adjacent to an existing | ||
877 | * square with n in; then we winnow those by removing too-small | ||
878 | * connected components, to get the set of squares which could | ||
879 | * possibly be part of a brand new n-region; and finally we do the | ||
880 | * breadth-first search to add in the set of squares which could | ||
881 | * possibly be added to some existing n-region. | ||
882 | */ | ||
883 | |||
884 | /* | ||
885 | * Start by initialising our bitmap to 'all numbers possible in | ||
886 | * all squares'. | ||
887 | */ | ||
888 | for (y = 0; y < h; y++) | ||
889 | for (x = 0; x < w; x++) | ||
890 | bm[y*w+x] = (1 << 10) - (1 << 1); /* bits 1,2,...,9 now set */ | ||
891 | #if 0 | ||
892 | printv("initial bitmap:\n"); | ||
893 | print_bitmap(bm, w, h); | ||
894 | #endif | ||
895 | |||
896 | /* | ||
897 | * Now completely zero out the bitmap for squares that are already | ||
898 | * filled in (we aren't interested in those anyway). Also, for any | ||
899 | * filled square, eliminate its number from all its neighbours | ||
900 | * (because, as discussed above, the neighbours couldn't be part | ||
901 | * of a _new_ region with that number in it, and that's the case | ||
902 | * we consider first). | ||
903 | */ | ||
904 | for (y = 0; y < h; y++) { | ||
905 | for (x = 0; x < w; x++) { | ||
906 | i = y*w+x; | ||
907 | n = s->board[i]; | ||
908 | |||
909 | if (n != EMPTY) { | ||
910 | bm[i] = 0; | ||
911 | |||
912 | if (x > 0) | ||
913 | bm[i-1] &= ~(1 << n); | ||
914 | if (x+1 < w) | ||
915 | bm[i+1] &= ~(1 << n); | ||
916 | if (y > 0) | ||
917 | bm[i-w] &= ~(1 << n); | ||
918 | if (y+1 < h) | ||
919 | bm[i+w] &= ~(1 << n); | ||
920 | } | ||
921 | } | ||
922 | } | ||
923 | #if 0 | ||
924 | printv("bitmap after filled squares:\n"); | ||
925 | print_bitmap(bm, w, h); | ||
926 | #endif | ||
927 | |||
928 | /* | ||
929 | * Now, for each n, we separately find the connected components of | ||
930 | * squares for which n is still a possibility. Then discard any | ||
931 | * component of size < n, because that component is too small to | ||
932 | * have a completely new n-region in it. | ||
933 | */ | ||
934 | for (n = 1; n <= 9; n++) { | ||
935 | dsf_init(dsf, sz); | ||
936 | |||
937 | /* Build the dsf */ | ||
938 | for (y = 0; y < h; y++) | ||
939 | for (x = 0; x+1 < w; x++) | ||
940 | if (bm[y*w+x] & bm[y*w+(x+1)] & (1 << n)) | ||
941 | dsf_merge(dsf, y*w+x, y*w+(x+1)); | ||
942 | for (y = 0; y+1 < h; y++) | ||
943 | for (x = 0; x < w; x++) | ||
944 | if (bm[y*w+x] & bm[(y+1)*w+x] & (1 << n)) | ||
945 | dsf_merge(dsf, y*w+x, (y+1)*w+x); | ||
946 | |||
947 | /* Query the dsf */ | ||
948 | for (i = 0; i < sz; i++) | ||
949 | if ((bm[i] & (1 << n)) && dsf_size(dsf, i) < n) | ||
950 | bm[i] &= ~(1 << n); | ||
951 | } | ||
952 | #if 0 | ||
953 | printv("bitmap after winnowing small components:\n"); | ||
954 | print_bitmap(bm, w, h); | ||
955 | #endif | ||
956 | |||
957 | /* | ||
958 | * Now our bitmap includes every square which could be part of a | ||
959 | * completely new region, of any size. Extend it to include | ||
960 | * squares which could be part of an existing region. | ||
961 | */ | ||
962 | for (n = 1; n <= 9; n++) { | ||
963 | /* | ||
964 | * We're going to do a breadth-first search starting from | ||
965 | * existing connected components with cell value n, to find | ||
966 | * all cells they might possibly extend into. | ||
967 | * | ||
968 | * The quantity we compute, for each square, is 'minimum size | ||
969 | * that any existing CC would have to have if extended to | ||
970 | * include this square'. So squares already _in_ an existing | ||
971 | * CC are initialised to the size of that CC; then we search | ||
972 | * outwards using the rule that if a square's score is j, then | ||
973 | * its neighbours can't score more than j+1. | ||
974 | * | ||
975 | * Scores are capped at n+1, because if a square scores more | ||
976 | * than n then that's enough to know it can't possibly be | ||
977 | * reached by extending an existing region - we don't need to | ||
978 | * know exactly _how far_ out of reach it is. | ||
979 | */ | ||
980 | for (i = 0; i < sz; i++) { | ||
981 | if (s->board[i] == n) { | ||
982 | /* Square is part of an existing CC. */ | ||
983 | minsize[i] = dsf_size(s->dsf, i); | ||
984 | } else { | ||
985 | /* Otherwise, initialise to the maximum score n+1; | ||
986 | * we'll reduce this later if we find a neighbouring | ||
987 | * square with a lower score. */ | ||
988 | minsize[i] = n+1; | ||
989 | } | ||
990 | } | ||
991 | |||
992 | for (j = 1; j < n; j++) { | ||
993 | /* | ||
994 | * Find neighbours of cells scoring j, and set their score | ||
995 | * to at most j+1. | ||
996 | * | ||
997 | * Doing the BFS this way means we need n passes over the | ||
998 | * grid, which isn't entirely optimal but it seems to be | ||
999 | * fast enough for the moment. This could probably be | ||
1000 | * improved by keeping a linked-list queue of cells in | ||
1001 | * some way, but I think you'd have to be a bit careful to | ||
1002 | * insert things into the right place in the queue; this | ||
1003 | * way is easier not to get wrong. | ||
1004 | */ | ||
1005 | for (y = 0; y < h; y++) { | ||
1006 | for (x = 0; x < w; x++) { | ||
1007 | i = y*w+x; | ||
1008 | if (minsize[i] == j) { | ||
1009 | if (x > 0 && minsize[i-1] > j+1) | ||
1010 | minsize[i-1] = j+1; | ||
1011 | if (x+1 < w && minsize[i+1] > j+1) | ||
1012 | minsize[i+1] = j+1; | ||
1013 | if (y > 0 && minsize[i-w] > j+1) | ||
1014 | minsize[i-w] = j+1; | ||
1015 | if (y+1 < h && minsize[i+w] > j+1) | ||
1016 | minsize[i+w] = j+1; | ||
1017 | } | ||
1018 | } | ||
1019 | } | ||
1020 | } | ||
1021 | |||
1022 | /* | ||
1023 | * Now, every cell scoring at most n should have its 1<<n bit | ||
1024 | * in the bitmap reinstated, because we've found that it's | ||
1025 | * potentially reachable by extending an existing CC. | ||
1026 | */ | ||
1027 | for (i = 0; i < sz; i++) | ||
1028 | if (minsize[i] <= n) | ||
1029 | bm[i] |= 1<<n; | ||
1030 | } | ||
1031 | #if 0 | ||
1032 | printv("bitmap after bfs:\n"); | ||
1033 | print_bitmap(bm, w, h); | ||
1034 | #endif | ||
1035 | |||
1036 | /* | ||
1037 | * Now our bitmap is complete. Look for entries with only one bit | ||
1038 | * set; those are squares with only one possible number, in which | ||
1039 | * case we can fill that number in. | ||
1040 | */ | ||
1041 | for (i = 0; i < sz; i++) { | ||
1042 | if (bm[i] && !(bm[i] & (bm[i]-1))) { /* is bm[i] a power of two? */ | ||
1043 | int val = bm[i]; | ||
1044 | |||
1045 | /* Integer log2, by simple binary search. */ | ||
1046 | n = 0; | ||
1047 | if (val >> 8) { val >>= 8; n += 8; } | ||
1048 | if (val >> 4) { val >>= 4; n += 4; } | ||
1049 | if (val >> 2) { val >>= 2; n += 2; } | ||
1050 | if (val >> 1) { val >>= 1; n += 1; } | ||
1051 | |||
1052 | /* Double-check that we ended up with a sensible | ||
1053 | * answer. */ | ||
1054 | assert(1 <= n); | ||
1055 | assert(n <= 9); | ||
1056 | assert(bm[i] == (1 << n)); | ||
1057 | |||
1058 | if (s->board[i] == EMPTY) { | ||
1059 | printv("learn: %d is only possibility at (%d, %d)\n", | ||
1060 | n, i % w, i / w); | ||
1061 | s->board[i] = n; | ||
1062 | filled_square(s, w, h, i); | ||
1063 | assert(s->nempty); | ||
1064 | --s->nempty; | ||
1065 | learn = TRUE; | ||
1066 | } | ||
1067 | } | ||
1068 | } | ||
1069 | |||
1070 | return learn; | ||
1071 | } | ||
1072 | |||
1073 | static int solver(const int *orig, int w, int h, char **solution) { | ||
1074 | const int sz = w * h; | ||
1075 | |||
1076 | struct solver_state ss; | ||
1077 | ss.board = memdup(orig, sz, sizeof (int)); | ||
1078 | ss.dsf = snew_dsf(sz); /* eqv classes: connected components */ | ||
1079 | ss.connected = snewn(sz, int); /* connected[n] := n.next; */ | ||
1080 | /* cyclic disjoint singly linked lists, same partitioning as dsf. | ||
1081 | * The lists lets you iterate over a partition given any member */ | ||
1082 | ss.bm = snewn(sz, int); | ||
1083 | ss.bmdsf = snew_dsf(sz); | ||
1084 | ss.bmminsize = snewn(sz, int); | ||
1085 | |||
1086 | printv("trying to solve this:\n"); | ||
1087 | print_board(ss.board, w, h); | ||
1088 | |||
1089 | init_solver_state(&ss, w, h); | ||
1090 | do { | ||
1091 | if (learn_blocked_expansion(&ss, w, h)) continue; | ||
1092 | if (learn_expand_or_one(&ss, w, h)) continue; | ||
1093 | if (learn_critical_square(&ss, w, h)) continue; | ||
1094 | if (learn_bitmap_deductions(&ss, w, h)) continue; | ||
1095 | break; | ||
1096 | } while (ss.nempty); | ||
1097 | |||
1098 | printv("best guess:\n"); | ||
1099 | print_board(ss.board, w, h); | ||
1100 | |||
1101 | if (solution) { | ||
1102 | int i; | ||
1103 | *solution = snewn(sz + 2, char); | ||
1104 | **solution = 's'; | ||
1105 | for (i = 0; i < sz; ++i) (*solution)[i + 1] = ss.board[i] + '0'; | ||
1106 | (*solution)[sz + 1] = '\0'; | ||
1107 | /* We don't need the \0 for execute_move (the only user) | ||
1108 | * I'm just being printf-friendly in case I wanna print */ | ||
1109 | } | ||
1110 | |||
1111 | sfree(ss.dsf); | ||
1112 | sfree(ss.board); | ||
1113 | sfree(ss.connected); | ||
1114 | sfree(ss.bm); | ||
1115 | sfree(ss.bmdsf); | ||
1116 | sfree(ss.bmminsize); | ||
1117 | |||
1118 | return !ss.nempty; | ||
1119 | } | ||
1120 | |||
1121 | static int *make_dsf(int *dsf, int *board, const int w, const int h) { | ||
1122 | const int sz = w * h; | ||
1123 | int i; | ||
1124 | |||
1125 | if (!dsf) | ||
1126 | dsf = snew_dsf(w * h); | ||
1127 | else | ||
1128 | dsf_init(dsf, w * h); | ||
1129 | |||
1130 | for (i = 0; i < sz; ++i) { | ||
1131 | int j; | ||
1132 | for (j = 0; j < 4; ++j) { | ||
1133 | const int x = (i % w) + dx[j]; | ||
1134 | const int y = (i / w) + dy[j]; | ||
1135 | const int k = w*y + x; | ||
1136 | if (x < 0 || x >= w || y < 0 || y >= h) continue; | ||
1137 | if (board[i] == board[k]) dsf_merge(dsf, i, k); | ||
1138 | } | ||
1139 | } | ||
1140 | return dsf; | ||
1141 | } | ||
1142 | |||
1143 | static void minimize_clue_set(int *board, int w, int h, random_state *rs) | ||
1144 | { | ||
1145 | const int sz = w * h; | ||
1146 | int *shuf = snewn(sz, int), i; | ||
1147 | int *dsf, *next; | ||
1148 | |||
1149 | for (i = 0; i < sz; ++i) shuf[i] = i; | ||
1150 | shuffle(shuf, sz, sizeof (int), rs); | ||
1151 | |||
1152 | /* | ||
1153 | * First, try to eliminate an entire region at a time if possible, | ||
1154 | * because inferring the existence of a completely unclued region | ||
1155 | * is a particularly good aspect of this puzzle type and we want | ||
1156 | * to encourage it to happen. | ||
1157 | * | ||
1158 | * Begin by identifying the regions as linked lists of cells using | ||
1159 | * the 'next' array. | ||
1160 | */ | ||
1161 | dsf = make_dsf(NULL, board, w, h); | ||
1162 | next = snewn(sz, int); | ||
1163 | for (i = 0; i < sz; ++i) { | ||
1164 | int j = dsf_canonify(dsf, i); | ||
1165 | if (i == j) { | ||
1166 | /* First cell of a region; set next[i] = -1 to indicate | ||
1167 | * end-of-list. */ | ||
1168 | next[i] = -1; | ||
1169 | } else { | ||
1170 | /* Add this cell to a region which already has a | ||
1171 | * linked-list head, by pointing the canonical element j | ||
1172 | * at this one, and pointing this one in turn at wherever | ||
1173 | * j previously pointed. (This should end up with the | ||
1174 | * elements linked in the order 1,n,n-1,n-2,...,2, which | ||
1175 | * is a bit weird-looking, but any order is fine.) | ||
1176 | */ | ||
1177 | assert(j < i); | ||
1178 | next[i] = next[j]; | ||
1179 | next[j] = i; | ||
1180 | } | ||
1181 | } | ||
1182 | |||
1183 | /* | ||
1184 | * Now loop over the grid cells in our shuffled order, and each | ||
1185 | * time we encounter a region for the first time, try to remove it | ||
1186 | * all. Then we set next[canonical index] to -2 rather than -1, to | ||
1187 | * mark it as already tried. | ||
1188 | * | ||
1189 | * Doing this in a loop over _cells_, rather than extracting and | ||
1190 | * shuffling a list of _regions_, is intended to skew the | ||
1191 | * probabilities towards trying to remove larger regions first | ||
1192 | * (but without anything as crudely predictable as enforcing that | ||
1193 | * we _always_ process regions in descending size order). Region | ||
1194 | * removals might well be mutually exclusive, and larger ghost | ||
1195 | * regions are more interesting, so we want to bias towards them | ||
1196 | * if we can. | ||
1197 | */ | ||
1198 | for (i = 0; i < sz; ++i) { | ||
1199 | int j = dsf_canonify(dsf, shuf[i]); | ||
1200 | if (next[j] != -2) { | ||
1201 | int tmp = board[j]; | ||
1202 | int k; | ||
1203 | |||
1204 | /* Blank out the whole thing. */ | ||
1205 | for (k = j; k >= 0; k = next[k]) | ||
1206 | board[k] = EMPTY; | ||
1207 | |||
1208 | if (!solver(board, w, h, NULL)) { | ||
1209 | /* Wasn't still solvable; reinstate it all */ | ||
1210 | for (k = j; k >= 0; k = next[k]) | ||
1211 | board[k] = tmp; | ||
1212 | } | ||
1213 | |||
1214 | /* Either way, don't try this region again. */ | ||
1215 | next[j] = -2; | ||
1216 | } | ||
1217 | } | ||
1218 | sfree(next); | ||
1219 | sfree(dsf); | ||
1220 | |||
1221 | /* | ||
1222 | * Now go through individual cells, in the same shuffled order, | ||
1223 | * and try to remove each one by itself. | ||
1224 | */ | ||
1225 | for (i = 0; i < sz; ++i) { | ||
1226 | int tmp = board[shuf[i]]; | ||
1227 | board[shuf[i]] = EMPTY; | ||
1228 | if (!solver(board, w, h, NULL)) board[shuf[i]] = tmp; | ||
1229 | } | ||
1230 | |||
1231 | sfree(shuf); | ||
1232 | } | ||
1233 | |||
1234 | static int encode_run(char *buffer, int run) | ||
1235 | { | ||
1236 | int i = 0; | ||
1237 | for (; run > 26; run -= 26) | ||
1238 | buffer[i++] = 'z'; | ||
1239 | if (run) | ||
1240 | buffer[i++] = 'a' - 1 + run; | ||
1241 | return i; | ||
1242 | } | ||
1243 | |||
1244 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
1245 | char **aux, int interactive) | ||
1246 | { | ||
1247 | const int w = params->w, h = params->h, sz = w * h; | ||
1248 | int *board = snewn(sz, int), i, j, run; | ||
1249 | char *description = snewn(sz + 1, char); | ||
1250 | |||
1251 | make_board(board, w, h, rs); | ||
1252 | minimize_clue_set(board, w, h, rs); | ||
1253 | |||
1254 | for (run = j = i = 0; i < sz; ++i) { | ||
1255 | assert(board[i] >= 0); | ||
1256 | assert(board[i] < 10); | ||
1257 | if (board[i] == 0) { | ||
1258 | ++run; | ||
1259 | } else { | ||
1260 | j += encode_run(description + j, run); | ||
1261 | run = 0; | ||
1262 | description[j++] = board[i] + '0'; | ||
1263 | } | ||
1264 | } | ||
1265 | j += encode_run(description + j, run); | ||
1266 | description[j++] = '\0'; | ||
1267 | |||
1268 | sfree(board); | ||
1269 | |||
1270 | return sresize(description, j, char); | ||
1271 | } | ||
1272 | |||
1273 | static char *validate_desc(const game_params *params, const char *desc) | ||
1274 | { | ||
1275 | const int sz = params->w * params->h; | ||
1276 | const char m = '0' + max(max(params->w, params->h), 3); | ||
1277 | int area; | ||
1278 | |||
1279 | for (area = 0; *desc; ++desc) { | ||
1280 | if (*desc >= 'a' && *desc <= 'z') area += *desc - 'a' + 1; | ||
1281 | else if (*desc >= '0' && *desc <= m) ++area; | ||
1282 | else { | ||
1283 | static char s[] = "Invalid character '%""' in game description"; | ||
1284 | int n = sprintf(s, "Invalid character '%1c' in game description", | ||
1285 | *desc); | ||
1286 | assert(n + 1 <= lenof(s)); /* +1 for the terminating NUL */ | ||
1287 | return s; | ||
1288 | } | ||
1289 | if (area > sz) return "Too much data to fit in grid"; | ||
1290 | } | ||
1291 | return (area < sz) ? "Not enough data to fill grid" : NULL; | ||
1292 | } | ||
1293 | |||
1294 | static game_state *new_game(midend *me, const game_params *params, | ||
1295 | const char *desc) | ||
1296 | { | ||
1297 | game_state *state = snew(game_state); | ||
1298 | int sz = params->w * params->h; | ||
1299 | int i; | ||
1300 | |||
1301 | state->cheated = state->completed = FALSE; | ||
1302 | state->shared = snew(struct shared_state); | ||
1303 | state->shared->refcnt = 1; | ||
1304 | state->shared->params = *params; /* struct copy */ | ||
1305 | state->shared->clues = snewn(sz, int); | ||
1306 | |||
1307 | for (i = 0; *desc; ++desc) { | ||
1308 | if (*desc >= 'a' && *desc <= 'z') { | ||
1309 | int j = *desc - 'a' + 1; | ||
1310 | assert(i + j <= sz); | ||
1311 | for (; j; --j) state->shared->clues[i++] = 0; | ||
1312 | } else state->shared->clues[i++] = *desc - '0'; | ||
1313 | } | ||
1314 | state->board = memdup(state->shared->clues, sz, sizeof (int)); | ||
1315 | |||
1316 | return state; | ||
1317 | } | ||
1318 | |||
1319 | static game_state *dup_game(const game_state *state) | ||
1320 | { | ||
1321 | const int sz = state->shared->params.w * state->shared->params.h; | ||
1322 | game_state *ret = snew(game_state); | ||
1323 | |||
1324 | ret->board = memdup(state->board, sz, sizeof (int)); | ||
1325 | ret->shared = state->shared; | ||
1326 | ret->cheated = state->cheated; | ||
1327 | ret->completed = state->completed; | ||
1328 | ++ret->shared->refcnt; | ||
1329 | |||
1330 | return ret; | ||
1331 | } | ||
1332 | |||
1333 | static void free_game(game_state *state) | ||
1334 | { | ||
1335 | assert(state); | ||
1336 | sfree(state->board); | ||
1337 | if (--state->shared->refcnt == 0) { | ||
1338 | sfree(state->shared->clues); | ||
1339 | sfree(state->shared); | ||
1340 | } | ||
1341 | sfree(state); | ||
1342 | } | ||
1343 | |||
1344 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1345 | const char *aux, char **error) | ||
1346 | { | ||
1347 | if (aux == NULL) { | ||
1348 | const int w = state->shared->params.w; | ||
1349 | const int h = state->shared->params.h; | ||
1350 | char *new_aux; | ||
1351 | if (!solver(state->board, w, h, &new_aux)) | ||
1352 | *error = "Sorry, I couldn't find a solution"; | ||
1353 | return new_aux; | ||
1354 | } | ||
1355 | return dupstr(aux); | ||
1356 | } | ||
1357 | |||
1358 | /***************************************************************************** | ||
1359 | * USER INTERFACE STATE AND ACTION * | ||
1360 | *****************************************************************************/ | ||
1361 | |||
1362 | struct game_ui { | ||
1363 | int *sel; /* w*h highlighted squares, or NULL */ | ||
1364 | int cur_x, cur_y, cur_visible, keydragging; | ||
1365 | }; | ||
1366 | |||
1367 | static game_ui *new_ui(const game_state *state) | ||
1368 | { | ||
1369 | game_ui *ui = snew(game_ui); | ||
1370 | |||
1371 | ui->sel = NULL; | ||
1372 | ui->cur_x = ui->cur_y = ui->cur_visible = ui->keydragging = 0; | ||
1373 | |||
1374 | return ui; | ||
1375 | } | ||
1376 | |||
1377 | static void free_ui(game_ui *ui) | ||
1378 | { | ||
1379 | if (ui->sel) | ||
1380 | sfree(ui->sel); | ||
1381 | sfree(ui); | ||
1382 | } | ||
1383 | |||
1384 | static char *encode_ui(const game_ui *ui) | ||
1385 | { | ||
1386 | return NULL; | ||
1387 | } | ||
1388 | |||
1389 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1390 | { | ||
1391 | } | ||
1392 | |||
1393 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1394 | const game_state *newstate) | ||
1395 | { | ||
1396 | /* Clear any selection */ | ||
1397 | if (ui->sel) { | ||
1398 | sfree(ui->sel); | ||
1399 | ui->sel = NULL; | ||
1400 | } | ||
1401 | ui->keydragging = FALSE; | ||
1402 | } | ||
1403 | |||
1404 | #define PREFERRED_TILE_SIZE 32 | ||
1405 | #define TILE_SIZE (ds->tilesize) | ||
1406 | #define BORDER (TILE_SIZE / 2) | ||
1407 | #define BORDER_WIDTH (max(TILE_SIZE / 32, 1)) | ||
1408 | |||
1409 | struct game_drawstate { | ||
1410 | struct game_params params; | ||
1411 | int tilesize; | ||
1412 | int started; | ||
1413 | int *v, *flags; | ||
1414 | int *dsf_scratch, *border_scratch; | ||
1415 | }; | ||
1416 | |||
1417 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1418 | const game_drawstate *ds, | ||
1419 | int x, int y, int button) | ||
1420 | { | ||
1421 | const int w = state->shared->params.w; | ||
1422 | const int h = state->shared->params.h; | ||
1423 | |||
1424 | const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1; | ||
1425 | const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1; | ||
1426 | |||
1427 | char *move = NULL; | ||
1428 | int i; | ||
1429 | |||
1430 | assert(ui); | ||
1431 | assert(ds); | ||
1432 | |||
1433 | button &= ~MOD_MASK; | ||
1434 | |||
1435 | if (button == LEFT_BUTTON || button == LEFT_DRAG) { | ||
1436 | /* A left-click anywhere will clear the current selection. */ | ||
1437 | if (button == LEFT_BUTTON) { | ||
1438 | if (ui->sel) { | ||
1439 | sfree(ui->sel); | ||
1440 | ui->sel = NULL; | ||
1441 | } | ||
1442 | } | ||
1443 | if (tx >= 0 && tx < w && ty >= 0 && ty < h) { | ||
1444 | if (!ui->sel) { | ||
1445 | ui->sel = snewn(w*h, int); | ||
1446 | memset(ui->sel, 0, w*h*sizeof(int)); | ||
1447 | } | ||
1448 | if (!state->shared->clues[w*ty+tx]) | ||
1449 | ui->sel[w*ty+tx] = 1; | ||
1450 | } | ||
1451 | ui->cur_visible = 0; | ||
1452 | return ""; /* redraw */ | ||
1453 | } | ||
1454 | |||
1455 | if (IS_CURSOR_MOVE(button)) { | ||
1456 | ui->cur_visible = 1; | ||
1457 | move_cursor(button, &ui->cur_x, &ui->cur_y, w, h, 0); | ||
1458 | if (ui->keydragging) goto select_square; | ||
1459 | return ""; | ||
1460 | } | ||
1461 | if (button == CURSOR_SELECT) { | ||
1462 | if (!ui->cur_visible) { | ||
1463 | ui->cur_visible = 1; | ||
1464 | return ""; | ||
1465 | } | ||
1466 | ui->keydragging = !ui->keydragging; | ||
1467 | if (!ui->keydragging) return ""; | ||
1468 | |||
1469 | select_square: | ||
1470 | if (!ui->sel) { | ||
1471 | ui->sel = snewn(w*h, int); | ||
1472 | memset(ui->sel, 0, w*h*sizeof(int)); | ||
1473 | } | ||
1474 | if (!state->shared->clues[w*ui->cur_y + ui->cur_x]) | ||
1475 | ui->sel[w*ui->cur_y + ui->cur_x] = 1; | ||
1476 | return ""; | ||
1477 | } | ||
1478 | if (button == CURSOR_SELECT2) { | ||
1479 | if (!ui->cur_visible) { | ||
1480 | ui->cur_visible = 1; | ||
1481 | return ""; | ||
1482 | } | ||
1483 | if (!ui->sel) { | ||
1484 | ui->sel = snewn(w*h, int); | ||
1485 | memset(ui->sel, 0, w*h*sizeof(int)); | ||
1486 | } | ||
1487 | ui->keydragging = FALSE; | ||
1488 | if (!state->shared->clues[w*ui->cur_y + ui->cur_x]) | ||
1489 | ui->sel[w*ui->cur_y + ui->cur_x] ^= 1; | ||
1490 | for (i = 0; i < w*h && !ui->sel[i]; i++); | ||
1491 | if (i == w*h) { | ||
1492 | sfree(ui->sel); | ||
1493 | ui->sel = NULL; | ||
1494 | } | ||
1495 | return ""; | ||
1496 | } | ||
1497 | |||
1498 | if (button == '\b' || button == 27) { | ||
1499 | sfree(ui->sel); | ||
1500 | ui->sel = NULL; | ||
1501 | ui->keydragging = FALSE; | ||
1502 | return ""; | ||
1503 | } | ||
1504 | |||
1505 | if (button < '0' || button > '9') return NULL; | ||
1506 | button -= '0'; | ||
1507 | if (button > (w == 2 && h == 2 ? 3 : max(w, h))) return NULL; | ||
1508 | ui->keydragging = FALSE; | ||
1509 | |||
1510 | for (i = 0; i < w*h; i++) { | ||
1511 | char buf[32]; | ||
1512 | if ((ui->sel && ui->sel[i]) || | ||
1513 | (!ui->sel && ui->cur_visible && (w*ui->cur_y+ui->cur_x) == i)) { | ||
1514 | if (state->shared->clues[i] != 0) continue; /* in case cursor is on clue */ | ||
1515 | if (state->board[i] != button) { | ||
1516 | sprintf(buf, "%s%d", move ? "," : "", i); | ||
1517 | if (move) { | ||
1518 | move = srealloc(move, strlen(move)+strlen(buf)+1); | ||
1519 | strcat(move, buf); | ||
1520 | } else { | ||
1521 | move = smalloc(strlen(buf)+1); | ||
1522 | strcpy(move, buf); | ||
1523 | } | ||
1524 | } | ||
1525 | } | ||
1526 | } | ||
1527 | if (move) { | ||
1528 | char buf[32]; | ||
1529 | sprintf(buf, "_%d", button); | ||
1530 | move = srealloc(move, strlen(move)+strlen(buf)+1); | ||
1531 | strcat(move, buf); | ||
1532 | } | ||
1533 | if (!ui->sel) return move ? move : NULL; | ||
1534 | sfree(ui->sel); | ||
1535 | ui->sel = NULL; | ||
1536 | /* Need to update UI at least, as we cleared the selection */ | ||
1537 | return move ? move : ""; | ||
1538 | } | ||
1539 | |||
1540 | static game_state *execute_move(const game_state *state, const char *move) | ||
1541 | { | ||
1542 | game_state *new_state = NULL; | ||
1543 | const int sz = state->shared->params.w * state->shared->params.h; | ||
1544 | |||
1545 | if (*move == 's') { | ||
1546 | int i = 0; | ||
1547 | new_state = dup_game(state); | ||
1548 | for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0'; | ||
1549 | new_state->cheated = TRUE; | ||
1550 | } else { | ||
1551 | int value; | ||
1552 | char *endptr, *delim = strchr(move, '_'); | ||
1553 | if (!delim) goto err; | ||
1554 | value = strtol(delim+1, &endptr, 0); | ||
1555 | if (*endptr || endptr == delim+1) goto err; | ||
1556 | if (value < 0 || value > 9) goto err; | ||
1557 | new_state = dup_game(state); | ||
1558 | while (*move) { | ||
1559 | const int i = strtol(move, &endptr, 0); | ||
1560 | if (endptr == move) goto err; | ||
1561 | if (i < 0 || i >= sz) goto err; | ||
1562 | new_state->board[i] = value; | ||
1563 | if (*endptr == '_') break; | ||
1564 | if (*endptr != ',') goto err; | ||
1565 | move = endptr + 1; | ||
1566 | } | ||
1567 | } | ||
1568 | |||
1569 | /* | ||
1570 | * Check for completion. | ||
1571 | */ | ||
1572 | if (!new_state->completed) { | ||
1573 | const int w = new_state->shared->params.w; | ||
1574 | const int h = new_state->shared->params.h; | ||
1575 | const int sz = w * h; | ||
1576 | int *dsf = make_dsf(NULL, new_state->board, w, h); | ||
1577 | int i; | ||
1578 | for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i); | ||
1579 | sfree(dsf); | ||
1580 | if (i == sz) | ||
1581 | new_state->completed = TRUE; | ||
1582 | } | ||
1583 | |||
1584 | return new_state; | ||
1585 | |||
1586 | err: | ||
1587 | if (new_state) free_game(new_state); | ||
1588 | return NULL; | ||
1589 | } | ||
1590 | |||
1591 | /* ---------------------------------------------------------------------- | ||
1592 | * Drawing routines. | ||
1593 | */ | ||
1594 | |||
1595 | #define FLASH_TIME 0.4F | ||
1596 | |||
1597 | #define COL_CLUE COL_GRID | ||
1598 | enum { | ||
1599 | COL_BACKGROUND, | ||
1600 | COL_GRID, | ||
1601 | COL_HIGHLIGHT, | ||
1602 | COL_CORRECT, | ||
1603 | COL_ERROR, | ||
1604 | COL_USER, | ||
1605 | COL_CURSOR, | ||
1606 | NCOLOURS | ||
1607 | }; | ||
1608 | |||
1609 | static void game_compute_size(const game_params *params, int tilesize, | ||
1610 | int *x, int *y) | ||
1611 | { | ||
1612 | *x = (params->w + 1) * tilesize; | ||
1613 | *y = (params->h + 1) * tilesize; | ||
1614 | } | ||
1615 | |||
1616 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1617 | const game_params *params, int tilesize) | ||
1618 | { | ||
1619 | ds->tilesize = tilesize; | ||
1620 | } | ||
1621 | |||
1622 | static float *game_colours(frontend *fe, int *ncolours) | ||
1623 | { | ||
1624 | float *ret = snewn(3 * NCOLOURS, float); | ||
1625 | |||
1626 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
1627 | |||
1628 | ret[COL_GRID * 3 + 0] = 0.0F; | ||
1629 | ret[COL_GRID * 3 + 1] = 0.0F; | ||
1630 | ret[COL_GRID * 3 + 2] = 0.0F; | ||
1631 | |||
1632 | ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0]; | ||
1633 | ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1]; | ||
1634 | ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2]; | ||
1635 | |||
1636 | ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0]; | ||
1637 | ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1]; | ||
1638 | ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2]; | ||
1639 | |||
1640 | ret[COL_CURSOR * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; | ||
1641 | ret[COL_CURSOR * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; | ||
1642 | ret[COL_CURSOR * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2]; | ||
1643 | |||
1644 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
1645 | ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1]; | ||
1646 | ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2]; | ||
1647 | |||
1648 | ret[COL_USER * 3 + 0] = 0.0F; | ||
1649 | ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1]; | ||
1650 | ret[COL_USER * 3 + 2] = 0.0F; | ||
1651 | |||
1652 | *ncolours = NCOLOURS; | ||
1653 | return ret; | ||
1654 | } | ||
1655 | |||
1656 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1657 | { | ||
1658 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1659 | int i; | ||
1660 | |||
1661 | ds->tilesize = PREFERRED_TILE_SIZE; | ||
1662 | ds->started = 0; | ||
1663 | ds->params = state->shared->params; | ||
1664 | ds->v = snewn(ds->params.w * ds->params.h, int); | ||
1665 | ds->flags = snewn(ds->params.w * ds->params.h, int); | ||
1666 | for (i = 0; i < ds->params.w * ds->params.h; i++) | ||
1667 | ds->v[i] = ds->flags[i] = -1; | ||
1668 | ds->border_scratch = snewn(ds->params.w * ds->params.h, int); | ||
1669 | ds->dsf_scratch = NULL; | ||
1670 | |||
1671 | return ds; | ||
1672 | } | ||
1673 | |||
1674 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1675 | { | ||
1676 | sfree(ds->v); | ||
1677 | sfree(ds->flags); | ||
1678 | sfree(ds->border_scratch); | ||
1679 | sfree(ds->dsf_scratch); | ||
1680 | sfree(ds); | ||
1681 | } | ||
1682 | |||
1683 | #define BORDER_U 0x001 | ||
1684 | #define BORDER_D 0x002 | ||
1685 | #define BORDER_L 0x004 | ||
1686 | #define BORDER_R 0x008 | ||
1687 | #define BORDER_UR 0x010 | ||
1688 | #define BORDER_DR 0x020 | ||
1689 | #define BORDER_UL 0x040 | ||
1690 | #define BORDER_DL 0x080 | ||
1691 | #define HIGH_BG 0x100 | ||
1692 | #define CORRECT_BG 0x200 | ||
1693 | #define ERROR_BG 0x400 | ||
1694 | #define USER_COL 0x800 | ||
1695 | #define CURSOR_SQ 0x1000 | ||
1696 | |||
1697 | static void draw_square(drawing *dr, game_drawstate *ds, int x, int y, | ||
1698 | int n, int flags) | ||
1699 | { | ||
1700 | assert(dr); | ||
1701 | assert(ds); | ||
1702 | |||
1703 | /* | ||
1704 | * Clip to the grid square. | ||
1705 | */ | ||
1706 | clip(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE, | ||
1707 | TILE_SIZE, TILE_SIZE); | ||
1708 | |||
1709 | /* | ||
1710 | * Clear the square. | ||
1711 | */ | ||
1712 | draw_rect(dr, | ||
1713 | BORDER + x*TILE_SIZE, | ||
1714 | BORDER + y*TILE_SIZE, | ||
1715 | TILE_SIZE, | ||
1716 | TILE_SIZE, | ||
1717 | (flags & HIGH_BG ? COL_HIGHLIGHT : | ||
1718 | flags & ERROR_BG ? COL_ERROR : | ||
1719 | flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND)); | ||
1720 | |||
1721 | /* | ||
1722 | * Draw the grid lines. | ||
1723 | */ | ||
1724 | draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE, | ||
1725 | BORDER + (x+1)*TILE_SIZE, BORDER + y*TILE_SIZE, COL_GRID); | ||
1726 | draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE, | ||
1727 | BORDER + x*TILE_SIZE, BORDER + (y+1)*TILE_SIZE, COL_GRID); | ||
1728 | |||
1729 | /* | ||
1730 | * Draw the number. | ||
1731 | */ | ||
1732 | if (n) { | ||
1733 | char buf[2]; | ||
1734 | buf[0] = n + '0'; | ||
1735 | buf[1] = '\0'; | ||
1736 | draw_text(dr, | ||
1737 | (x + 1) * TILE_SIZE, | ||
1738 | (y + 1) * TILE_SIZE, | ||
1739 | FONT_VARIABLE, | ||
1740 | TILE_SIZE / 2, | ||
1741 | ALIGN_VCENTRE | ALIGN_HCENTRE, | ||
1742 | flags & USER_COL ? COL_USER : COL_CLUE, | ||
1743 | buf); | ||
1744 | } | ||
1745 | |||
1746 | /* | ||
1747 | * Draw bold lines around the borders. | ||
1748 | */ | ||
1749 | if (flags & BORDER_L) | ||
1750 | draw_rect(dr, | ||
1751 | BORDER + x*TILE_SIZE + 1, | ||
1752 | BORDER + y*TILE_SIZE + 1, | ||
1753 | BORDER_WIDTH, | ||
1754 | TILE_SIZE - 1, | ||
1755 | COL_GRID); | ||
1756 | if (flags & BORDER_U) | ||
1757 | draw_rect(dr, | ||
1758 | BORDER + x*TILE_SIZE + 1, | ||
1759 | BORDER + y*TILE_SIZE + 1, | ||
1760 | TILE_SIZE - 1, | ||
1761 | BORDER_WIDTH, | ||
1762 | COL_GRID); | ||
1763 | if (flags & BORDER_R) | ||
1764 | draw_rect(dr, | ||
1765 | BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH, | ||
1766 | BORDER + y*TILE_SIZE + 1, | ||
1767 | BORDER_WIDTH, | ||
1768 | TILE_SIZE - 1, | ||
1769 | COL_GRID); | ||
1770 | if (flags & BORDER_D) | ||
1771 | draw_rect(dr, | ||
1772 | BORDER + x*TILE_SIZE + 1, | ||
1773 | BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH, | ||
1774 | TILE_SIZE - 1, | ||
1775 | BORDER_WIDTH, | ||
1776 | COL_GRID); | ||
1777 | if (flags & BORDER_UL) | ||
1778 | draw_rect(dr, | ||
1779 | BORDER + x*TILE_SIZE + 1, | ||
1780 | BORDER + y*TILE_SIZE + 1, | ||
1781 | BORDER_WIDTH, | ||
1782 | BORDER_WIDTH, | ||
1783 | COL_GRID); | ||
1784 | if (flags & BORDER_UR) | ||
1785 | draw_rect(dr, | ||
1786 | BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH, | ||
1787 | BORDER + y*TILE_SIZE + 1, | ||
1788 | BORDER_WIDTH, | ||
1789 | BORDER_WIDTH, | ||
1790 | COL_GRID); | ||
1791 | if (flags & BORDER_DL) | ||
1792 | draw_rect(dr, | ||
1793 | BORDER + x*TILE_SIZE + 1, | ||
1794 | BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH, | ||
1795 | BORDER_WIDTH, | ||
1796 | BORDER_WIDTH, | ||
1797 | COL_GRID); | ||
1798 | if (flags & BORDER_DR) | ||
1799 | draw_rect(dr, | ||
1800 | BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH, | ||
1801 | BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH, | ||
1802 | BORDER_WIDTH, | ||
1803 | BORDER_WIDTH, | ||
1804 | COL_GRID); | ||
1805 | |||
1806 | if (flags & CURSOR_SQ) { | ||
1807 | int coff = TILE_SIZE/8; | ||
1808 | draw_rect_outline(dr, | ||
1809 | BORDER + x*TILE_SIZE + coff, | ||
1810 | BORDER + y*TILE_SIZE + coff, | ||
1811 | TILE_SIZE - coff*2, | ||
1812 | TILE_SIZE - coff*2, | ||
1813 | COL_CURSOR); | ||
1814 | } | ||
1815 | |||
1816 | unclip(dr); | ||
1817 | |||
1818 | draw_update(dr, | ||
1819 | BORDER + x*TILE_SIZE, | ||
1820 | BORDER + y*TILE_SIZE, | ||
1821 | TILE_SIZE, | ||
1822 | TILE_SIZE); | ||
1823 | } | ||
1824 | |||
1825 | static void draw_grid(drawing *dr, game_drawstate *ds, const game_state *state, | ||
1826 | const game_ui *ui, int flashy, int borders, int shading) | ||
1827 | { | ||
1828 | const int w = state->shared->params.w; | ||
1829 | const int h = state->shared->params.h; | ||
1830 | int x; | ||
1831 | int y; | ||
1832 | |||
1833 | /* | ||
1834 | * Build a dsf for the board in its current state, to use for | ||
1835 | * highlights and hints. | ||
1836 | */ | ||
1837 | ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h); | ||
1838 | |||
1839 | /* | ||
1840 | * Work out where we're putting borders between the cells. | ||
1841 | */ | ||
1842 | for (y = 0; y < w*h; y++) | ||
1843 | ds->border_scratch[y] = 0; | ||
1844 | |||
1845 | for (y = 0; y < h; y++) | ||
1846 | for (x = 0; x < w; x++) { | ||
1847 | int dx, dy; | ||
1848 | int v1, s1, v2, s2; | ||
1849 | |||
1850 | for (dx = 0; dx <= 1; dx++) { | ||
1851 | int border = FALSE; | ||
1852 | |||
1853 | dy = 1 - dx; | ||
1854 | |||
1855 | if (x+dx >= w || y+dy >= h) | ||
1856 | continue; | ||
1857 | |||
1858 | v1 = state->board[y*w+x]; | ||
1859 | v2 = state->board[(y+dy)*w+(x+dx)]; | ||
1860 | s1 = dsf_size(ds->dsf_scratch, y*w+x); | ||
1861 | s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx)); | ||
1862 | |||
1863 | /* | ||
1864 | * We only ever draw a border between two cells if | ||
1865 | * they don't have the same contents. | ||
1866 | */ | ||
1867 | if (v1 != v2) { | ||
1868 | /* | ||
1869 | * But in that situation, we don't always draw | ||
1870 | * a border. We do if the two cells both | ||
1871 | * contain actual numbers... | ||
1872 | */ | ||
1873 | if (v1 && v2) | ||
1874 | border = TRUE; | ||
1875 | |||
1876 | /* | ||
1877 | * ... or if at least one of them is a | ||
1878 | * completed or overfull omino. | ||
1879 | */ | ||
1880 | if (v1 && s1 >= v1) | ||
1881 | border = TRUE; | ||
1882 | if (v2 && s2 >= v2) | ||
1883 | border = TRUE; | ||
1884 | } | ||
1885 | |||
1886 | if (border) | ||
1887 | ds->border_scratch[y*w+x] |= (dx ? 1 : 2); | ||
1888 | } | ||
1889 | } | ||
1890 | |||
1891 | /* | ||
1892 | * Actually do the drawing. | ||
1893 | */ | ||
1894 | for (y = 0; y < h; ++y) | ||
1895 | for (x = 0; x < w; ++x) { | ||
1896 | /* | ||
1897 | * Determine what we need to draw in this square. | ||
1898 | */ | ||
1899 | int i = y*w+x, v = state->board[i]; | ||
1900 | int flags = 0; | ||
1901 | |||
1902 | if (flashy || !shading) { | ||
1903 | /* clear all background flags */ | ||
1904 | } else if (ui && ui->sel && ui->sel[i]) { | ||
1905 | flags |= HIGH_BG; | ||
1906 | } else if (v) { | ||
1907 | int size = dsf_size(ds->dsf_scratch, i); | ||
1908 | if (size == v) | ||
1909 | flags |= CORRECT_BG; | ||
1910 | else if (size > v) | ||
1911 | flags |= ERROR_BG; | ||
1912 | else { | ||
1913 | int rt = dsf_canonify(ds->dsf_scratch, i), j; | ||
1914 | for (j = 0; j < w*h; ++j) { | ||
1915 | int k; | ||
1916 | if (dsf_canonify(ds->dsf_scratch, j) != rt) continue; | ||
1917 | for (k = 0; k < 4; ++k) { | ||
1918 | const int xx = j % w + dx[k], yy = j / w + dy[k]; | ||
1919 | if (xx >= 0 && xx < w && yy >= 0 && yy < h && | ||
1920 | state->board[yy*w + xx] == EMPTY) | ||
1921 | goto noflag; | ||
1922 | } | ||
1923 | } | ||
1924 | flags |= ERROR_BG; | ||
1925 | noflag: | ||
1926 | ; | ||
1927 | } | ||
1928 | } | ||
1929 | if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y) | ||
1930 | flags |= CURSOR_SQ; | ||
1931 | |||
1932 | /* | ||
1933 | * Borders at the very edges of the grid are | ||
1934 | * independent of the `borders' flag. | ||
1935 | */ | ||
1936 | if (x == 0) | ||
1937 | flags |= BORDER_L; | ||
1938 | if (y == 0) | ||
1939 | flags |= BORDER_U; | ||
1940 | if (x == w-1) | ||
1941 | flags |= BORDER_R; | ||
1942 | if (y == h-1) | ||
1943 | flags |= BORDER_D; | ||
1944 | |||
1945 | if (borders) { | ||
1946 | if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1)) | ||
1947 | flags |= BORDER_L; | ||
1948 | if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2)) | ||
1949 | flags |= BORDER_U; | ||
1950 | if (x == w-1 || (ds->border_scratch[y*w+x] & 1)) | ||
1951 | flags |= BORDER_R; | ||
1952 | if (y == h-1 || (ds->border_scratch[y*w+x] & 2)) | ||
1953 | flags |= BORDER_D; | ||
1954 | |||
1955 | if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)])) | ||
1956 | flags |= BORDER_UL; | ||
1957 | if (y > 0 && x < w-1 && | ||
1958 | ((ds->border_scratch[(y-1)*w+x] & 1) || | ||
1959 | (ds->border_scratch[(y-1)*w+(x+1)] & 2))) | ||
1960 | flags |= BORDER_UR; | ||
1961 | if (y < h-1 && x > 0 && | ||
1962 | ((ds->border_scratch[y*w+(x-1)] & 2) || | ||
1963 | (ds->border_scratch[(y+1)*w+(x-1)] & 1))) | ||
1964 | flags |= BORDER_DL; | ||
1965 | if (y < h-1 && x < w-1 && | ||
1966 | ((ds->border_scratch[y*w+(x+1)] & 2) || | ||
1967 | (ds->border_scratch[(y+1)*w+x] & 1))) | ||
1968 | flags |= BORDER_DR; | ||
1969 | } | ||
1970 | |||
1971 | if (!state->shared->clues[y*w+x]) | ||
1972 | flags |= USER_COL; | ||
1973 | |||
1974 | if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) { | ||
1975 | draw_square(dr, ds, x, y, v, flags); | ||
1976 | ds->v[y*w+x] = v; | ||
1977 | ds->flags[y*w+x] = flags; | ||
1978 | } | ||
1979 | } | ||
1980 | } | ||
1981 | |||
1982 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1983 | const game_state *oldstate, const game_state *state, | ||
1984 | int dir, const game_ui *ui, | ||
1985 | float animtime, float flashtime) | ||
1986 | { | ||
1987 | const int w = state->shared->params.w; | ||
1988 | const int h = state->shared->params.h; | ||
1989 | |||
1990 | const int flashy = | ||
1991 | flashtime > 0 && | ||
1992 | (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3); | ||
1993 | |||
1994 | if (!ds->started) { | ||
1995 | /* | ||
1996 | * The initial contents of the window are not guaranteed and | ||
1997 | * can vary with front ends. To be on the safe side, all games | ||
1998 | * should start by drawing a big background-colour rectangle | ||
1999 | * covering the whole window. | ||
2000 | */ | ||
2001 | draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER, | ||
2002 | COL_BACKGROUND); | ||
2003 | |||
2004 | /* | ||
2005 | * Smaller black rectangle which is the main grid. | ||
2006 | */ | ||
2007 | draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH, | ||
2008 | w*TILE_SIZE + 2*BORDER_WIDTH + 1, | ||
2009 | h*TILE_SIZE + 2*BORDER_WIDTH + 1, | ||
2010 | COL_GRID); | ||
2011 | |||
2012 | draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER); | ||
2013 | |||
2014 | ds->started = TRUE; | ||
2015 | } | ||
2016 | |||
2017 | draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE); | ||
2018 | } | ||
2019 | |||
2020 | static float game_anim_length(const game_state *oldstate, | ||
2021 | const game_state *newstate, int dir, game_ui *ui) | ||
2022 | { | ||
2023 | return 0.0F; | ||
2024 | } | ||
2025 | |||
2026 | static float game_flash_length(const game_state *oldstate, | ||
2027 | const game_state *newstate, int dir, game_ui *ui) | ||
2028 | { | ||
2029 | assert(oldstate); | ||
2030 | assert(newstate); | ||
2031 | assert(newstate->shared); | ||
2032 | assert(oldstate->shared == newstate->shared); | ||
2033 | if (!oldstate->completed && newstate->completed && | ||
2034 | !oldstate->cheated && !newstate->cheated) | ||
2035 | return FLASH_TIME; | ||
2036 | return 0.0F; | ||
2037 | } | ||
2038 | |||
2039 | static int game_status(const game_state *state) | ||
2040 | { | ||
2041 | return state->completed ? +1 : 0; | ||
2042 | } | ||
2043 | |||
2044 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
2045 | { | ||
2046 | return TRUE; | ||
2047 | } | ||
2048 | |||
2049 | static void game_print_size(const game_params *params, float *x, float *y) | ||
2050 | { | ||
2051 | int pw, ph; | ||
2052 | |||
2053 | /* | ||
2054 | * I'll use 6mm squares by default. | ||
2055 | */ | ||
2056 | game_compute_size(params, 600, &pw, &ph); | ||
2057 | *x = pw / 100.0F; | ||
2058 | *y = ph / 100.0F; | ||
2059 | } | ||
2060 | |||
2061 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
2062 | { | ||
2063 | const int w = state->shared->params.w; | ||
2064 | const int h = state->shared->params.h; | ||
2065 | int c, i, borders; | ||
2066 | |||
2067 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2068 | game_drawstate *ds = game_new_drawstate(dr, state); | ||
2069 | game_set_size(dr, ds, NULL, tilesize); | ||
2070 | |||
2071 | c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND); | ||
2072 | c = print_mono_colour(dr, 0); assert(c == COL_GRID); | ||
2073 | c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT); | ||
2074 | c = print_mono_colour(dr, 1); assert(c == COL_CORRECT); | ||
2075 | c = print_mono_colour(dr, 1); assert(c == COL_ERROR); | ||
2076 | c = print_mono_colour(dr, 0); assert(c == COL_USER); | ||
2077 | |||
2078 | /* | ||
2079 | * Border. | ||
2080 | */ | ||
2081 | draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH, | ||
2082 | w*TILE_SIZE + 2*BORDER_WIDTH + 1, | ||
2083 | h*TILE_SIZE + 2*BORDER_WIDTH + 1, | ||
2084 | COL_GRID); | ||
2085 | |||
2086 | /* | ||
2087 | * We'll draw borders between the ominoes iff the grid is not | ||
2088 | * pristine. So scan it to see if it is. | ||
2089 | */ | ||
2090 | borders = FALSE; | ||
2091 | for (i = 0; i < w*h; i++) | ||
2092 | if (state->board[i] && !state->shared->clues[i]) | ||
2093 | borders = TRUE; | ||
2094 | |||
2095 | /* | ||
2096 | * Draw grid. | ||
2097 | */ | ||
2098 | print_line_width(dr, TILE_SIZE / 64); | ||
2099 | draw_grid(dr, ds, state, NULL, FALSE, borders, FALSE); | ||
2100 | |||
2101 | /* | ||
2102 | * Clean up. | ||
2103 | */ | ||
2104 | game_free_drawstate(dr, ds); | ||
2105 | } | ||
2106 | |||
2107 | #ifdef COMBINED | ||
2108 | #define thegame filling | ||
2109 | #endif | ||
2110 | |||
2111 | const struct game thegame = { | ||
2112 | "Filling", "games.filling", "filling", | ||
2113 | default_params, | ||
2114 | game_fetch_preset, NULL, | ||
2115 | decode_params, | ||
2116 | encode_params, | ||
2117 | free_params, | ||
2118 | dup_params, | ||
2119 | TRUE, game_configure, custom_params, | ||
2120 | validate_params, | ||
2121 | new_game_desc, | ||
2122 | validate_desc, | ||
2123 | new_game, | ||
2124 | dup_game, | ||
2125 | free_game, | ||
2126 | TRUE, solve_game, | ||
2127 | TRUE, game_can_format_as_text_now, game_text_format, | ||
2128 | new_ui, | ||
2129 | free_ui, | ||
2130 | encode_ui, | ||
2131 | decode_ui, | ||
2132 | game_changed_state, | ||
2133 | interpret_move, | ||
2134 | execute_move, | ||
2135 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
2136 | game_colours, | ||
2137 | game_new_drawstate, | ||
2138 | game_free_drawstate, | ||
2139 | game_redraw, | ||
2140 | game_anim_length, | ||
2141 | game_flash_length, | ||
2142 | game_status, | ||
2143 | TRUE, FALSE, game_print_size, game_print, | ||
2144 | FALSE, /* wants_statusbar */ | ||
2145 | FALSE, game_timing_state, | ||
2146 | REQUIRE_NUMPAD, /* flags */ | ||
2147 | }; | ||
2148 | |||
2149 | #ifdef STANDALONE_SOLVER /* solver? hah! */ | ||
2150 | |||
2151 | int main(int argc, char **argv) { | ||
2152 | while (*++argv) { | ||
2153 | game_params *params; | ||
2154 | game_state *state; | ||
2155 | char *par; | ||
2156 | char *desc; | ||
2157 | |||
2158 | for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc); | ||
2159 | if (*desc == '\0') { | ||
2160 | fprintf(stderr, "bad puzzle id: %s", par); | ||
2161 | continue; | ||
2162 | } | ||
2163 | |||
2164 | *desc++ = '\0'; | ||
2165 | |||
2166 | params = snew(game_params); | ||
2167 | decode_params(params, par); | ||
2168 | state = new_game(NULL, params, desc); | ||
2169 | if (solver(state->board, params->w, params->h, NULL)) | ||
2170 | printf("%s:%s: solvable\n", par, desc); | ||
2171 | else | ||
2172 | printf("%s:%s: not solvable\n", par, desc); | ||
2173 | } | ||
2174 | return 0; | ||
2175 | } | ||
2176 | |||
2177 | #endif | ||
2178 | |||
2179 | /* vim: set shiftwidth=4 tabstop=8: */ | ||