diff options
Diffstat (limited to 'apps/plugins/puzzles/solo.c')
-rw-r--r-- | apps/plugins/puzzles/solo.c | 5656 |
1 files changed, 5656 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/solo.c b/apps/plugins/puzzles/solo.c new file mode 100644 index 0000000000..26f0eddd1a --- /dev/null +++ b/apps/plugins/puzzles/solo.c | |||
@@ -0,0 +1,5656 @@ | |||
1 | /* | ||
2 | * solo.c: the number-placing puzzle most popularly known as `Sudoku'. | ||
3 | * | ||
4 | * TODO: | ||
5 | * | ||
6 | * - reports from users are that `Trivial'-mode puzzles are still | ||
7 | * rather hard compared to newspapers' easy ones, so some better | ||
8 | * low-end difficulty grading would be nice | ||
9 | * + it's possible that really easy puzzles always have | ||
10 | * _several_ things you can do, so don't make you hunt too | ||
11 | * hard for the one deduction you can currently make | ||
12 | * + it's also possible that easy puzzles require fewer | ||
13 | * cross-eliminations: perhaps there's a higher incidence of | ||
14 | * things you can deduce by looking only at (say) rows, | ||
15 | * rather than things you have to check both rows and columns | ||
16 | * for | ||
17 | * + but really, what I need to do is find some really easy | ||
18 | * puzzles and _play_ them, to see what's actually easy about | ||
19 | * them | ||
20 | * + while I'm revamping this area, filling in the _last_ | ||
21 | * number in a nearly-full row or column should certainly be | ||
22 | * permitted even at the lowest difficulty level. | ||
23 | * + also Owen noticed that `Basic' grids requiring numeric | ||
24 | * elimination are actually very hard, so I wonder if a | ||
25 | * difficulty gradation between that and positional- | ||
26 | * elimination-only might be in order | ||
27 | * + but it's not good to have _too_ many difficulty levels, or | ||
28 | * it'll take too long to randomly generate a given level. | ||
29 | * | ||
30 | * - it might still be nice to do some prioritisation on the | ||
31 | * removal of numbers from the grid | ||
32 | * + one possibility is to try to minimise the maximum number | ||
33 | * of filled squares in any block, which in particular ought | ||
34 | * to enforce never leaving a completely filled block in the | ||
35 | * puzzle as presented. | ||
36 | * | ||
37 | * - alternative interface modes | ||
38 | * + sudoku.com's Windows program has a palette of possible | ||
39 | * entries; you select a palette entry first and then click | ||
40 | * on the square you want it to go in, thus enabling | ||
41 | * mouse-only play. Useful for PDAs! I don't think it's | ||
42 | * actually incompatible with the current highlight-then-type | ||
43 | * approach: you _either_ highlight a palette entry and then | ||
44 | * click, _or_ you highlight a square and then type. At most | ||
45 | * one thing is ever highlighted at a time, so there's no way | ||
46 | * to confuse the two. | ||
47 | * + then again, I don't actually like sudoku.com's interface; | ||
48 | * it's too much like a paint package whereas I prefer to | ||
49 | * think of Solo as a text editor. | ||
50 | * + another PDA-friendly possibility is a drag interface: | ||
51 | * _drag_ numbers from the palette into the grid squares. | ||
52 | * Thought experiments suggest I'd prefer that to the | ||
53 | * sudoku.com approach, but I haven't actually tried it. | ||
54 | */ | ||
55 | |||
56 | /* | ||
57 | * Solo puzzles need to be square overall (since each row and each | ||
58 | * column must contain one of every digit), but they need not be | ||
59 | * subdivided the same way internally. I am going to adopt a | ||
60 | * convention whereby I _always_ refer to `r' as the number of rows | ||
61 | * of _big_ divisions, and `c' as the number of columns of _big_ | ||
62 | * divisions. Thus, a 2c by 3r puzzle looks something like this: | ||
63 | * | ||
64 | * 4 5 1 | 2 6 3 | ||
65 | * 6 3 2 | 5 4 1 | ||
66 | * ------+------ (Of course, you can't subdivide it the other way | ||
67 | * 1 4 5 | 6 3 2 or you'll get clashes; observe that the 4 in the | ||
68 | * 3 2 6 | 4 1 5 top left would conflict with the 4 in the second | ||
69 | * ------+------ box down on the left-hand side.) | ||
70 | * 5 1 4 | 3 2 6 | ||
71 | * 2 6 3 | 1 5 4 | ||
72 | * | ||
73 | * The need for a strong naming convention should now be clear: | ||
74 | * each small box is two rows of digits by three columns, while the | ||
75 | * overall puzzle has three rows of small boxes by two columns. So | ||
76 | * I will (hopefully) consistently use `r' to denote the number of | ||
77 | * rows _of small boxes_ (here 3), which is also the number of | ||
78 | * columns of digits in each small box; and `c' vice versa (here | ||
79 | * 2). | ||
80 | * | ||
81 | * I'm also going to choose arbitrarily to list c first wherever | ||
82 | * possible: the above is a 2x3 puzzle, not a 3x2 one. | ||
83 | */ | ||
84 | |||
85 | #include <stdio.h> | ||
86 | #include <stdlib.h> | ||
87 | #include <string.h> | ||
88 | #include "rbassert.h" | ||
89 | #include <ctype.h> | ||
90 | #include <math.h> | ||
91 | |||
92 | #ifdef STANDALONE_SOLVER | ||
93 | #include <stdarg.h> | ||
94 | int solver_show_working, solver_recurse_depth; | ||
95 | #endif | ||
96 | |||
97 | #include "puzzles.h" | ||
98 | |||
99 | /* | ||
100 | * To save space, I store digits internally as unsigned char. This | ||
101 | * imposes a hard limit of 255 on the order of the puzzle. Since | ||
102 | * even a 5x5 takes unacceptably long to generate, I don't see this | ||
103 | * as a serious limitation unless something _really_ impressive | ||
104 | * happens in computing technology; but here's a typedef anyway for | ||
105 | * general good practice. | ||
106 | */ | ||
107 | typedef unsigned char digit; | ||
108 | #define ORDER_MAX 255 | ||
109 | |||
110 | #define PREFERRED_TILE_SIZE 48 | ||
111 | #define TILE_SIZE (ds->tilesize) | ||
112 | #define BORDER (TILE_SIZE / 2) | ||
113 | #define GRIDEXTRA max((TILE_SIZE / 32),1) | ||
114 | |||
115 | #define FLASH_TIME 0.4F | ||
116 | |||
117 | enum { SYMM_NONE, SYMM_ROT2, SYMM_ROT4, SYMM_REF2, SYMM_REF2D, SYMM_REF4, | ||
118 | SYMM_REF4D, SYMM_REF8 }; | ||
119 | |||
120 | enum { DIFF_BLOCK, | ||
121 | DIFF_SIMPLE, DIFF_INTERSECT, DIFF_SET, DIFF_EXTREME, DIFF_RECURSIVE, | ||
122 | DIFF_AMBIGUOUS, DIFF_IMPOSSIBLE }; | ||
123 | |||
124 | enum { DIFF_KSINGLE, DIFF_KMINMAX, DIFF_KSUMS, DIFF_KINTERSECT }; | ||
125 | |||
126 | enum { | ||
127 | COL_BACKGROUND, | ||
128 | COL_XDIAGONALS, | ||
129 | COL_GRID, | ||
130 | COL_CLUE, | ||
131 | COL_USER, | ||
132 | COL_HIGHLIGHT, | ||
133 | COL_ERROR, | ||
134 | COL_PENCIL, | ||
135 | COL_KILLER, | ||
136 | NCOLOURS | ||
137 | }; | ||
138 | |||
139 | /* | ||
140 | * To determine all possible ways to reach a given sum by adding two or | ||
141 | * three numbers from 1..9, each of which occurs exactly once in the sum, | ||
142 | * these arrays contain a list of bitmasks for each sum value, where if | ||
143 | * bit N is set, it means that N occurs in the sum. Each list is | ||
144 | * terminated by a zero if it is shorter than the size of the array. | ||
145 | */ | ||
146 | #define MAX_2SUMS 5 | ||
147 | #define MAX_3SUMS 8 | ||
148 | #define MAX_4SUMS 12 | ||
149 | unsigned long sum_bits2[18][MAX_2SUMS]; | ||
150 | unsigned long sum_bits3[25][MAX_3SUMS]; | ||
151 | unsigned long sum_bits4[31][MAX_4SUMS]; | ||
152 | |||
153 | static int find_sum_bits(unsigned long *array, int idx, int value_left, | ||
154 | int addends_left, int min_addend, | ||
155 | unsigned long bitmask_so_far) | ||
156 | { | ||
157 | int i; | ||
158 | assert(addends_left >= 2); | ||
159 | |||
160 | for (i = min_addend; i < value_left; i++) { | ||
161 | unsigned long new_bitmask = bitmask_so_far | (1L << i); | ||
162 | assert(bitmask_so_far != new_bitmask); | ||
163 | |||
164 | if (addends_left == 2) { | ||
165 | int j = value_left - i; | ||
166 | if (j <= i) | ||
167 | break; | ||
168 | if (j > 9) | ||
169 | continue; | ||
170 | array[idx++] = new_bitmask | (1L << j); | ||
171 | } else | ||
172 | idx = find_sum_bits(array, idx, value_left - i, | ||
173 | addends_left - 1, i + 1, | ||
174 | new_bitmask); | ||
175 | } | ||
176 | return idx; | ||
177 | } | ||
178 | |||
179 | static void precompute_sum_bits(void) | ||
180 | { | ||
181 | int i; | ||
182 | for (i = 3; i < 31; i++) { | ||
183 | int j; | ||
184 | if (i < 18) { | ||
185 | j = find_sum_bits(sum_bits2[i], 0, i, 2, 1, 0); | ||
186 | assert (j <= MAX_2SUMS); | ||
187 | if (j < MAX_2SUMS) | ||
188 | sum_bits2[i][j] = 0; | ||
189 | } | ||
190 | if (i < 25) { | ||
191 | j = find_sum_bits(sum_bits3[i], 0, i, 3, 1, 0); | ||
192 | assert (j <= MAX_3SUMS); | ||
193 | if (j < MAX_3SUMS) | ||
194 | sum_bits3[i][j] = 0; | ||
195 | } | ||
196 | j = find_sum_bits(sum_bits4[i], 0, i, 4, 1, 0); | ||
197 | assert (j <= MAX_4SUMS); | ||
198 | if (j < MAX_4SUMS) | ||
199 | sum_bits4[i][j] = 0; | ||
200 | } | ||
201 | } | ||
202 | |||
203 | struct game_params { | ||
204 | /* | ||
205 | * For a square puzzle, `c' and `r' indicate the puzzle | ||
206 | * parameters as described above. | ||
207 | * | ||
208 | * A jigsaw-style puzzle is indicated by r==1, in which case c | ||
209 | * can be whatever it likes (there is no constraint on | ||
210 | * compositeness - a 7x7 jigsaw sudoku makes perfect sense). | ||
211 | */ | ||
212 | int c, r, symm, diff, kdiff; | ||
213 | int xtype; /* require all digits in X-diagonals */ | ||
214 | int killer; | ||
215 | }; | ||
216 | |||
217 | struct block_structure { | ||
218 | int refcount; | ||
219 | |||
220 | /* | ||
221 | * For text formatting, we do need c and r here. | ||
222 | */ | ||
223 | int c, r, area; | ||
224 | |||
225 | /* | ||
226 | * For any square index, whichblock[i] gives its block index. | ||
227 | * | ||
228 | * For 0 <= b,i < cr, blocks[b][i] gives the index of the ith | ||
229 | * square in block b. nr_squares[b] gives the number of squares | ||
230 | * in block b (also the number of valid elements in blocks[b]). | ||
231 | * | ||
232 | * blocks_data holds the data pointed to by blocks. | ||
233 | * | ||
234 | * nr_squares may be NULL for block structures where all blocks are | ||
235 | * the same size. | ||
236 | */ | ||
237 | int *whichblock, **blocks, *nr_squares, *blocks_data; | ||
238 | int nr_blocks, max_nr_squares; | ||
239 | |||
240 | #ifdef STANDALONE_SOLVER | ||
241 | /* | ||
242 | * Textual descriptions of each block. For normal Sudoku these | ||
243 | * are of the form "(1,3)"; for jigsaw they are "starting at | ||
244 | * (5,7)". So the sensible usage in both cases is to say | ||
245 | * "elimination within block %s" with one of these strings. | ||
246 | * | ||
247 | * Only blocknames itself needs individually freeing; it's all | ||
248 | * one block. | ||
249 | */ | ||
250 | char **blocknames; | ||
251 | #endif | ||
252 | }; | ||
253 | |||
254 | struct game_state { | ||
255 | /* | ||
256 | * For historical reasons, I use `cr' to denote the overall | ||
257 | * width/height of the puzzle. It was a natural notation when | ||
258 | * all puzzles were divided into blocks in a grid, but doesn't | ||
259 | * really make much sense given jigsaw puzzles. However, the | ||
260 | * obvious `n' is heavily used in the solver to describe the | ||
261 | * index of a number being placed, so `cr' will have to stay. | ||
262 | */ | ||
263 | int cr; | ||
264 | struct block_structure *blocks; | ||
265 | struct block_structure *kblocks; /* Blocks for killer puzzles. */ | ||
266 | int xtype, killer; | ||
267 | digit *grid, *kgrid; | ||
268 | unsigned char *pencil; /* c*r*c*r elements */ | ||
269 | unsigned char *immutable; /* marks which digits are clues */ | ||
270 | int completed, cheated; | ||
271 | }; | ||
272 | |||
273 | static game_params *default_params(void) | ||
274 | { | ||
275 | game_params *ret = snew(game_params); | ||
276 | |||
277 | ret->c = ret->r = 3; | ||
278 | ret->xtype = FALSE; | ||
279 | ret->killer = FALSE; | ||
280 | ret->symm = SYMM_ROT2; /* a plausible default */ | ||
281 | ret->diff = DIFF_BLOCK; /* so is this */ | ||
282 | ret->kdiff = DIFF_KINTERSECT; /* so is this */ | ||
283 | |||
284 | return ret; | ||
285 | } | ||
286 | |||
287 | static void free_params(game_params *params) | ||
288 | { | ||
289 | sfree(params); | ||
290 | } | ||
291 | |||
292 | static game_params *dup_params(const game_params *params) | ||
293 | { | ||
294 | game_params *ret = snew(game_params); | ||
295 | *ret = *params; /* structure copy */ | ||
296 | return ret; | ||
297 | } | ||
298 | |||
299 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
300 | { | ||
301 | static struct { | ||
302 | char *title; | ||
303 | game_params params; | ||
304 | } presets[] = { | ||
305 | { "2x2 Trivial", { 2, 2, SYMM_ROT2, DIFF_BLOCK, DIFF_KMINMAX, FALSE, FALSE } }, | ||
306 | { "2x3 Basic", { 2, 3, SYMM_ROT2, DIFF_SIMPLE, DIFF_KMINMAX, FALSE, FALSE } }, | ||
307 | { "3x3 Trivial", { 3, 3, SYMM_ROT2, DIFF_BLOCK, DIFF_KMINMAX, FALSE, FALSE } }, | ||
308 | { "3x3 Basic", { 3, 3, SYMM_ROT2, DIFF_SIMPLE, DIFF_KMINMAX, FALSE, FALSE } }, | ||
309 | { "3x3 Basic X", { 3, 3, SYMM_ROT2, DIFF_SIMPLE, DIFF_KMINMAX, TRUE } }, | ||
310 | { "3x3 Intermediate", { 3, 3, SYMM_ROT2, DIFF_INTERSECT, DIFF_KMINMAX, FALSE, FALSE } }, | ||
311 | { "3x3 Advanced", { 3, 3, SYMM_ROT2, DIFF_SET, DIFF_KMINMAX, FALSE, FALSE } }, | ||
312 | { "3x3 Advanced X", { 3, 3, SYMM_ROT2, DIFF_SET, DIFF_KMINMAX, TRUE } }, | ||
313 | { "3x3 Extreme", { 3, 3, SYMM_ROT2, DIFF_EXTREME, DIFF_KMINMAX, FALSE, FALSE } }, | ||
314 | { "3x3 Unreasonable", { 3, 3, SYMM_ROT2, DIFF_RECURSIVE, DIFF_KMINMAX, FALSE, FALSE } }, | ||
315 | { "3x3 Killer", { 3, 3, SYMM_NONE, DIFF_BLOCK, DIFF_KINTERSECT, FALSE, TRUE } }, | ||
316 | { "9 Jigsaw Basic", { 9, 1, SYMM_ROT2, DIFF_SIMPLE, DIFF_KMINMAX, FALSE, FALSE } }, | ||
317 | { "9 Jigsaw Basic X", { 9, 1, SYMM_ROT2, DIFF_SIMPLE, DIFF_KMINMAX, TRUE } }, | ||
318 | { "9 Jigsaw Advanced", { 9, 1, SYMM_ROT2, DIFF_SET, DIFF_KMINMAX, FALSE, FALSE } }, | ||
319 | #ifndef SLOW_SYSTEM | ||
320 | { "3x4 Basic", { 3, 4, SYMM_ROT2, DIFF_SIMPLE, DIFF_KMINMAX, FALSE, FALSE } }, | ||
321 | { "4x4 Basic", { 4, 4, SYMM_ROT2, DIFF_SIMPLE, DIFF_KMINMAX, FALSE, FALSE } }, | ||
322 | #endif | ||
323 | }; | ||
324 | |||
325 | if (i < 0 || i >= lenof(presets)) | ||
326 | return FALSE; | ||
327 | |||
328 | *name = dupstr(presets[i].title); | ||
329 | *params = dup_params(&presets[i].params); | ||
330 | |||
331 | return TRUE; | ||
332 | } | ||
333 | |||
334 | static void decode_params(game_params *ret, char const *string) | ||
335 | { | ||
336 | int seen_r = FALSE; | ||
337 | |||
338 | ret->c = ret->r = atoi(string); | ||
339 | ret->xtype = FALSE; | ||
340 | ret->killer = FALSE; | ||
341 | while (*string && isdigit((unsigned char)*string)) string++; | ||
342 | if (*string == 'x') { | ||
343 | string++; | ||
344 | ret->r = atoi(string); | ||
345 | seen_r = TRUE; | ||
346 | while (*string && isdigit((unsigned char)*string)) string++; | ||
347 | } | ||
348 | while (*string) { | ||
349 | if (*string == 'j') { | ||
350 | string++; | ||
351 | if (seen_r) | ||
352 | ret->c *= ret->r; | ||
353 | ret->r = 1; | ||
354 | } else if (*string == 'x') { | ||
355 | string++; | ||
356 | ret->xtype = TRUE; | ||
357 | } else if (*string == 'k') { | ||
358 | string++; | ||
359 | ret->killer = TRUE; | ||
360 | } else if (*string == 'r' || *string == 'm' || *string == 'a') { | ||
361 | int sn, sc, sd; | ||
362 | sc = *string++; | ||
363 | if (sc == 'm' && *string == 'd') { | ||
364 | sd = TRUE; | ||
365 | string++; | ||
366 | } else { | ||
367 | sd = FALSE; | ||
368 | } | ||
369 | sn = atoi(string); | ||
370 | while (*string && isdigit((unsigned char)*string)) string++; | ||
371 | if (sc == 'm' && sn == 8) | ||
372 | ret->symm = SYMM_REF8; | ||
373 | if (sc == 'm' && sn == 4) | ||
374 | ret->symm = sd ? SYMM_REF4D : SYMM_REF4; | ||
375 | if (sc == 'm' && sn == 2) | ||
376 | ret->symm = sd ? SYMM_REF2D : SYMM_REF2; | ||
377 | if (sc == 'r' && sn == 4) | ||
378 | ret->symm = SYMM_ROT4; | ||
379 | if (sc == 'r' && sn == 2) | ||
380 | ret->symm = SYMM_ROT2; | ||
381 | if (sc == 'a') | ||
382 | ret->symm = SYMM_NONE; | ||
383 | } else if (*string == 'd') { | ||
384 | string++; | ||
385 | if (*string == 't') /* trivial */ | ||
386 | string++, ret->diff = DIFF_BLOCK; | ||
387 | else if (*string == 'b') /* basic */ | ||
388 | string++, ret->diff = DIFF_SIMPLE; | ||
389 | else if (*string == 'i') /* intermediate */ | ||
390 | string++, ret->diff = DIFF_INTERSECT; | ||
391 | else if (*string == 'a') /* advanced */ | ||
392 | string++, ret->diff = DIFF_SET; | ||
393 | else if (*string == 'e') /* extreme */ | ||
394 | string++, ret->diff = DIFF_EXTREME; | ||
395 | else if (*string == 'u') /* unreasonable */ | ||
396 | string++, ret->diff = DIFF_RECURSIVE; | ||
397 | } else | ||
398 | string++; /* eat unknown character */ | ||
399 | } | ||
400 | } | ||
401 | |||
402 | static char *encode_params(const game_params *params, int full) | ||
403 | { | ||
404 | char str[80]; | ||
405 | |||
406 | if (params->r > 1) | ||
407 | sprintf(str, "%dx%d", params->c, params->r); | ||
408 | else | ||
409 | sprintf(str, "%dj", params->c); | ||
410 | if (params->xtype) | ||
411 | strcat(str, "x"); | ||
412 | if (params->killer) | ||
413 | strcat(str, "k"); | ||
414 | |||
415 | if (full) { | ||
416 | switch (params->symm) { | ||
417 | case SYMM_REF8: strcat(str, "m8"); break; | ||
418 | case SYMM_REF4: strcat(str, "m4"); break; | ||
419 | case SYMM_REF4D: strcat(str, "md4"); break; | ||
420 | case SYMM_REF2: strcat(str, "m2"); break; | ||
421 | case SYMM_REF2D: strcat(str, "md2"); break; | ||
422 | case SYMM_ROT4: strcat(str, "r4"); break; | ||
423 | /* case SYMM_ROT2: strcat(str, "r2"); break; [default] */ | ||
424 | case SYMM_NONE: strcat(str, "a"); break; | ||
425 | } | ||
426 | switch (params->diff) { | ||
427 | /* case DIFF_BLOCK: strcat(str, "dt"); break; [default] */ | ||
428 | case DIFF_SIMPLE: strcat(str, "db"); break; | ||
429 | case DIFF_INTERSECT: strcat(str, "di"); break; | ||
430 | case DIFF_SET: strcat(str, "da"); break; | ||
431 | case DIFF_EXTREME: strcat(str, "de"); break; | ||
432 | case DIFF_RECURSIVE: strcat(str, "du"); break; | ||
433 | } | ||
434 | } | ||
435 | return dupstr(str); | ||
436 | } | ||
437 | |||
438 | static config_item *game_configure(const game_params *params) | ||
439 | { | ||
440 | config_item *ret; | ||
441 | char buf[80]; | ||
442 | |||
443 | ret = snewn(8, config_item); | ||
444 | |||
445 | ret[0].name = "Columns of sub-blocks"; | ||
446 | ret[0].type = C_STRING; | ||
447 | sprintf(buf, "%d", params->c); | ||
448 | ret[0].sval = dupstr(buf); | ||
449 | ret[0].ival = 0; | ||
450 | |||
451 | ret[1].name = "Rows of sub-blocks"; | ||
452 | ret[1].type = C_STRING; | ||
453 | sprintf(buf, "%d", params->r); | ||
454 | ret[1].sval = dupstr(buf); | ||
455 | ret[1].ival = 0; | ||
456 | |||
457 | ret[2].name = "\"X\" (require every number in each main diagonal)"; | ||
458 | ret[2].type = C_BOOLEAN; | ||
459 | ret[2].sval = NULL; | ||
460 | ret[2].ival = params->xtype; | ||
461 | |||
462 | ret[3].name = "Jigsaw (irregularly shaped sub-blocks)"; | ||
463 | ret[3].type = C_BOOLEAN; | ||
464 | ret[3].sval = NULL; | ||
465 | ret[3].ival = (params->r == 1); | ||
466 | |||
467 | ret[4].name = "Killer (digit sums)"; | ||
468 | ret[4].type = C_BOOLEAN; | ||
469 | ret[4].sval = NULL; | ||
470 | ret[4].ival = params->killer; | ||
471 | |||
472 | ret[5].name = "Symmetry"; | ||
473 | ret[5].type = C_CHOICES; | ||
474 | ret[5].sval = ":None:2-way rotation:4-way rotation:2-way mirror:" | ||
475 | "2-way diagonal mirror:4-way mirror:4-way diagonal mirror:" | ||
476 | "8-way mirror"; | ||
477 | ret[5].ival = params->symm; | ||
478 | |||
479 | ret[6].name = "Difficulty"; | ||
480 | ret[6].type = C_CHOICES; | ||
481 | ret[6].sval = ":Trivial:Basic:Intermediate:Advanced:Extreme:Unreasonable"; | ||
482 | ret[6].ival = params->diff; | ||
483 | |||
484 | ret[7].name = NULL; | ||
485 | ret[7].type = C_END; | ||
486 | ret[7].sval = NULL; | ||
487 | ret[7].ival = 0; | ||
488 | |||
489 | return ret; | ||
490 | } | ||
491 | |||
492 | static game_params *custom_params(const config_item *cfg) | ||
493 | { | ||
494 | game_params *ret = snew(game_params); | ||
495 | |||
496 | ret->c = atoi(cfg[0].sval); | ||
497 | ret->r = atoi(cfg[1].sval); | ||
498 | ret->xtype = cfg[2].ival; | ||
499 | if (cfg[3].ival) { | ||
500 | ret->c *= ret->r; | ||
501 | ret->r = 1; | ||
502 | } | ||
503 | ret->killer = cfg[4].ival; | ||
504 | ret->symm = cfg[5].ival; | ||
505 | ret->diff = cfg[6].ival; | ||
506 | ret->kdiff = DIFF_KINTERSECT; | ||
507 | |||
508 | return ret; | ||
509 | } | ||
510 | |||
511 | static char *validate_params(const game_params *params, int full) | ||
512 | { | ||
513 | if (params->c < 2) | ||
514 | return "Both dimensions must be at least 2"; | ||
515 | if (params->c > ORDER_MAX || params->r > ORDER_MAX) | ||
516 | return "Dimensions greater than "STR(ORDER_MAX)" are not supported"; | ||
517 | if ((params->c * params->r) > 31) | ||
518 | return "Unable to support more than 31 distinct symbols in a puzzle"; | ||
519 | if (params->killer && params->c * params->r > 9) | ||
520 | return "Killer puzzle dimensions must be smaller than 10."; | ||
521 | return NULL; | ||
522 | } | ||
523 | |||
524 | /* | ||
525 | * ---------------------------------------------------------------------- | ||
526 | * Block structure functions. | ||
527 | */ | ||
528 | |||
529 | static struct block_structure *alloc_block_structure(int c, int r, int area, | ||
530 | int max_nr_squares, | ||
531 | int nr_blocks) | ||
532 | { | ||
533 | int i; | ||
534 | struct block_structure *b = snew(struct block_structure); | ||
535 | |||
536 | b->refcount = 1; | ||
537 | b->nr_blocks = nr_blocks; | ||
538 | b->max_nr_squares = max_nr_squares; | ||
539 | b->c = c; b->r = r; b->area = area; | ||
540 | b->whichblock = snewn(area, int); | ||
541 | b->blocks_data = snewn(nr_blocks * max_nr_squares, int); | ||
542 | b->blocks = snewn(nr_blocks, int *); | ||
543 | b->nr_squares = snewn(nr_blocks, int); | ||
544 | |||
545 | for (i = 0; i < nr_blocks; i++) | ||
546 | b->blocks[i] = b->blocks_data + i*max_nr_squares; | ||
547 | |||
548 | #ifdef STANDALONE_SOLVER | ||
549 | b->blocknames = (char **)smalloc(c*r*(sizeof(char *)+80)); | ||
550 | for (i = 0; i < c * r; i++) | ||
551 | b->blocknames[i] = NULL; | ||
552 | #endif | ||
553 | return b; | ||
554 | } | ||
555 | |||
556 | static void free_block_structure(struct block_structure *b) | ||
557 | { | ||
558 | if (--b->refcount == 0) { | ||
559 | sfree(b->whichblock); | ||
560 | sfree(b->blocks); | ||
561 | sfree(b->blocks_data); | ||
562 | #ifdef STANDALONE_SOLVER | ||
563 | sfree(b->blocknames); | ||
564 | #endif | ||
565 | sfree(b->nr_squares); | ||
566 | sfree(b); | ||
567 | } | ||
568 | } | ||
569 | |||
570 | static struct block_structure *dup_block_structure(struct block_structure *b) | ||
571 | { | ||
572 | struct block_structure *nb; | ||
573 | int i; | ||
574 | |||
575 | nb = alloc_block_structure(b->c, b->r, b->area, b->max_nr_squares, | ||
576 | b->nr_blocks); | ||
577 | memcpy(nb->nr_squares, b->nr_squares, b->nr_blocks * sizeof *b->nr_squares); | ||
578 | memcpy(nb->whichblock, b->whichblock, b->area * sizeof *b->whichblock); | ||
579 | memcpy(nb->blocks_data, b->blocks_data, | ||
580 | b->nr_blocks * b->max_nr_squares * sizeof *b->blocks_data); | ||
581 | for (i = 0; i < b->nr_blocks; i++) | ||
582 | nb->blocks[i] = nb->blocks_data + i*nb->max_nr_squares; | ||
583 | |||
584 | #ifdef STANDALONE_SOLVER | ||
585 | memcpy(nb->blocknames, b->blocknames, b->c * b->r *(sizeof(char *)+80)); | ||
586 | { | ||
587 | int i; | ||
588 | for (i = 0; i < b->c * b->r; i++) | ||
589 | if (b->blocknames[i] == NULL) | ||
590 | nb->blocknames[i] = NULL; | ||
591 | else | ||
592 | nb->blocknames[i] = ((char *)nb->blocknames) + (b->blocknames[i] - (char *)b->blocknames); | ||
593 | } | ||
594 | #endif | ||
595 | return nb; | ||
596 | } | ||
597 | |||
598 | static void split_block(struct block_structure *b, int *squares, int nr_squares) | ||
599 | { | ||
600 | int i, j; | ||
601 | int previous_block = b->whichblock[squares[0]]; | ||
602 | int newblock = b->nr_blocks; | ||
603 | |||
604 | assert(b->max_nr_squares >= nr_squares); | ||
605 | assert(b->nr_squares[previous_block] > nr_squares); | ||
606 | |||
607 | b->nr_blocks++; | ||
608 | b->blocks_data = sresize(b->blocks_data, | ||
609 | b->nr_blocks * b->max_nr_squares, int); | ||
610 | b->nr_squares = sresize(b->nr_squares, b->nr_blocks, int); | ||
611 | sfree(b->blocks); | ||
612 | b->blocks = snewn(b->nr_blocks, int *); | ||
613 | for (i = 0; i < b->nr_blocks; i++) | ||
614 | b->blocks[i] = b->blocks_data + i*b->max_nr_squares; | ||
615 | for (i = 0; i < nr_squares; i++) { | ||
616 | assert(b->whichblock[squares[i]] == previous_block); | ||
617 | b->whichblock[squares[i]] = newblock; | ||
618 | b->blocks[newblock][i] = squares[i]; | ||
619 | } | ||
620 | for (i = j = 0; i < b->nr_squares[previous_block]; i++) { | ||
621 | int k; | ||
622 | int sq = b->blocks[previous_block][i]; | ||
623 | for (k = 0; k < nr_squares; k++) | ||
624 | if (squares[k] == sq) | ||
625 | break; | ||
626 | if (k == nr_squares) | ||
627 | b->blocks[previous_block][j++] = sq; | ||
628 | } | ||
629 | b->nr_squares[previous_block] -= nr_squares; | ||
630 | b->nr_squares[newblock] = nr_squares; | ||
631 | } | ||
632 | |||
633 | static void remove_from_block(struct block_structure *blocks, int b, int n) | ||
634 | { | ||
635 | int i, j; | ||
636 | blocks->whichblock[n] = -1; | ||
637 | for (i = j = 0; i < blocks->nr_squares[b]; i++) | ||
638 | if (blocks->blocks[b][i] != n) | ||
639 | blocks->blocks[b][j++] = blocks->blocks[b][i]; | ||
640 | assert(j+1 == i); | ||
641 | blocks->nr_squares[b]--; | ||
642 | } | ||
643 | |||
644 | /* ---------------------------------------------------------------------- | ||
645 | * Solver. | ||
646 | * | ||
647 | * This solver is used for two purposes: | ||
648 | * + to check solubility of a grid as we gradually remove numbers | ||
649 | * from it | ||
650 | * + to solve an externally generated puzzle when the user selects | ||
651 | * `Solve'. | ||
652 | * | ||
653 | * It supports a variety of specific modes of reasoning. By | ||
654 | * enabling or disabling subsets of these modes we can arrange a | ||
655 | * range of difficulty levels. | ||
656 | */ | ||
657 | |||
658 | /* | ||
659 | * Modes of reasoning currently supported: | ||
660 | * | ||
661 | * - Positional elimination: a number must go in a particular | ||
662 | * square because all the other empty squares in a given | ||
663 | * row/col/blk are ruled out. | ||
664 | * | ||
665 | * - Killer minmax elimination: for killer-type puzzles, a number | ||
666 | * is impossible if choosing it would cause the sum in a killer | ||
667 | * region to be guaranteed to be too large or too small. | ||
668 | * | ||
669 | * - Numeric elimination: a square must have a particular number | ||
670 | * in because all the other numbers that could go in it are | ||
671 | * ruled out. | ||
672 | * | ||
673 | * - Intersectional analysis: given two domains which overlap | ||
674 | * (hence one must be a block, and the other can be a row or | ||
675 | * col), if the possible locations for a particular number in | ||
676 | * one of the domains can be narrowed down to the overlap, then | ||
677 | * that number can be ruled out everywhere but the overlap in | ||
678 | * the other domain too. | ||
679 | * | ||
680 | * - Set elimination: if there is a subset of the empty squares | ||
681 | * within a domain such that the union of the possible numbers | ||
682 | * in that subset has the same size as the subset itself, then | ||
683 | * those numbers can be ruled out everywhere else in the domain. | ||
684 | * (For example, if there are five empty squares and the | ||
685 | * possible numbers in each are 12, 23, 13, 134 and 1345, then | ||
686 | * the first three empty squares form such a subset: the numbers | ||
687 | * 1, 2 and 3 _must_ be in those three squares in some | ||
688 | * permutation, and hence we can deduce none of them can be in | ||
689 | * the fourth or fifth squares.) | ||
690 | * + You can also see this the other way round, concentrating | ||
691 | * on numbers rather than squares: if there is a subset of | ||
692 | * the unplaced numbers within a domain such that the union | ||
693 | * of all their possible positions has the same size as the | ||
694 | * subset itself, then all other numbers can be ruled out for | ||
695 | * those positions. However, it turns out that this is | ||
696 | * exactly equivalent to the first formulation at all times: | ||
697 | * there is a 1-1 correspondence between suitable subsets of | ||
698 | * the unplaced numbers and suitable subsets of the unfilled | ||
699 | * places, found by taking the _complement_ of the union of | ||
700 | * the numbers' possible positions (or the spaces' possible | ||
701 | * contents). | ||
702 | * | ||
703 | * - Forcing chains (see comment for solver_forcing().) | ||
704 | * | ||
705 | * - Recursion. If all else fails, we pick one of the currently | ||
706 | * most constrained empty squares and take a random guess at its | ||
707 | * contents, then continue solving on that basis and see if we | ||
708 | * get any further. | ||
709 | */ | ||
710 | |||
711 | struct solver_usage { | ||
712 | int cr; | ||
713 | struct block_structure *blocks, *kblocks, *extra_cages; | ||
714 | /* | ||
715 | * We set up a cubic array, indexed by x, y and digit; each | ||
716 | * element of this array is TRUE or FALSE according to whether | ||
717 | * or not that digit _could_ in principle go in that position. | ||
718 | * | ||
719 | * The way to index this array is cube[(y*cr+x)*cr+n-1]; there | ||
720 | * are macros below to help with this. | ||
721 | */ | ||
722 | unsigned char *cube; | ||
723 | /* | ||
724 | * This is the grid in which we write down our final | ||
725 | * deductions. y-coordinates in here are _not_ transformed. | ||
726 | */ | ||
727 | digit *grid; | ||
728 | /* | ||
729 | * For killer-type puzzles, kclues holds the secondary clue for | ||
730 | * each cage. For derived cages, the clue is in extra_clues. | ||
731 | */ | ||
732 | digit *kclues, *extra_clues; | ||
733 | /* | ||
734 | * Now we keep track, at a slightly higher level, of what we | ||
735 | * have yet to work out, to prevent doing the same deduction | ||
736 | * many times. | ||
737 | */ | ||
738 | /* row[y*cr+n-1] TRUE if digit n has been placed in row y */ | ||
739 | unsigned char *row; | ||
740 | /* col[x*cr+n-1] TRUE if digit n has been placed in row x */ | ||
741 | unsigned char *col; | ||
742 | /* blk[i*cr+n-1] TRUE if digit n has been placed in block i */ | ||
743 | unsigned char *blk; | ||
744 | /* diag[i*cr+n-1] TRUE if digit n has been placed in diagonal i */ | ||
745 | unsigned char *diag; /* diag 0 is \, 1 is / */ | ||
746 | |||
747 | int *regions; | ||
748 | int nr_regions; | ||
749 | int **sq2region; | ||
750 | }; | ||
751 | #define cubepos2(xy,n) ((xy)*usage->cr+(n)-1) | ||
752 | #define cubepos(x,y,n) cubepos2((y)*usage->cr+(x),n) | ||
753 | #define cube(x,y,n) (usage->cube[cubepos(x,y,n)]) | ||
754 | #define cube2(xy,n) (usage->cube[cubepos2(xy,n)]) | ||
755 | |||
756 | #define ondiag0(xy) ((xy) % (cr+1) == 0) | ||
757 | #define ondiag1(xy) ((xy) % (cr-1) == 0 && (xy) > 0 && (xy) < cr*cr-1) | ||
758 | #define diag0(i) ((i) * (cr+1)) | ||
759 | #define diag1(i) ((i+1) * (cr-1)) | ||
760 | |||
761 | /* | ||
762 | * Function called when we are certain that a particular square has | ||
763 | * a particular number in it. The y-coordinate passed in here is | ||
764 | * transformed. | ||
765 | */ | ||
766 | static void solver_place(struct solver_usage *usage, int x, int y, int n) | ||
767 | { | ||
768 | int cr = usage->cr; | ||
769 | int sqindex = y*cr+x; | ||
770 | int i, bi; | ||
771 | |||
772 | assert(cube(x,y,n)); | ||
773 | |||
774 | /* | ||
775 | * Rule out all other numbers in this square. | ||
776 | */ | ||
777 | for (i = 1; i <= cr; i++) | ||
778 | if (i != n) | ||
779 | cube(x,y,i) = FALSE; | ||
780 | |||
781 | /* | ||
782 | * Rule out this number in all other positions in the row. | ||
783 | */ | ||
784 | for (i = 0; i < cr; i++) | ||
785 | if (i != y) | ||
786 | cube(x,i,n) = FALSE; | ||
787 | |||
788 | /* | ||
789 | * Rule out this number in all other positions in the column. | ||
790 | */ | ||
791 | for (i = 0; i < cr; i++) | ||
792 | if (i != x) | ||
793 | cube(i,y,n) = FALSE; | ||
794 | |||
795 | /* | ||
796 | * Rule out this number in all other positions in the block. | ||
797 | */ | ||
798 | bi = usage->blocks->whichblock[sqindex]; | ||
799 | for (i = 0; i < cr; i++) { | ||
800 | int bp = usage->blocks->blocks[bi][i]; | ||
801 | if (bp != sqindex) | ||
802 | cube2(bp,n) = FALSE; | ||
803 | } | ||
804 | |||
805 | /* | ||
806 | * Enter the number in the result grid. | ||
807 | */ | ||
808 | usage->grid[sqindex] = n; | ||
809 | |||
810 | /* | ||
811 | * Cross out this number from the list of numbers left to place | ||
812 | * in its row, its column and its block. | ||
813 | */ | ||
814 | usage->row[y*cr+n-1] = usage->col[x*cr+n-1] = | ||
815 | usage->blk[bi*cr+n-1] = TRUE; | ||
816 | |||
817 | if (usage->diag) { | ||
818 | if (ondiag0(sqindex)) { | ||
819 | for (i = 0; i < cr; i++) | ||
820 | if (diag0(i) != sqindex) | ||
821 | cube2(diag0(i),n) = FALSE; | ||
822 | usage->diag[n-1] = TRUE; | ||
823 | } | ||
824 | if (ondiag1(sqindex)) { | ||
825 | for (i = 0; i < cr; i++) | ||
826 | if (diag1(i) != sqindex) | ||
827 | cube2(diag1(i),n) = FALSE; | ||
828 | usage->diag[cr+n-1] = TRUE; | ||
829 | } | ||
830 | } | ||
831 | } | ||
832 | |||
833 | #if defined STANDALONE_SOLVER && defined __GNUC__ | ||
834 | /* | ||
835 | * Forward-declare the functions taking printf-like format arguments | ||
836 | * with __attribute__((format)) so as to ensure the argument syntax | ||
837 | * gets debugged. | ||
838 | */ | ||
839 | struct solver_scratch; | ||
840 | static int solver_elim(struct solver_usage *usage, int *indices, | ||
841 | char *fmt, ...) __attribute__((format(printf,3,4))); | ||
842 | static int solver_intersect(struct solver_usage *usage, | ||
843 | int *indices1, int *indices2, char *fmt, ...) | ||
844 | __attribute__((format(printf,4,5))); | ||
845 | static int solver_set(struct solver_usage *usage, | ||
846 | struct solver_scratch *scratch, | ||
847 | int *indices, char *fmt, ...) | ||
848 | __attribute__((format(printf,4,5))); | ||
849 | #endif | ||
850 | |||
851 | static int solver_elim(struct solver_usage *usage, int *indices | ||
852 | #ifdef STANDALONE_SOLVER | ||
853 | , char *fmt, ... | ||
854 | #endif | ||
855 | ) | ||
856 | { | ||
857 | int cr = usage->cr; | ||
858 | int fpos, m, i; | ||
859 | |||
860 | /* | ||
861 | * Count the number of set bits within this section of the | ||
862 | * cube. | ||
863 | */ | ||
864 | m = 0; | ||
865 | fpos = -1; | ||
866 | for (i = 0; i < cr; i++) | ||
867 | if (usage->cube[indices[i]]) { | ||
868 | fpos = indices[i]; | ||
869 | m++; | ||
870 | } | ||
871 | |||
872 | if (m == 1) { | ||
873 | int x, y, n; | ||
874 | assert(fpos >= 0); | ||
875 | |||
876 | n = 1 + fpos % cr; | ||
877 | x = fpos / cr; | ||
878 | y = x / cr; | ||
879 | x %= cr; | ||
880 | |||
881 | if (!usage->grid[y*cr+x]) { | ||
882 | #ifdef STANDALONE_SOLVER | ||
883 | if (solver_show_working) { | ||
884 | va_list ap; | ||
885 | printf("%*s", solver_recurse_depth*4, ""); | ||
886 | va_start(ap, fmt); | ||
887 | vprintf(fmt, ap); | ||
888 | va_end(ap); | ||
889 | printf(":\n%*s placing %d at (%d,%d)\n", | ||
890 | solver_recurse_depth*4, "", n, 1+x, 1+y); | ||
891 | } | ||
892 | #endif | ||
893 | solver_place(usage, x, y, n); | ||
894 | return +1; | ||
895 | } | ||
896 | } else if (m == 0) { | ||
897 | #ifdef STANDALONE_SOLVER | ||
898 | if (solver_show_working) { | ||
899 | va_list ap; | ||
900 | printf("%*s", solver_recurse_depth*4, ""); | ||
901 | va_start(ap, fmt); | ||
902 | vprintf(fmt, ap); | ||
903 | va_end(ap); | ||
904 | printf(":\n%*s no possibilities available\n", | ||
905 | solver_recurse_depth*4, ""); | ||
906 | } | ||
907 | #endif | ||
908 | return -1; | ||
909 | } | ||
910 | |||
911 | return 0; | ||
912 | } | ||
913 | |||
914 | static int solver_intersect(struct solver_usage *usage, | ||
915 | int *indices1, int *indices2 | ||
916 | #ifdef STANDALONE_SOLVER | ||
917 | , char *fmt, ... | ||
918 | #endif | ||
919 | ) | ||
920 | { | ||
921 | int cr = usage->cr; | ||
922 | int ret, i, j; | ||
923 | |||
924 | /* | ||
925 | * Loop over the first domain and see if there's any set bit | ||
926 | * not also in the second. | ||
927 | */ | ||
928 | for (i = j = 0; i < cr; i++) { | ||
929 | int p = indices1[i]; | ||
930 | while (j < cr && indices2[j] < p) | ||
931 | j++; | ||
932 | if (usage->cube[p]) { | ||
933 | if (j < cr && indices2[j] == p) | ||
934 | continue; /* both domains contain this index */ | ||
935 | else | ||
936 | return 0; /* there is, so we can't deduce */ | ||
937 | } | ||
938 | } | ||
939 | |||
940 | /* | ||
941 | * We have determined that all set bits in the first domain are | ||
942 | * within its overlap with the second. So loop over the second | ||
943 | * domain and remove all set bits that aren't also in that | ||
944 | * overlap; return +1 iff we actually _did_ anything. | ||
945 | */ | ||
946 | ret = 0; | ||
947 | for (i = j = 0; i < cr; i++) { | ||
948 | int p = indices2[i]; | ||
949 | while (j < cr && indices1[j] < p) | ||
950 | j++; | ||
951 | if (usage->cube[p] && (j >= cr || indices1[j] != p)) { | ||
952 | #ifdef STANDALONE_SOLVER | ||
953 | if (solver_show_working) { | ||
954 | int px, py, pn; | ||
955 | |||
956 | if (!ret) { | ||
957 | va_list ap; | ||
958 | printf("%*s", solver_recurse_depth*4, ""); | ||
959 | va_start(ap, fmt); | ||
960 | vprintf(fmt, ap); | ||
961 | va_end(ap); | ||
962 | printf(":\n"); | ||
963 | } | ||
964 | |||
965 | pn = 1 + p % cr; | ||
966 | px = p / cr; | ||
967 | py = px / cr; | ||
968 | px %= cr; | ||
969 | |||
970 | printf("%*s ruling out %d at (%d,%d)\n", | ||
971 | solver_recurse_depth*4, "", pn, 1+px, 1+py); | ||
972 | } | ||
973 | #endif | ||
974 | ret = +1; /* we did something */ | ||
975 | usage->cube[p] = 0; | ||
976 | } | ||
977 | } | ||
978 | |||
979 | return ret; | ||
980 | } | ||
981 | |||
982 | struct solver_scratch { | ||
983 | unsigned char *grid, *rowidx, *colidx, *set; | ||
984 | int *neighbours, *bfsqueue; | ||
985 | int *indexlist, *indexlist2; | ||
986 | #ifdef STANDALONE_SOLVER | ||
987 | int *bfsprev; | ||
988 | #endif | ||
989 | }; | ||
990 | |||
991 | static int solver_set(struct solver_usage *usage, | ||
992 | struct solver_scratch *scratch, | ||
993 | int *indices | ||
994 | #ifdef STANDALONE_SOLVER | ||
995 | , char *fmt, ... | ||
996 | #endif | ||
997 | ) | ||
998 | { | ||
999 | int cr = usage->cr; | ||
1000 | int i, j, n, count; | ||
1001 | unsigned char *grid = scratch->grid; | ||
1002 | unsigned char *rowidx = scratch->rowidx; | ||
1003 | unsigned char *colidx = scratch->colidx; | ||
1004 | unsigned char *set = scratch->set; | ||
1005 | |||
1006 | /* | ||
1007 | * We are passed a cr-by-cr matrix of booleans. Our first job | ||
1008 | * is to winnow it by finding any definite placements - i.e. | ||
1009 | * any row with a solitary 1 - and discarding that row and the | ||
1010 | * column containing the 1. | ||
1011 | */ | ||
1012 | memset(rowidx, TRUE, cr); | ||
1013 | memset(colidx, TRUE, cr); | ||
1014 | for (i = 0; i < cr; i++) { | ||
1015 | int count = 0, first = -1; | ||
1016 | for (j = 0; j < cr; j++) | ||
1017 | if (usage->cube[indices[i*cr+j]]) | ||
1018 | first = j, count++; | ||
1019 | |||
1020 | /* | ||
1021 | * If count == 0, then there's a row with no 1s at all and | ||
1022 | * the puzzle is internally inconsistent. However, we ought | ||
1023 | * to have caught this already during the simpler reasoning | ||
1024 | * methods, so we can safely fail an assertion if we reach | ||
1025 | * this point here. | ||
1026 | */ | ||
1027 | assert(count > 0); | ||
1028 | if (count == 1) | ||
1029 | rowidx[i] = colidx[first] = FALSE; | ||
1030 | } | ||
1031 | |||
1032 | /* | ||
1033 | * Convert each of rowidx/colidx from a list of 0s and 1s to a | ||
1034 | * list of the indices of the 1s. | ||
1035 | */ | ||
1036 | for (i = j = 0; i < cr; i++) | ||
1037 | if (rowidx[i]) | ||
1038 | rowidx[j++] = i; | ||
1039 | n = j; | ||
1040 | for (i = j = 0; i < cr; i++) | ||
1041 | if (colidx[i]) | ||
1042 | colidx[j++] = i; | ||
1043 | assert(n == j); | ||
1044 | |||
1045 | /* | ||
1046 | * And create the smaller matrix. | ||
1047 | */ | ||
1048 | for (i = 0; i < n; i++) | ||
1049 | for (j = 0; j < n; j++) | ||
1050 | grid[i*cr+j] = usage->cube[indices[rowidx[i]*cr+colidx[j]]]; | ||
1051 | |||
1052 | /* | ||
1053 | * Having done that, we now have a matrix in which every row | ||
1054 | * has at least two 1s in. Now we search to see if we can find | ||
1055 | * a rectangle of zeroes (in the set-theoretic sense of | ||
1056 | * `rectangle', i.e. a subset of rows crossed with a subset of | ||
1057 | * columns) whose width and height add up to n. | ||
1058 | */ | ||
1059 | |||
1060 | memset(set, 0, n); | ||
1061 | count = 0; | ||
1062 | while (1) { | ||
1063 | /* | ||
1064 | * We have a candidate set. If its size is <=1 or >=n-1 | ||
1065 | * then we move on immediately. | ||
1066 | */ | ||
1067 | if (count > 1 && count < n-1) { | ||
1068 | /* | ||
1069 | * The number of rows we need is n-count. See if we can | ||
1070 | * find that many rows which each have a zero in all | ||
1071 | * the positions listed in `set'. | ||
1072 | */ | ||
1073 | int rows = 0; | ||
1074 | for (i = 0; i < n; i++) { | ||
1075 | int ok = TRUE; | ||
1076 | for (j = 0; j < n; j++) | ||
1077 | if (set[j] && grid[i*cr+j]) { | ||
1078 | ok = FALSE; | ||
1079 | break; | ||
1080 | } | ||
1081 | if (ok) | ||
1082 | rows++; | ||
1083 | } | ||
1084 | |||
1085 | /* | ||
1086 | * We expect never to be able to get _more_ than | ||
1087 | * n-count suitable rows: this would imply that (for | ||
1088 | * example) there are four numbers which between them | ||
1089 | * have at most three possible positions, and hence it | ||
1090 | * indicates a faulty deduction before this point or | ||
1091 | * even a bogus clue. | ||
1092 | */ | ||
1093 | if (rows > n - count) { | ||
1094 | #ifdef STANDALONE_SOLVER | ||
1095 | if (solver_show_working) { | ||
1096 | va_list ap; | ||
1097 | printf("%*s", solver_recurse_depth*4, | ||
1098 | ""); | ||
1099 | va_start(ap, fmt); | ||
1100 | vprintf(fmt, ap); | ||
1101 | va_end(ap); | ||
1102 | printf(":\n%*s contradiction reached\n", | ||
1103 | solver_recurse_depth*4, ""); | ||
1104 | } | ||
1105 | #endif | ||
1106 | return -1; | ||
1107 | } | ||
1108 | |||
1109 | if (rows >= n - count) { | ||
1110 | int progress = FALSE; | ||
1111 | |||
1112 | /* | ||
1113 | * We've got one! Now, for each row which _doesn't_ | ||
1114 | * satisfy the criterion, eliminate all its set | ||
1115 | * bits in the positions _not_ listed in `set'. | ||
1116 | * Return +1 (meaning progress has been made) if we | ||
1117 | * successfully eliminated anything at all. | ||
1118 | * | ||
1119 | * This involves referring back through | ||
1120 | * rowidx/colidx in order to work out which actual | ||
1121 | * positions in the cube to meddle with. | ||
1122 | */ | ||
1123 | for (i = 0; i < n; i++) { | ||
1124 | int ok = TRUE; | ||
1125 | for (j = 0; j < n; j++) | ||
1126 | if (set[j] && grid[i*cr+j]) { | ||
1127 | ok = FALSE; | ||
1128 | break; | ||
1129 | } | ||
1130 | if (!ok) { | ||
1131 | for (j = 0; j < n; j++) | ||
1132 | if (!set[j] && grid[i*cr+j]) { | ||
1133 | int fpos = indices[rowidx[i]*cr+colidx[j]]; | ||
1134 | #ifdef STANDALONE_SOLVER | ||
1135 | if (solver_show_working) { | ||
1136 | int px, py, pn; | ||
1137 | |||
1138 | if (!progress) { | ||
1139 | va_list ap; | ||
1140 | printf("%*s", solver_recurse_depth*4, | ||
1141 | ""); | ||
1142 | va_start(ap, fmt); | ||
1143 | vprintf(fmt, ap); | ||
1144 | va_end(ap); | ||
1145 | printf(":\n"); | ||
1146 | } | ||
1147 | |||
1148 | pn = 1 + fpos % cr; | ||
1149 | px = fpos / cr; | ||
1150 | py = px / cr; | ||
1151 | px %= cr; | ||
1152 | |||
1153 | printf("%*s ruling out %d at (%d,%d)\n", | ||
1154 | solver_recurse_depth*4, "", | ||
1155 | pn, 1+px, 1+py); | ||
1156 | } | ||
1157 | #endif | ||
1158 | progress = TRUE; | ||
1159 | usage->cube[fpos] = FALSE; | ||
1160 | } | ||
1161 | } | ||
1162 | } | ||
1163 | |||
1164 | if (progress) { | ||
1165 | return +1; | ||
1166 | } | ||
1167 | } | ||
1168 | } | ||
1169 | |||
1170 | /* | ||
1171 | * Binary increment: change the rightmost 0 to a 1, and | ||
1172 | * change all 1s to the right of it to 0s. | ||
1173 | */ | ||
1174 | i = n; | ||
1175 | while (i > 0 && set[i-1]) | ||
1176 | set[--i] = 0, count--; | ||
1177 | if (i > 0) | ||
1178 | set[--i] = 1, count++; | ||
1179 | else | ||
1180 | break; /* done */ | ||
1181 | } | ||
1182 | |||
1183 | return 0; | ||
1184 | } | ||
1185 | |||
1186 | /* | ||
1187 | * Look for forcing chains. A forcing chain is a path of | ||
1188 | * pairwise-exclusive squares (i.e. each pair of adjacent squares | ||
1189 | * in the path are in the same row, column or block) with the | ||
1190 | * following properties: | ||
1191 | * | ||
1192 | * (a) Each square on the path has precisely two possible numbers. | ||
1193 | * | ||
1194 | * (b) Each pair of squares which are adjacent on the path share | ||
1195 | * at least one possible number in common. | ||
1196 | * | ||
1197 | * (c) Each square in the middle of the path shares _both_ of its | ||
1198 | * numbers with at least one of its neighbours (not the same | ||
1199 | * one with both neighbours). | ||
1200 | * | ||
1201 | * These together imply that at least one of the possible number | ||
1202 | * choices at one end of the path forces _all_ the rest of the | ||
1203 | * numbers along the path. In order to make real use of this, we | ||
1204 | * need further properties: | ||
1205 | * | ||
1206 | * (c) Ruling out some number N from the square at one end of the | ||
1207 | * path forces the square at the other end to take the same | ||
1208 | * number N. | ||
1209 | * | ||
1210 | * (d) The two end squares are both in line with some third | ||
1211 | * square. | ||
1212 | * | ||
1213 | * (e) That third square currently has N as a possibility. | ||
1214 | * | ||
1215 | * If we can find all of that lot, we can deduce that at least one | ||
1216 | * of the two ends of the forcing chain has number N, and that | ||
1217 | * therefore the mutually adjacent third square does not. | ||
1218 | * | ||
1219 | * To find forcing chains, we're going to start a bfs at each | ||
1220 | * suitable square, once for each of its two possible numbers. | ||
1221 | */ | ||
1222 | static int solver_forcing(struct solver_usage *usage, | ||
1223 | struct solver_scratch *scratch) | ||
1224 | { | ||
1225 | int cr = usage->cr; | ||
1226 | int *bfsqueue = scratch->bfsqueue; | ||
1227 | #ifdef STANDALONE_SOLVER | ||
1228 | int *bfsprev = scratch->bfsprev; | ||
1229 | #endif | ||
1230 | unsigned char *number = scratch->grid; | ||
1231 | int *neighbours = scratch->neighbours; | ||
1232 | int x, y; | ||
1233 | |||
1234 | for (y = 0; y < cr; y++) | ||
1235 | for (x = 0; x < cr; x++) { | ||
1236 | int count, t, n; | ||
1237 | |||
1238 | /* | ||
1239 | * If this square doesn't have exactly two candidate | ||
1240 | * numbers, don't try it. | ||
1241 | * | ||
1242 | * In this loop we also sum the candidate numbers, | ||
1243 | * which is a nasty hack to allow us to quickly find | ||
1244 | * `the other one' (since we will shortly know there | ||
1245 | * are exactly two). | ||
1246 | */ | ||
1247 | for (count = t = 0, n = 1; n <= cr; n++) | ||
1248 | if (cube(x, y, n)) | ||
1249 | count++, t += n; | ||
1250 | if (count != 2) | ||
1251 | continue; | ||
1252 | |||
1253 | /* | ||
1254 | * Now attempt a bfs for each candidate. | ||
1255 | */ | ||
1256 | for (n = 1; n <= cr; n++) | ||
1257 | if (cube(x, y, n)) { | ||
1258 | int orign, currn, head, tail; | ||
1259 | |||
1260 | /* | ||
1261 | * Begin a bfs. | ||
1262 | */ | ||
1263 | orign = n; | ||
1264 | |||
1265 | memset(number, cr+1, cr*cr); | ||
1266 | head = tail = 0; | ||
1267 | bfsqueue[tail++] = y*cr+x; | ||
1268 | #ifdef STANDALONE_SOLVER | ||
1269 | bfsprev[y*cr+x] = -1; | ||
1270 | #endif | ||
1271 | number[y*cr+x] = t - n; | ||
1272 | |||
1273 | while (head < tail) { | ||
1274 | int xx, yy, nneighbours, xt, yt, i; | ||
1275 | |||
1276 | xx = bfsqueue[head++]; | ||
1277 | yy = xx / cr; | ||
1278 | xx %= cr; | ||
1279 | |||
1280 | currn = number[yy*cr+xx]; | ||
1281 | |||
1282 | /* | ||
1283 | * Find neighbours of yy,xx. | ||
1284 | */ | ||
1285 | nneighbours = 0; | ||
1286 | for (yt = 0; yt < cr; yt++) | ||
1287 | neighbours[nneighbours++] = yt*cr+xx; | ||
1288 | for (xt = 0; xt < cr; xt++) | ||
1289 | neighbours[nneighbours++] = yy*cr+xt; | ||
1290 | xt = usage->blocks->whichblock[yy*cr+xx]; | ||
1291 | for (yt = 0; yt < cr; yt++) | ||
1292 | neighbours[nneighbours++] = usage->blocks->blocks[xt][yt]; | ||
1293 | if (usage->diag) { | ||
1294 | int sqindex = yy*cr+xx; | ||
1295 | if (ondiag0(sqindex)) { | ||
1296 | for (i = 0; i < cr; i++) | ||
1297 | neighbours[nneighbours++] = diag0(i); | ||
1298 | } | ||
1299 | if (ondiag1(sqindex)) { | ||
1300 | for (i = 0; i < cr; i++) | ||
1301 | neighbours[nneighbours++] = diag1(i); | ||
1302 | } | ||
1303 | } | ||
1304 | |||
1305 | /* | ||
1306 | * Try visiting each of those neighbours. | ||
1307 | */ | ||
1308 | for (i = 0; i < nneighbours; i++) { | ||
1309 | int cc, tt, nn; | ||
1310 | |||
1311 | xt = neighbours[i] % cr; | ||
1312 | yt = neighbours[i] / cr; | ||
1313 | |||
1314 | /* | ||
1315 | * We need this square to not be | ||
1316 | * already visited, and to include | ||
1317 | * currn as a possible number. | ||
1318 | */ | ||
1319 | if (number[yt*cr+xt] <= cr) | ||
1320 | continue; | ||
1321 | if (!cube(xt, yt, currn)) | ||
1322 | continue; | ||
1323 | |||
1324 | /* | ||
1325 | * Don't visit _this_ square a second | ||
1326 | * time! | ||
1327 | */ | ||
1328 | if (xt == xx && yt == yy) | ||
1329 | continue; | ||
1330 | |||
1331 | /* | ||
1332 | * To continue with the bfs, we need | ||
1333 | * this square to have exactly two | ||
1334 | * possible numbers. | ||
1335 | */ | ||
1336 | for (cc = tt = 0, nn = 1; nn <= cr; nn++) | ||
1337 | if (cube(xt, yt, nn)) | ||
1338 | cc++, tt += nn; | ||
1339 | if (cc == 2) { | ||
1340 | bfsqueue[tail++] = yt*cr+xt; | ||
1341 | #ifdef STANDALONE_SOLVER | ||
1342 | bfsprev[yt*cr+xt] = yy*cr+xx; | ||
1343 | #endif | ||
1344 | number[yt*cr+xt] = tt - currn; | ||
1345 | } | ||
1346 | |||
1347 | /* | ||
1348 | * One other possibility is that this | ||
1349 | * might be the square in which we can | ||
1350 | * make a real deduction: if it's | ||
1351 | * adjacent to x,y, and currn is equal | ||
1352 | * to the original number we ruled out. | ||
1353 | */ | ||
1354 | if (currn == orign && | ||
1355 | (xt == x || yt == y || | ||
1356 | (usage->blocks->whichblock[yt*cr+xt] == usage->blocks->whichblock[y*cr+x]) || | ||
1357 | (usage->diag && ((ondiag0(yt*cr+xt) && ondiag0(y*cr+x)) || | ||
1358 | (ondiag1(yt*cr+xt) && ondiag1(y*cr+x)))))) { | ||
1359 | #ifdef STANDALONE_SOLVER | ||
1360 | if (solver_show_working) { | ||
1361 | char *sep = ""; | ||
1362 | int xl, yl; | ||
1363 | printf("%*sforcing chain, %d at ends of ", | ||
1364 | solver_recurse_depth*4, "", orign); | ||
1365 | xl = xx; | ||
1366 | yl = yy; | ||
1367 | while (1) { | ||
1368 | printf("%s(%d,%d)", sep, 1+xl, | ||
1369 | 1+yl); | ||
1370 | xl = bfsprev[yl*cr+xl]; | ||
1371 | if (xl < 0) | ||
1372 | break; | ||
1373 | yl = xl / cr; | ||
1374 | xl %= cr; | ||
1375 | sep = "-"; | ||
1376 | } | ||
1377 | printf("\n%*s ruling out %d at (%d,%d)\n", | ||
1378 | solver_recurse_depth*4, "", | ||
1379 | orign, 1+xt, 1+yt); | ||
1380 | } | ||
1381 | #endif | ||
1382 | cube(xt, yt, orign) = FALSE; | ||
1383 | return 1; | ||
1384 | } | ||
1385 | } | ||
1386 | } | ||
1387 | } | ||
1388 | } | ||
1389 | |||
1390 | return 0; | ||
1391 | } | ||
1392 | |||
1393 | static int solver_killer_minmax(struct solver_usage *usage, | ||
1394 | struct block_structure *cages, digit *clues, | ||
1395 | int b | ||
1396 | #ifdef STANDALONE_SOLVER | ||
1397 | , const char *extra | ||
1398 | #endif | ||
1399 | ) | ||
1400 | { | ||
1401 | int cr = usage->cr; | ||
1402 | int i; | ||
1403 | int ret = 0; | ||
1404 | int nsquares = cages->nr_squares[b]; | ||
1405 | |||
1406 | if (clues[b] == 0) | ||
1407 | return 0; | ||
1408 | |||
1409 | for (i = 0; i < nsquares; i++) { | ||
1410 | int n, x = cages->blocks[b][i]; | ||
1411 | |||
1412 | for (n = 1; n <= cr; n++) | ||
1413 | if (cube2(x, n)) { | ||
1414 | int maxval = 0, minval = 0; | ||
1415 | int j; | ||
1416 | for (j = 0; j < nsquares; j++) { | ||
1417 | int m; | ||
1418 | int y = cages->blocks[b][j]; | ||
1419 | if (i == j) | ||
1420 | continue; | ||
1421 | for (m = 1; m <= cr; m++) | ||
1422 | if (cube2(y, m)) { | ||
1423 | minval += m; | ||
1424 | break; | ||
1425 | } | ||
1426 | for (m = cr; m > 0; m--) | ||
1427 | if (cube2(y, m)) { | ||
1428 | maxval += m; | ||
1429 | break; | ||
1430 | } | ||
1431 | } | ||
1432 | if (maxval + n < clues[b]) { | ||
1433 | cube2(x, n) = FALSE; | ||
1434 | ret = 1; | ||
1435 | #ifdef STANDALONE_SOLVER | ||
1436 | if (solver_show_working) | ||
1437 | printf("%*s ruling out %d at (%d,%d) as too low %s\n", | ||
1438 | solver_recurse_depth*4, "killer minmax analysis", | ||
1439 | n, 1 + x%cr, 1 + x/cr, extra); | ||
1440 | #endif | ||
1441 | } | ||
1442 | if (minval + n > clues[b]) { | ||
1443 | cube2(x, n) = FALSE; | ||
1444 | ret = 1; | ||
1445 | #ifdef STANDALONE_SOLVER | ||
1446 | if (solver_show_working) | ||
1447 | printf("%*s ruling out %d at (%d,%d) as too high %s\n", | ||
1448 | solver_recurse_depth*4, "killer minmax analysis", | ||
1449 | n, 1 + x%cr, 1 + x/cr, extra); | ||
1450 | #endif | ||
1451 | } | ||
1452 | } | ||
1453 | } | ||
1454 | return ret; | ||
1455 | } | ||
1456 | |||
1457 | static int solver_killer_sums(struct solver_usage *usage, int b, | ||
1458 | struct block_structure *cages, int clue, | ||
1459 | int cage_is_region | ||
1460 | #ifdef STANDALONE_SOLVER | ||
1461 | , const char *cage_type | ||
1462 | #endif | ||
1463 | ) | ||
1464 | { | ||
1465 | int cr = usage->cr; | ||
1466 | int i, ret, max_sums; | ||
1467 | int nsquares = cages->nr_squares[b]; | ||
1468 | unsigned long *sumbits, possible_addends; | ||
1469 | |||
1470 | if (clue == 0) { | ||
1471 | assert(nsquares == 0); | ||
1472 | return 0; | ||
1473 | } | ||
1474 | assert(nsquares > 0); | ||
1475 | |||
1476 | if (nsquares < 2 || nsquares > 4) | ||
1477 | return 0; | ||
1478 | |||
1479 | if (!cage_is_region) { | ||
1480 | int known_row = -1, known_col = -1, known_block = -1; | ||
1481 | /* | ||
1482 | * Verify that the cage lies entirely within one region, | ||
1483 | * so that using the precomputed sums is valid. | ||
1484 | */ | ||
1485 | for (i = 0; i < nsquares; i++) { | ||
1486 | int x = cages->blocks[b][i]; | ||
1487 | |||
1488 | assert(usage->grid[x] == 0); | ||
1489 | |||
1490 | if (i == 0) { | ||
1491 | known_row = x/cr; | ||
1492 | known_col = x%cr; | ||
1493 | known_block = usage->blocks->whichblock[x]; | ||
1494 | } else { | ||
1495 | if (known_row != x/cr) | ||
1496 | known_row = -1; | ||
1497 | if (known_col != x%cr) | ||
1498 | known_col = -1; | ||
1499 | if (known_block != usage->blocks->whichblock[x]) | ||
1500 | known_block = -1; | ||
1501 | } | ||
1502 | } | ||
1503 | if (known_block == -1 && known_col == -1 && known_row == -1) | ||
1504 | return 0; | ||
1505 | } | ||
1506 | if (nsquares == 2) { | ||
1507 | if (clue < 3 || clue > 17) | ||
1508 | return -1; | ||
1509 | |||
1510 | sumbits = sum_bits2[clue]; | ||
1511 | max_sums = MAX_2SUMS; | ||
1512 | } else if (nsquares == 3) { | ||
1513 | if (clue < 6 || clue > 24) | ||
1514 | return -1; | ||
1515 | |||
1516 | sumbits = sum_bits3[clue]; | ||
1517 | max_sums = MAX_3SUMS; | ||
1518 | } else { | ||
1519 | if (clue < 10 || clue > 30) | ||
1520 | return -1; | ||
1521 | |||
1522 | sumbits = sum_bits4[clue]; | ||
1523 | max_sums = MAX_4SUMS; | ||
1524 | } | ||
1525 | /* | ||
1526 | * For every possible way to get the sum, see if there is | ||
1527 | * one square in the cage that disallows all the required | ||
1528 | * addends. If we find one such square, this way to compute | ||
1529 | * the sum is impossible. | ||
1530 | */ | ||
1531 | possible_addends = 0; | ||
1532 | for (i = 0; i < max_sums; i++) { | ||
1533 | int j; | ||
1534 | unsigned long bits = sumbits[i]; | ||
1535 | |||
1536 | if (bits == 0) | ||
1537 | break; | ||
1538 | |||
1539 | for (j = 0; j < nsquares; j++) { | ||
1540 | int n; | ||
1541 | unsigned long square_bits = bits; | ||
1542 | int x = cages->blocks[b][j]; | ||
1543 | for (n = 1; n <= cr; n++) | ||
1544 | if (!cube2(x, n)) | ||
1545 | square_bits &= ~(1L << n); | ||
1546 | if (square_bits == 0) { | ||
1547 | break; | ||
1548 | } | ||
1549 | } | ||
1550 | if (j == nsquares) | ||
1551 | possible_addends |= bits; | ||
1552 | } | ||
1553 | /* | ||
1554 | * Now we know which addends can possibly be used to | ||
1555 | * compute the sum. Remove all other digits from the | ||
1556 | * set of possibilities. | ||
1557 | */ | ||
1558 | if (possible_addends == 0) | ||
1559 | return -1; | ||
1560 | |||
1561 | ret = 0; | ||
1562 | for (i = 0; i < nsquares; i++) { | ||
1563 | int n; | ||
1564 | int x = cages->blocks[b][i]; | ||
1565 | for (n = 1; n <= cr; n++) { | ||
1566 | if (!cube2(x, n)) | ||
1567 | continue; | ||
1568 | if ((possible_addends & (1 << n)) == 0) { | ||
1569 | cube2(x, n) = FALSE; | ||
1570 | ret = 1; | ||
1571 | #ifdef STANDALONE_SOLVER | ||
1572 | if (solver_show_working) { | ||
1573 | printf("%*s using %s\n", | ||
1574 | solver_recurse_depth*4, "killer sums analysis", | ||
1575 | cage_type); | ||
1576 | printf("%*s ruling out %d at (%d,%d) due to impossible %d-sum\n", | ||
1577 | solver_recurse_depth*4, "", | ||
1578 | n, 1 + x%cr, 1 + x/cr, nsquares); | ||
1579 | } | ||
1580 | #endif | ||
1581 | } | ||
1582 | } | ||
1583 | } | ||
1584 | return ret; | ||
1585 | } | ||
1586 | |||
1587 | static int filter_whole_cages(struct solver_usage *usage, int *squares, int n, | ||
1588 | int *filtered_sum) | ||
1589 | { | ||
1590 | int b, i, j, off; | ||
1591 | *filtered_sum = 0; | ||
1592 | |||
1593 | /* First, filter squares with a clue. */ | ||
1594 | for (i = j = 0; i < n; i++) | ||
1595 | if (usage->grid[squares[i]]) | ||
1596 | *filtered_sum += usage->grid[squares[i]]; | ||
1597 | else | ||
1598 | squares[j++] = squares[i]; | ||
1599 | n = j; | ||
1600 | |||
1601 | /* | ||
1602 | * Filter all cages that are covered entirely by the list of | ||
1603 | * squares. | ||
1604 | */ | ||
1605 | off = 0; | ||
1606 | for (b = 0; b < usage->kblocks->nr_blocks && off < n; b++) { | ||
1607 | int b_squares = usage->kblocks->nr_squares[b]; | ||
1608 | int matched = 0; | ||
1609 | |||
1610 | if (b_squares == 0) | ||
1611 | continue; | ||
1612 | |||
1613 | /* | ||
1614 | * Find all squares of block b that lie in our list, | ||
1615 | * and make them contiguous at off, which is the current position | ||
1616 | * in the output list. | ||
1617 | */ | ||
1618 | for (i = 0; i < b_squares; i++) { | ||
1619 | for (j = off; j < n; j++) | ||
1620 | if (squares[j] == usage->kblocks->blocks[b][i]) { | ||
1621 | int t = squares[off + matched]; | ||
1622 | squares[off + matched] = squares[j]; | ||
1623 | squares[j] = t; | ||
1624 | matched++; | ||
1625 | break; | ||
1626 | } | ||
1627 | } | ||
1628 | /* If so, filter out all squares of b from the list. */ | ||
1629 | if (matched != usage->kblocks->nr_squares[b]) { | ||
1630 | off += matched; | ||
1631 | continue; | ||
1632 | } | ||
1633 | memmove(squares + off, squares + off + matched, | ||
1634 | (n - off - matched) * sizeof *squares); | ||
1635 | n -= matched; | ||
1636 | |||
1637 | *filtered_sum += usage->kclues[b]; | ||
1638 | } | ||
1639 | assert(off == n); | ||
1640 | return off; | ||
1641 | } | ||
1642 | |||
1643 | static struct solver_scratch *solver_new_scratch(struct solver_usage *usage) | ||
1644 | { | ||
1645 | struct solver_scratch *scratch = snew(struct solver_scratch); | ||
1646 | int cr = usage->cr; | ||
1647 | scratch->grid = snewn(cr*cr, unsigned char); | ||
1648 | scratch->rowidx = snewn(cr, unsigned char); | ||
1649 | scratch->colidx = snewn(cr, unsigned char); | ||
1650 | scratch->set = snewn(cr, unsigned char); | ||
1651 | scratch->neighbours = snewn(5*cr, int); | ||
1652 | scratch->bfsqueue = snewn(cr*cr, int); | ||
1653 | #ifdef STANDALONE_SOLVER | ||
1654 | scratch->bfsprev = snewn(cr*cr, int); | ||
1655 | #endif | ||
1656 | scratch->indexlist = snewn(cr*cr, int); /* used for set elimination */ | ||
1657 | scratch->indexlist2 = snewn(cr, int); /* only used for intersect() */ | ||
1658 | return scratch; | ||
1659 | } | ||
1660 | |||
1661 | static void solver_free_scratch(struct solver_scratch *scratch) | ||
1662 | { | ||
1663 | #ifdef STANDALONE_SOLVER | ||
1664 | sfree(scratch->bfsprev); | ||
1665 | #endif | ||
1666 | sfree(scratch->bfsqueue); | ||
1667 | sfree(scratch->neighbours); | ||
1668 | sfree(scratch->set); | ||
1669 | sfree(scratch->colidx); | ||
1670 | sfree(scratch->rowidx); | ||
1671 | sfree(scratch->grid); | ||
1672 | sfree(scratch->indexlist); | ||
1673 | sfree(scratch->indexlist2); | ||
1674 | sfree(scratch); | ||
1675 | } | ||
1676 | |||
1677 | /* | ||
1678 | * Used for passing information about difficulty levels between the solver | ||
1679 | * and its callers. | ||
1680 | */ | ||
1681 | struct difficulty { | ||
1682 | /* Maximum levels allowed. */ | ||
1683 | int maxdiff, maxkdiff; | ||
1684 | /* Levels reached by the solver. */ | ||
1685 | int diff, kdiff; | ||
1686 | }; | ||
1687 | |||
1688 | static void solver(int cr, struct block_structure *blocks, | ||
1689 | struct block_structure *kblocks, int xtype, | ||
1690 | digit *grid, digit *kgrid, struct difficulty *dlev) | ||
1691 | { | ||
1692 | struct solver_usage *usage; | ||
1693 | struct solver_scratch *scratch; | ||
1694 | int x, y, b, i, n, ret; | ||
1695 | int diff = DIFF_BLOCK; | ||
1696 | int kdiff = DIFF_KSINGLE; | ||
1697 | |||
1698 | /* | ||
1699 | * Set up a usage structure as a clean slate (everything | ||
1700 | * possible). | ||
1701 | */ | ||
1702 | usage = snew(struct solver_usage); | ||
1703 | usage->cr = cr; | ||
1704 | usage->blocks = blocks; | ||
1705 | if (kblocks) { | ||
1706 | usage->kblocks = dup_block_structure(kblocks); | ||
1707 | usage->extra_cages = alloc_block_structure (kblocks->c, kblocks->r, | ||
1708 | cr * cr, cr, cr * cr); | ||
1709 | usage->extra_clues = snewn(cr*cr, digit); | ||
1710 | } else { | ||
1711 | usage->kblocks = usage->extra_cages = NULL; | ||
1712 | usage->extra_clues = NULL; | ||
1713 | } | ||
1714 | usage->cube = snewn(cr*cr*cr, unsigned char); | ||
1715 | usage->grid = grid; /* write straight back to the input */ | ||
1716 | if (kgrid) { | ||
1717 | int nclues; | ||
1718 | |||
1719 | assert(kblocks); | ||
1720 | nclues = kblocks->nr_blocks; | ||
1721 | /* | ||
1722 | * Allow for expansion of the killer regions, the absolute | ||
1723 | * limit is obviously one region per square. | ||
1724 | */ | ||
1725 | usage->kclues = snewn(cr*cr, digit); | ||
1726 | for (i = 0; i < nclues; i++) { | ||
1727 | for (n = 0; n < kblocks->nr_squares[i]; n++) | ||
1728 | if (kgrid[kblocks->blocks[i][n]] != 0) | ||
1729 | usage->kclues[i] = kgrid[kblocks->blocks[i][n]]; | ||
1730 | assert(usage->kclues[i] > 0); | ||
1731 | } | ||
1732 | memset(usage->kclues + nclues, 0, cr*cr - nclues); | ||
1733 | } else { | ||
1734 | usage->kclues = NULL; | ||
1735 | } | ||
1736 | |||
1737 | memset(usage->cube, TRUE, cr*cr*cr); | ||
1738 | |||
1739 | usage->row = snewn(cr * cr, unsigned char); | ||
1740 | usage->col = snewn(cr * cr, unsigned char); | ||
1741 | usage->blk = snewn(cr * cr, unsigned char); | ||
1742 | memset(usage->row, FALSE, cr * cr); | ||
1743 | memset(usage->col, FALSE, cr * cr); | ||
1744 | memset(usage->blk, FALSE, cr * cr); | ||
1745 | |||
1746 | if (xtype) { | ||
1747 | usage->diag = snewn(cr * 2, unsigned char); | ||
1748 | memset(usage->diag, FALSE, cr * 2); | ||
1749 | } else | ||
1750 | usage->diag = NULL; | ||
1751 | |||
1752 | usage->nr_regions = cr * 3 + (xtype ? 2 : 0); | ||
1753 | usage->regions = snewn(cr * usage->nr_regions, int); | ||
1754 | usage->sq2region = snewn(cr * cr * 3, int *); | ||
1755 | |||
1756 | for (n = 0; n < cr; n++) { | ||
1757 | for (i = 0; i < cr; i++) { | ||
1758 | x = n*cr+i; | ||
1759 | y = i*cr+n; | ||
1760 | b = usage->blocks->blocks[n][i]; | ||
1761 | usage->regions[cr*n*3 + i] = x; | ||
1762 | usage->regions[cr*n*3 + cr + i] = y; | ||
1763 | usage->regions[cr*n*3 + 2*cr + i] = b; | ||
1764 | usage->sq2region[x*3] = usage->regions + cr*n*3; | ||
1765 | usage->sq2region[y*3 + 1] = usage->regions + cr*n*3 + cr; | ||
1766 | usage->sq2region[b*3 + 2] = usage->regions + cr*n*3 + 2*cr; | ||
1767 | } | ||
1768 | } | ||
1769 | |||
1770 | scratch = solver_new_scratch(usage); | ||
1771 | |||
1772 | /* | ||
1773 | * Place all the clue numbers we are given. | ||
1774 | */ | ||
1775 | for (x = 0; x < cr; x++) | ||
1776 | for (y = 0; y < cr; y++) { | ||
1777 | int n = grid[y*cr+x]; | ||
1778 | if (n) { | ||
1779 | if (!cube(x,y,n)) { | ||
1780 | diff = DIFF_IMPOSSIBLE; | ||
1781 | goto got_result; | ||
1782 | } | ||
1783 | solver_place(usage, x, y, grid[y*cr+x]); | ||
1784 | } | ||
1785 | } | ||
1786 | |||
1787 | /* | ||
1788 | * Now loop over the grid repeatedly trying all permitted modes | ||
1789 | * of reasoning. The loop terminates if we complete an | ||
1790 | * iteration without making any progress; we then return | ||
1791 | * failure or success depending on whether the grid is full or | ||
1792 | * not. | ||
1793 | */ | ||
1794 | while (1) { | ||
1795 | /* | ||
1796 | * I'd like to write `continue;' inside each of the | ||
1797 | * following loops, so that the solver returns here after | ||
1798 | * making some progress. However, I can't specify that I | ||
1799 | * want to continue an outer loop rather than the innermost | ||
1800 | * one, so I'm apologetically resorting to a goto. | ||
1801 | */ | ||
1802 | cont: | ||
1803 | |||
1804 | /* | ||
1805 | * Blockwise positional elimination. | ||
1806 | */ | ||
1807 | for (b = 0; b < cr; b++) | ||
1808 | for (n = 1; n <= cr; n++) | ||
1809 | if (!usage->blk[b*cr+n-1]) { | ||
1810 | for (i = 0; i < cr; i++) | ||
1811 | scratch->indexlist[i] = cubepos2(usage->blocks->blocks[b][i],n); | ||
1812 | ret = solver_elim(usage, scratch->indexlist | ||
1813 | #ifdef STANDALONE_SOLVER | ||
1814 | , "positional elimination," | ||
1815 | " %d in block %s", n, | ||
1816 | usage->blocks->blocknames[b] | ||
1817 | #endif | ||
1818 | ); | ||
1819 | if (ret < 0) { | ||
1820 | diff = DIFF_IMPOSSIBLE; | ||
1821 | goto got_result; | ||
1822 | } else if (ret > 0) { | ||
1823 | diff = max(diff, DIFF_BLOCK); | ||
1824 | goto cont; | ||
1825 | } | ||
1826 | } | ||
1827 | |||
1828 | if (usage->kclues != NULL) { | ||
1829 | int changed = FALSE; | ||
1830 | |||
1831 | /* | ||
1832 | * First, bring the kblocks into a more useful form: remove | ||
1833 | * all filled-in squares, and reduce the sum by their values. | ||
1834 | * Walk in reverse order, since otherwise remove_from_block | ||
1835 | * can move element past our loop counter. | ||
1836 | */ | ||
1837 | for (b = 0; b < usage->kblocks->nr_blocks; b++) | ||
1838 | for (i = usage->kblocks->nr_squares[b] -1; i >= 0; i--) { | ||
1839 | int x = usage->kblocks->blocks[b][i]; | ||
1840 | int t = usage->grid[x]; | ||
1841 | |||
1842 | if (t == 0) | ||
1843 | continue; | ||
1844 | remove_from_block(usage->kblocks, b, x); | ||
1845 | if (t > usage->kclues[b]) { | ||
1846 | diff = DIFF_IMPOSSIBLE; | ||
1847 | goto got_result; | ||
1848 | } | ||
1849 | usage->kclues[b] -= t; | ||
1850 | /* | ||
1851 | * Since cages are regions, this tells us something | ||
1852 | * about the other squares in the cage. | ||
1853 | */ | ||
1854 | for (n = 0; n < usage->kblocks->nr_squares[b]; n++) { | ||
1855 | cube2(usage->kblocks->blocks[b][n], t) = FALSE; | ||
1856 | } | ||
1857 | } | ||
1858 | |||
1859 | /* | ||
1860 | * The most trivial kind of solver for killer puzzles: fill | ||
1861 | * single-square cages. | ||
1862 | */ | ||
1863 | for (b = 0; b < usage->kblocks->nr_blocks; b++) { | ||
1864 | int squares = usage->kblocks->nr_squares[b]; | ||
1865 | if (squares == 1) { | ||
1866 | int v = usage->kclues[b]; | ||
1867 | if (v < 1 || v > cr) { | ||
1868 | diff = DIFF_IMPOSSIBLE; | ||
1869 | goto got_result; | ||
1870 | } | ||
1871 | x = usage->kblocks->blocks[b][0] % cr; | ||
1872 | y = usage->kblocks->blocks[b][0] / cr; | ||
1873 | if (!cube(x, y, v)) { | ||
1874 | diff = DIFF_IMPOSSIBLE; | ||
1875 | goto got_result; | ||
1876 | } | ||
1877 | solver_place(usage, x, y, v); | ||
1878 | |||
1879 | #ifdef STANDALONE_SOLVER | ||
1880 | if (solver_show_working) { | ||
1881 | printf("%*s placing %d at (%d,%d)\n", | ||
1882 | solver_recurse_depth*4, "killer single-square cage", | ||
1883 | v, 1 + x%cr, 1 + x/cr); | ||
1884 | } | ||
1885 | #endif | ||
1886 | changed = TRUE; | ||
1887 | } | ||
1888 | } | ||
1889 | |||
1890 | if (changed) { | ||
1891 | kdiff = max(kdiff, DIFF_KSINGLE); | ||
1892 | goto cont; | ||
1893 | } | ||
1894 | } | ||
1895 | if (dlev->maxkdiff >= DIFF_KINTERSECT && usage->kclues != NULL) { | ||
1896 | int changed = FALSE; | ||
1897 | /* | ||
1898 | * Now, create the extra_cages information. Every full region | ||
1899 | * (row, column, or block) has the same sum total (45 for 3x3 | ||
1900 | * puzzles. After we try to cover these regions with cages that | ||
1901 | * lie entirely within them, any squares that remain must bring | ||
1902 | * the total to this known value, and so they form additional | ||
1903 | * cages which aren't immediately evident in the displayed form | ||
1904 | * of the puzzle. | ||
1905 | */ | ||
1906 | usage->extra_cages->nr_blocks = 0; | ||
1907 | for (i = 0; i < 3; i++) { | ||
1908 | for (n = 0; n < cr; n++) { | ||
1909 | int *region = usage->regions + cr*n*3 + i*cr; | ||
1910 | int sum = cr * (cr + 1) / 2; | ||
1911 | int nsquares = cr; | ||
1912 | int filtered; | ||
1913 | int n_extra = usage->extra_cages->nr_blocks; | ||
1914 | int *extra_list = usage->extra_cages->blocks[n_extra]; | ||
1915 | memcpy(extra_list, region, cr * sizeof *extra_list); | ||
1916 | |||
1917 | nsquares = filter_whole_cages(usage, extra_list, nsquares, &filtered); | ||
1918 | sum -= filtered; | ||
1919 | if (nsquares == cr || nsquares == 0) | ||
1920 | continue; | ||
1921 | if (dlev->maxdiff >= DIFF_RECURSIVE) { | ||
1922 | if (sum <= 0) { | ||
1923 | dlev->diff = DIFF_IMPOSSIBLE; | ||
1924 | goto got_result; | ||
1925 | } | ||
1926 | } | ||
1927 | assert(sum > 0); | ||
1928 | |||
1929 | if (nsquares == 1) { | ||
1930 | if (sum > cr) { | ||
1931 | diff = DIFF_IMPOSSIBLE; | ||
1932 | goto got_result; | ||
1933 | } | ||
1934 | x = extra_list[0] % cr; | ||
1935 | y = extra_list[0] / cr; | ||
1936 | if (!cube(x, y, sum)) { | ||
1937 | diff = DIFF_IMPOSSIBLE; | ||
1938 | goto got_result; | ||
1939 | } | ||
1940 | solver_place(usage, x, y, sum); | ||
1941 | changed = TRUE; | ||
1942 | #ifdef STANDALONE_SOLVER | ||
1943 | if (solver_show_working) { | ||
1944 | printf("%*s placing %d at (%d,%d)\n", | ||
1945 | solver_recurse_depth*4, "killer single-square deduced cage", | ||
1946 | sum, 1 + x, 1 + y); | ||
1947 | } | ||
1948 | #endif | ||
1949 | } | ||
1950 | |||
1951 | b = usage->kblocks->whichblock[extra_list[0]]; | ||
1952 | for (x = 1; x < nsquares; x++) | ||
1953 | if (usage->kblocks->whichblock[extra_list[x]] != b) | ||
1954 | break; | ||
1955 | if (x == nsquares) { | ||
1956 | assert(usage->kblocks->nr_squares[b] > nsquares); | ||
1957 | split_block(usage->kblocks, extra_list, nsquares); | ||
1958 | assert(usage->kblocks->nr_squares[usage->kblocks->nr_blocks - 1] == nsquares); | ||
1959 | usage->kclues[usage->kblocks->nr_blocks - 1] = sum; | ||
1960 | usage->kclues[b] -= sum; | ||
1961 | } else { | ||
1962 | usage->extra_cages->nr_squares[n_extra] = nsquares; | ||
1963 | usage->extra_cages->nr_blocks++; | ||
1964 | usage->extra_clues[n_extra] = sum; | ||
1965 | } | ||
1966 | } | ||
1967 | } | ||
1968 | if (changed) { | ||
1969 | kdiff = max(kdiff, DIFF_KINTERSECT); | ||
1970 | goto cont; | ||
1971 | } | ||
1972 | } | ||
1973 | |||
1974 | /* | ||
1975 | * Another simple killer-type elimination. For every square in a | ||
1976 | * cage, find the minimum and maximum possible sums of all the | ||
1977 | * other squares in the same cage, and rule out possibilities | ||
1978 | * for the given square based on whether they are guaranteed to | ||
1979 | * cause the sum to be either too high or too low. | ||
1980 | * This is a special case of trying all possible sums across a | ||
1981 | * region, which is a recursive algorithm. We should probably | ||
1982 | * implement it for a higher difficulty level. | ||
1983 | */ | ||
1984 | if (dlev->maxkdiff >= DIFF_KMINMAX && usage->kclues != NULL) { | ||
1985 | int changed = FALSE; | ||
1986 | for (b = 0; b < usage->kblocks->nr_blocks; b++) { | ||
1987 | int ret = solver_killer_minmax(usage, usage->kblocks, | ||
1988 | usage->kclues, b | ||
1989 | #ifdef STANDALONE_SOLVER | ||
1990 | , "" | ||
1991 | #endif | ||
1992 | ); | ||
1993 | if (ret < 0) { | ||
1994 | diff = DIFF_IMPOSSIBLE; | ||
1995 | goto got_result; | ||
1996 | } else if (ret > 0) | ||
1997 | changed = TRUE; | ||
1998 | } | ||
1999 | for (b = 0; b < usage->extra_cages->nr_blocks; b++) { | ||
2000 | int ret = solver_killer_minmax(usage, usage->extra_cages, | ||
2001 | usage->extra_clues, b | ||
2002 | #ifdef STANDALONE_SOLVER | ||
2003 | , "using deduced cages" | ||
2004 | #endif | ||
2005 | ); | ||
2006 | if (ret < 0) { | ||
2007 | diff = DIFF_IMPOSSIBLE; | ||
2008 | goto got_result; | ||
2009 | } else if (ret > 0) | ||
2010 | changed = TRUE; | ||
2011 | } | ||
2012 | if (changed) { | ||
2013 | kdiff = max(kdiff, DIFF_KMINMAX); | ||
2014 | goto cont; | ||
2015 | } | ||
2016 | } | ||
2017 | |||
2018 | /* | ||
2019 | * Try to use knowledge of which numbers can be used to generate | ||
2020 | * a given sum. | ||
2021 | * This can only be used if a cage lies entirely within a region. | ||
2022 | */ | ||
2023 | if (dlev->maxkdiff >= DIFF_KSUMS && usage->kclues != NULL) { | ||
2024 | int changed = FALSE; | ||
2025 | |||
2026 | for (b = 0; b < usage->kblocks->nr_blocks; b++) { | ||
2027 | int ret = solver_killer_sums(usage, b, usage->kblocks, | ||
2028 | usage->kclues[b], TRUE | ||
2029 | #ifdef STANDALONE_SOLVER | ||
2030 | , "regular clues" | ||
2031 | #endif | ||
2032 | ); | ||
2033 | if (ret > 0) { | ||
2034 | changed = TRUE; | ||
2035 | kdiff = max(kdiff, DIFF_KSUMS); | ||
2036 | } else if (ret < 0) { | ||
2037 | diff = DIFF_IMPOSSIBLE; | ||
2038 | goto got_result; | ||
2039 | } | ||
2040 | } | ||
2041 | |||
2042 | for (b = 0; b < usage->extra_cages->nr_blocks; b++) { | ||
2043 | int ret = solver_killer_sums(usage, b, usage->extra_cages, | ||
2044 | usage->extra_clues[b], FALSE | ||
2045 | #ifdef STANDALONE_SOLVER | ||
2046 | , "deduced clues" | ||
2047 | #endif | ||
2048 | ); | ||
2049 | if (ret > 0) { | ||
2050 | changed = TRUE; | ||
2051 | kdiff = max(kdiff, DIFF_KSUMS); | ||
2052 | } else if (ret < 0) { | ||
2053 | diff = DIFF_IMPOSSIBLE; | ||
2054 | goto got_result; | ||
2055 | } | ||
2056 | } | ||
2057 | |||
2058 | if (changed) | ||
2059 | goto cont; | ||
2060 | } | ||
2061 | |||
2062 | if (dlev->maxdiff <= DIFF_BLOCK) | ||
2063 | break; | ||
2064 | |||
2065 | /* | ||
2066 | * Row-wise positional elimination. | ||
2067 | */ | ||
2068 | for (y = 0; y < cr; y++) | ||
2069 | for (n = 1; n <= cr; n++) | ||
2070 | if (!usage->row[y*cr+n-1]) { | ||
2071 | for (x = 0; x < cr; x++) | ||
2072 | scratch->indexlist[x] = cubepos(x, y, n); | ||
2073 | ret = solver_elim(usage, scratch->indexlist | ||
2074 | #ifdef STANDALONE_SOLVER | ||
2075 | , "positional elimination," | ||
2076 | " %d in row %d", n, 1+y | ||
2077 | #endif | ||
2078 | ); | ||
2079 | if (ret < 0) { | ||
2080 | diff = DIFF_IMPOSSIBLE; | ||
2081 | goto got_result; | ||
2082 | } else if (ret > 0) { | ||
2083 | diff = max(diff, DIFF_SIMPLE); | ||
2084 | goto cont; | ||
2085 | } | ||
2086 | } | ||
2087 | /* | ||
2088 | * Column-wise positional elimination. | ||
2089 | */ | ||
2090 | for (x = 0; x < cr; x++) | ||
2091 | for (n = 1; n <= cr; n++) | ||
2092 | if (!usage->col[x*cr+n-1]) { | ||
2093 | for (y = 0; y < cr; y++) | ||
2094 | scratch->indexlist[y] = cubepos(x, y, n); | ||
2095 | ret = solver_elim(usage, scratch->indexlist | ||
2096 | #ifdef STANDALONE_SOLVER | ||
2097 | , "positional elimination," | ||
2098 | " %d in column %d", n, 1+x | ||
2099 | #endif | ||
2100 | ); | ||
2101 | if (ret < 0) { | ||
2102 | diff = DIFF_IMPOSSIBLE; | ||
2103 | goto got_result; | ||
2104 | } else if (ret > 0) { | ||
2105 | diff = max(diff, DIFF_SIMPLE); | ||
2106 | goto cont; | ||
2107 | } | ||
2108 | } | ||
2109 | |||
2110 | /* | ||
2111 | * X-diagonal positional elimination. | ||
2112 | */ | ||
2113 | if (usage->diag) { | ||
2114 | for (n = 1; n <= cr; n++) | ||
2115 | if (!usage->diag[n-1]) { | ||
2116 | for (i = 0; i < cr; i++) | ||
2117 | scratch->indexlist[i] = cubepos2(diag0(i), n); | ||
2118 | ret = solver_elim(usage, scratch->indexlist | ||
2119 | #ifdef STANDALONE_SOLVER | ||
2120 | , "positional elimination," | ||
2121 | " %d in \\-diagonal", n | ||
2122 | #endif | ||
2123 | ); | ||
2124 | if (ret < 0) { | ||
2125 | diff = DIFF_IMPOSSIBLE; | ||
2126 | goto got_result; | ||
2127 | } else if (ret > 0) { | ||
2128 | diff = max(diff, DIFF_SIMPLE); | ||
2129 | goto cont; | ||
2130 | } | ||
2131 | } | ||
2132 | for (n = 1; n <= cr; n++) | ||
2133 | if (!usage->diag[cr+n-1]) { | ||
2134 | for (i = 0; i < cr; i++) | ||
2135 | scratch->indexlist[i] = cubepos2(diag1(i), n); | ||
2136 | ret = solver_elim(usage, scratch->indexlist | ||
2137 | #ifdef STANDALONE_SOLVER | ||
2138 | , "positional elimination," | ||
2139 | " %d in /-diagonal", n | ||
2140 | #endif | ||
2141 | ); | ||
2142 | if (ret < 0) { | ||
2143 | diff = DIFF_IMPOSSIBLE; | ||
2144 | goto got_result; | ||
2145 | } else if (ret > 0) { | ||
2146 | diff = max(diff, DIFF_SIMPLE); | ||
2147 | goto cont; | ||
2148 | } | ||
2149 | } | ||
2150 | } | ||
2151 | |||
2152 | /* | ||
2153 | * Numeric elimination. | ||
2154 | */ | ||
2155 | for (x = 0; x < cr; x++) | ||
2156 | for (y = 0; y < cr; y++) | ||
2157 | if (!usage->grid[y*cr+x]) { | ||
2158 | for (n = 1; n <= cr; n++) | ||
2159 | scratch->indexlist[n-1] = cubepos(x, y, n); | ||
2160 | ret = solver_elim(usage, scratch->indexlist | ||
2161 | #ifdef STANDALONE_SOLVER | ||
2162 | , "numeric elimination at (%d,%d)", | ||
2163 | 1+x, 1+y | ||
2164 | #endif | ||
2165 | ); | ||
2166 | if (ret < 0) { | ||
2167 | diff = DIFF_IMPOSSIBLE; | ||
2168 | goto got_result; | ||
2169 | } else if (ret > 0) { | ||
2170 | diff = max(diff, DIFF_SIMPLE); | ||
2171 | goto cont; | ||
2172 | } | ||
2173 | } | ||
2174 | |||
2175 | if (dlev->maxdiff <= DIFF_SIMPLE) | ||
2176 | break; | ||
2177 | |||
2178 | /* | ||
2179 | * Intersectional analysis, rows vs blocks. | ||
2180 | */ | ||
2181 | for (y = 0; y < cr; y++) | ||
2182 | for (b = 0; b < cr; b++) | ||
2183 | for (n = 1; n <= cr; n++) { | ||
2184 | if (usage->row[y*cr+n-1] || | ||
2185 | usage->blk[b*cr+n-1]) | ||
2186 | continue; | ||
2187 | for (i = 0; i < cr; i++) { | ||
2188 | scratch->indexlist[i] = cubepos(i, y, n); | ||
2189 | scratch->indexlist2[i] = cubepos2(usage->blocks->blocks[b][i], n); | ||
2190 | } | ||
2191 | /* | ||
2192 | * solver_intersect() never returns -1. | ||
2193 | */ | ||
2194 | if (solver_intersect(usage, scratch->indexlist, | ||
2195 | scratch->indexlist2 | ||
2196 | #ifdef STANDALONE_SOLVER | ||
2197 | , "intersectional analysis," | ||
2198 | " %d in row %d vs block %s", | ||
2199 | n, 1+y, usage->blocks->blocknames[b] | ||
2200 | #endif | ||
2201 | ) || | ||
2202 | solver_intersect(usage, scratch->indexlist2, | ||
2203 | scratch->indexlist | ||
2204 | #ifdef STANDALONE_SOLVER | ||
2205 | , "intersectional analysis," | ||
2206 | " %d in block %s vs row %d", | ||
2207 | n, usage->blocks->blocknames[b], 1+y | ||
2208 | #endif | ||
2209 | )) { | ||
2210 | diff = max(diff, DIFF_INTERSECT); | ||
2211 | goto cont; | ||
2212 | } | ||
2213 | } | ||
2214 | |||
2215 | /* | ||
2216 | * Intersectional analysis, columns vs blocks. | ||
2217 | */ | ||
2218 | for (x = 0; x < cr; x++) | ||
2219 | for (b = 0; b < cr; b++) | ||
2220 | for (n = 1; n <= cr; n++) { | ||
2221 | if (usage->col[x*cr+n-1] || | ||
2222 | usage->blk[b*cr+n-1]) | ||
2223 | continue; | ||
2224 | for (i = 0; i < cr; i++) { | ||
2225 | scratch->indexlist[i] = cubepos(x, i, n); | ||
2226 | scratch->indexlist2[i] = cubepos2(usage->blocks->blocks[b][i], n); | ||
2227 | } | ||
2228 | if (solver_intersect(usage, scratch->indexlist, | ||
2229 | scratch->indexlist2 | ||
2230 | #ifdef STANDALONE_SOLVER | ||
2231 | , "intersectional analysis," | ||
2232 | " %d in column %d vs block %s", | ||
2233 | n, 1+x, usage->blocks->blocknames[b] | ||
2234 | #endif | ||
2235 | ) || | ||
2236 | solver_intersect(usage, scratch->indexlist2, | ||
2237 | scratch->indexlist | ||
2238 | #ifdef STANDALONE_SOLVER | ||
2239 | , "intersectional analysis," | ||
2240 | " %d in block %s vs column %d", | ||
2241 | n, usage->blocks->blocknames[b], 1+x | ||
2242 | #endif | ||
2243 | )) { | ||
2244 | diff = max(diff, DIFF_INTERSECT); | ||
2245 | goto cont; | ||
2246 | } | ||
2247 | } | ||
2248 | |||
2249 | if (usage->diag) { | ||
2250 | /* | ||
2251 | * Intersectional analysis, \-diagonal vs blocks. | ||
2252 | */ | ||
2253 | for (b = 0; b < cr; b++) | ||
2254 | for (n = 1; n <= cr; n++) { | ||
2255 | if (usage->diag[n-1] || | ||
2256 | usage->blk[b*cr+n-1]) | ||
2257 | continue; | ||
2258 | for (i = 0; i < cr; i++) { | ||
2259 | scratch->indexlist[i] = cubepos2(diag0(i), n); | ||
2260 | scratch->indexlist2[i] = cubepos2(usage->blocks->blocks[b][i], n); | ||
2261 | } | ||
2262 | if (solver_intersect(usage, scratch->indexlist, | ||
2263 | scratch->indexlist2 | ||
2264 | #ifdef STANDALONE_SOLVER | ||
2265 | , "intersectional analysis," | ||
2266 | " %d in \\-diagonal vs block %s", | ||
2267 | n, usage->blocks->blocknames[b] | ||
2268 | #endif | ||
2269 | ) || | ||
2270 | solver_intersect(usage, scratch->indexlist2, | ||
2271 | scratch->indexlist | ||
2272 | #ifdef STANDALONE_SOLVER | ||
2273 | , "intersectional analysis," | ||
2274 | " %d in block %s vs \\-diagonal", | ||
2275 | n, usage->blocks->blocknames[b] | ||
2276 | #endif | ||
2277 | )) { | ||
2278 | diff = max(diff, DIFF_INTERSECT); | ||
2279 | goto cont; | ||
2280 | } | ||
2281 | } | ||
2282 | |||
2283 | /* | ||
2284 | * Intersectional analysis, /-diagonal vs blocks. | ||
2285 | */ | ||
2286 | for (b = 0; b < cr; b++) | ||
2287 | for (n = 1; n <= cr; n++) { | ||
2288 | if (usage->diag[cr+n-1] || | ||
2289 | usage->blk[b*cr+n-1]) | ||
2290 | continue; | ||
2291 | for (i = 0; i < cr; i++) { | ||
2292 | scratch->indexlist[i] = cubepos2(diag1(i), n); | ||
2293 | scratch->indexlist2[i] = cubepos2(usage->blocks->blocks[b][i], n); | ||
2294 | } | ||
2295 | if (solver_intersect(usage, scratch->indexlist, | ||
2296 | scratch->indexlist2 | ||
2297 | #ifdef STANDALONE_SOLVER | ||
2298 | , "intersectional analysis," | ||
2299 | " %d in /-diagonal vs block %s", | ||
2300 | n, usage->blocks->blocknames[b] | ||
2301 | #endif | ||
2302 | ) || | ||
2303 | solver_intersect(usage, scratch->indexlist2, | ||
2304 | scratch->indexlist | ||
2305 | #ifdef STANDALONE_SOLVER | ||
2306 | , "intersectional analysis," | ||
2307 | " %d in block %s vs /-diagonal", | ||
2308 | n, usage->blocks->blocknames[b] | ||
2309 | #endif | ||
2310 | )) { | ||
2311 | diff = max(diff, DIFF_INTERSECT); | ||
2312 | goto cont; | ||
2313 | } | ||
2314 | } | ||
2315 | } | ||
2316 | |||
2317 | if (dlev->maxdiff <= DIFF_INTERSECT) | ||
2318 | break; | ||
2319 | |||
2320 | /* | ||
2321 | * Blockwise set elimination. | ||
2322 | */ | ||
2323 | for (b = 0; b < cr; b++) { | ||
2324 | for (i = 0; i < cr; i++) | ||
2325 | for (n = 1; n <= cr; n++) | ||
2326 | scratch->indexlist[i*cr+n-1] = cubepos2(usage->blocks->blocks[b][i], n); | ||
2327 | ret = solver_set(usage, scratch, scratch->indexlist | ||
2328 | #ifdef STANDALONE_SOLVER | ||
2329 | , "set elimination, block %s", | ||
2330 | usage->blocks->blocknames[b] | ||
2331 | #endif | ||
2332 | ); | ||
2333 | if (ret < 0) { | ||
2334 | diff = DIFF_IMPOSSIBLE; | ||
2335 | goto got_result; | ||
2336 | } else if (ret > 0) { | ||
2337 | diff = max(diff, DIFF_SET); | ||
2338 | goto cont; | ||
2339 | } | ||
2340 | } | ||
2341 | |||
2342 | /* | ||
2343 | * Row-wise set elimination. | ||
2344 | */ | ||
2345 | for (y = 0; y < cr; y++) { | ||
2346 | for (x = 0; x < cr; x++) | ||
2347 | for (n = 1; n <= cr; n++) | ||
2348 | scratch->indexlist[x*cr+n-1] = cubepos(x, y, n); | ||
2349 | ret = solver_set(usage, scratch, scratch->indexlist | ||
2350 | #ifdef STANDALONE_SOLVER | ||
2351 | , "set elimination, row %d", 1+y | ||
2352 | #endif | ||
2353 | ); | ||
2354 | if (ret < 0) { | ||
2355 | diff = DIFF_IMPOSSIBLE; | ||
2356 | goto got_result; | ||
2357 | } else if (ret > 0) { | ||
2358 | diff = max(diff, DIFF_SET); | ||
2359 | goto cont; | ||
2360 | } | ||
2361 | } | ||
2362 | |||
2363 | /* | ||
2364 | * Column-wise set elimination. | ||
2365 | */ | ||
2366 | for (x = 0; x < cr; x++) { | ||
2367 | for (y = 0; y < cr; y++) | ||
2368 | for (n = 1; n <= cr; n++) | ||
2369 | scratch->indexlist[y*cr+n-1] = cubepos(x, y, n); | ||
2370 | ret = solver_set(usage, scratch, scratch->indexlist | ||
2371 | #ifdef STANDALONE_SOLVER | ||
2372 | , "set elimination, column %d", 1+x | ||
2373 | #endif | ||
2374 | ); | ||
2375 | if (ret < 0) { | ||
2376 | diff = DIFF_IMPOSSIBLE; | ||
2377 | goto got_result; | ||
2378 | } else if (ret > 0) { | ||
2379 | diff = max(diff, DIFF_SET); | ||
2380 | goto cont; | ||
2381 | } | ||
2382 | } | ||
2383 | |||
2384 | if (usage->diag) { | ||
2385 | /* | ||
2386 | * \-diagonal set elimination. | ||
2387 | */ | ||
2388 | for (i = 0; i < cr; i++) | ||
2389 | for (n = 1; n <= cr; n++) | ||
2390 | scratch->indexlist[i*cr+n-1] = cubepos2(diag0(i), n); | ||
2391 | ret = solver_set(usage, scratch, scratch->indexlist | ||
2392 | #ifdef STANDALONE_SOLVER | ||
2393 | , "set elimination, \\-diagonal" | ||
2394 | #endif | ||
2395 | ); | ||
2396 | if (ret < 0) { | ||
2397 | diff = DIFF_IMPOSSIBLE; | ||
2398 | goto got_result; | ||
2399 | } else if (ret > 0) { | ||
2400 | diff = max(diff, DIFF_SET); | ||
2401 | goto cont; | ||
2402 | } | ||
2403 | |||
2404 | /* | ||
2405 | * /-diagonal set elimination. | ||
2406 | */ | ||
2407 | for (i = 0; i < cr; i++) | ||
2408 | for (n = 1; n <= cr; n++) | ||
2409 | scratch->indexlist[i*cr+n-1] = cubepos2(diag1(i), n); | ||
2410 | ret = solver_set(usage, scratch, scratch->indexlist | ||
2411 | #ifdef STANDALONE_SOLVER | ||
2412 | , "set elimination, /-diagonal" | ||
2413 | #endif | ||
2414 | ); | ||
2415 | if (ret < 0) { | ||
2416 | diff = DIFF_IMPOSSIBLE; | ||
2417 | goto got_result; | ||
2418 | } else if (ret > 0) { | ||
2419 | diff = max(diff, DIFF_SET); | ||
2420 | goto cont; | ||
2421 | } | ||
2422 | } | ||
2423 | |||
2424 | if (dlev->maxdiff <= DIFF_SET) | ||
2425 | break; | ||
2426 | |||
2427 | /* | ||
2428 | * Row-vs-column set elimination on a single number. | ||
2429 | */ | ||
2430 | for (n = 1; n <= cr; n++) { | ||
2431 | for (y = 0; y < cr; y++) | ||
2432 | for (x = 0; x < cr; x++) | ||
2433 | scratch->indexlist[y*cr+x] = cubepos(x, y, n); | ||
2434 | ret = solver_set(usage, scratch, scratch->indexlist | ||
2435 | #ifdef STANDALONE_SOLVER | ||
2436 | , "positional set elimination, number %d", n | ||
2437 | #endif | ||
2438 | ); | ||
2439 | if (ret < 0) { | ||
2440 | diff = DIFF_IMPOSSIBLE; | ||
2441 | goto got_result; | ||
2442 | } else if (ret > 0) { | ||
2443 | diff = max(diff, DIFF_EXTREME); | ||
2444 | goto cont; | ||
2445 | } | ||
2446 | } | ||
2447 | |||
2448 | /* | ||
2449 | * Forcing chains. | ||
2450 | */ | ||
2451 | if (solver_forcing(usage, scratch)) { | ||
2452 | diff = max(diff, DIFF_EXTREME); | ||
2453 | goto cont; | ||
2454 | } | ||
2455 | |||
2456 | /* | ||
2457 | * If we reach here, we have made no deductions in this | ||
2458 | * iteration, so the algorithm terminates. | ||
2459 | */ | ||
2460 | break; | ||
2461 | } | ||
2462 | |||
2463 | /* | ||
2464 | * Last chance: if we haven't fully solved the puzzle yet, try | ||
2465 | * recursing based on guesses for a particular square. We pick | ||
2466 | * one of the most constrained empty squares we can find, which | ||
2467 | * has the effect of pruning the search tree as much as | ||
2468 | * possible. | ||
2469 | */ | ||
2470 | if (dlev->maxdiff >= DIFF_RECURSIVE) { | ||
2471 | int best, bestcount; | ||
2472 | |||
2473 | best = -1; | ||
2474 | bestcount = cr+1; | ||
2475 | |||
2476 | for (y = 0; y < cr; y++) | ||
2477 | for (x = 0; x < cr; x++) | ||
2478 | if (!grid[y*cr+x]) { | ||
2479 | int count; | ||
2480 | |||
2481 | /* | ||
2482 | * An unfilled square. Count the number of | ||
2483 | * possible digits in it. | ||
2484 | */ | ||
2485 | count = 0; | ||
2486 | for (n = 1; n <= cr; n++) | ||
2487 | if (cube(x,y,n)) | ||
2488 | count++; | ||
2489 | |||
2490 | /* | ||
2491 | * We should have found any impossibilities | ||
2492 | * already, so this can safely be an assert. | ||
2493 | */ | ||
2494 | assert(count > 1); | ||
2495 | |||
2496 | if (count < bestcount) { | ||
2497 | bestcount = count; | ||
2498 | best = y*cr+x; | ||
2499 | } | ||
2500 | } | ||
2501 | |||
2502 | if (best != -1) { | ||
2503 | int i, j; | ||
2504 | digit *list, *ingrid, *outgrid; | ||
2505 | |||
2506 | diff = DIFF_IMPOSSIBLE; /* no solution found yet */ | ||
2507 | |||
2508 | /* | ||
2509 | * Attempt recursion. | ||
2510 | */ | ||
2511 | y = best / cr; | ||
2512 | x = best % cr; | ||
2513 | |||
2514 | list = snewn(cr, digit); | ||
2515 | ingrid = snewn(cr * cr, digit); | ||
2516 | outgrid = snewn(cr * cr, digit); | ||
2517 | memcpy(ingrid, grid, cr * cr); | ||
2518 | |||
2519 | /* Make a list of the possible digits. */ | ||
2520 | for (j = 0, n = 1; n <= cr; n++) | ||
2521 | if (cube(x,y,n)) | ||
2522 | list[j++] = n; | ||
2523 | |||
2524 | #ifdef STANDALONE_SOLVER | ||
2525 | if (solver_show_working) { | ||
2526 | char *sep = ""; | ||
2527 | printf("%*srecursing on (%d,%d) [", | ||
2528 | solver_recurse_depth*4, "", x + 1, y + 1); | ||
2529 | for (i = 0; i < j; i++) { | ||
2530 | printf("%s%d", sep, list[i]); | ||
2531 | sep = " or "; | ||
2532 | } | ||
2533 | printf("]\n"); | ||
2534 | } | ||
2535 | #endif | ||
2536 | |||
2537 | /* | ||
2538 | * And step along the list, recursing back into the | ||
2539 | * main solver at every stage. | ||
2540 | */ | ||
2541 | for (i = 0; i < j; i++) { | ||
2542 | memcpy(outgrid, ingrid, cr * cr); | ||
2543 | outgrid[y*cr+x] = list[i]; | ||
2544 | |||
2545 | #ifdef STANDALONE_SOLVER | ||
2546 | if (solver_show_working) | ||
2547 | printf("%*sguessing %d at (%d,%d)\n", | ||
2548 | solver_recurse_depth*4, "", list[i], x + 1, y + 1); | ||
2549 | solver_recurse_depth++; | ||
2550 | #endif | ||
2551 | |||
2552 | solver(cr, blocks, kblocks, xtype, outgrid, kgrid, dlev); | ||
2553 | |||
2554 | #ifdef STANDALONE_SOLVER | ||
2555 | solver_recurse_depth--; | ||
2556 | if (solver_show_working) { | ||
2557 | printf("%*sretracting %d at (%d,%d)\n", | ||
2558 | solver_recurse_depth*4, "", list[i], x + 1, y + 1); | ||
2559 | } | ||
2560 | #endif | ||
2561 | |||
2562 | /* | ||
2563 | * If we have our first solution, copy it into the | ||
2564 | * grid we will return. | ||
2565 | */ | ||
2566 | if (diff == DIFF_IMPOSSIBLE && dlev->diff != DIFF_IMPOSSIBLE) | ||
2567 | memcpy(grid, outgrid, cr*cr); | ||
2568 | |||
2569 | if (dlev->diff == DIFF_AMBIGUOUS) | ||
2570 | diff = DIFF_AMBIGUOUS; | ||
2571 | else if (dlev->diff == DIFF_IMPOSSIBLE) | ||
2572 | /* do not change our return value */; | ||
2573 | else { | ||
2574 | /* the recursion turned up exactly one solution */ | ||
2575 | if (diff == DIFF_IMPOSSIBLE) | ||
2576 | diff = DIFF_RECURSIVE; | ||
2577 | else | ||
2578 | diff = DIFF_AMBIGUOUS; | ||
2579 | } | ||
2580 | |||
2581 | /* | ||
2582 | * As soon as we've found more than one solution, | ||
2583 | * give up immediately. | ||
2584 | */ | ||
2585 | if (diff == DIFF_AMBIGUOUS) | ||
2586 | break; | ||
2587 | } | ||
2588 | |||
2589 | sfree(outgrid); | ||
2590 | sfree(ingrid); | ||
2591 | sfree(list); | ||
2592 | } | ||
2593 | |||
2594 | } else { | ||
2595 | /* | ||
2596 | * We're forbidden to use recursion, so we just see whether | ||
2597 | * our grid is fully solved, and return DIFF_IMPOSSIBLE | ||
2598 | * otherwise. | ||
2599 | */ | ||
2600 | for (y = 0; y < cr; y++) | ||
2601 | for (x = 0; x < cr; x++) | ||
2602 | if (!grid[y*cr+x]) | ||
2603 | diff = DIFF_IMPOSSIBLE; | ||
2604 | } | ||
2605 | |||
2606 | got_result: | ||
2607 | dlev->diff = diff; | ||
2608 | dlev->kdiff = kdiff; | ||
2609 | |||
2610 | #ifdef STANDALONE_SOLVER | ||
2611 | if (solver_show_working) | ||
2612 | printf("%*s%s found\n", | ||
2613 | solver_recurse_depth*4, "", | ||
2614 | diff == DIFF_IMPOSSIBLE ? "no solution" : | ||
2615 | diff == DIFF_AMBIGUOUS ? "multiple solutions" : | ||
2616 | "one solution"); | ||
2617 | #endif | ||
2618 | |||
2619 | sfree(usage->sq2region); | ||
2620 | sfree(usage->regions); | ||
2621 | sfree(usage->cube); | ||
2622 | sfree(usage->row); | ||
2623 | sfree(usage->col); | ||
2624 | sfree(usage->blk); | ||
2625 | if (usage->kblocks) { | ||
2626 | free_block_structure(usage->kblocks); | ||
2627 | free_block_structure(usage->extra_cages); | ||
2628 | sfree(usage->extra_clues); | ||
2629 | } | ||
2630 | if (usage->kclues) sfree(usage->kclues); | ||
2631 | sfree(usage); | ||
2632 | |||
2633 | solver_free_scratch(scratch); | ||
2634 | } | ||
2635 | |||
2636 | /* ---------------------------------------------------------------------- | ||
2637 | * End of solver code. | ||
2638 | */ | ||
2639 | |||
2640 | /* ---------------------------------------------------------------------- | ||
2641 | * Killer set generator. | ||
2642 | */ | ||
2643 | |||
2644 | /* ---------------------------------------------------------------------- | ||
2645 | * Solo filled-grid generator. | ||
2646 | * | ||
2647 | * This grid generator works by essentially trying to solve a grid | ||
2648 | * starting from no clues, and not worrying that there's more than | ||
2649 | * one possible solution. Unfortunately, it isn't computationally | ||
2650 | * feasible to do this by calling the above solver with an empty | ||
2651 | * grid, because that one needs to allocate a lot of scratch space | ||
2652 | * at every recursion level. Instead, I have a much simpler | ||
2653 | * algorithm which I shamelessly copied from a Python solver | ||
2654 | * written by Andrew Wilkinson (which is GPLed, but I've reused | ||
2655 | * only ideas and no code). It mostly just does the obvious | ||
2656 | * recursive thing: pick an empty square, put one of the possible | ||
2657 | * digits in it, recurse until all squares are filled, backtrack | ||
2658 | * and change some choices if necessary. | ||
2659 | * | ||
2660 | * The clever bit is that every time it chooses which square to | ||
2661 | * fill in next, it does so by counting the number of _possible_ | ||
2662 | * numbers that can go in each square, and it prioritises so that | ||
2663 | * it picks a square with the _lowest_ number of possibilities. The | ||
2664 | * idea is that filling in lots of the obvious bits (particularly | ||
2665 | * any squares with only one possibility) will cut down on the list | ||
2666 | * of possibilities for other squares and hence reduce the enormous | ||
2667 | * search space as much as possible as early as possible. | ||
2668 | * | ||
2669 | * The use of bit sets implies that we support puzzles up to a size of | ||
2670 | * 32x32 (less if anyone finds a 16-bit machine to compile this on). | ||
2671 | */ | ||
2672 | |||
2673 | /* | ||
2674 | * Internal data structure used in gridgen to keep track of | ||
2675 | * progress. | ||
2676 | */ | ||
2677 | struct gridgen_coord { int x, y, r; }; | ||
2678 | struct gridgen_usage { | ||
2679 | int cr; | ||
2680 | struct block_structure *blocks, *kblocks; | ||
2681 | /* grid is a copy of the input grid, modified as we go along */ | ||
2682 | digit *grid; | ||
2683 | /* | ||
2684 | * Bitsets. In each of them, bit n is set if digit n has been placed | ||
2685 | * in the corresponding region. row, col and blk are used for all | ||
2686 | * puzzles. cge is used only for killer puzzles, and diag is used | ||
2687 | * only for x-type puzzles. | ||
2688 | * All of these have cr entries, except diag which only has 2, | ||
2689 | * and cge, which has as many entries as kblocks. | ||
2690 | */ | ||
2691 | unsigned int *row, *col, *blk, *cge, *diag; | ||
2692 | /* This lists all the empty spaces remaining in the grid. */ | ||
2693 | struct gridgen_coord *spaces; | ||
2694 | int nspaces; | ||
2695 | /* If we need randomisation in the solve, this is our random state. */ | ||
2696 | random_state *rs; | ||
2697 | }; | ||
2698 | |||
2699 | static void gridgen_place(struct gridgen_usage *usage, int x, int y, digit n) | ||
2700 | { | ||
2701 | unsigned int bit = 1 << n; | ||
2702 | int cr = usage->cr; | ||
2703 | usage->row[y] |= bit; | ||
2704 | usage->col[x] |= bit; | ||
2705 | usage->blk[usage->blocks->whichblock[y*cr+x]] |= bit; | ||
2706 | if (usage->cge) | ||
2707 | usage->cge[usage->kblocks->whichblock[y*cr+x]] |= bit; | ||
2708 | if (usage->diag) { | ||
2709 | if (ondiag0(y*cr+x)) | ||
2710 | usage->diag[0] |= bit; | ||
2711 | if (ondiag1(y*cr+x)) | ||
2712 | usage->diag[1] |= bit; | ||
2713 | } | ||
2714 | usage->grid[y*cr+x] = n; | ||
2715 | } | ||
2716 | |||
2717 | static void gridgen_remove(struct gridgen_usage *usage, int x, int y, digit n) | ||
2718 | { | ||
2719 | unsigned int mask = ~(1 << n); | ||
2720 | int cr = usage->cr; | ||
2721 | usage->row[y] &= mask; | ||
2722 | usage->col[x] &= mask; | ||
2723 | usage->blk[usage->blocks->whichblock[y*cr+x]] &= mask; | ||
2724 | if (usage->cge) | ||
2725 | usage->cge[usage->kblocks->whichblock[y*cr+x]] &= mask; | ||
2726 | if (usage->diag) { | ||
2727 | if (ondiag0(y*cr+x)) | ||
2728 | usage->diag[0] &= mask; | ||
2729 | if (ondiag1(y*cr+x)) | ||
2730 | usage->diag[1] &= mask; | ||
2731 | } | ||
2732 | usage->grid[y*cr+x] = 0; | ||
2733 | } | ||
2734 | |||
2735 | #define N_SINGLE 32 | ||
2736 | |||
2737 | /* | ||
2738 | * The real recursive step in the generating function. | ||
2739 | * | ||
2740 | * Return values: 1 means solution found, 0 means no solution | ||
2741 | * found on this branch. | ||
2742 | */ | ||
2743 | static int gridgen_real(struct gridgen_usage *usage, digit *grid, int *steps) | ||
2744 | { | ||
2745 | int cr = usage->cr; | ||
2746 | int i, j, n, sx, sy, bestm, bestr, ret; | ||
2747 | int *digits; | ||
2748 | unsigned int used; | ||
2749 | |||
2750 | /* | ||
2751 | * Firstly, check for completion! If there are no spaces left | ||
2752 | * in the grid, we have a solution. | ||
2753 | */ | ||
2754 | if (usage->nspaces == 0) | ||
2755 | return TRUE; | ||
2756 | |||
2757 | /* | ||
2758 | * Next, abandon generation if we went over our steps limit. | ||
2759 | */ | ||
2760 | if (*steps <= 0) | ||
2761 | return FALSE; | ||
2762 | (*steps)--; | ||
2763 | |||
2764 | /* | ||
2765 | * Otherwise, there must be at least one space. Find the most | ||
2766 | * constrained space, using the `r' field as a tie-breaker. | ||
2767 | */ | ||
2768 | bestm = cr+1; /* so that any space will beat it */ | ||
2769 | bestr = 0; | ||
2770 | used = ~0; | ||
2771 | i = sx = sy = -1; | ||
2772 | for (j = 0; j < usage->nspaces; j++) { | ||
2773 | int x = usage->spaces[j].x, y = usage->spaces[j].y; | ||
2774 | unsigned int used_xy; | ||
2775 | int m; | ||
2776 | |||
2777 | m = usage->blocks->whichblock[y*cr+x]; | ||
2778 | used_xy = usage->row[y] | usage->col[x] | usage->blk[m]; | ||
2779 | if (usage->cge != NULL) | ||
2780 | used_xy |= usage->cge[usage->kblocks->whichblock[y*cr+x]]; | ||
2781 | if (usage->cge != NULL) | ||
2782 | used_xy |= usage->cge[usage->kblocks->whichblock[y*cr+x]]; | ||
2783 | if (usage->diag != NULL) { | ||
2784 | if (ondiag0(y*cr+x)) | ||
2785 | used_xy |= usage->diag[0]; | ||
2786 | if (ondiag1(y*cr+x)) | ||
2787 | used_xy |= usage->diag[1]; | ||
2788 | } | ||
2789 | |||
2790 | /* | ||
2791 | * Find the number of digits that could go in this space. | ||
2792 | */ | ||
2793 | m = 0; | ||
2794 | for (n = 1; n <= cr; n++) { | ||
2795 | unsigned int bit = 1 << n; | ||
2796 | if ((used_xy & bit) == 0) | ||
2797 | m++; | ||
2798 | } | ||
2799 | if (m < bestm || (m == bestm && usage->spaces[j].r < bestr)) { | ||
2800 | bestm = m; | ||
2801 | bestr = usage->spaces[j].r; | ||
2802 | sx = x; | ||
2803 | sy = y; | ||
2804 | i = j; | ||
2805 | used = used_xy; | ||
2806 | } | ||
2807 | } | ||
2808 | |||
2809 | /* | ||
2810 | * Swap that square into the final place in the spaces array, | ||
2811 | * so that decrementing nspaces will remove it from the list. | ||
2812 | */ | ||
2813 | if (i != usage->nspaces-1) { | ||
2814 | struct gridgen_coord t; | ||
2815 | t = usage->spaces[usage->nspaces-1]; | ||
2816 | usage->spaces[usage->nspaces-1] = usage->spaces[i]; | ||
2817 | usage->spaces[i] = t; | ||
2818 | } | ||
2819 | |||
2820 | /* | ||
2821 | * Now we've decided which square to start our recursion at, | ||
2822 | * simply go through all possible values, shuffling them | ||
2823 | * randomly first if necessary. | ||
2824 | */ | ||
2825 | digits = snewn(bestm, int); | ||
2826 | |||
2827 | j = 0; | ||
2828 | for (n = 1; n <= cr; n++) { | ||
2829 | unsigned int bit = 1 << n; | ||
2830 | |||
2831 | if ((used & bit) == 0) | ||
2832 | digits[j++] = n; | ||
2833 | } | ||
2834 | |||
2835 | if (usage->rs) | ||
2836 | shuffle(digits, j, sizeof(*digits), usage->rs); | ||
2837 | |||
2838 | /* And finally, go through the digit list and actually recurse. */ | ||
2839 | ret = FALSE; | ||
2840 | for (i = 0; i < j; i++) { | ||
2841 | n = digits[i]; | ||
2842 | |||
2843 | /* Update the usage structure to reflect the placing of this digit. */ | ||
2844 | gridgen_place(usage, sx, sy, n); | ||
2845 | usage->nspaces--; | ||
2846 | |||
2847 | /* Call the solver recursively. Stop when we find a solution. */ | ||
2848 | if (gridgen_real(usage, grid, steps)) { | ||
2849 | ret = TRUE; | ||
2850 | break; | ||
2851 | } | ||
2852 | |||
2853 | /* Revert the usage structure. */ | ||
2854 | gridgen_remove(usage, sx, sy, n); | ||
2855 | usage->nspaces++; | ||
2856 | } | ||
2857 | |||
2858 | sfree(digits); | ||
2859 | return ret; | ||
2860 | } | ||
2861 | |||
2862 | /* | ||
2863 | * Entry point to generator. You give it parameters and a starting | ||
2864 | * grid, which is simply an array of cr*cr digits. | ||
2865 | */ | ||
2866 | static int gridgen(int cr, struct block_structure *blocks, | ||
2867 | struct block_structure *kblocks, int xtype, | ||
2868 | digit *grid, random_state *rs, int maxsteps) | ||
2869 | { | ||
2870 | struct gridgen_usage *usage; | ||
2871 | int x, y, ret; | ||
2872 | |||
2873 | /* | ||
2874 | * Clear the grid to start with. | ||
2875 | */ | ||
2876 | memset(grid, 0, cr*cr); | ||
2877 | |||
2878 | /* | ||
2879 | * Create a gridgen_usage structure. | ||
2880 | */ | ||
2881 | usage = snew(struct gridgen_usage); | ||
2882 | |||
2883 | usage->cr = cr; | ||
2884 | usage->blocks = blocks; | ||
2885 | |||
2886 | usage->grid = grid; | ||
2887 | |||
2888 | usage->row = snewn(cr, unsigned int); | ||
2889 | usage->col = snewn(cr, unsigned int); | ||
2890 | usage->blk = snewn(cr, unsigned int); | ||
2891 | if (kblocks != NULL) { | ||
2892 | usage->kblocks = kblocks; | ||
2893 | usage->cge = snewn(usage->kblocks->nr_blocks, unsigned int); | ||
2894 | memset(usage->cge, FALSE, kblocks->nr_blocks * sizeof *usage->cge); | ||
2895 | } else { | ||
2896 | usage->cge = NULL; | ||
2897 | } | ||
2898 | |||
2899 | memset(usage->row, 0, cr * sizeof *usage->row); | ||
2900 | memset(usage->col, 0, cr * sizeof *usage->col); | ||
2901 | memset(usage->blk, 0, cr * sizeof *usage->blk); | ||
2902 | |||
2903 | if (xtype) { | ||
2904 | usage->diag = snewn(2, unsigned int); | ||
2905 | memset(usage->diag, 0, 2 * sizeof *usage->diag); | ||
2906 | } else { | ||
2907 | usage->diag = NULL; | ||
2908 | } | ||
2909 | |||
2910 | /* | ||
2911 | * Begin by filling in the whole top row with randomly chosen | ||
2912 | * numbers. This cannot introduce any bias or restriction on | ||
2913 | * the available grids, since we already know those numbers | ||
2914 | * are all distinct so all we're doing is choosing their | ||
2915 | * labels. | ||
2916 | */ | ||
2917 | for (x = 0; x < cr; x++) | ||
2918 | grid[x] = x+1; | ||
2919 | shuffle(grid, cr, sizeof(*grid), rs); | ||
2920 | for (x = 0; x < cr; x++) | ||
2921 | gridgen_place(usage, x, 0, grid[x]); | ||
2922 | |||
2923 | usage->spaces = snewn(cr * cr, struct gridgen_coord); | ||
2924 | usage->nspaces = 0; | ||
2925 | |||
2926 | usage->rs = rs; | ||
2927 | |||
2928 | /* | ||
2929 | * Initialise the list of grid spaces, taking care to leave | ||
2930 | * out the row I've already filled in above. | ||
2931 | */ | ||
2932 | for (y = 1; y < cr; y++) { | ||
2933 | for (x = 0; x < cr; x++) { | ||
2934 | usage->spaces[usage->nspaces].x = x; | ||
2935 | usage->spaces[usage->nspaces].y = y; | ||
2936 | usage->spaces[usage->nspaces].r = random_bits(rs, 31); | ||
2937 | usage->nspaces++; | ||
2938 | } | ||
2939 | } | ||
2940 | |||
2941 | /* | ||
2942 | * Run the real generator function. | ||
2943 | */ | ||
2944 | ret = gridgen_real(usage, grid, &maxsteps); | ||
2945 | |||
2946 | /* | ||
2947 | * Clean up the usage structure now we have our answer. | ||
2948 | */ | ||
2949 | sfree(usage->spaces); | ||
2950 | sfree(usage->cge); | ||
2951 | sfree(usage->blk); | ||
2952 | sfree(usage->col); | ||
2953 | sfree(usage->row); | ||
2954 | sfree(usage); | ||
2955 | |||
2956 | return ret; | ||
2957 | } | ||
2958 | |||
2959 | /* ---------------------------------------------------------------------- | ||
2960 | * End of grid generator code. | ||
2961 | */ | ||
2962 | |||
2963 | static int check_killer_cage_sum(struct block_structure *kblocks, | ||
2964 | digit *kgrid, digit *grid, int blk) | ||
2965 | { | ||
2966 | /* | ||
2967 | * Returns: -1 if the cage has any empty square; 0 if all squares | ||
2968 | * are full but the sum is wrong; +1 if all squares are full and | ||
2969 | * they have the right sum. | ||
2970 | * | ||
2971 | * Does not check uniqueness of numbers within the cage; that's | ||
2972 | * done elsewhere (because in error highlighting it needs to be | ||
2973 | * detected separately so as to flag the error in a visually | ||
2974 | * different way). | ||
2975 | */ | ||
2976 | int n_squares = kblocks->nr_squares[blk]; | ||
2977 | int sum = 0, clue = 0; | ||
2978 | int i; | ||
2979 | |||
2980 | for (i = 0; i < n_squares; i++) { | ||
2981 | int xy = kblocks->blocks[blk][i]; | ||
2982 | |||
2983 | if (grid[xy] == 0) | ||
2984 | return -1; | ||
2985 | sum += grid[xy]; | ||
2986 | |||
2987 | if (kgrid[xy]) { | ||
2988 | assert(clue == 0); | ||
2989 | clue = kgrid[xy]; | ||
2990 | } | ||
2991 | } | ||
2992 | |||
2993 | assert(clue != 0); | ||
2994 | return sum == clue; | ||
2995 | } | ||
2996 | |||
2997 | /* | ||
2998 | * Check whether a grid contains a valid complete puzzle. | ||
2999 | */ | ||
3000 | static int check_valid(int cr, struct block_structure *blocks, | ||
3001 | struct block_structure *kblocks, | ||
3002 | digit *kgrid, int xtype, digit *grid) | ||
3003 | { | ||
3004 | unsigned char *used; | ||
3005 | int x, y, i, j, n; | ||
3006 | |||
3007 | used = snewn(cr, unsigned char); | ||
3008 | |||
3009 | /* | ||
3010 | * Check that each row contains precisely one of everything. | ||
3011 | */ | ||
3012 | for (y = 0; y < cr; y++) { | ||
3013 | memset(used, FALSE, cr); | ||
3014 | for (x = 0; x < cr; x++) | ||
3015 | if (grid[y*cr+x] > 0 && grid[y*cr+x] <= cr) | ||
3016 | used[grid[y*cr+x]-1] = TRUE; | ||
3017 | for (n = 0; n < cr; n++) | ||
3018 | if (!used[n]) { | ||
3019 | sfree(used); | ||
3020 | return FALSE; | ||
3021 | } | ||
3022 | } | ||
3023 | |||
3024 | /* | ||
3025 | * Check that each column contains precisely one of everything. | ||
3026 | */ | ||
3027 | for (x = 0; x < cr; x++) { | ||
3028 | memset(used, FALSE, cr); | ||
3029 | for (y = 0; y < cr; y++) | ||
3030 | if (grid[y*cr+x] > 0 && grid[y*cr+x] <= cr) | ||
3031 | used[grid[y*cr+x]-1] = TRUE; | ||
3032 | for (n = 0; n < cr; n++) | ||
3033 | if (!used[n]) { | ||
3034 | sfree(used); | ||
3035 | return FALSE; | ||
3036 | } | ||
3037 | } | ||
3038 | |||
3039 | /* | ||
3040 | * Check that each block contains precisely one of everything. | ||
3041 | */ | ||
3042 | for (i = 0; i < cr; i++) { | ||
3043 | memset(used, FALSE, cr); | ||
3044 | for (j = 0; j < cr; j++) | ||
3045 | if (grid[blocks->blocks[i][j]] > 0 && | ||
3046 | grid[blocks->blocks[i][j]] <= cr) | ||
3047 | used[grid[blocks->blocks[i][j]]-1] = TRUE; | ||
3048 | for (n = 0; n < cr; n++) | ||
3049 | if (!used[n]) { | ||
3050 | sfree(used); | ||
3051 | return FALSE; | ||
3052 | } | ||
3053 | } | ||
3054 | |||
3055 | /* | ||
3056 | * Check that each Killer cage, if any, contains at most one of | ||
3057 | * everything. If we also know the clues for those cages (which we | ||
3058 | * might not, when this function is called early in puzzle | ||
3059 | * generation), we also check that they all have the right sum. | ||
3060 | */ | ||
3061 | if (kblocks) { | ||
3062 | for (i = 0; i < kblocks->nr_blocks; i++) { | ||
3063 | memset(used, FALSE, cr); | ||
3064 | for (j = 0; j < kblocks->nr_squares[i]; j++) | ||
3065 | if (grid[kblocks->blocks[i][j]] > 0 && | ||
3066 | grid[kblocks->blocks[i][j]] <= cr) { | ||
3067 | if (used[grid[kblocks->blocks[i][j]]-1]) { | ||
3068 | sfree(used); | ||
3069 | return FALSE; | ||
3070 | } | ||
3071 | used[grid[kblocks->blocks[i][j]]-1] = TRUE; | ||
3072 | } | ||
3073 | |||
3074 | if (kgrid && check_killer_cage_sum(kblocks, kgrid, grid, i) != 1) { | ||
3075 | sfree(used); | ||
3076 | return FALSE; | ||
3077 | } | ||
3078 | } | ||
3079 | } | ||
3080 | |||
3081 | /* | ||
3082 | * Check that each diagonal contains precisely one of everything. | ||
3083 | */ | ||
3084 | if (xtype) { | ||
3085 | memset(used, FALSE, cr); | ||
3086 | for (i = 0; i < cr; i++) | ||
3087 | if (grid[diag0(i)] > 0 && grid[diag0(i)] <= cr) | ||
3088 | used[grid[diag0(i)]-1] = TRUE; | ||
3089 | for (n = 0; n < cr; n++) | ||
3090 | if (!used[n]) { | ||
3091 | sfree(used); | ||
3092 | return FALSE; | ||
3093 | } | ||
3094 | for (i = 0; i < cr; i++) | ||
3095 | if (grid[diag1(i)] > 0 && grid[diag1(i)] <= cr) | ||
3096 | used[grid[diag1(i)]-1] = TRUE; | ||
3097 | for (n = 0; n < cr; n++) | ||
3098 | if (!used[n]) { | ||
3099 | sfree(used); | ||
3100 | return FALSE; | ||
3101 | } | ||
3102 | } | ||
3103 | |||
3104 | sfree(used); | ||
3105 | return TRUE; | ||
3106 | } | ||
3107 | |||
3108 | static int symmetries(const game_params *params, int x, int y, | ||
3109 | int *output, int s) | ||
3110 | { | ||
3111 | int c = params->c, r = params->r, cr = c*r; | ||
3112 | int i = 0; | ||
3113 | |||
3114 | #define ADD(x,y) (*output++ = (x), *output++ = (y), i++) | ||
3115 | |||
3116 | ADD(x, y); | ||
3117 | |||
3118 | switch (s) { | ||
3119 | case SYMM_NONE: | ||
3120 | break; /* just x,y is all we need */ | ||
3121 | case SYMM_ROT2: | ||
3122 | ADD(cr - 1 - x, cr - 1 - y); | ||
3123 | break; | ||
3124 | case SYMM_ROT4: | ||
3125 | ADD(cr - 1 - y, x); | ||
3126 | ADD(y, cr - 1 - x); | ||
3127 | ADD(cr - 1 - x, cr - 1 - y); | ||
3128 | break; | ||
3129 | case SYMM_REF2: | ||
3130 | ADD(cr - 1 - x, y); | ||
3131 | break; | ||
3132 | case SYMM_REF2D: | ||
3133 | ADD(y, x); | ||
3134 | break; | ||
3135 | case SYMM_REF4: | ||
3136 | ADD(cr - 1 - x, y); | ||
3137 | ADD(x, cr - 1 - y); | ||
3138 | ADD(cr - 1 - x, cr - 1 - y); | ||
3139 | break; | ||
3140 | case SYMM_REF4D: | ||
3141 | ADD(y, x); | ||
3142 | ADD(cr - 1 - x, cr - 1 - y); | ||
3143 | ADD(cr - 1 - y, cr - 1 - x); | ||
3144 | break; | ||
3145 | case SYMM_REF8: | ||
3146 | ADD(cr - 1 - x, y); | ||
3147 | ADD(x, cr - 1 - y); | ||
3148 | ADD(cr - 1 - x, cr - 1 - y); | ||
3149 | ADD(y, x); | ||
3150 | ADD(y, cr - 1 - x); | ||
3151 | ADD(cr - 1 - y, x); | ||
3152 | ADD(cr - 1 - y, cr - 1 - x); | ||
3153 | break; | ||
3154 | } | ||
3155 | |||
3156 | #undef ADD | ||
3157 | |||
3158 | return i; | ||
3159 | } | ||
3160 | |||
3161 | static char *encode_solve_move(int cr, digit *grid) | ||
3162 | { | ||
3163 | int i, len; | ||
3164 | char *ret, *p, *sep; | ||
3165 | |||
3166 | /* | ||
3167 | * It's surprisingly easy to work out _exactly_ how long this | ||
3168 | * string needs to be. To decimal-encode all the numbers from 1 | ||
3169 | * to n: | ||
3170 | * | ||
3171 | * - every number has a units digit; total is n. | ||
3172 | * - all numbers above 9 have a tens digit; total is max(n-9,0). | ||
3173 | * - all numbers above 99 have a hundreds digit; total is max(n-99,0). | ||
3174 | * - and so on. | ||
3175 | */ | ||
3176 | len = 0; | ||
3177 | for (i = 1; i <= cr; i *= 10) | ||
3178 | len += max(cr - i + 1, 0); | ||
3179 | len += cr; /* don't forget the commas */ | ||
3180 | len *= cr; /* there are cr rows of these */ | ||
3181 | |||
3182 | /* | ||
3183 | * Now len is one bigger than the total size of the | ||
3184 | * comma-separated numbers (because we counted an | ||
3185 | * additional leading comma). We need to have a leading S | ||
3186 | * and a trailing NUL, so we're off by one in total. | ||
3187 | */ | ||
3188 | len++; | ||
3189 | |||
3190 | ret = snewn(len, char); | ||
3191 | p = ret; | ||
3192 | *p++ = 'S'; | ||
3193 | sep = ""; | ||
3194 | for (i = 0; i < cr*cr; i++) { | ||
3195 | p += sprintf(p, "%s%d", sep, grid[i]); | ||
3196 | sep = ","; | ||
3197 | } | ||
3198 | *p++ = '\0'; | ||
3199 | assert(p - ret == len); | ||
3200 | |||
3201 | return ret; | ||
3202 | } | ||
3203 | |||
3204 | static void dsf_to_blocks(int *dsf, struct block_structure *blocks, | ||
3205 | int min_expected, int max_expected) | ||
3206 | { | ||
3207 | int cr = blocks->c * blocks->r, area = cr * cr; | ||
3208 | int i, nb = 0; | ||
3209 | |||
3210 | for (i = 0; i < area; i++) | ||
3211 | blocks->whichblock[i] = -1; | ||
3212 | for (i = 0; i < area; i++) { | ||
3213 | int j = dsf_canonify(dsf, i); | ||
3214 | if (blocks->whichblock[j] < 0) | ||
3215 | blocks->whichblock[j] = nb++; | ||
3216 | blocks->whichblock[i] = blocks->whichblock[j]; | ||
3217 | } | ||
3218 | assert(nb >= min_expected && nb <= max_expected); | ||
3219 | blocks->nr_blocks = nb; | ||
3220 | } | ||
3221 | |||
3222 | static void make_blocks_from_whichblock(struct block_structure *blocks) | ||
3223 | { | ||
3224 | int i; | ||
3225 | |||
3226 | for (i = 0; i < blocks->nr_blocks; i++) { | ||
3227 | blocks->blocks[i][blocks->max_nr_squares-1] = 0; | ||
3228 | blocks->nr_squares[i] = 0; | ||
3229 | } | ||
3230 | for (i = 0; i < blocks->area; i++) { | ||
3231 | int b = blocks->whichblock[i]; | ||
3232 | int j = blocks->blocks[b][blocks->max_nr_squares-1]++; | ||
3233 | assert(j < blocks->max_nr_squares); | ||
3234 | blocks->blocks[b][j] = i; | ||
3235 | blocks->nr_squares[b]++; | ||
3236 | } | ||
3237 | } | ||
3238 | |||
3239 | static char *encode_block_structure_desc(char *p, struct block_structure *blocks) | ||
3240 | { | ||
3241 | int i, currrun = 0; | ||
3242 | int c = blocks->c, r = blocks->r, cr = c * r; | ||
3243 | |||
3244 | /* | ||
3245 | * Encode the block structure. We do this by encoding | ||
3246 | * the pattern of dividing lines: first we iterate | ||
3247 | * over the cr*(cr-1) internal vertical grid lines in | ||
3248 | * ordinary reading order, then over the cr*(cr-1) | ||
3249 | * internal horizontal ones in transposed reading | ||
3250 | * order. | ||
3251 | * | ||
3252 | * We encode the number of non-lines between the | ||
3253 | * lines; _ means zero (two adjacent divisions), a | ||
3254 | * means 1, ..., y means 25, and z means 25 non-lines | ||
3255 | * _and no following line_ (so that za means 26, zb 27 | ||
3256 | * etc). | ||
3257 | */ | ||
3258 | for (i = 0; i <= 2*cr*(cr-1); i++) { | ||
3259 | int x, y, p0, p1, edge; | ||
3260 | |||
3261 | if (i == 2*cr*(cr-1)) { | ||
3262 | edge = TRUE; /* terminating virtual edge */ | ||
3263 | } else { | ||
3264 | if (i < cr*(cr-1)) { | ||
3265 | y = i/(cr-1); | ||
3266 | x = i%(cr-1); | ||
3267 | p0 = y*cr+x; | ||
3268 | p1 = y*cr+x+1; | ||
3269 | } else { | ||
3270 | x = i/(cr-1) - cr; | ||
3271 | y = i%(cr-1); | ||
3272 | p0 = y*cr+x; | ||
3273 | p1 = (y+1)*cr+x; | ||
3274 | } | ||
3275 | edge = (blocks->whichblock[p0] != blocks->whichblock[p1]); | ||
3276 | } | ||
3277 | |||
3278 | if (edge) { | ||
3279 | while (currrun > 25) | ||
3280 | *p++ = 'z', currrun -= 25; | ||
3281 | if (currrun) | ||
3282 | *p++ = 'a'-1 + currrun; | ||
3283 | else | ||
3284 | *p++ = '_'; | ||
3285 | currrun = 0; | ||
3286 | } else | ||
3287 | currrun++; | ||
3288 | } | ||
3289 | return p; | ||
3290 | } | ||
3291 | |||
3292 | static char *encode_grid(char *desc, digit *grid, int area) | ||
3293 | { | ||
3294 | int run, i; | ||
3295 | char *p = desc; | ||
3296 | |||
3297 | run = 0; | ||
3298 | for (i = 0; i <= area; i++) { | ||
3299 | int n = (i < area ? grid[i] : -1); | ||
3300 | |||
3301 | if (!n) | ||
3302 | run++; | ||
3303 | else { | ||
3304 | if (run) { | ||
3305 | while (run > 0) { | ||
3306 | int c = 'a' - 1 + run; | ||
3307 | if (run > 26) | ||
3308 | c = 'z'; | ||
3309 | *p++ = c; | ||
3310 | run -= c - ('a' - 1); | ||
3311 | } | ||
3312 | } else { | ||
3313 | /* | ||
3314 | * If there's a number in the very top left or | ||
3315 | * bottom right, there's no point putting an | ||
3316 | * unnecessary _ before or after it. | ||
3317 | */ | ||
3318 | if (p > desc && n > 0) | ||
3319 | *p++ = '_'; | ||
3320 | } | ||
3321 | if (n > 0) | ||
3322 | p += sprintf(p, "%d", n); | ||
3323 | run = 0; | ||
3324 | } | ||
3325 | } | ||
3326 | return p; | ||
3327 | } | ||
3328 | |||
3329 | /* | ||
3330 | * Conservatively stimate the number of characters required for | ||
3331 | * encoding a grid of a certain area. | ||
3332 | */ | ||
3333 | static int grid_encode_space (int area) | ||
3334 | { | ||
3335 | int t, count; | ||
3336 | for (count = 1, t = area; t > 26; t -= 26) | ||
3337 | count++; | ||
3338 | return count * area; | ||
3339 | } | ||
3340 | |||
3341 | /* | ||
3342 | * Conservatively stimate the number of characters required for | ||
3343 | * encoding a given blocks structure. | ||
3344 | */ | ||
3345 | static int blocks_encode_space(struct block_structure *blocks) | ||
3346 | { | ||
3347 | int cr = blocks->c * blocks->r, area = cr * cr; | ||
3348 | return grid_encode_space(area); | ||
3349 | } | ||
3350 | |||
3351 | static char *encode_puzzle_desc(const game_params *params, digit *grid, | ||
3352 | struct block_structure *blocks, | ||
3353 | digit *kgrid, | ||
3354 | struct block_structure *kblocks) | ||
3355 | { | ||
3356 | int c = params->c, r = params->r, cr = c*r; | ||
3357 | int area = cr*cr; | ||
3358 | char *p, *desc; | ||
3359 | int space; | ||
3360 | |||
3361 | space = grid_encode_space(area) + 1; | ||
3362 | if (r == 1) | ||
3363 | space += blocks_encode_space(blocks) + 1; | ||
3364 | if (params->killer) { | ||
3365 | space += blocks_encode_space(kblocks) + 1; | ||
3366 | space += grid_encode_space(area) + 1; | ||
3367 | } | ||
3368 | desc = snewn(space, char); | ||
3369 | p = encode_grid(desc, grid, area); | ||
3370 | |||
3371 | if (r == 1) { | ||
3372 | *p++ = ','; | ||
3373 | p = encode_block_structure_desc(p, blocks); | ||
3374 | } | ||
3375 | if (params->killer) { | ||
3376 | *p++ = ','; | ||
3377 | p = encode_block_structure_desc(p, kblocks); | ||
3378 | *p++ = ','; | ||
3379 | p = encode_grid(p, kgrid, area); | ||
3380 | } | ||
3381 | assert(p - desc < space); | ||
3382 | *p++ = '\0'; | ||
3383 | desc = sresize(desc, p - desc, char); | ||
3384 | |||
3385 | return desc; | ||
3386 | } | ||
3387 | |||
3388 | static void merge_blocks(struct block_structure *b, int n1, int n2) | ||
3389 | { | ||
3390 | int i; | ||
3391 | /* Move data towards the lower block number. */ | ||
3392 | if (n2 < n1) { | ||
3393 | int t = n2; | ||
3394 | n2 = n1; | ||
3395 | n1 = t; | ||
3396 | } | ||
3397 | |||
3398 | /* Merge n2 into n1, and move the last block into n2's position. */ | ||
3399 | for (i = 0; i < b->nr_squares[n2]; i++) | ||
3400 | b->whichblock[b->blocks[n2][i]] = n1; | ||
3401 | memcpy(b->blocks[n1] + b->nr_squares[n1], b->blocks[n2], | ||
3402 | b->nr_squares[n2] * sizeof **b->blocks); | ||
3403 | b->nr_squares[n1] += b->nr_squares[n2]; | ||
3404 | |||
3405 | n1 = b->nr_blocks - 1; | ||
3406 | if (n2 != n1) { | ||
3407 | memcpy(b->blocks[n2], b->blocks[n1], | ||
3408 | b->nr_squares[n1] * sizeof **b->blocks); | ||
3409 | for (i = 0; i < b->nr_squares[n1]; i++) | ||
3410 | b->whichblock[b->blocks[n1][i]] = n2; | ||
3411 | b->nr_squares[n2] = b->nr_squares[n1]; | ||
3412 | } | ||
3413 | b->nr_blocks = n1; | ||
3414 | } | ||
3415 | |||
3416 | static int merge_some_cages(struct block_structure *b, int cr, int area, | ||
3417 | digit *grid, random_state *rs) | ||
3418 | { | ||
3419 | /* | ||
3420 | * Make a list of all the pairs of adjacent blocks. | ||
3421 | */ | ||
3422 | int i, j, k; | ||
3423 | struct pair { | ||
3424 | int b1, b2; | ||
3425 | } *pairs; | ||
3426 | int npairs; | ||
3427 | |||
3428 | pairs = snewn(b->nr_blocks * b->nr_blocks, struct pair); | ||
3429 | npairs = 0; | ||
3430 | |||
3431 | for (i = 0; i < b->nr_blocks; i++) { | ||
3432 | for (j = i+1; j < b->nr_blocks; j++) { | ||
3433 | |||
3434 | /* | ||
3435 | * Rule the merger out of consideration if it's | ||
3436 | * obviously not viable. | ||
3437 | */ | ||
3438 | if (b->nr_squares[i] + b->nr_squares[j] > b->max_nr_squares) | ||
3439 | continue; /* we couldn't merge these anyway */ | ||
3440 | |||
3441 | /* | ||
3442 | * See if these two blocks have a pair of squares | ||
3443 | * adjacent to each other. | ||
3444 | */ | ||
3445 | for (k = 0; k < b->nr_squares[i]; k++) { | ||
3446 | int xy = b->blocks[i][k]; | ||
3447 | int y = xy / cr, x = xy % cr; | ||
3448 | if ((y > 0 && b->whichblock[xy - cr] == j) || | ||
3449 | (y+1 < cr && b->whichblock[xy + cr] == j) || | ||
3450 | (x > 0 && b->whichblock[xy - 1] == j) || | ||
3451 | (x+1 < cr && b->whichblock[xy + 1] == j)) { | ||
3452 | /* | ||
3453 | * Yes! Add this pair to our list. | ||
3454 | */ | ||
3455 | pairs[npairs].b1 = i; | ||
3456 | pairs[npairs].b2 = j; | ||
3457 | break; | ||
3458 | } | ||
3459 | } | ||
3460 | } | ||
3461 | } | ||
3462 | |||
3463 | /* | ||
3464 | * Now go through that list in random order until we find a pair | ||
3465 | * of blocks we can merge. | ||
3466 | */ | ||
3467 | while (npairs > 0) { | ||
3468 | int n1, n2; | ||
3469 | unsigned int digits_found; | ||
3470 | |||
3471 | /* | ||
3472 | * Pick a random pair, and remove it from the list. | ||
3473 | */ | ||
3474 | i = random_upto(rs, npairs); | ||
3475 | n1 = pairs[i].b1; | ||
3476 | n2 = pairs[i].b2; | ||
3477 | if (i != npairs-1) | ||
3478 | pairs[i] = pairs[npairs-1]; | ||
3479 | npairs--; | ||
3480 | |||
3481 | /* Guarantee that the merged cage would still be a region. */ | ||
3482 | digits_found = 0; | ||
3483 | for (i = 0; i < b->nr_squares[n1]; i++) | ||
3484 | digits_found |= 1 << grid[b->blocks[n1][i]]; | ||
3485 | for (i = 0; i < b->nr_squares[n2]; i++) | ||
3486 | if (digits_found & (1 << grid[b->blocks[n2][i]])) | ||
3487 | break; | ||
3488 | if (i != b->nr_squares[n2]) | ||
3489 | continue; | ||
3490 | |||
3491 | /* | ||
3492 | * Got one! Do the merge. | ||
3493 | */ | ||
3494 | merge_blocks(b, n1, n2); | ||
3495 | sfree(pairs); | ||
3496 | return TRUE; | ||
3497 | } | ||
3498 | |||
3499 | sfree(pairs); | ||
3500 | return FALSE; | ||
3501 | } | ||
3502 | |||
3503 | static void compute_kclues(struct block_structure *cages, digit *kclues, | ||
3504 | digit *grid, int area) | ||
3505 | { | ||
3506 | int i; | ||
3507 | memset(kclues, 0, area * sizeof *kclues); | ||
3508 | for (i = 0; i < cages->nr_blocks; i++) { | ||
3509 | int j, sum = 0; | ||
3510 | for (j = 0; j < area; j++) | ||
3511 | if (cages->whichblock[j] == i) | ||
3512 | sum += grid[j]; | ||
3513 | for (j = 0; j < area; j++) | ||
3514 | if (cages->whichblock[j] == i) | ||
3515 | break; | ||
3516 | assert (j != area); | ||
3517 | kclues[j] = sum; | ||
3518 | } | ||
3519 | } | ||
3520 | |||
3521 | static struct block_structure *gen_killer_cages(int cr, random_state *rs, | ||
3522 | int remove_singletons) | ||
3523 | { | ||
3524 | int nr; | ||
3525 | int x, y, area = cr * cr; | ||
3526 | int n_singletons = 0; | ||
3527 | struct block_structure *b = alloc_block_structure (1, cr, area, cr, area); | ||
3528 | |||
3529 | for (x = 0; x < area; x++) | ||
3530 | b->whichblock[x] = -1; | ||
3531 | nr = 0; | ||
3532 | for (y = 0; y < cr; y++) | ||
3533 | for (x = 0; x < cr; x++) { | ||
3534 | int rnd; | ||
3535 | int xy = y*cr+x; | ||
3536 | if (b->whichblock[xy] != -1) | ||
3537 | continue; | ||
3538 | b->whichblock[xy] = nr; | ||
3539 | |||
3540 | rnd = random_bits(rs, 4); | ||
3541 | if (xy + 1 < area && (rnd >= 4 || (!remove_singletons && rnd >= 1))) { | ||
3542 | int xy2 = xy + 1; | ||
3543 | if (x + 1 == cr || b->whichblock[xy2] != -1 || | ||
3544 | (xy + cr < area && random_bits(rs, 1) == 0)) | ||
3545 | xy2 = xy + cr; | ||
3546 | if (xy2 >= area) | ||
3547 | n_singletons++; | ||
3548 | else | ||
3549 | b->whichblock[xy2] = nr; | ||
3550 | } else | ||
3551 | n_singletons++; | ||
3552 | nr++; | ||
3553 | } | ||
3554 | |||
3555 | b->nr_blocks = nr; | ||
3556 | make_blocks_from_whichblock(b); | ||
3557 | |||
3558 | for (x = y = 0; x < b->nr_blocks; x++) | ||
3559 | if (b->nr_squares[x] == 1) | ||
3560 | y++; | ||
3561 | assert(y == n_singletons); | ||
3562 | |||
3563 | if (n_singletons > 0 && remove_singletons) { | ||
3564 | int n; | ||
3565 | for (n = 0; n < b->nr_blocks;) { | ||
3566 | int xy, x, y, xy2, other; | ||
3567 | if (b->nr_squares[n] > 1) { | ||
3568 | n++; | ||
3569 | continue; | ||
3570 | } | ||
3571 | xy = b->blocks[n][0]; | ||
3572 | x = xy % cr; | ||
3573 | y = xy / cr; | ||
3574 | if (xy + 1 == area) | ||
3575 | xy2 = xy - 1; | ||
3576 | else if (x + 1 < cr && (y + 1 == cr || random_bits(rs, 1) == 0)) | ||
3577 | xy2 = xy + 1; | ||
3578 | else | ||
3579 | xy2 = xy + cr; | ||
3580 | other = b->whichblock[xy2]; | ||
3581 | |||
3582 | if (b->nr_squares[other] == 1) | ||
3583 | n_singletons--; | ||
3584 | n_singletons--; | ||
3585 | merge_blocks(b, n, other); | ||
3586 | if (n < other) | ||
3587 | n++; | ||
3588 | } | ||
3589 | assert(n_singletons == 0); | ||
3590 | } | ||
3591 | return b; | ||
3592 | } | ||
3593 | |||
3594 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
3595 | char **aux, int interactive) | ||
3596 | { | ||
3597 | int c = params->c, r = params->r, cr = c*r; | ||
3598 | int area = cr*cr; | ||
3599 | struct block_structure *blocks, *kblocks; | ||
3600 | digit *grid, *grid2, *kgrid; | ||
3601 | struct xy { int x, y; } *locs; | ||
3602 | int nlocs; | ||
3603 | char *desc; | ||
3604 | int coords[16], ncoords; | ||
3605 | int x, y, i, j; | ||
3606 | struct difficulty dlev; | ||
3607 | |||
3608 | precompute_sum_bits(); | ||
3609 | |||
3610 | /* | ||
3611 | * Adjust the maximum difficulty level to be consistent with | ||
3612 | * the puzzle size: all 2x2 puzzles appear to be Trivial | ||
3613 | * (DIFF_BLOCK) so we cannot hold out for even a Basic | ||
3614 | * (DIFF_SIMPLE) one. | ||
3615 | */ | ||
3616 | dlev.maxdiff = params->diff; | ||
3617 | dlev.maxkdiff = params->kdiff; | ||
3618 | if (c == 2 && r == 2) | ||
3619 | dlev.maxdiff = DIFF_BLOCK; | ||
3620 | |||
3621 | grid = snewn(area, digit); | ||
3622 | locs = snewn(area, struct xy); | ||
3623 | grid2 = snewn(area, digit); | ||
3624 | |||
3625 | blocks = alloc_block_structure (c, r, area, cr, cr); | ||
3626 | |||
3627 | kblocks = NULL; | ||
3628 | kgrid = (params->killer) ? snewn(area, digit) : NULL; | ||
3629 | |||
3630 | #ifdef STANDALONE_SOLVER | ||
3631 | assert(!"This should never happen, so we don't need to create blocknames"); | ||
3632 | #endif | ||
3633 | |||
3634 | /* | ||
3635 | * Loop until we get a grid of the required difficulty. This is | ||
3636 | * nasty, but it seems to be unpleasantly hard to generate | ||
3637 | * difficult grids otherwise. | ||
3638 | */ | ||
3639 | while (1) { | ||
3640 | /* | ||
3641 | * Generate a random solved state, starting by | ||
3642 | * constructing the block structure. | ||
3643 | */ | ||
3644 | if (r == 1) { /* jigsaw mode */ | ||
3645 | int *dsf = divvy_rectangle(cr, cr, cr, rs); | ||
3646 | |||
3647 | dsf_to_blocks (dsf, blocks, cr, cr); | ||
3648 | |||
3649 | sfree(dsf); | ||
3650 | } else { /* basic Sudoku mode */ | ||
3651 | for (y = 0; y < cr; y++) | ||
3652 | for (x = 0; x < cr; x++) | ||
3653 | blocks->whichblock[y*cr+x] = (y/c) * c + (x/r); | ||
3654 | } | ||
3655 | make_blocks_from_whichblock(blocks); | ||
3656 | |||
3657 | if (params->killer) { | ||
3658 | if (kblocks) free_block_structure(kblocks); | ||
3659 | kblocks = gen_killer_cages(cr, rs, params->kdiff > DIFF_KSINGLE); | ||
3660 | } | ||
3661 | |||
3662 | if (!gridgen(cr, blocks, kblocks, params->xtype, grid, rs, area*area)) | ||
3663 | continue; | ||
3664 | assert(check_valid(cr, blocks, kblocks, NULL, params->xtype, grid)); | ||
3665 | |||
3666 | /* | ||
3667 | * Save the solved grid in aux. | ||
3668 | */ | ||
3669 | { | ||
3670 | /* | ||
3671 | * We might already have written *aux the last time we | ||
3672 | * went round this loop, in which case we should free | ||
3673 | * the old aux before overwriting it with the new one. | ||
3674 | */ | ||
3675 | if (*aux) { | ||
3676 | sfree(*aux); | ||
3677 | } | ||
3678 | |||
3679 | *aux = encode_solve_move(cr, grid); | ||
3680 | } | ||
3681 | |||
3682 | /* | ||
3683 | * Now we have a solved grid. For normal puzzles, we start removing | ||
3684 | * things from it while preserving solubility. Killer puzzles are | ||
3685 | * different: we just pass the empty grid to the solver, and use | ||
3686 | * the puzzle if it comes back solved. | ||
3687 | */ | ||
3688 | |||
3689 | if (params->killer) { | ||
3690 | struct block_structure *good_cages = NULL; | ||
3691 | struct block_structure *last_cages = NULL; | ||
3692 | int ntries = 0; | ||
3693 | |||
3694 | memcpy(grid2, grid, area); | ||
3695 | |||
3696 | for (;;) { | ||
3697 | compute_kclues(kblocks, kgrid, grid2, area); | ||
3698 | |||
3699 | memset(grid, 0, area * sizeof *grid); | ||
3700 | solver(cr, blocks, kblocks, params->xtype, grid, kgrid, &dlev); | ||
3701 | if (dlev.diff == dlev.maxdiff && dlev.kdiff == dlev.maxkdiff) { | ||
3702 | /* | ||
3703 | * We have one that matches our difficulty. Store it for | ||
3704 | * later, but keep going. | ||
3705 | */ | ||
3706 | if (good_cages) | ||
3707 | free_block_structure(good_cages); | ||
3708 | ntries = 0; | ||
3709 | good_cages = dup_block_structure(kblocks); | ||
3710 | if (!merge_some_cages(kblocks, cr, area, grid2, rs)) | ||
3711 | break; | ||
3712 | } else if (dlev.diff > dlev.maxdiff || dlev.kdiff > dlev.maxkdiff) { | ||
3713 | /* | ||
3714 | * Give up after too many tries and either use the good one we | ||
3715 | * found, or generate a new grid. | ||
3716 | */ | ||
3717 | if (++ntries > 50) | ||
3718 | break; | ||
3719 | /* | ||
3720 | * The difficulty level got too high. If we have a good | ||
3721 | * one, use it, otherwise go back to the last one that | ||
3722 | * was at a lower difficulty and restart the process from | ||
3723 | * there. | ||
3724 | */ | ||
3725 | if (good_cages != NULL) { | ||
3726 | free_block_structure(kblocks); | ||
3727 | kblocks = dup_block_structure(good_cages); | ||
3728 | if (!merge_some_cages(kblocks, cr, area, grid2, rs)) | ||
3729 | break; | ||
3730 | } else { | ||
3731 | if (last_cages == NULL) | ||
3732 | break; | ||
3733 | free_block_structure(kblocks); | ||
3734 | kblocks = last_cages; | ||
3735 | last_cages = NULL; | ||
3736 | } | ||
3737 | } else { | ||
3738 | if (last_cages) | ||
3739 | free_block_structure(last_cages); | ||
3740 | last_cages = dup_block_structure(kblocks); | ||
3741 | if (!merge_some_cages(kblocks, cr, area, grid2, rs)) | ||
3742 | break; | ||
3743 | } | ||
3744 | } | ||
3745 | if (last_cages) | ||
3746 | free_block_structure(last_cages); | ||
3747 | if (good_cages != NULL) { | ||
3748 | free_block_structure(kblocks); | ||
3749 | kblocks = good_cages; | ||
3750 | compute_kclues(kblocks, kgrid, grid2, area); | ||
3751 | memset(grid, 0, area * sizeof *grid); | ||
3752 | break; | ||
3753 | } | ||
3754 | continue; | ||
3755 | } | ||
3756 | |||
3757 | /* | ||
3758 | * Find the set of equivalence classes of squares permitted | ||
3759 | * by the selected symmetry. We do this by enumerating all | ||
3760 | * the grid squares which have no symmetric companion | ||
3761 | * sorting lower than themselves. | ||
3762 | */ | ||
3763 | nlocs = 0; | ||
3764 | for (y = 0; y < cr; y++) | ||
3765 | for (x = 0; x < cr; x++) { | ||
3766 | int i = y*cr+x; | ||
3767 | int j; | ||
3768 | |||
3769 | ncoords = symmetries(params, x, y, coords, params->symm); | ||
3770 | for (j = 0; j < ncoords; j++) | ||
3771 | if (coords[2*j+1]*cr+coords[2*j] < i) | ||
3772 | break; | ||
3773 | if (j == ncoords) { | ||
3774 | locs[nlocs].x = x; | ||
3775 | locs[nlocs].y = y; | ||
3776 | nlocs++; | ||
3777 | } | ||
3778 | } | ||
3779 | |||
3780 | /* | ||
3781 | * Now shuffle that list. | ||
3782 | */ | ||
3783 | shuffle(locs, nlocs, sizeof(*locs), rs); | ||
3784 | |||
3785 | /* | ||
3786 | * Now loop over the shuffled list and, for each element, | ||
3787 | * see whether removing that element (and its reflections) | ||
3788 | * from the grid will still leave the grid soluble. | ||
3789 | */ | ||
3790 | for (i = 0; i < nlocs; i++) { | ||
3791 | x = locs[i].x; | ||
3792 | y = locs[i].y; | ||
3793 | |||
3794 | memcpy(grid2, grid, area); | ||
3795 | ncoords = symmetries(params, x, y, coords, params->symm); | ||
3796 | for (j = 0; j < ncoords; j++) | ||
3797 | grid2[coords[2*j+1]*cr+coords[2*j]] = 0; | ||
3798 | |||
3799 | solver(cr, blocks, kblocks, params->xtype, grid2, kgrid, &dlev); | ||
3800 | if (dlev.diff <= dlev.maxdiff && | ||
3801 | (!params->killer || dlev.kdiff <= dlev.maxkdiff)) { | ||
3802 | for (j = 0; j < ncoords; j++) | ||
3803 | grid[coords[2*j+1]*cr+coords[2*j]] = 0; | ||
3804 | } | ||
3805 | } | ||
3806 | |||
3807 | memcpy(grid2, grid, area); | ||
3808 | |||
3809 | solver(cr, blocks, kblocks, params->xtype, grid2, kgrid, &dlev); | ||
3810 | if (dlev.diff == dlev.maxdiff && | ||
3811 | (!params->killer || dlev.kdiff == dlev.maxkdiff)) | ||
3812 | break; /* found one! */ | ||
3813 | } | ||
3814 | |||
3815 | sfree(grid2); | ||
3816 | sfree(locs); | ||
3817 | |||
3818 | /* | ||
3819 | * Now we have the grid as it will be presented to the user. | ||
3820 | * Encode it in a game desc. | ||
3821 | */ | ||
3822 | desc = encode_puzzle_desc(params, grid, blocks, kgrid, kblocks); | ||
3823 | |||
3824 | sfree(grid); | ||
3825 | free_block_structure(blocks); | ||
3826 | if (params->killer) { | ||
3827 | free_block_structure(kblocks); | ||
3828 | sfree(kgrid); | ||
3829 | } | ||
3830 | |||
3831 | return desc; | ||
3832 | } | ||
3833 | |||
3834 | static const char *spec_to_grid(const char *desc, digit *grid, int area) | ||
3835 | { | ||
3836 | int i = 0; | ||
3837 | while (*desc && *desc != ',') { | ||
3838 | int n = *desc++; | ||
3839 | if (n >= 'a' && n <= 'z') { | ||
3840 | int run = n - 'a' + 1; | ||
3841 | assert(i + run <= area); | ||
3842 | while (run-- > 0) | ||
3843 | grid[i++] = 0; | ||
3844 | } else if (n == '_') { | ||
3845 | /* do nothing */; | ||
3846 | } else if (n > '0' && n <= '9') { | ||
3847 | assert(i < area); | ||
3848 | grid[i++] = atoi(desc-1); | ||
3849 | while (*desc >= '0' && *desc <= '9') | ||
3850 | desc++; | ||
3851 | } else { | ||
3852 | assert(!"We can't get here"); | ||
3853 | } | ||
3854 | } | ||
3855 | assert(i == area); | ||
3856 | return desc; | ||
3857 | } | ||
3858 | |||
3859 | /* | ||
3860 | * Create a DSF from a spec found in *pdesc. Update this to point past the | ||
3861 | * end of the block spec, and return an error string or NULL if everything | ||
3862 | * is OK. The DSF is stored in *PDSF. | ||
3863 | */ | ||
3864 | static char *spec_to_dsf(const char **pdesc, int **pdsf, int cr, int area) | ||
3865 | { | ||
3866 | const char *desc = *pdesc; | ||
3867 | int pos = 0; | ||
3868 | int *dsf; | ||
3869 | |||
3870 | *pdsf = dsf = snew_dsf(area); | ||
3871 | |||
3872 | while (*desc && *desc != ',') { | ||
3873 | int c, adv; | ||
3874 | |||
3875 | if (*desc == '_') | ||
3876 | c = 0; | ||
3877 | else if (*desc >= 'a' && *desc <= 'z') | ||
3878 | c = *desc - 'a' + 1; | ||
3879 | else { | ||
3880 | sfree(dsf); | ||
3881 | return "Invalid character in game description"; | ||
3882 | } | ||
3883 | desc++; | ||
3884 | |||
3885 | adv = (c != 26); /* 'z' is a special case */ | ||
3886 | |||
3887 | while (c-- > 0) { | ||
3888 | int p0, p1; | ||
3889 | |||
3890 | /* | ||
3891 | * Non-edge; merge the two dsf classes on either | ||
3892 | * side of it. | ||
3893 | */ | ||
3894 | if (pos >= 2*cr*(cr-1)) { | ||
3895 | sfree(dsf); | ||
3896 | return "Too much data in block structure specification"; | ||
3897 | } | ||
3898 | |||
3899 | if (pos < cr*(cr-1)) { | ||
3900 | int y = pos/(cr-1); | ||
3901 | int x = pos%(cr-1); | ||
3902 | p0 = y*cr+x; | ||
3903 | p1 = y*cr+x+1; | ||
3904 | } else { | ||
3905 | int x = pos/(cr-1) - cr; | ||
3906 | int y = pos%(cr-1); | ||
3907 | p0 = y*cr+x; | ||
3908 | p1 = (y+1)*cr+x; | ||
3909 | } | ||
3910 | dsf_merge(dsf, p0, p1); | ||
3911 | |||
3912 | pos++; | ||
3913 | } | ||
3914 | if (adv) | ||
3915 | pos++; | ||
3916 | } | ||
3917 | *pdesc = desc; | ||
3918 | |||
3919 | /* | ||
3920 | * When desc is exhausted, we expect to have gone exactly | ||
3921 | * one space _past_ the end of the grid, due to the dummy | ||
3922 | * edge at the end. | ||
3923 | */ | ||
3924 | if (pos != 2*cr*(cr-1)+1) { | ||
3925 | sfree(dsf); | ||
3926 | return "Not enough data in block structure specification"; | ||
3927 | } | ||
3928 | |||
3929 | return NULL; | ||
3930 | } | ||
3931 | |||
3932 | static char *validate_grid_desc(const char **pdesc, int range, int area) | ||
3933 | { | ||
3934 | const char *desc = *pdesc; | ||
3935 | int squares = 0; | ||
3936 | while (*desc && *desc != ',') { | ||
3937 | int n = *desc++; | ||
3938 | if (n >= 'a' && n <= 'z') { | ||
3939 | squares += n - 'a' + 1; | ||
3940 | } else if (n == '_') { | ||
3941 | /* do nothing */; | ||
3942 | } else if (n > '0' && n <= '9') { | ||
3943 | int val = atoi(desc-1); | ||
3944 | if (val < 1 || val > range) | ||
3945 | return "Out-of-range number in game description"; | ||
3946 | squares++; | ||
3947 | while (*desc >= '0' && *desc <= '9') | ||
3948 | desc++; | ||
3949 | } else | ||
3950 | return "Invalid character in game description"; | ||
3951 | } | ||
3952 | |||
3953 | if (squares < area) | ||
3954 | return "Not enough data to fill grid"; | ||
3955 | |||
3956 | if (squares > area) | ||
3957 | return "Too much data to fit in grid"; | ||
3958 | *pdesc = desc; | ||
3959 | return NULL; | ||
3960 | } | ||
3961 | |||
3962 | static char *validate_block_desc(const char **pdesc, int cr, int area, | ||
3963 | int min_nr_blocks, int max_nr_blocks, | ||
3964 | int min_nr_squares, int max_nr_squares) | ||
3965 | { | ||
3966 | char *err; | ||
3967 | int *dsf; | ||
3968 | |||
3969 | err = spec_to_dsf(pdesc, &dsf, cr, area); | ||
3970 | if (err) { | ||
3971 | return err; | ||
3972 | } | ||
3973 | |||
3974 | if (min_nr_squares == max_nr_squares) { | ||
3975 | assert(min_nr_blocks == max_nr_blocks); | ||
3976 | assert(min_nr_blocks * min_nr_squares == area); | ||
3977 | } | ||
3978 | /* | ||
3979 | * Now we've got our dsf. Verify that it matches | ||
3980 | * expectations. | ||
3981 | */ | ||
3982 | { | ||
3983 | int *canons, *counts; | ||
3984 | int i, j, c, ncanons = 0; | ||
3985 | |||
3986 | canons = snewn(max_nr_blocks, int); | ||
3987 | counts = snewn(max_nr_blocks, int); | ||
3988 | |||
3989 | for (i = 0; i < area; i++) { | ||
3990 | j = dsf_canonify(dsf, i); | ||
3991 | |||
3992 | for (c = 0; c < ncanons; c++) | ||
3993 | if (canons[c] == j) { | ||
3994 | counts[c]++; | ||
3995 | if (counts[c] > max_nr_squares) { | ||
3996 | sfree(dsf); | ||
3997 | sfree(canons); | ||
3998 | sfree(counts); | ||
3999 | return "A jigsaw block is too big"; | ||
4000 | } | ||
4001 | break; | ||
4002 | } | ||
4003 | |||
4004 | if (c == ncanons) { | ||
4005 | if (ncanons >= max_nr_blocks) { | ||
4006 | sfree(dsf); | ||
4007 | sfree(canons); | ||
4008 | sfree(counts); | ||
4009 | return "Too many distinct jigsaw blocks"; | ||
4010 | } | ||
4011 | canons[ncanons] = j; | ||
4012 | counts[ncanons] = 1; | ||
4013 | ncanons++; | ||
4014 | } | ||
4015 | } | ||
4016 | |||
4017 | if (ncanons < min_nr_blocks) { | ||
4018 | sfree(dsf); | ||
4019 | sfree(canons); | ||
4020 | sfree(counts); | ||
4021 | return "Not enough distinct jigsaw blocks"; | ||
4022 | } | ||
4023 | for (c = 0; c < ncanons; c++) { | ||
4024 | if (counts[c] < min_nr_squares) { | ||
4025 | sfree(dsf); | ||
4026 | sfree(canons); | ||
4027 | sfree(counts); | ||
4028 | return "A jigsaw block is too small"; | ||
4029 | } | ||
4030 | } | ||
4031 | sfree(canons); | ||
4032 | sfree(counts); | ||
4033 | } | ||
4034 | |||
4035 | sfree(dsf); | ||
4036 | return NULL; | ||
4037 | } | ||
4038 | |||
4039 | static char *validate_desc(const game_params *params, const char *desc) | ||
4040 | { | ||
4041 | int cr = params->c * params->r, area = cr*cr; | ||
4042 | char *err; | ||
4043 | |||
4044 | err = validate_grid_desc(&desc, cr, area); | ||
4045 | if (err) | ||
4046 | return err; | ||
4047 | |||
4048 | if (params->r == 1) { | ||
4049 | /* | ||
4050 | * Now we expect a suffix giving the jigsaw block | ||
4051 | * structure. Parse it and validate that it divides the | ||
4052 | * grid into the right number of regions which are the | ||
4053 | * right size. | ||
4054 | */ | ||
4055 | if (*desc != ',') | ||
4056 | return "Expected jigsaw block structure in game description"; | ||
4057 | desc++; | ||
4058 | err = validate_block_desc(&desc, cr, area, cr, cr, cr, cr); | ||
4059 | if (err) | ||
4060 | return err; | ||
4061 | |||
4062 | } | ||
4063 | if (params->killer) { | ||
4064 | if (*desc != ',') | ||
4065 | return "Expected killer block structure in game description"; | ||
4066 | desc++; | ||
4067 | err = validate_block_desc(&desc, cr, area, cr, area, 2, cr); | ||
4068 | if (err) | ||
4069 | return err; | ||
4070 | if (*desc != ',') | ||
4071 | return "Expected killer clue grid in game description"; | ||
4072 | desc++; | ||
4073 | err = validate_grid_desc(&desc, cr * area, area); | ||
4074 | if (err) | ||
4075 | return err; | ||
4076 | } | ||
4077 | if (*desc) | ||
4078 | return "Unexpected data at end of game description"; | ||
4079 | |||
4080 | return NULL; | ||
4081 | } | ||
4082 | |||
4083 | static game_state *new_game(midend *me, const game_params *params, | ||
4084 | const char *desc) | ||
4085 | { | ||
4086 | game_state *state = snew(game_state); | ||
4087 | int c = params->c, r = params->r, cr = c*r, area = cr * cr; | ||
4088 | int i; | ||
4089 | |||
4090 | precompute_sum_bits(); | ||
4091 | |||
4092 | state->cr = cr; | ||
4093 | state->xtype = params->xtype; | ||
4094 | state->killer = params->killer; | ||
4095 | |||
4096 | state->grid = snewn(area, digit); | ||
4097 | state->pencil = snewn(area * cr, unsigned char); | ||
4098 | memset(state->pencil, 0, area * cr); | ||
4099 | state->immutable = snewn(area, unsigned char); | ||
4100 | memset(state->immutable, FALSE, area); | ||
4101 | |||
4102 | state->blocks = alloc_block_structure (c, r, area, cr, cr); | ||
4103 | |||
4104 | if (params->killer) { | ||
4105 | state->kblocks = alloc_block_structure (c, r, area, cr, area); | ||
4106 | state->kgrid = snewn(area, digit); | ||
4107 | } else { | ||
4108 | state->kblocks = NULL; | ||
4109 | state->kgrid = NULL; | ||
4110 | } | ||
4111 | state->completed = state->cheated = FALSE; | ||
4112 | |||
4113 | desc = spec_to_grid(desc, state->grid, area); | ||
4114 | for (i = 0; i < area; i++) | ||
4115 | if (state->grid[i] != 0) | ||
4116 | state->immutable[i] = TRUE; | ||
4117 | |||
4118 | if (r == 1) { | ||
4119 | char *err; | ||
4120 | int *dsf; | ||
4121 | assert(*desc == ','); | ||
4122 | desc++; | ||
4123 | err = spec_to_dsf(&desc, &dsf, cr, area); | ||
4124 | assert(err == NULL); | ||
4125 | dsf_to_blocks(dsf, state->blocks, cr, cr); | ||
4126 | sfree(dsf); | ||
4127 | } else { | ||
4128 | int x, y; | ||
4129 | |||
4130 | for (y = 0; y < cr; y++) | ||
4131 | for (x = 0; x < cr; x++) | ||
4132 | state->blocks->whichblock[y*cr+x] = (y/c) * c + (x/r); | ||
4133 | } | ||
4134 | make_blocks_from_whichblock(state->blocks); | ||
4135 | |||
4136 | if (params->killer) { | ||
4137 | char *err; | ||
4138 | int *dsf; | ||
4139 | assert(*desc == ','); | ||
4140 | desc++; | ||
4141 | err = spec_to_dsf(&desc, &dsf, cr, area); | ||
4142 | assert(err == NULL); | ||
4143 | dsf_to_blocks(dsf, state->kblocks, cr, area); | ||
4144 | sfree(dsf); | ||
4145 | make_blocks_from_whichblock(state->kblocks); | ||
4146 | |||
4147 | assert(*desc == ','); | ||
4148 | desc++; | ||
4149 | desc = spec_to_grid(desc, state->kgrid, area); | ||
4150 | } | ||
4151 | assert(!*desc); | ||
4152 | |||
4153 | #ifdef STANDALONE_SOLVER | ||
4154 | /* | ||
4155 | * Set up the block names for solver diagnostic output. | ||
4156 | */ | ||
4157 | { | ||
4158 | char *p = (char *)(state->blocks->blocknames + cr); | ||
4159 | |||
4160 | if (r == 1) { | ||
4161 | for (i = 0; i < area; i++) { | ||
4162 | int j = state->blocks->whichblock[i]; | ||
4163 | if (!state->blocks->blocknames[j]) { | ||
4164 | state->blocks->blocknames[j] = p; | ||
4165 | p += 1 + sprintf(p, "starting at (%d,%d)", | ||
4166 | 1 + i%cr, 1 + i/cr); | ||
4167 | } | ||
4168 | } | ||
4169 | } else { | ||
4170 | int bx, by; | ||
4171 | for (by = 0; by < r; by++) | ||
4172 | for (bx = 0; bx < c; bx++) { | ||
4173 | state->blocks->blocknames[by*c+bx] = p; | ||
4174 | p += 1 + sprintf(p, "(%d,%d)", bx+1, by+1); | ||
4175 | } | ||
4176 | } | ||
4177 | assert(p - (char *)state->blocks->blocknames < (int)(cr*(sizeof(char *)+80))); | ||
4178 | for (i = 0; i < cr; i++) | ||
4179 | assert(state->blocks->blocknames[i]); | ||
4180 | } | ||
4181 | #endif | ||
4182 | |||
4183 | return state; | ||
4184 | } | ||
4185 | |||
4186 | static game_state *dup_game(const game_state *state) | ||
4187 | { | ||
4188 | game_state *ret = snew(game_state); | ||
4189 | int cr = state->cr, area = cr * cr; | ||
4190 | |||
4191 | ret->cr = state->cr; | ||
4192 | ret->xtype = state->xtype; | ||
4193 | ret->killer = state->killer; | ||
4194 | |||
4195 | ret->blocks = state->blocks; | ||
4196 | ret->blocks->refcount++; | ||
4197 | |||
4198 | ret->kblocks = state->kblocks; | ||
4199 | if (ret->kblocks) | ||
4200 | ret->kblocks->refcount++; | ||
4201 | |||
4202 | ret->grid = snewn(area, digit); | ||
4203 | memcpy(ret->grid, state->grid, area); | ||
4204 | |||
4205 | if (state->killer) { | ||
4206 | ret->kgrid = snewn(area, digit); | ||
4207 | memcpy(ret->kgrid, state->kgrid, area); | ||
4208 | } else | ||
4209 | ret->kgrid = NULL; | ||
4210 | |||
4211 | ret->pencil = snewn(area * cr, unsigned char); | ||
4212 | memcpy(ret->pencil, state->pencil, area * cr); | ||
4213 | |||
4214 | ret->immutable = snewn(area, unsigned char); | ||
4215 | memcpy(ret->immutable, state->immutable, area); | ||
4216 | |||
4217 | ret->completed = state->completed; | ||
4218 | ret->cheated = state->cheated; | ||
4219 | |||
4220 | return ret; | ||
4221 | } | ||
4222 | |||
4223 | static void free_game(game_state *state) | ||
4224 | { | ||
4225 | free_block_structure(state->blocks); | ||
4226 | if (state->kblocks) | ||
4227 | free_block_structure(state->kblocks); | ||
4228 | |||
4229 | sfree(state->immutable); | ||
4230 | sfree(state->pencil); | ||
4231 | sfree(state->grid); | ||
4232 | if (state->kgrid) sfree(state->kgrid); | ||
4233 | sfree(state); | ||
4234 | } | ||
4235 | |||
4236 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
4237 | const char *ai, char **error) | ||
4238 | { | ||
4239 | int cr = state->cr; | ||
4240 | char *ret; | ||
4241 | digit *grid; | ||
4242 | struct difficulty dlev; | ||
4243 | |||
4244 | /* | ||
4245 | * If we already have the solution in ai, save ourselves some | ||
4246 | * time. | ||
4247 | */ | ||
4248 | if (ai) | ||
4249 | return dupstr(ai); | ||
4250 | |||
4251 | grid = snewn(cr*cr, digit); | ||
4252 | memcpy(grid, state->grid, cr*cr); | ||
4253 | dlev.maxdiff = DIFF_RECURSIVE; | ||
4254 | dlev.maxkdiff = DIFF_KINTERSECT; | ||
4255 | solver(cr, state->blocks, state->kblocks, state->xtype, grid, | ||
4256 | state->kgrid, &dlev); | ||
4257 | |||
4258 | *error = NULL; | ||
4259 | |||
4260 | if (dlev.diff == DIFF_IMPOSSIBLE) | ||
4261 | *error = "No solution exists for this puzzle"; | ||
4262 | else if (dlev.diff == DIFF_AMBIGUOUS) | ||
4263 | *error = "Multiple solutions exist for this puzzle"; | ||
4264 | |||
4265 | if (*error) { | ||
4266 | sfree(grid); | ||
4267 | return NULL; | ||
4268 | } | ||
4269 | |||
4270 | ret = encode_solve_move(cr, grid); | ||
4271 | |||
4272 | sfree(grid); | ||
4273 | |||
4274 | return ret; | ||
4275 | } | ||
4276 | |||
4277 | static char *grid_text_format(int cr, struct block_structure *blocks, | ||
4278 | int xtype, digit *grid) | ||
4279 | { | ||
4280 | int vmod, hmod; | ||
4281 | int x, y; | ||
4282 | int totallen, linelen, nlines; | ||
4283 | char *ret, *p, ch; | ||
4284 | |||
4285 | /* | ||
4286 | * For non-jigsaw Sudoku, we format in the way we always have, | ||
4287 | * by having the digits unevenly spaced so that the dividing | ||
4288 | * lines can fit in: | ||
4289 | * | ||
4290 | * . . | . . | ||
4291 | * . . | . . | ||
4292 | * ----+---- | ||
4293 | * . . | . . | ||
4294 | * . . | . . | ||
4295 | * | ||
4296 | * For jigsaw puzzles, however, we must leave space between | ||
4297 | * _all_ pairs of digits for an optional dividing line, so we | ||
4298 | * have to move to the rather ugly | ||
4299 | * | ||
4300 | * . . . . | ||
4301 | * ------+------ | ||
4302 | * . . | . . | ||
4303 | * +---+ | ||
4304 | * . . | . | . | ||
4305 | * ------+ | | ||
4306 | * . . . | . | ||
4307 | * | ||
4308 | * We deal with both cases using the same formatting code; we | ||
4309 | * simply invent a vmod value such that there's a vertical | ||
4310 | * dividing line before column i iff i is divisible by vmod | ||
4311 | * (so it's r in the first case and 1 in the second), and hmod | ||
4312 | * likewise for horizontal dividing lines. | ||
4313 | */ | ||
4314 | |||
4315 | if (blocks->r != 1) { | ||
4316 | vmod = blocks->r; | ||
4317 | hmod = blocks->c; | ||
4318 | } else { | ||
4319 | vmod = hmod = 1; | ||
4320 | } | ||
4321 | |||
4322 | /* | ||
4323 | * Line length: we have cr digits, each with a space after it, | ||
4324 | * and (cr-1)/vmod dividing lines, each with a space after it. | ||
4325 | * The final space is replaced by a newline, but that doesn't | ||
4326 | * affect the length. | ||
4327 | */ | ||
4328 | linelen = 2*(cr + (cr-1)/vmod); | ||
4329 | |||
4330 | /* | ||
4331 | * Number of lines: we have cr rows of digits, and (cr-1)/hmod | ||
4332 | * dividing rows. | ||
4333 | */ | ||
4334 | nlines = cr + (cr-1)/hmod; | ||
4335 | |||
4336 | /* | ||
4337 | * Allocate the space. | ||
4338 | */ | ||
4339 | totallen = linelen * nlines; | ||
4340 | ret = snewn(totallen+1, char); /* leave room for terminating NUL */ | ||
4341 | |||
4342 | /* | ||
4343 | * Write the text. | ||
4344 | */ | ||
4345 | p = ret; | ||
4346 | for (y = 0; y < cr; y++) { | ||
4347 | /* | ||
4348 | * Row of digits. | ||
4349 | */ | ||
4350 | for (x = 0; x < cr; x++) { | ||
4351 | /* | ||
4352 | * Digit. | ||
4353 | */ | ||
4354 | digit d = grid[y*cr+x]; | ||
4355 | |||
4356 | if (d == 0) { | ||
4357 | /* | ||
4358 | * Empty space: we usually write a dot, but we'll | ||
4359 | * highlight spaces on the X-diagonals (in X mode) | ||
4360 | * by using underscores instead. | ||
4361 | */ | ||
4362 | if (xtype && (ondiag0(y*cr+x) || ondiag1(y*cr+x))) | ||
4363 | ch = '_'; | ||
4364 | else | ||
4365 | ch = '.'; | ||
4366 | } else if (d <= 9) { | ||
4367 | ch = '0' + d; | ||
4368 | } else { | ||
4369 | ch = 'a' + d-10; | ||
4370 | } | ||
4371 | |||
4372 | *p++ = ch; | ||
4373 | if (x == cr-1) { | ||
4374 | *p++ = '\n'; | ||
4375 | continue; | ||
4376 | } | ||
4377 | *p++ = ' '; | ||
4378 | |||
4379 | if ((x+1) % vmod) | ||
4380 | continue; | ||
4381 | |||
4382 | /* | ||
4383 | * Optional dividing line. | ||
4384 | */ | ||
4385 | if (blocks->whichblock[y*cr+x] != blocks->whichblock[y*cr+x+1]) | ||
4386 | ch = '|'; | ||
4387 | else | ||
4388 | ch = ' '; | ||
4389 | *p++ = ch; | ||
4390 | *p++ = ' '; | ||
4391 | } | ||
4392 | if (y == cr-1 || (y+1) % hmod) | ||
4393 | continue; | ||
4394 | |||
4395 | /* | ||
4396 | * Dividing row. | ||
4397 | */ | ||
4398 | for (x = 0; x < cr; x++) { | ||
4399 | int dwid; | ||
4400 | int tl, tr, bl, br; | ||
4401 | |||
4402 | /* | ||
4403 | * Division between two squares. This varies | ||
4404 | * complicatedly in length. | ||
4405 | */ | ||
4406 | dwid = 2; /* digit and its following space */ | ||
4407 | if (x == cr-1) | ||
4408 | dwid--; /* no following space at end of line */ | ||
4409 | if (x > 0 && x % vmod == 0) | ||
4410 | dwid++; /* preceding space after a divider */ | ||
4411 | |||
4412 | if (blocks->whichblock[y*cr+x] != blocks->whichblock[(y+1)*cr+x]) | ||
4413 | ch = '-'; | ||
4414 | else | ||
4415 | ch = ' '; | ||
4416 | |||
4417 | while (dwid-- > 0) | ||
4418 | *p++ = ch; | ||
4419 | |||
4420 | if (x == cr-1) { | ||
4421 | *p++ = '\n'; | ||
4422 | break; | ||
4423 | } | ||
4424 | |||
4425 | if ((x+1) % vmod) | ||
4426 | continue; | ||
4427 | |||
4428 | /* | ||
4429 | * Corner square. This is: | ||
4430 | * - a space if all four surrounding squares are in | ||
4431 | * the same block | ||
4432 | * - a vertical line if the two left ones are in one | ||
4433 | * block and the two right in another | ||
4434 | * - a horizontal line if the two top ones are in one | ||
4435 | * block and the two bottom in another | ||
4436 | * - a plus sign in all other cases. (If we had a | ||
4437 | * richer character set available we could break | ||
4438 | * this case up further by doing fun things with | ||
4439 | * line-drawing T-pieces.) | ||
4440 | */ | ||
4441 | tl = blocks->whichblock[y*cr+x]; | ||
4442 | tr = blocks->whichblock[y*cr+x+1]; | ||
4443 | bl = blocks->whichblock[(y+1)*cr+x]; | ||
4444 | br = blocks->whichblock[(y+1)*cr+x+1]; | ||
4445 | |||
4446 | if (tl == tr && tr == bl && bl == br) | ||
4447 | ch = ' '; | ||
4448 | else if (tl == bl && tr == br) | ||
4449 | ch = '|'; | ||
4450 | else if (tl == tr && bl == br) | ||
4451 | ch = '-'; | ||
4452 | else | ||
4453 | ch = '+'; | ||
4454 | |||
4455 | *p++ = ch; | ||
4456 | } | ||
4457 | } | ||
4458 | |||
4459 | assert(p - ret == totallen); | ||
4460 | *p = '\0'; | ||
4461 | return ret; | ||
4462 | } | ||
4463 | |||
4464 | static int game_can_format_as_text_now(const game_params *params) | ||
4465 | { | ||
4466 | /* | ||
4467 | * Formatting Killer puzzles as text is currently unsupported. I | ||
4468 | * can't think of any sensible way of doing it which doesn't | ||
4469 | * involve expanding the puzzle to such a large scale as to make | ||
4470 | * it unusable. | ||
4471 | */ | ||
4472 | if (params->killer) | ||
4473 | return FALSE; | ||
4474 | return TRUE; | ||
4475 | } | ||
4476 | |||
4477 | static char *game_text_format(const game_state *state) | ||
4478 | { | ||
4479 | assert(!state->kblocks); | ||
4480 | return grid_text_format(state->cr, state->blocks, state->xtype, | ||
4481 | state->grid); | ||
4482 | } | ||
4483 | |||
4484 | struct game_ui { | ||
4485 | /* | ||
4486 | * These are the coordinates of the currently highlighted | ||
4487 | * square on the grid, if hshow = 1. | ||
4488 | */ | ||
4489 | int hx, hy; | ||
4490 | /* | ||
4491 | * This indicates whether the current highlight is a | ||
4492 | * pencil-mark one or a real one. | ||
4493 | */ | ||
4494 | int hpencil; | ||
4495 | /* | ||
4496 | * This indicates whether or not we're showing the highlight | ||
4497 | * (used to be hx = hy = -1); important so that when we're | ||
4498 | * using the cursor keys it doesn't keep coming back at a | ||
4499 | * fixed position. When hshow = 1, pressing a valid number | ||
4500 | * or letter key or Space will enter that number or letter in the grid. | ||
4501 | */ | ||
4502 | int hshow; | ||
4503 | /* | ||
4504 | * This indicates whether we're using the highlight as a cursor; | ||
4505 | * it means that it doesn't vanish on a keypress, and that it is | ||
4506 | * allowed on immutable squares. | ||
4507 | */ | ||
4508 | int hcursor; | ||
4509 | }; | ||
4510 | |||
4511 | static game_ui *new_ui(const game_state *state) | ||
4512 | { | ||
4513 | game_ui *ui = snew(game_ui); | ||
4514 | |||
4515 | ui->hx = ui->hy = 0; | ||
4516 | ui->hpencil = ui->hshow = ui->hcursor = 0; | ||
4517 | |||
4518 | return ui; | ||
4519 | } | ||
4520 | |||
4521 | static void free_ui(game_ui *ui) | ||
4522 | { | ||
4523 | sfree(ui); | ||
4524 | } | ||
4525 | |||
4526 | static char *encode_ui(const game_ui *ui) | ||
4527 | { | ||
4528 | return NULL; | ||
4529 | } | ||
4530 | |||
4531 | static void decode_ui(game_ui *ui, const char *encoding) | ||
4532 | { | ||
4533 | } | ||
4534 | |||
4535 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
4536 | const game_state *newstate) | ||
4537 | { | ||
4538 | int cr = newstate->cr; | ||
4539 | /* | ||
4540 | * We prevent pencil-mode highlighting of a filled square, unless | ||
4541 | * we're using the cursor keys. So if the user has just filled in | ||
4542 | * a square which we had a pencil-mode highlight in (by Undo, or | ||
4543 | * by Redo, or by Solve), then we cancel the highlight. | ||
4544 | */ | ||
4545 | if (ui->hshow && ui->hpencil && !ui->hcursor && | ||
4546 | newstate->grid[ui->hy * cr + ui->hx] != 0) { | ||
4547 | ui->hshow = 0; | ||
4548 | } | ||
4549 | } | ||
4550 | |||
4551 | struct game_drawstate { | ||
4552 | int started; | ||
4553 | int cr, xtype; | ||
4554 | int tilesize; | ||
4555 | digit *grid; | ||
4556 | unsigned char *pencil; | ||
4557 | unsigned char *hl; | ||
4558 | /* This is scratch space used within a single call to game_redraw. */ | ||
4559 | int nregions, *entered_items; | ||
4560 | }; | ||
4561 | |||
4562 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
4563 | const game_drawstate *ds, | ||
4564 | int x, int y, int button) | ||
4565 | { | ||
4566 | int cr = state->cr; | ||
4567 | int tx, ty; | ||
4568 | char buf[80]; | ||
4569 | |||
4570 | button &= ~MOD_MASK; | ||
4571 | |||
4572 | tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1; | ||
4573 | ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1; | ||
4574 | |||
4575 | if (tx >= 0 && tx < cr && ty >= 0 && ty < cr) { | ||
4576 | if (button == LEFT_BUTTON) { | ||
4577 | if (state->immutable[ty*cr+tx]) { | ||
4578 | ui->hshow = 0; | ||
4579 | } else if (tx == ui->hx && ty == ui->hy && | ||
4580 | ui->hshow && ui->hpencil == 0) { | ||
4581 | ui->hshow = 0; | ||
4582 | } else { | ||
4583 | ui->hx = tx; | ||
4584 | ui->hy = ty; | ||
4585 | ui->hshow = 1; | ||
4586 | ui->hpencil = 0; | ||
4587 | } | ||
4588 | ui->hcursor = 0; | ||
4589 | return ""; /* UI activity occurred */ | ||
4590 | } | ||
4591 | if (button == RIGHT_BUTTON) { | ||
4592 | /* | ||
4593 | * Pencil-mode highlighting for non filled squares. | ||
4594 | */ | ||
4595 | if (state->grid[ty*cr+tx] == 0) { | ||
4596 | if (tx == ui->hx && ty == ui->hy && | ||
4597 | ui->hshow && ui->hpencil) { | ||
4598 | ui->hshow = 0; | ||
4599 | } else { | ||
4600 | ui->hpencil = 1; | ||
4601 | ui->hx = tx; | ||
4602 | ui->hy = ty; | ||
4603 | ui->hshow = 1; | ||
4604 | } | ||
4605 | } else { | ||
4606 | ui->hshow = 0; | ||
4607 | } | ||
4608 | ui->hcursor = 0; | ||
4609 | return ""; /* UI activity occurred */ | ||
4610 | } | ||
4611 | } | ||
4612 | if (IS_CURSOR_MOVE(button)) { | ||
4613 | move_cursor(button, &ui->hx, &ui->hy, cr, cr, 0); | ||
4614 | ui->hshow = ui->hcursor = 1; | ||
4615 | return ""; | ||
4616 | } | ||
4617 | if (ui->hshow && | ||
4618 | (button == CURSOR_SELECT)) { | ||
4619 | ui->hpencil = 1 - ui->hpencil; | ||
4620 | ui->hcursor = 1; | ||
4621 | return ""; | ||
4622 | } | ||
4623 | |||
4624 | if (ui->hshow && | ||
4625 | ((button >= '0' && button <= '9' && button - '0' <= cr) || | ||
4626 | (button >= 'a' && button <= 'z' && button - 'a' + 10 <= cr) || | ||
4627 | (button >= 'A' && button <= 'Z' && button - 'A' + 10 <= cr) || | ||
4628 | button == CURSOR_SELECT2 || button == '\b')) { | ||
4629 | int n = button - '0'; | ||
4630 | if (button >= 'A' && button <= 'Z') | ||
4631 | n = button - 'A' + 10; | ||
4632 | if (button >= 'a' && button <= 'z') | ||
4633 | n = button - 'a' + 10; | ||
4634 | if (button == CURSOR_SELECT2 || button == '\b') | ||
4635 | n = 0; | ||
4636 | |||
4637 | /* | ||
4638 | * Can't overwrite this square. This can only happen here | ||
4639 | * if we're using the cursor keys. | ||
4640 | */ | ||
4641 | if (state->immutable[ui->hy*cr+ui->hx]) | ||
4642 | return NULL; | ||
4643 | |||
4644 | /* | ||
4645 | * Can't make pencil marks in a filled square. Again, this | ||
4646 | * can only become highlighted if we're using cursor keys. | ||
4647 | */ | ||
4648 | if (ui->hpencil && state->grid[ui->hy*cr+ui->hx]) | ||
4649 | return NULL; | ||
4650 | |||
4651 | sprintf(buf, "%c%d,%d,%d", | ||
4652 | (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n); | ||
4653 | |||
4654 | if (!ui->hcursor) ui->hshow = 0; | ||
4655 | |||
4656 | return dupstr(buf); | ||
4657 | } | ||
4658 | |||
4659 | if (button == 'M' || button == 'm') | ||
4660 | return dupstr("M"); | ||
4661 | |||
4662 | return NULL; | ||
4663 | } | ||
4664 | |||
4665 | static game_state *execute_move(const game_state *from, const char *move) | ||
4666 | { | ||
4667 | int cr = from->cr; | ||
4668 | game_state *ret; | ||
4669 | int x, y, n; | ||
4670 | |||
4671 | if (move[0] == 'S') { | ||
4672 | const char *p; | ||
4673 | |||
4674 | ret = dup_game(from); | ||
4675 | ret->completed = ret->cheated = TRUE; | ||
4676 | |||
4677 | p = move+1; | ||
4678 | for (n = 0; n < cr*cr; n++) { | ||
4679 | ret->grid[n] = atoi(p); | ||
4680 | |||
4681 | if (!*p || ret->grid[n] < 1 || ret->grid[n] > cr) { | ||
4682 | free_game(ret); | ||
4683 | return NULL; | ||
4684 | } | ||
4685 | |||
4686 | while (*p && isdigit((unsigned char)*p)) p++; | ||
4687 | if (*p == ',') p++; | ||
4688 | } | ||
4689 | |||
4690 | return ret; | ||
4691 | } else if ((move[0] == 'P' || move[0] == 'R') && | ||
4692 | sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 && | ||
4693 | x >= 0 && x < cr && y >= 0 && y < cr && n >= 0 && n <= cr) { | ||
4694 | |||
4695 | ret = dup_game(from); | ||
4696 | if (move[0] == 'P' && n > 0) { | ||
4697 | int index = (y*cr+x) * cr + (n-1); | ||
4698 | ret->pencil[index] = !ret->pencil[index]; | ||
4699 | } else { | ||
4700 | ret->grid[y*cr+x] = n; | ||
4701 | memset(ret->pencil + (y*cr+x)*cr, 0, cr); | ||
4702 | |||
4703 | /* | ||
4704 | * We've made a real change to the grid. Check to see | ||
4705 | * if the game has been completed. | ||
4706 | */ | ||
4707 | if (!ret->completed && check_valid( | ||
4708 | cr, ret->blocks, ret->kblocks, ret->kgrid, | ||
4709 | ret->xtype, ret->grid)) { | ||
4710 | ret->completed = TRUE; | ||
4711 | } | ||
4712 | } | ||
4713 | return ret; | ||
4714 | } else if (move[0] == 'M') { | ||
4715 | /* | ||
4716 | * Fill in absolutely all pencil marks in unfilled squares, | ||
4717 | * for those who like to play by the rigorous approach of | ||
4718 | * starting off in that state and eliminating things. | ||
4719 | */ | ||
4720 | ret = dup_game(from); | ||
4721 | for (y = 0; y < cr; y++) { | ||
4722 | for (x = 0; x < cr; x++) { | ||
4723 | if (!ret->grid[y*cr+x]) { | ||
4724 | memset(ret->pencil + (y*cr+x)*cr, 1, cr); | ||
4725 | } | ||
4726 | } | ||
4727 | } | ||
4728 | return ret; | ||
4729 | } else | ||
4730 | return NULL; /* couldn't parse move string */ | ||
4731 | } | ||
4732 | |||
4733 | /* ---------------------------------------------------------------------- | ||
4734 | * Drawing routines. | ||
4735 | */ | ||
4736 | |||
4737 | #define SIZE(cr) ((cr) * TILE_SIZE + 2*BORDER + 1) | ||
4738 | #define GETTILESIZE(cr, w) ( (double)(w-1) / (double)(cr+1) ) | ||
4739 | |||
4740 | static void game_compute_size(const game_params *params, int tilesize, | ||
4741 | int *x, int *y) | ||
4742 | { | ||
4743 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
4744 | struct { int tilesize; } ads, *ds = &ads; | ||
4745 | ads.tilesize = tilesize; | ||
4746 | |||
4747 | *x = SIZE(params->c * params->r); | ||
4748 | *y = SIZE(params->c * params->r); | ||
4749 | } | ||
4750 | |||
4751 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
4752 | const game_params *params, int tilesize) | ||
4753 | { | ||
4754 | ds->tilesize = tilesize; | ||
4755 | } | ||
4756 | |||
4757 | static float *game_colours(frontend *fe, int *ncolours) | ||
4758 | { | ||
4759 | float *ret = snewn(3 * NCOLOURS, float); | ||
4760 | |||
4761 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
4762 | |||
4763 | ret[COL_XDIAGONALS * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0]; | ||
4764 | ret[COL_XDIAGONALS * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1]; | ||
4765 | ret[COL_XDIAGONALS * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2]; | ||
4766 | |||
4767 | ret[COL_GRID * 3 + 0] = 0.0F; | ||
4768 | ret[COL_GRID * 3 + 1] = 0.0F; | ||
4769 | ret[COL_GRID * 3 + 2] = 0.0F; | ||
4770 | |||
4771 | ret[COL_CLUE * 3 + 0] = 0.0F; | ||
4772 | ret[COL_CLUE * 3 + 1] = 0.0F; | ||
4773 | ret[COL_CLUE * 3 + 2] = 0.0F; | ||
4774 | |||
4775 | ret[COL_USER * 3 + 0] = 0.0F; | ||
4776 | ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1]; | ||
4777 | ret[COL_USER * 3 + 2] = 0.0F; | ||
4778 | |||
4779 | ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0]; | ||
4780 | ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1]; | ||
4781 | ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2]; | ||
4782 | |||
4783 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
4784 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
4785 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
4786 | |||
4787 | ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; | ||
4788 | ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; | ||
4789 | ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; | ||
4790 | |||
4791 | ret[COL_KILLER * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; | ||
4792 | ret[COL_KILLER * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; | ||
4793 | ret[COL_KILLER * 3 + 2] = 0.1F * ret[COL_BACKGROUND * 3 + 2]; | ||
4794 | |||
4795 | *ncolours = NCOLOURS; | ||
4796 | return ret; | ||
4797 | } | ||
4798 | |||
4799 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
4800 | { | ||
4801 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
4802 | int cr = state->cr; | ||
4803 | |||
4804 | ds->started = FALSE; | ||
4805 | ds->cr = cr; | ||
4806 | ds->xtype = state->xtype; | ||
4807 | ds->grid = snewn(cr*cr, digit); | ||
4808 | memset(ds->grid, cr+2, cr*cr); | ||
4809 | ds->pencil = snewn(cr*cr*cr, digit); | ||
4810 | memset(ds->pencil, 0, cr*cr*cr); | ||
4811 | ds->hl = snewn(cr*cr, unsigned char); | ||
4812 | memset(ds->hl, 0, cr*cr); | ||
4813 | /* | ||
4814 | * ds->entered_items needs one row of cr entries per entity in | ||
4815 | * which digits may not be duplicated. That's one for each row, | ||
4816 | * each column, each block, each diagonal, and each Killer cage. | ||
4817 | */ | ||
4818 | ds->nregions = cr*3 + 2; | ||
4819 | if (state->kblocks) | ||
4820 | ds->nregions += state->kblocks->nr_blocks; | ||
4821 | ds->entered_items = snewn(cr * ds->nregions, int); | ||
4822 | ds->tilesize = 0; /* not decided yet */ | ||
4823 | return ds; | ||
4824 | } | ||
4825 | |||
4826 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
4827 | { | ||
4828 | sfree(ds->hl); | ||
4829 | sfree(ds->pencil); | ||
4830 | sfree(ds->grid); | ||
4831 | sfree(ds->entered_items); | ||
4832 | sfree(ds); | ||
4833 | } | ||
4834 | |||
4835 | static void draw_number(drawing *dr, game_drawstate *ds, | ||
4836 | const game_state *state, int x, int y, int hl) | ||
4837 | { | ||
4838 | int cr = state->cr; | ||
4839 | int tx, ty, tw, th; | ||
4840 | int cx, cy, cw, ch; | ||
4841 | int col_killer = (hl & 32 ? COL_ERROR : COL_KILLER); | ||
4842 | char str[20]; | ||
4843 | |||
4844 | if (ds->grid[y*cr+x] == state->grid[y*cr+x] && | ||
4845 | ds->hl[y*cr+x] == hl && | ||
4846 | !memcmp(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr)) | ||
4847 | return; /* no change required */ | ||
4848 | |||
4849 | tx = BORDER + x * TILE_SIZE + 1 + GRIDEXTRA; | ||
4850 | ty = BORDER + y * TILE_SIZE + 1 + GRIDEXTRA; | ||
4851 | |||
4852 | cx = tx; | ||
4853 | cy = ty; | ||
4854 | cw = tw = TILE_SIZE-1-2*GRIDEXTRA; | ||
4855 | ch = th = TILE_SIZE-1-2*GRIDEXTRA; | ||
4856 | |||
4857 | if (x > 0 && state->blocks->whichblock[y*cr+x] == state->blocks->whichblock[y*cr+x-1]) | ||
4858 | cx -= GRIDEXTRA, cw += GRIDEXTRA; | ||
4859 | if (x+1 < cr && state->blocks->whichblock[y*cr+x] == state->blocks->whichblock[y*cr+x+1]) | ||
4860 | cw += GRIDEXTRA; | ||
4861 | if (y > 0 && state->blocks->whichblock[y*cr+x] == state->blocks->whichblock[(y-1)*cr+x]) | ||
4862 | cy -= GRIDEXTRA, ch += GRIDEXTRA; | ||
4863 | if (y+1 < cr && state->blocks->whichblock[y*cr+x] == state->blocks->whichblock[(y+1)*cr+x]) | ||
4864 | ch += GRIDEXTRA; | ||
4865 | |||
4866 | clip(dr, cx, cy, cw, ch); | ||
4867 | |||
4868 | /* background needs erasing */ | ||
4869 | draw_rect(dr, cx, cy, cw, ch, | ||
4870 | ((hl & 15) == 1 ? COL_HIGHLIGHT : | ||
4871 | (ds->xtype && (ondiag0(y*cr+x) || ondiag1(y*cr+x))) ? COL_XDIAGONALS : | ||
4872 | COL_BACKGROUND)); | ||
4873 | |||
4874 | /* | ||
4875 | * Draw the corners of thick lines in corner-adjacent squares, | ||
4876 | * which jut into this square by one pixel. | ||
4877 | */ | ||
4878 | if (x > 0 && y > 0 && state->blocks->whichblock[y*cr+x] != state->blocks->whichblock[(y-1)*cr+x-1]) | ||
4879 | draw_rect(dr, tx-GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID); | ||
4880 | if (x+1 < cr && y > 0 && state->blocks->whichblock[y*cr+x] != state->blocks->whichblock[(y-1)*cr+x+1]) | ||
4881 | draw_rect(dr, tx+TILE_SIZE-1-2*GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID); | ||
4882 | if (x > 0 && y+1 < cr && state->blocks->whichblock[y*cr+x] != state->blocks->whichblock[(y+1)*cr+x-1]) | ||
4883 | draw_rect(dr, tx-GRIDEXTRA, ty+TILE_SIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID); | ||
4884 | if (x+1 < cr && y+1 < cr && state->blocks->whichblock[y*cr+x] != state->blocks->whichblock[(y+1)*cr+x+1]) | ||
4885 | draw_rect(dr, tx+TILE_SIZE-1-2*GRIDEXTRA, ty+TILE_SIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID); | ||
4886 | |||
4887 | /* pencil-mode highlight */ | ||
4888 | if ((hl & 15) == 2) { | ||
4889 | int coords[6]; | ||
4890 | coords[0] = cx; | ||
4891 | coords[1] = cy; | ||
4892 | coords[2] = cx+cw/2; | ||
4893 | coords[3] = cy; | ||
4894 | coords[4] = cx; | ||
4895 | coords[5] = cy+ch/2; | ||
4896 | draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); | ||
4897 | } | ||
4898 | |||
4899 | if (state->kblocks) { | ||
4900 | int t = GRIDEXTRA * 3; | ||
4901 | int kcx, kcy, kcw, kch; | ||
4902 | int kl, kt, kr, kb; | ||
4903 | int has_left = 0, has_right = 0, has_top = 0, has_bottom = 0; | ||
4904 | |||
4905 | /* | ||
4906 | * In non-jigsaw mode, the Killer cages are placed at a | ||
4907 | * fixed offset from the outer edge of the cell dividing | ||
4908 | * lines, so that they look right whether those lines are | ||
4909 | * thick or thin. In jigsaw mode, however, doing this will | ||
4910 | * sometimes cause the cage outlines in adjacent squares to | ||
4911 | * fail to match up with each other, so we must offset a | ||
4912 | * fixed amount from the _centre_ of the cell dividing | ||
4913 | * lines. | ||
4914 | */ | ||
4915 | if (state->blocks->r == 1) { | ||
4916 | kcx = tx; | ||
4917 | kcy = ty; | ||
4918 | kcw = tw; | ||
4919 | kch = th; | ||
4920 | } else { | ||
4921 | kcx = cx; | ||
4922 | kcy = cy; | ||
4923 | kcw = cw; | ||
4924 | kch = ch; | ||
4925 | } | ||
4926 | kl = kcx - 1; | ||
4927 | kt = kcy - 1; | ||
4928 | kr = kcx + kcw; | ||
4929 | kb = kcy + kch; | ||
4930 | |||
4931 | /* | ||
4932 | * First, draw the lines dividing this area from neighbouring | ||
4933 | * different areas. | ||
4934 | */ | ||
4935 | if (x == 0 || state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[y*cr+x-1]) | ||
4936 | has_left = 1, kl += t; | ||
4937 | if (x+1 >= cr || state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[y*cr+x+1]) | ||
4938 | has_right = 1, kr -= t; | ||
4939 | if (y == 0 || state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[(y-1)*cr+x]) | ||
4940 | has_top = 1, kt += t; | ||
4941 | if (y+1 >= cr || state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[(y+1)*cr+x]) | ||
4942 | has_bottom = 1, kb -= t; | ||
4943 | if (has_top) | ||
4944 | draw_line(dr, kl, kt, kr, kt, col_killer); | ||
4945 | if (has_bottom) | ||
4946 | draw_line(dr, kl, kb, kr, kb, col_killer); | ||
4947 | if (has_left) | ||
4948 | draw_line(dr, kl, kt, kl, kb, col_killer); | ||
4949 | if (has_right) | ||
4950 | draw_line(dr, kr, kt, kr, kb, col_killer); | ||
4951 | /* | ||
4952 | * Now, take care of the corners (just as for the normal borders). | ||
4953 | * We only need a corner if there wasn't a full edge. | ||
4954 | */ | ||
4955 | if (x > 0 && y > 0 && !has_left && !has_top | ||
4956 | && state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[(y-1)*cr+x-1]) | ||
4957 | { | ||
4958 | draw_line(dr, kl, kt + t, kl + t, kt + t, col_killer); | ||
4959 | draw_line(dr, kl + t, kt, kl + t, kt + t, col_killer); | ||
4960 | } | ||
4961 | if (x+1 < cr && y > 0 && !has_right && !has_top | ||
4962 | && state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[(y-1)*cr+x+1]) | ||
4963 | { | ||
4964 | draw_line(dr, kcx + kcw - t, kt + t, kcx + kcw, kt + t, col_killer); | ||
4965 | draw_line(dr, kcx + kcw - t, kt, kcx + kcw - t, kt + t, col_killer); | ||
4966 | } | ||
4967 | if (x > 0 && y+1 < cr && !has_left && !has_bottom | ||
4968 | && state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[(y+1)*cr+x-1]) | ||
4969 | { | ||
4970 | draw_line(dr, kl, kcy + kch - t, kl + t, kcy + kch - t, col_killer); | ||
4971 | draw_line(dr, kl + t, kcy + kch - t, kl + t, kcy + kch, col_killer); | ||
4972 | } | ||
4973 | if (x+1 < cr && y+1 < cr && !has_right && !has_bottom | ||
4974 | && state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[(y+1)*cr+x+1]) | ||
4975 | { | ||
4976 | draw_line(dr, kcx + kcw - t, kcy + kch - t, kcx + kcw - t, kcy + kch, col_killer); | ||
4977 | draw_line(dr, kcx + kcw - t, kcy + kch - t, kcx + kcw, kcy + kch - t, col_killer); | ||
4978 | } | ||
4979 | |||
4980 | } | ||
4981 | |||
4982 | if (state->killer && state->kgrid[y*cr+x]) { | ||
4983 | sprintf (str, "%d", state->kgrid[y*cr+x]); | ||
4984 | draw_text(dr, tx + GRIDEXTRA * 4, ty + GRIDEXTRA * 4 + TILE_SIZE/4, | ||
4985 | FONT_VARIABLE, TILE_SIZE/4, ALIGN_VNORMAL | ALIGN_HLEFT, | ||
4986 | col_killer, str); | ||
4987 | } | ||
4988 | |||
4989 | /* new number needs drawing? */ | ||
4990 | if (state->grid[y*cr+x]) { | ||
4991 | str[1] = '\0'; | ||
4992 | str[0] = state->grid[y*cr+x] + '0'; | ||
4993 | if (str[0] > '9') | ||
4994 | str[0] += 'a' - ('9'+1); | ||
4995 | draw_text(dr, tx + TILE_SIZE/2, ty + TILE_SIZE/2, | ||
4996 | FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE, | ||
4997 | state->immutable[y*cr+x] ? COL_CLUE : (hl & 16) ? COL_ERROR : COL_USER, str); | ||
4998 | } else { | ||
4999 | int i, j, npencil; | ||
5000 | int pl, pr, pt, pb; | ||
5001 | float bestsize; | ||
5002 | int pw, ph, minph, pbest, fontsize; | ||
5003 | |||
5004 | /* Count the pencil marks required. */ | ||
5005 | for (i = npencil = 0; i < cr; i++) | ||
5006 | if (state->pencil[(y*cr+x)*cr+i]) | ||
5007 | npencil++; | ||
5008 | if (npencil) { | ||
5009 | |||
5010 | minph = 2; | ||
5011 | |||
5012 | /* | ||
5013 | * Determine the bounding rectangle within which we're going | ||
5014 | * to put the pencil marks. | ||
5015 | */ | ||
5016 | /* Start with the whole square */ | ||
5017 | pl = tx + GRIDEXTRA; | ||
5018 | pr = pl + TILE_SIZE - GRIDEXTRA; | ||
5019 | pt = ty + GRIDEXTRA; | ||
5020 | pb = pt + TILE_SIZE - GRIDEXTRA; | ||
5021 | if (state->killer) { | ||
5022 | /* | ||
5023 | * Make space for the Killer cages. We do this | ||
5024 | * unconditionally, for uniformity between squares, | ||
5025 | * rather than making it depend on whether a Killer | ||
5026 | * cage edge is actually present on any given side. | ||
5027 | */ | ||
5028 | pl += GRIDEXTRA * 3; | ||
5029 | pr -= GRIDEXTRA * 3; | ||
5030 | pt += GRIDEXTRA * 3; | ||
5031 | pb -= GRIDEXTRA * 3; | ||
5032 | if (state->kgrid[y*cr+x] != 0) { | ||
5033 | /* Make further space for the Killer number. */ | ||
5034 | pt += TILE_SIZE/4; | ||
5035 | /* minph--; */ | ||
5036 | } | ||
5037 | } | ||
5038 | |||
5039 | /* | ||
5040 | * We arrange our pencil marks in a grid layout, with | ||
5041 | * the number of rows and columns adjusted to allow the | ||
5042 | * maximum font size. | ||
5043 | * | ||
5044 | * So now we work out what the grid size ought to be. | ||
5045 | */ | ||
5046 | bestsize = 0.0; | ||
5047 | pbest = 0; | ||
5048 | /* Minimum */ | ||
5049 | for (pw = 3; pw < max(npencil,4); pw++) { | ||
5050 | float fw, fh, fs; | ||
5051 | |||
5052 | ph = (npencil + pw - 1) / pw; | ||
5053 | ph = max(ph, minph); | ||
5054 | fw = (pr - pl) / (float)pw; | ||
5055 | fh = (pb - pt) / (float)ph; | ||
5056 | fs = min(fw, fh); | ||
5057 | if (fs > bestsize) { | ||
5058 | bestsize = fs; | ||
5059 | pbest = pw; | ||
5060 | } | ||
5061 | } | ||
5062 | assert(pbest > 0); | ||
5063 | pw = pbest; | ||
5064 | ph = (npencil + pw - 1) / pw; | ||
5065 | ph = max(ph, minph); | ||
5066 | |||
5067 | /* | ||
5068 | * Now we've got our grid dimensions, work out the pixel | ||
5069 | * size of a grid element, and round it to the nearest | ||
5070 | * pixel. (We don't want rounding errors to make the | ||
5071 | * grid look uneven at low pixel sizes.) | ||
5072 | */ | ||
5073 | fontsize = min((pr - pl) / pw, (pb - pt) / ph); | ||
5074 | |||
5075 | /* | ||
5076 | * Centre the resulting figure in the square. | ||
5077 | */ | ||
5078 | pl = tx + (TILE_SIZE - fontsize * pw) / 2; | ||
5079 | pt = ty + (TILE_SIZE - fontsize * ph) / 2; | ||
5080 | |||
5081 | /* | ||
5082 | * And move it down a bit if it's collided with the | ||
5083 | * Killer cage number. | ||
5084 | */ | ||
5085 | if (state->killer && state->kgrid[y*cr+x] != 0) { | ||
5086 | pt = max(pt, ty + GRIDEXTRA * 3 + TILE_SIZE/4); | ||
5087 | } | ||
5088 | |||
5089 | /* | ||
5090 | * Now actually draw the pencil marks. | ||
5091 | */ | ||
5092 | for (i = j = 0; i < cr; i++) | ||
5093 | if (state->pencil[(y*cr+x)*cr+i]) { | ||
5094 | int dx = j % pw, dy = j / pw; | ||
5095 | |||
5096 | str[1] = '\0'; | ||
5097 | str[0] = i + '1'; | ||
5098 | if (str[0] > '9') | ||
5099 | str[0] += 'a' - ('9'+1); | ||
5100 | draw_text(dr, pl + fontsize * (2*dx+1) / 2, | ||
5101 | pt + fontsize * (2*dy+1) / 2, | ||
5102 | FONT_VARIABLE, fontsize, | ||
5103 | ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str); | ||
5104 | j++; | ||
5105 | } | ||
5106 | } | ||
5107 | } | ||
5108 | |||
5109 | unclip(dr); | ||
5110 | |||
5111 | draw_update(dr, cx, cy, cw, ch); | ||
5112 | |||
5113 | ds->grid[y*cr+x] = state->grid[y*cr+x]; | ||
5114 | memcpy(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr); | ||
5115 | ds->hl[y*cr+x] = hl; | ||
5116 | } | ||
5117 | |||
5118 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
5119 | const game_state *oldstate, const game_state *state, | ||
5120 | int dir, const game_ui *ui, | ||
5121 | float animtime, float flashtime) | ||
5122 | { | ||
5123 | int cr = state->cr; | ||
5124 | int x, y; | ||
5125 | |||
5126 | if (!ds->started) { | ||
5127 | /* | ||
5128 | * The initial contents of the window are not guaranteed | ||
5129 | * and can vary with front ends. To be on the safe side, | ||
5130 | * all games should start by drawing a big | ||
5131 | * background-colour rectangle covering the whole window. | ||
5132 | */ | ||
5133 | draw_rect(dr, 0, 0, SIZE(cr), SIZE(cr), COL_BACKGROUND); | ||
5134 | |||
5135 | /* | ||
5136 | * Draw the grid. We draw it as a big thick rectangle of | ||
5137 | * COL_GRID initially; individual calls to draw_number() | ||
5138 | * will poke the right-shaped holes in it. | ||
5139 | */ | ||
5140 | draw_rect(dr, BORDER-GRIDEXTRA, BORDER-GRIDEXTRA, | ||
5141 | cr*TILE_SIZE+1+2*GRIDEXTRA, cr*TILE_SIZE+1+2*GRIDEXTRA, | ||
5142 | COL_GRID); | ||
5143 | } | ||
5144 | |||
5145 | /* | ||
5146 | * This array is used to keep track of rows, columns and boxes | ||
5147 | * which contain a number more than once. | ||
5148 | */ | ||
5149 | for (x = 0; x < cr * ds->nregions; x++) | ||
5150 | ds->entered_items[x] = 0; | ||
5151 | for (x = 0; x < cr; x++) | ||
5152 | for (y = 0; y < cr; y++) { | ||
5153 | digit d = state->grid[y*cr+x]; | ||
5154 | if (d) { | ||
5155 | int box, kbox; | ||
5156 | |||
5157 | /* Rows */ | ||
5158 | ds->entered_items[x*cr+d-1]++; | ||
5159 | |||
5160 | /* Columns */ | ||
5161 | ds->entered_items[(y+cr)*cr+d-1]++; | ||
5162 | |||
5163 | /* Blocks */ | ||
5164 | box = state->blocks->whichblock[y*cr+x]; | ||
5165 | ds->entered_items[(box+2*cr)*cr+d-1]++; | ||
5166 | |||
5167 | /* Diagonals */ | ||
5168 | if (ds->xtype) { | ||
5169 | if (ondiag0(y*cr+x)) | ||
5170 | ds->entered_items[(3*cr)*cr+d-1]++; | ||
5171 | if (ondiag1(y*cr+x)) | ||
5172 | ds->entered_items[(3*cr+1)*cr+d-1]++; | ||
5173 | } | ||
5174 | |||
5175 | /* Killer cages */ | ||
5176 | if (state->kblocks) { | ||
5177 | kbox = state->kblocks->whichblock[y*cr+x]; | ||
5178 | ds->entered_items[(kbox+3*cr+2)*cr+d-1]++; | ||
5179 | } | ||
5180 | } | ||
5181 | } | ||
5182 | |||
5183 | /* | ||
5184 | * Draw any numbers which need redrawing. | ||
5185 | */ | ||
5186 | for (x = 0; x < cr; x++) { | ||
5187 | for (y = 0; y < cr; y++) { | ||
5188 | int highlight = 0; | ||
5189 | digit d = state->grid[y*cr+x]; | ||
5190 | |||
5191 | if (flashtime > 0 && | ||
5192 | (flashtime <= FLASH_TIME/3 || | ||
5193 | flashtime >= FLASH_TIME*2/3)) | ||
5194 | highlight = 1; | ||
5195 | |||
5196 | /* Highlight active input areas. */ | ||
5197 | if (x == ui->hx && y == ui->hy && ui->hshow) | ||
5198 | highlight = ui->hpencil ? 2 : 1; | ||
5199 | |||
5200 | /* Mark obvious errors (ie, numbers which occur more than once | ||
5201 | * in a single row, column, or box). */ | ||
5202 | if (d && (ds->entered_items[x*cr+d-1] > 1 || | ||
5203 | ds->entered_items[(y+cr)*cr+d-1] > 1 || | ||
5204 | ds->entered_items[(state->blocks->whichblock[y*cr+x] | ||
5205 | +2*cr)*cr+d-1] > 1 || | ||
5206 | (ds->xtype && ((ondiag0(y*cr+x) && | ||
5207 | ds->entered_items[(3*cr)*cr+d-1] > 1) || | ||
5208 | (ondiag1(y*cr+x) && | ||
5209 | ds->entered_items[(3*cr+1)*cr+d-1]>1)))|| | ||
5210 | (state->kblocks && | ||
5211 | ds->entered_items[(state->kblocks->whichblock[y*cr+x] | ||
5212 | +3*cr+2)*cr+d-1] > 1))) | ||
5213 | highlight |= 16; | ||
5214 | |||
5215 | if (d && state->kblocks) { | ||
5216 | if (check_killer_cage_sum( | ||
5217 | state->kblocks, state->kgrid, state->grid, | ||
5218 | state->kblocks->whichblock[y*cr+x]) == 0) | ||
5219 | highlight |= 32; | ||
5220 | } | ||
5221 | |||
5222 | draw_number(dr, ds, state, x, y, highlight); | ||
5223 | } | ||
5224 | } | ||
5225 | |||
5226 | /* | ||
5227 | * Update the _entire_ grid if necessary. | ||
5228 | */ | ||
5229 | if (!ds->started) { | ||
5230 | draw_update(dr, 0, 0, SIZE(cr), SIZE(cr)); | ||
5231 | ds->started = TRUE; | ||
5232 | } | ||
5233 | } | ||
5234 | |||
5235 | static float game_anim_length(const game_state *oldstate, | ||
5236 | const game_state *newstate, int dir, game_ui *ui) | ||
5237 | { | ||
5238 | return 0.0F; | ||
5239 | } | ||
5240 | |||
5241 | static float game_flash_length(const game_state *oldstate, | ||
5242 | const game_state *newstate, int dir, game_ui *ui) | ||
5243 | { | ||
5244 | if (!oldstate->completed && newstate->completed && | ||
5245 | !oldstate->cheated && !newstate->cheated) | ||
5246 | return FLASH_TIME; | ||
5247 | return 0.0F; | ||
5248 | } | ||
5249 | |||
5250 | static int game_status(const game_state *state) | ||
5251 | { | ||
5252 | return state->completed ? +1 : 0; | ||
5253 | } | ||
5254 | |||
5255 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
5256 | { | ||
5257 | if (state->completed) | ||
5258 | return FALSE; | ||
5259 | return TRUE; | ||
5260 | } | ||
5261 | |||
5262 | static void game_print_size(const game_params *params, float *x, float *y) | ||
5263 | { | ||
5264 | int pw, ph; | ||
5265 | |||
5266 | /* | ||
5267 | * I'll use 9mm squares by default. They should be quite big | ||
5268 | * for this game, because players will want to jot down no end | ||
5269 | * of pencil marks in the squares. | ||
5270 | */ | ||
5271 | game_compute_size(params, 900, &pw, &ph); | ||
5272 | *x = pw / 100.0F; | ||
5273 | *y = ph / 100.0F; | ||
5274 | } | ||
5275 | |||
5276 | /* | ||
5277 | * Subfunction to draw the thick lines between cells. In order to do | ||
5278 | * this using the line-drawing rather than rectangle-drawing API (so | ||
5279 | * as to get line thicknesses to scale correctly) and yet have | ||
5280 | * correctly mitred joins between lines, we must do this by tracing | ||
5281 | * the boundary of each sub-block and drawing it in one go as a | ||
5282 | * single polygon. | ||
5283 | * | ||
5284 | * This subfunction is also reused with thinner dotted lines to | ||
5285 | * outline the Killer cages, this time offsetting the outline toward | ||
5286 | * the interior of the affected squares. | ||
5287 | */ | ||
5288 | static void outline_block_structure(drawing *dr, game_drawstate *ds, | ||
5289 | const game_state *state, | ||
5290 | struct block_structure *blocks, | ||
5291 | int ink, int inset) | ||
5292 | { | ||
5293 | int cr = state->cr; | ||
5294 | int *coords; | ||
5295 | int bi, i, n; | ||
5296 | int x, y, dx, dy, sx, sy, sdx, sdy; | ||
5297 | |||
5298 | /* | ||
5299 | * Maximum perimeter of a k-omino is 2k+2. (Proof: start | ||
5300 | * with k unconnected squares, with total perimeter 4k. | ||
5301 | * Now repeatedly join two disconnected components | ||
5302 | * together into a larger one; every time you do so you | ||
5303 | * remove at least two unit edges, and you require k-1 of | ||
5304 | * these operations to create a single connected piece, so | ||
5305 | * you must have at most 4k-2(k-1) = 2k+2 unit edges left | ||
5306 | * afterwards.) | ||
5307 | */ | ||
5308 | coords = snewn(4*cr+4, int); /* 2k+2 points, 2 coords per point */ | ||
5309 | |||
5310 | /* | ||
5311 | * Iterate over all the blocks. | ||
5312 | */ | ||
5313 | for (bi = 0; bi < blocks->nr_blocks; bi++) { | ||
5314 | if (blocks->nr_squares[bi] == 0) | ||
5315 | continue; | ||
5316 | |||
5317 | /* | ||
5318 | * For each block, find a starting square within it | ||
5319 | * which has a boundary at the left. | ||
5320 | */ | ||
5321 | for (i = 0; i < cr; i++) { | ||
5322 | int j = blocks->blocks[bi][i]; | ||
5323 | if (j % cr == 0 || blocks->whichblock[j-1] != bi) | ||
5324 | break; | ||
5325 | } | ||
5326 | assert(i < cr); /* every block must have _some_ leftmost square */ | ||
5327 | x = blocks->blocks[bi][i] % cr; | ||
5328 | y = blocks->blocks[bi][i] / cr; | ||
5329 | dx = -1; | ||
5330 | dy = 0; | ||
5331 | |||
5332 | /* | ||
5333 | * Now begin tracing round the perimeter. At all | ||
5334 | * times, (x,y) describes some square within the | ||
5335 | * block, and (x+dx,y+dy) is some adjacent square | ||
5336 | * outside it; so the edge between those two squares | ||
5337 | * is always an edge of the block. | ||
5338 | */ | ||
5339 | sx = x, sy = y, sdx = dx, sdy = dy; /* save starting position */ | ||
5340 | n = 0; | ||
5341 | do { | ||
5342 | int cx, cy, tx, ty, nin; | ||
5343 | |||
5344 | /* | ||
5345 | * Advance to the next edge, by looking at the two | ||
5346 | * squares beyond it. If they're both outside the block, | ||
5347 | * we turn right (by leaving x,y the same and rotating | ||
5348 | * dx,dy clockwise); if they're both inside, we turn | ||
5349 | * left (by rotating dx,dy anticlockwise and contriving | ||
5350 | * to leave x+dx,y+dy unchanged); if one of each, we go | ||
5351 | * straight on (and may enforce by assertion that | ||
5352 | * they're one of each the _right_ way round). | ||
5353 | */ | ||
5354 | nin = 0; | ||
5355 | tx = x - dy + dx; | ||
5356 | ty = y + dx + dy; | ||
5357 | nin += (tx >= 0 && tx < cr && ty >= 0 && ty < cr && | ||
5358 | blocks->whichblock[ty*cr+tx] == bi); | ||
5359 | tx = x - dy; | ||
5360 | ty = y + dx; | ||
5361 | nin += (tx >= 0 && tx < cr && ty >= 0 && ty < cr && | ||
5362 | blocks->whichblock[ty*cr+tx] == bi); | ||
5363 | if (nin == 0) { | ||
5364 | /* | ||
5365 | * Turn right. | ||
5366 | */ | ||
5367 | int tmp; | ||
5368 | tmp = dx; | ||
5369 | dx = -dy; | ||
5370 | dy = tmp; | ||
5371 | } else if (nin == 2) { | ||
5372 | /* | ||
5373 | * Turn left. | ||
5374 | */ | ||
5375 | int tmp; | ||
5376 | |||
5377 | x += dx; | ||
5378 | y += dy; | ||
5379 | |||
5380 | tmp = dx; | ||
5381 | dx = dy; | ||
5382 | dy = -tmp; | ||
5383 | |||
5384 | x -= dx; | ||
5385 | y -= dy; | ||
5386 | } else { | ||
5387 | /* | ||
5388 | * Go straight on. | ||
5389 | */ | ||
5390 | x -= dy; | ||
5391 | y += dx; | ||
5392 | } | ||
5393 | |||
5394 | /* | ||
5395 | * Now enforce by assertion that we ended up | ||
5396 | * somewhere sensible. | ||
5397 | */ | ||
5398 | assert(x >= 0 && x < cr && y >= 0 && y < cr && | ||
5399 | blocks->whichblock[y*cr+x] == bi); | ||
5400 | assert(x+dx < 0 || x+dx >= cr || y+dy < 0 || y+dy >= cr || | ||
5401 | blocks->whichblock[(y+dy)*cr+(x+dx)] != bi); | ||
5402 | |||
5403 | /* | ||
5404 | * Record the point we just went past at one end of the | ||
5405 | * edge. To do this, we translate (x,y) down and right | ||
5406 | * by half a unit (so they're describing a point in the | ||
5407 | * _centre_ of the square) and then translate back again | ||
5408 | * in a manner rotated by dy and dx. | ||
5409 | */ | ||
5410 | assert(n < 2*cr+2); | ||
5411 | cx = ((2*x+1) + dy + dx) / 2; | ||
5412 | cy = ((2*y+1) - dx + dy) / 2; | ||
5413 | coords[2*n+0] = BORDER + cx * TILE_SIZE; | ||
5414 | coords[2*n+1] = BORDER + cy * TILE_SIZE; | ||
5415 | coords[2*n+0] -= dx * inset; | ||
5416 | coords[2*n+1] -= dy * inset; | ||
5417 | if (nin == 0) { | ||
5418 | /* | ||
5419 | * We turned right, so inset this corner back along | ||
5420 | * the edge towards the centre of the square. | ||
5421 | */ | ||
5422 | coords[2*n+0] -= dy * inset; | ||
5423 | coords[2*n+1] += dx * inset; | ||
5424 | } else if (nin == 2) { | ||
5425 | /* | ||
5426 | * We turned left, so inset this corner further | ||
5427 | * _out_ along the edge into the next square. | ||
5428 | */ | ||
5429 | coords[2*n+0] += dy * inset; | ||
5430 | coords[2*n+1] -= dx * inset; | ||
5431 | } | ||
5432 | n++; | ||
5433 | |||
5434 | } while (x != sx || y != sy || dx != sdx || dy != sdy); | ||
5435 | |||
5436 | /* | ||
5437 | * That's our polygon; now draw it. | ||
5438 | */ | ||
5439 | draw_polygon(dr, coords, n, -1, ink); | ||
5440 | } | ||
5441 | |||
5442 | sfree(coords); | ||
5443 | } | ||
5444 | |||
5445 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
5446 | { | ||
5447 | int cr = state->cr; | ||
5448 | int ink = print_mono_colour(dr, 0); | ||
5449 | int x, y; | ||
5450 | |||
5451 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
5452 | game_drawstate ads, *ds = &ads; | ||
5453 | game_set_size(dr, ds, NULL, tilesize); | ||
5454 | |||
5455 | /* | ||
5456 | * Border. | ||
5457 | */ | ||
5458 | print_line_width(dr, 3 * TILE_SIZE / 40); | ||
5459 | draw_rect_outline(dr, BORDER, BORDER, cr*TILE_SIZE, cr*TILE_SIZE, ink); | ||
5460 | |||
5461 | /* | ||
5462 | * Highlight X-diagonal squares. | ||
5463 | */ | ||
5464 | if (state->xtype) { | ||
5465 | int i; | ||
5466 | int xhighlight = print_grey_colour(dr, 0.90F); | ||
5467 | |||
5468 | for (i = 0; i < cr; i++) | ||
5469 | draw_rect(dr, BORDER + i*TILE_SIZE, BORDER + i*TILE_SIZE, | ||
5470 | TILE_SIZE, TILE_SIZE, xhighlight); | ||
5471 | for (i = 0; i < cr; i++) | ||
5472 | if (i*2 != cr-1) /* avoid redoing centre square, just for fun */ | ||
5473 | draw_rect(dr, BORDER + i*TILE_SIZE, | ||
5474 | BORDER + (cr-1-i)*TILE_SIZE, | ||
5475 | TILE_SIZE, TILE_SIZE, xhighlight); | ||
5476 | } | ||
5477 | |||
5478 | /* | ||
5479 | * Main grid. | ||
5480 | */ | ||
5481 | for (x = 1; x < cr; x++) { | ||
5482 | print_line_width(dr, TILE_SIZE / 40); | ||
5483 | draw_line(dr, BORDER+x*TILE_SIZE, BORDER, | ||
5484 | BORDER+x*TILE_SIZE, BORDER+cr*TILE_SIZE, ink); | ||
5485 | } | ||
5486 | for (y = 1; y < cr; y++) { | ||
5487 | print_line_width(dr, TILE_SIZE / 40); | ||
5488 | draw_line(dr, BORDER, BORDER+y*TILE_SIZE, | ||
5489 | BORDER+cr*TILE_SIZE, BORDER+y*TILE_SIZE, ink); | ||
5490 | } | ||
5491 | |||
5492 | /* | ||
5493 | * Thick lines between cells. | ||
5494 | */ | ||
5495 | print_line_width(dr, 3 * TILE_SIZE / 40); | ||
5496 | outline_block_structure(dr, ds, state, state->blocks, ink, 0); | ||
5497 | |||
5498 | /* | ||
5499 | * Killer cages and their totals. | ||
5500 | */ | ||
5501 | if (state->kblocks) { | ||
5502 | print_line_width(dr, TILE_SIZE / 40); | ||
5503 | print_line_dotted(dr, TRUE); | ||
5504 | outline_block_structure(dr, ds, state, state->kblocks, ink, | ||
5505 | 5 * TILE_SIZE / 40); | ||
5506 | print_line_dotted(dr, FALSE); | ||
5507 | for (y = 0; y < cr; y++) | ||
5508 | for (x = 0; x < cr; x++) | ||
5509 | if (state->kgrid[y*cr+x]) { | ||
5510 | char str[20]; | ||
5511 | sprintf(str, "%d", state->kgrid[y*cr+x]); | ||
5512 | draw_text(dr, | ||
5513 | BORDER+x*TILE_SIZE + 7*TILE_SIZE/40, | ||
5514 | BORDER+y*TILE_SIZE + 16*TILE_SIZE/40, | ||
5515 | FONT_VARIABLE, TILE_SIZE/4, | ||
5516 | ALIGN_VNORMAL | ALIGN_HLEFT, | ||
5517 | ink, str); | ||
5518 | } | ||
5519 | } | ||
5520 | |||
5521 | /* | ||
5522 | * Standard (non-Killer) clue numbers. | ||
5523 | */ | ||
5524 | for (y = 0; y < cr; y++) | ||
5525 | for (x = 0; x < cr; x++) | ||
5526 | if (state->grid[y*cr+x]) { | ||
5527 | char str[2]; | ||
5528 | str[1] = '\0'; | ||
5529 | str[0] = state->grid[y*cr+x] + '0'; | ||
5530 | if (str[0] > '9') | ||
5531 | str[0] += 'a' - ('9'+1); | ||
5532 | draw_text(dr, BORDER + x*TILE_SIZE + TILE_SIZE/2, | ||
5533 | BORDER + y*TILE_SIZE + TILE_SIZE/2, | ||
5534 | FONT_VARIABLE, TILE_SIZE/2, | ||
5535 | ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); | ||
5536 | } | ||
5537 | } | ||
5538 | |||
5539 | #ifdef COMBINED | ||
5540 | #define thegame solo | ||
5541 | #endif | ||
5542 | |||
5543 | const struct game thegame = { | ||
5544 | "Solo", "games.solo", "solo", | ||
5545 | default_params, | ||
5546 | game_fetch_preset, | ||
5547 | decode_params, | ||
5548 | encode_params, | ||
5549 | free_params, | ||
5550 | dup_params, | ||
5551 | TRUE, game_configure, custom_params, | ||
5552 | validate_params, | ||
5553 | new_game_desc, | ||
5554 | validate_desc, | ||
5555 | new_game, | ||
5556 | dup_game, | ||
5557 | free_game, | ||
5558 | TRUE, solve_game, | ||
5559 | TRUE, game_can_format_as_text_now, game_text_format, | ||
5560 | new_ui, | ||
5561 | free_ui, | ||
5562 | encode_ui, | ||
5563 | decode_ui, | ||
5564 | game_changed_state, | ||
5565 | interpret_move, | ||
5566 | execute_move, | ||
5567 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
5568 | game_colours, | ||
5569 | game_new_drawstate, | ||
5570 | game_free_drawstate, | ||
5571 | game_redraw, | ||
5572 | game_anim_length, | ||
5573 | game_flash_length, | ||
5574 | game_status, | ||
5575 | TRUE, FALSE, game_print_size, game_print, | ||
5576 | FALSE, /* wants_statusbar */ | ||
5577 | FALSE, game_timing_state, | ||
5578 | REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */ | ||
5579 | }; | ||
5580 | |||
5581 | #ifdef STANDALONE_SOLVER | ||
5582 | |||
5583 | int main(int argc, char **argv) | ||
5584 | { | ||
5585 | game_params *p; | ||
5586 | game_state *s; | ||
5587 | char *id = NULL, *desc, *err; | ||
5588 | int grade = FALSE; | ||
5589 | struct difficulty dlev; | ||
5590 | |||
5591 | while (--argc > 0) { | ||
5592 | char *p = *++argv; | ||
5593 | if (!strcmp(p, "-v")) { | ||
5594 | solver_show_working = TRUE; | ||
5595 | } else if (!strcmp(p, "-g")) { | ||
5596 | grade = TRUE; | ||
5597 | } else if (*p == '-') { | ||
5598 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
5599 | return 1; | ||
5600 | } else { | ||
5601 | id = p; | ||
5602 | } | ||
5603 | } | ||
5604 | |||
5605 | if (!id) { | ||
5606 | fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]); | ||
5607 | return 1; | ||
5608 | } | ||
5609 | |||
5610 | desc = strchr(id, ':'); | ||
5611 | if (!desc) { | ||
5612 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
5613 | return 1; | ||
5614 | } | ||
5615 | *desc++ = '\0'; | ||
5616 | |||
5617 | p = default_params(); | ||
5618 | decode_params(p, id); | ||
5619 | err = validate_desc(p, desc); | ||
5620 | if (err) { | ||
5621 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
5622 | return 1; | ||
5623 | } | ||
5624 | s = new_game(NULL, p, desc); | ||
5625 | |||
5626 | dlev.maxdiff = DIFF_RECURSIVE; | ||
5627 | dlev.maxkdiff = DIFF_KINTERSECT; | ||
5628 | solver(s->cr, s->blocks, s->kblocks, s->xtype, s->grid, s->kgrid, &dlev); | ||
5629 | if (grade) { | ||
5630 | printf("Difficulty rating: %s\n", | ||
5631 | dlev.diff==DIFF_BLOCK ? "Trivial (blockwise positional elimination only)": | ||
5632 | dlev.diff==DIFF_SIMPLE ? "Basic (row/column/number elimination required)": | ||
5633 | dlev.diff==DIFF_INTERSECT ? "Intermediate (intersectional analysis required)": | ||
5634 | dlev.diff==DIFF_SET ? "Advanced (set elimination required)": | ||
5635 | dlev.diff==DIFF_EXTREME ? "Extreme (complex non-recursive techniques required)": | ||
5636 | dlev.diff==DIFF_RECURSIVE ? "Unreasonable (guesswork and backtracking required)": | ||
5637 | dlev.diff==DIFF_AMBIGUOUS ? "Ambiguous (multiple solutions exist)": | ||
5638 | dlev.diff==DIFF_IMPOSSIBLE ? "Impossible (no solution exists)": | ||
5639 | "INTERNAL ERROR: unrecognised difficulty code"); | ||
5640 | if (p->killer) | ||
5641 | printf("Killer difficulty: %s\n", | ||
5642 | dlev.kdiff==DIFF_KSINGLE ? "Trivial (single square cages only)": | ||
5643 | dlev.kdiff==DIFF_KMINMAX ? "Simple (maximum sum analysis required)": | ||
5644 | dlev.kdiff==DIFF_KSUMS ? "Intermediate (sum possibilities)": | ||
5645 | dlev.kdiff==DIFF_KINTERSECT ? "Advanced (sum region intersections)": | ||
5646 | "INTERNAL ERROR: unrecognised difficulty code"); | ||
5647 | } else { | ||
5648 | printf("%s\n", grid_text_format(s->cr, s->blocks, s->xtype, s->grid)); | ||
5649 | } | ||
5650 | |||
5651 | return 0; | ||
5652 | } | ||
5653 | |||
5654 | #endif | ||
5655 | |||
5656 | /* vim: set shiftwidth=4 tabstop=8: */ | ||