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