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 * dominosa.c: Domino jigsaw puzzle. Aim to place one of every
3 * possible domino within a rectangle in such a way that the number
4 * on each square matches the provided clue.
5 */
6
7/*
8 * Further possible deduction types in the solver:
9 *
10 * * possibly an advanced form of deduce_parity via 2-connectedness.
11 * We currently deal with areas of the graph with exactly one way
12 * in and out; but if you have an area with exactly _two_ routes in
13 * and out of it, then you can at least decide on the _relative_
14 * parity of the two (either 'these two edges both bisect dominoes
15 * or neither do', or 'exactly one of these edges bisects a
16 * domino'). And occasionally that can be enough to let you rule
17 * out one of the two remaining choices.
18 * + For example, if both those edges bisect a domino, then those
19 * two dominoes would also be both the same.
20 * + Or perhaps between them they rule out all possibilities for
21 * some other square.
22 * + Or perhaps they themselves would be duplicates!
23 * + Or perhaps, on purely geometric grounds, they would box in a
24 * square to the point where it ended up having to be an
25 * isolated singleton.
26 * + The tricky part of this is how you do the graph theory.
27 * Perhaps a modified form of Tarjan's bridge-finding algorithm
28 * would work, but I haven't thought through the details.
29 *
30 * * possibly an advanced version of set analysis which doesn't have
31 * to start from squares all having the same number? For example,
32 * if you have three mutually non-adjacent squares labelled 1,2,3
33 * such that the numbers adjacent to each are precisely the other
34 * two, then set analysis can work just fine in principle, and
35 * tells you that those three squares must overlap the three
36 * dominoes 1-2, 2-3 and 1-3 in some order, so you can rule out any
37 * placements of those elsewhere.
38 * + the difficulty with this is how you avoid it going painfully
39 * exponential-time. You can't iterate over all the subsets, so
40 * you'd need some kind of more sophisticated directed search.
41 * + and the adjacency allowance has to be similarly accounted
42 * for, which could get tricky to keep track of.
43 */
44
45#include <stdio.h>
46#include <stdlib.h>
47#include <string.h>
48#include <assert.h>
49#include <ctype.h>
50#include <limits.h>
51#ifdef NO_TGMATH_H
52# include <math.h>
53#else
54# include <tgmath.h>
55#endif
56
57#include "puzzles.h"
58
59/* nth triangular number */
60#define TRI(n) ( (n) * ((n) + 1) / 2 )
61/* number of dominoes for value n */
62#define DCOUNT(n) TRI((n)+1)
63/* map a pair of numbers to a unique domino index from 0 upwards. */
64#define DINDEX(n1,n2) ( TRI(max(n1,n2)) + min(n1,n2) )
65
66#define FLASH_TIME 0.13F
67
68/*
69 * Difficulty levels. I do some macro ickery here to ensure that my
70 * enum and the various forms of my name list always match up.
71 */
72#define DIFFLIST(X) \
73 X(TRIVIAL,Trivial,t) \
74 X(BASIC,Basic,b) \
75 X(HARD,Hard,h) \
76 X(EXTREME,Extreme,e) \
77 X(AMBIGUOUS,Ambiguous,a) \
78 /* end of list */
79#define ENUM(upper,title,lower) DIFF_ ## upper,
80#define TITLE(upper,title,lower) #title,
81#define ENCODE(upper,title,lower) #lower
82#define CONFIG(upper,title,lower) ":" #title
83enum { DIFFLIST(ENUM) DIFFCOUNT };
84static char const *const dominosa_diffnames[] = { DIFFLIST(TITLE) };
85static char const dominosa_diffchars[] = DIFFLIST(ENCODE);
86#define DIFFCONFIG DIFFLIST(CONFIG)
87
88enum {
89 COL_BACKGROUND,
90 COL_TEXT,
91 COL_DOMINO,
92 COL_DOMINOCLASH,
93 COL_DOMINOTEXT,
94 COL_EDGE,
95 COL_HIGHLIGHT_1,
96 COL_HIGHLIGHT_2,
97 NCOLOURS
98};
99
100struct game_params {
101 int n;
102 int diff;
103};
104
105struct game_numbers {
106 int refcount;
107 int *numbers; /* h x w */
108};
109
110#define EDGE_L 0x100
111#define EDGE_R 0x200
112#define EDGE_T 0x400
113#define EDGE_B 0x800
114
115struct game_state {
116 game_params params;
117 int w, h;
118 struct game_numbers *numbers;
119 int *grid;
120 unsigned short *edges; /* h x w */
121 bool completed, cheated;
122};
123
124static game_params *default_params(void)
125{
126 game_params *ret = snew(game_params);
127
128 ret->n = 6;
129 ret->diff = DIFF_BASIC;
130
131 return ret;
132}
133
134static const struct game_params dominosa_presets[] = {
135 { 3, DIFF_TRIVIAL },
136 { 4, DIFF_TRIVIAL },
137 { 5, DIFF_TRIVIAL },
138 { 6, DIFF_TRIVIAL },
139 { 4, DIFF_BASIC },
140 { 5, DIFF_BASIC },
141 { 6, DIFF_BASIC },
142 { 7, DIFF_BASIC },
143 { 8, DIFF_BASIC },
144 { 9, DIFF_BASIC },
145 { 6, DIFF_HARD },
146 { 6, DIFF_EXTREME },
147};
148
149static bool game_fetch_preset(int i, char **name, game_params **params_out)
150{
151 game_params *params;
152 char buf[80];
153
154 if (i < 0 || i >= lenof(dominosa_presets))
155 return false;
156
157 params = snew(game_params);
158 *params = dominosa_presets[i]; /* structure copy */
159
160 sprintf(buf, "Order %d, %s", params->n, dominosa_diffnames[params->diff]);
161
162 *name = dupstr(buf);
163 *params_out = params;
164 return true;
165}
166
167static void free_params(game_params *params)
168{
169 sfree(params);
170}
171
172static game_params *dup_params(const game_params *params)
173{
174 game_params *ret = snew(game_params);
175 *ret = *params; /* structure copy */
176 return ret;
177}
178
179static void decode_params(game_params *params, char const *string)
180{
181 const char *p = string;
182
183 params->n = atoi(p);
184 while (*p && isdigit((unsigned char)*p)) p++;
185
186 while (*p) {
187 char c = *p++;
188 if (c == 'a') {
189 /* Legacy encoding from before the difficulty system */
190 params->diff = DIFF_AMBIGUOUS;
191 } else if (c == 'd') {
192 int i;
193 params->diff = DIFFCOUNT+1; /* ...which is invalid */
194 if (*p) {
195 for (i = 0; i < DIFFCOUNT; i++) {
196 if (*p == dominosa_diffchars[i])
197 params->diff = i;
198 }
199 p++;
200 }
201 }
202 }
203}
204
205static char *encode_params(const game_params *params, bool full)
206{
207 char buf[80];
208 int len = sprintf(buf, "%d", params->n);
209 if (full)
210 len += sprintf(buf + len, "d%c", dominosa_diffchars[params->diff]);
211 return dupstr(buf);
212}
213
214static config_item *game_configure(const game_params *params)
215{
216 config_item *ret;
217 char buf[80];
218
219 ret = snewn(3, config_item);
220
221 ret[0].name = "Maximum number on dominoes";
222 ret[0].type = C_STRING;
223 sprintf(buf, "%d", params->n);
224 ret[0].u.string.sval = dupstr(buf);
225
226 ret[1].name = "Difficulty";
227 ret[1].type = C_CHOICES;
228 ret[1].u.choices.choicenames = DIFFCONFIG;
229 ret[1].u.choices.selected = params->diff;
230
231 ret[2].name = NULL;
232 ret[2].type = C_END;
233
234 return ret;
235}
236
237static game_params *custom_params(const config_item *cfg)
238{
239 game_params *ret = snew(game_params);
240
241 ret->n = atoi(cfg[0].u.string.sval);
242 ret->diff = cfg[1].u.choices.selected;
243
244 return ret;
245}
246
247static const char *validate_params(const game_params *params, bool full)
248{
249 if (params->n < 1)
250 return "Maximum face number must be at least one";
251 if (params->n > INT_MAX - 2 ||
252 params->n + 2 > INT_MAX / (params->n + 1))
253 return "Maximum face number must not be unreasonably large";
254
255 if (params->diff >= DIFFCOUNT)
256 return "Unknown difficulty rating";
257 return NULL;
258}
259
260/* ----------------------------------------------------------------------
261 * Solver.
262 */
263
264#ifdef STANDALONE_SOLVER
265#define SOLVER_DIAGNOSTICS
266static bool solver_diagnostics = false;
267#elif defined SOLVER_DIAGNOSTICS
268static const bool solver_diagnostics = true;
269#endif
270
271struct solver_domino;
272struct solver_placement;
273
274/*
275 * Information about a particular domino.
276 */
277struct solver_domino {
278 /* The numbers on the domino, and its index in the dominoes array. */
279 int lo, hi, index;
280
281 /* List of placements not yet ruled out for this domino. */
282 int nplacements;
283 struct solver_placement **placements;
284
285#ifdef SOLVER_DIAGNOSTICS
286 /* A textual name we can easily reuse in solver diagnostics. */
287 char *name;
288#endif
289};
290
291/*
292 * Information about a particular 'placement' (i.e. specific location
293 * that a domino might go in).
294 */
295struct solver_placement {
296 /* The index of this placement in sc->placements. */
297 int index;
298
299 /* The two squares that make up this placement. */
300 struct solver_square *squares[2];
301
302 /* The domino that has to go in this position, if any. */
303 struct solver_domino *domino;
304
305 /* The index of this placement in each square's placements array,
306 * and in that of the domino. */
307 int spi[2], dpi;
308
309 /* Whether this is still considered a possible placement. */
310 bool active;
311
312 /* Other domino placements that overlap with this one. (Maximum 6:
313 * three overlapping each square of the placement.) */
314 int noverlaps;
315 struct solver_placement *overlaps[6];
316
317#ifdef SOLVER_DIAGNOSTICS
318 /* A textual name we can easily reuse in solver diagnostics. */
319 char *name;
320#endif
321};
322
323/*
324 * Information about a particular solver square.
325 */
326struct solver_square {
327 /* The coordinates of the square, and its index in a normal grid array. */
328 int x, y, index;
329
330 /* List of domino placements not yet ruled out for this square. */
331 int nplacements;
332 struct solver_placement *placements[4];
333
334 /* The number in the square. */
335 int number;
336
337#ifdef SOLVER_DIAGNOSTICS
338 /* A textual name we can easily reuse in solver diagnostics. */
339 char *name;
340#endif
341};
342
343struct solver_scratch {
344 int n, dc, pc, w, h, wh;
345 int max_diff_used;
346 struct solver_domino *dominoes;
347 struct solver_placement *placements;
348 struct solver_square *squares;
349 struct solver_placement **domino_placement_lists;
350 struct solver_square **squares_by_number;
351 struct findloopstate *fls;
352 bool squares_by_number_initialised;
353 int *wh_scratch, *pc_scratch, *pc_scratch2, *dc_scratch;
354 DSF *dsf_scratch;
355};
356
357static struct solver_scratch *solver_make_scratch(int n)
358{
359 int dc = DCOUNT(n), w = n+2, h = n+1, wh = w*h;
360 int pc = (w-1)*h + w*(h-1);
361 struct solver_scratch *sc = snew(struct solver_scratch);
362 int hi, lo, di, x, y, pi, si;
363
364 sc->n = n;
365 sc->dc = dc;
366 sc->pc = pc;
367 sc->w = w;
368 sc->h = h;
369 sc->wh = wh;
370
371 sc->dominoes = snewn(dc, struct solver_domino);
372 sc->placements = snewn(pc, struct solver_placement);
373 sc->squares = snewn(wh, struct solver_square);
374 sc->domino_placement_lists = snewn(pc, struct solver_placement *);
375 sc->fls = findloop_new_state(wh);
376
377 for (di = hi = 0; hi <= n; hi++) {
378 for (lo = 0; lo <= hi; lo++) {
379 assert(di == DINDEX(hi, lo));
380 sc->dominoes[di].hi = hi;
381 sc->dominoes[di].lo = lo;
382 sc->dominoes[di].index = di;
383
384#ifdef SOLVER_DIAGNOSTICS
385 {
386 char buf[128];
387 sprintf(buf, "%d-%d", hi, lo);
388 sc->dominoes[di].name = dupstr(buf);
389 }
390#endif
391
392 di++;
393 }
394 }
395
396 for (y = 0; y < h; y++) {
397 for (x = 0; x < w; x++) {
398 struct solver_square *sq = &sc->squares[y*w+x];
399 sq->x = x;
400 sq->y = y;
401 sq->index = y * w + x;
402 sq->nplacements = 0;
403
404#ifdef SOLVER_DIAGNOSTICS
405 {
406 char buf[128];
407 sprintf(buf, "(%d,%d)", x, y);
408 sq->name = dupstr(buf);
409 }
410#endif
411 }
412 }
413
414 pi = 0;
415 for (y = 0; y < h-1; y++) {
416 for (x = 0; x < w; x++) {
417 assert(pi < pc);
418 sc->placements[pi].squares[0] = &sc->squares[y*w+x];
419 sc->placements[pi].squares[1] = &sc->squares[(y+1)*w+x];
420#ifdef SOLVER_DIAGNOSTICS
421 {
422 char buf[128];
423 sprintf(buf, "(%d,%d-%d)", x, y, y+1);
424 sc->placements[pi].name = dupstr(buf);
425 }
426#endif
427 pi++;
428 }
429 }
430 for (y = 0; y < h; y++) {
431 for (x = 0; x < w-1; x++) {
432 assert(pi < pc);
433 sc->placements[pi].squares[0] = &sc->squares[y*w+x];
434 sc->placements[pi].squares[1] = &sc->squares[y*w+(x+1)];
435#ifdef SOLVER_DIAGNOSTICS
436 {
437 char buf[128];
438 sprintf(buf, "(%d-%d,%d)", x, x+1, y);
439 sc->placements[pi].name = dupstr(buf);
440 }
441#endif
442 pi++;
443 }
444 }
445 assert(pi == pc);
446
447 /* Set up the full placement lists for all squares, temporarily,
448 * so as to use them to calculate the overlap lists */
449 for (si = 0; si < wh; si++)
450 sc->squares[si].nplacements = 0;
451 for (pi = 0; pi < pc; pi++) {
452 struct solver_placement *p = &sc->placements[pi];
453 for (si = 0; si < 2; si++) {
454 struct solver_square *sq = p->squares[si];
455 p->spi[si] = sq->nplacements;
456 sq->placements[sq->nplacements++] = p;
457 }
458 }
459
460 /* Actually calculate the overlap lists */
461 for (pi = 0; pi < pc; pi++) {
462 struct solver_placement *p = &sc->placements[pi];
463 p->noverlaps = 0;
464 for (si = 0; si < 2; si++) {
465 struct solver_square *sq = p->squares[si];
466 int j;
467 for (j = 0; j < sq->nplacements; j++) {
468 struct solver_placement *q = sq->placements[j];
469 if (q != p)
470 p->overlaps[p->noverlaps++] = q;
471 }
472 }
473 }
474
475 /* Fill in the index field of the placements */
476 for (pi = 0; pi < pc; pi++)
477 sc->placements[pi].index = pi;
478
479 /* Lazily initialised by particular solver techniques that might
480 * never be needed */
481 sc->squares_by_number = NULL;
482 sc->squares_by_number_initialised = false;
483 sc->wh_scratch = NULL;
484 sc->pc_scratch = sc->pc_scratch2 = NULL;
485 sc->dc_scratch = NULL;
486 sc->dsf_scratch = NULL;
487
488 return sc;
489}
490
491static void solver_free_scratch(struct solver_scratch *sc)
492{
493#ifdef SOLVER_DIAGNOSTICS
494 {
495 int i;
496 for (i = 0; i < sc->dc; i++)
497 sfree(sc->dominoes[i].name);
498 for (i = 0; i < sc->pc; i++)
499 sfree(sc->placements[i].name);
500 for (i = 0; i < sc->wh; i++)
501 sfree(sc->squares[i].name);
502 }
503#endif
504 sfree(sc->dominoes);
505 sfree(sc->placements);
506 sfree(sc->squares);
507 sfree(sc->domino_placement_lists);
508 sfree(sc->squares_by_number);
509 findloop_free_state(sc->fls);
510 sfree(sc->wh_scratch);
511 sfree(sc->pc_scratch);
512 sfree(sc->pc_scratch2);
513 sfree(sc->dc_scratch);
514 dsf_free(sc->dsf_scratch);
515 sfree(sc);
516}
517
518static void solver_setup_grid(struct solver_scratch *sc, const int *numbers)
519{
520 int i, j;
521
522 for (i = 0; i < sc->wh; i++) {
523 sc->squares[i].nplacements = 0;
524 sc->squares[i].number = numbers[sc->squares[i].index];
525 }
526
527 for (i = 0; i < sc->pc; i++) {
528 struct solver_placement *p = &sc->placements[i];
529 int di = DINDEX(p->squares[0]->number, p->squares[1]->number);
530 p->domino = &sc->dominoes[di];
531 }
532
533 for (i = 0; i < sc->dc; i++)
534 sc->dominoes[i].nplacements = 0;
535 for (i = 0; i < sc->pc; i++)
536 sc->placements[i].domino->nplacements++;
537 for (i = j = 0; i < sc->dc; i++) {
538 sc->dominoes[i].placements = sc->domino_placement_lists + j;
539 j += sc->dominoes[i].nplacements;
540 sc->dominoes[i].nplacements = 0;
541 }
542 for (i = 0; i < sc->pc; i++) {
543 struct solver_placement *p = &sc->placements[i];
544 p->dpi = p->domino->nplacements;
545 p->domino->placements[p->domino->nplacements++] = p;
546 p->active = true;
547 }
548
549 for (i = 0; i < sc->wh; i++)
550 sc->squares[i].nplacements = 0;
551 for (i = 0; i < sc->pc; i++) {
552 struct solver_placement *p = &sc->placements[i];
553 for (j = 0; j < 2; j++) {
554 struct solver_square *sq = p->squares[j];
555 p->spi[j] = sq->nplacements;
556 sq->placements[sq->nplacements++] = p;
557 }
558 }
559
560 sc->max_diff_used = DIFF_TRIVIAL;
561 sc->squares_by_number_initialised = false;
562}
563
564/* Given two placements p,q that overlap, returns si such that
565 * p->squares[si] is the square also in q */
566static int common_square_index(struct solver_placement *p,
567 struct solver_placement *q)
568{
569 return (p->squares[0] == q->squares[0] ||
570 p->squares[0] == q->squares[1]) ? 0 : 1;
571}
572
573/* Sort function used to set up squares_by_number */
574static int squares_by_number_cmpfn(const void *av, const void *bv)
575{
576 struct solver_square *a = *(struct solver_square *const *)av;
577 struct solver_square *b = *(struct solver_square *const *)bv;
578 return (a->number < b->number ? -1 : a->number > b->number ? +1 :
579 a->index < b->index ? -1 : a->index > b->index ? +1 : 0);
580}
581
582static void rule_out_placement(
583 struct solver_scratch *sc, struct solver_placement *p)
584{
585 struct solver_domino *d = p->domino;
586 int i, j, si;
587
588#ifdef SOLVER_DIAGNOSTICS
589 if (solver_diagnostics)
590 printf(" ruling out placement %s for domino %s\n", p->name, d->name);
591#endif
592
593 p->active = false;
594
595 i = p->dpi;
596 assert(d->placements[i] == p);
597 if (--d->nplacements != i) {
598 d->placements[i] = d->placements[d->nplacements];
599 d->placements[i]->dpi = i;
600 }
601
602 for (si = 0; si < 2; si++) {
603 struct solver_square *sq = p->squares[si];
604 i = p->spi[si];
605 assert(sq->placements[i] == p);
606 if (--sq->nplacements != i) {
607 sq->placements[i] = sq->placements[sq->nplacements];
608 j = (sq->placements[i]->squares[0] == sq ? 0 : 1);
609 sq->placements[i]->spi[j] = i;
610 }
611 }
612}
613
614/*
615 * If a domino has only one placement remaining, rule out all other
616 * placements that overlap it.
617 */
618static bool deduce_domino_single_placement(struct solver_scratch *sc, int di)
619{
620 struct solver_domino *d = &sc->dominoes[di];
621 struct solver_placement *p, *q;
622 int oi;
623 bool done_something = false;
624
625 if (d->nplacements != 1)
626 return false;
627 p = d->placements[0];
628
629 for (oi = 0; oi < p->noverlaps; oi++) {
630 q = p->overlaps[oi];
631 if (q->active) {
632 if (!done_something) {
633 done_something = true;
634#ifdef SOLVER_DIAGNOSTICS
635 if (solver_diagnostics)
636 printf("domino %s has unique placement %s\n",
637 d->name, p->name);
638#endif
639 }
640 rule_out_placement(sc, q);
641 }
642 }
643
644 return done_something;
645}
646
647/*
648 * If a square has only one placement remaining, rule out all other
649 * placements of its domino.
650 */
651static bool deduce_square_single_placement(struct solver_scratch *sc, int si)
652{
653 struct solver_square *sq = &sc->squares[si];
654 struct solver_placement *p;
655 struct solver_domino *d;
656
657 if (sq->nplacements != 1)
658 return false;
659 p = sq->placements[0];
660 d = p->domino;
661
662 if (d->nplacements <= 1)
663 return false; /* we already knew everything this would tell us */
664
665#ifdef SOLVER_DIAGNOSTICS
666 if (solver_diagnostics)
667 printf("square %s has unique placement %s (domino %s)\n",
668 sq->name, p->name, p->domino->name);
669#endif
670
671 while (d->nplacements > 1)
672 rule_out_placement(
673 sc, d->placements[0] == p ? d->placements[1] : d->placements[0]);
674
675 return true;
676}
677
678/*
679 * If all placements for a square involve the same domino, rule out
680 * all other placements of that domino.
681 */
682static bool deduce_square_single_domino(struct solver_scratch *sc, int si)
683{
684 struct solver_square *sq = &sc->squares[si];
685 struct solver_domino *d;
686 int i;
687
688 /*
689 * We only bother with this if the square has at least _two_
690 * placements. If it only has one, then a simpler deduction will
691 * have handled it already, or will do so the next time round the
692 * main solver loop - and we should let the simpler deduction do
693 * it, because that will give a less overblown diagnostic.
694 */
695 if (sq->nplacements < 2)
696 return false;
697
698 d = sq->placements[0]->domino;
699 for (i = 1; i < sq->nplacements; i++)
700 if (sq->placements[i]->domino != d)
701 return false; /* not all the same domino */
702
703 if (d->nplacements <= sq->nplacements)
704 return false; /* no other placements of d to rule out */
705
706#ifdef SOLVER_DIAGNOSTICS
707 if (solver_diagnostics)
708 printf("square %s can only contain domino %s\n", sq->name, d->name);
709#endif
710
711 for (i = d->nplacements; i-- > 0 ;) {
712 struct solver_placement *p = d->placements[i];
713 if (p->squares[0] != sq && p->squares[1] != sq)
714 rule_out_placement(sc, p);
715 }
716
717 return true;
718}
719
720/*
721 * If any placement is overlapped by _all_ possible placements of a
722 * given domino, rule that placement out.
723 */
724static bool deduce_domino_must_overlap(struct solver_scratch *sc, int di)
725{
726 struct solver_domino *d = &sc->dominoes[di];
727 struct solver_placement *intersection[6], *p;
728 int nintersection = 0;
729 int i, j, k;
730
731 /*
732 * As in deduce_square_single_domino, we only bother with this
733 * deduction if the domino has at least two placements.
734 */
735 if (d->nplacements < 2)
736 return false;
737
738 /* Initialise our set of overlapped placements with all the active
739 * ones overlapped by placements[0]. */
740 p = d->placements[0];
741 for (i = 0; i < p->noverlaps; i++)
742 if (p->overlaps[i]->active)
743 intersection[nintersection++] = p->overlaps[i];
744
745 /* Now loop over the other placements of d, winnowing that set. */
746 for (j = 1; j < d->nplacements; j++) {
747 int old_n;
748
749 p = d->placements[j];
750
751 old_n = nintersection;
752 nintersection = 0;
753
754 for (k = 0; k < old_n; k++) {
755 for (i = 0; i < p->noverlaps; i++)
756 if (p->overlaps[i] == intersection[k])
757 goto found;
758 /* If intersection[k] isn't in p->overlaps, exclude it
759 * from our set of placements overlapped by everything */
760 continue;
761 found:
762 intersection[nintersection++] = intersection[k];
763 }
764 }
765
766 if (nintersection == 0)
767 return false; /* no new exclusions */
768
769 for (i = 0; i < nintersection; i++) {
770 p = intersection[i];
771
772#ifdef SOLVER_DIAGNOSTICS
773 if (solver_diagnostics) {
774 printf("placement %s of domino %s overlaps all placements "
775 "of domino %s:", p->name, p->domino->name, d->name);
776 for (j = 0; j < d->nplacements; j++)
777 printf(" %s", d->placements[j]->name);
778 printf("\n");
779 }
780#endif
781 rule_out_placement(sc, p);
782 }
783
784 return true;
785}
786
787/*
788 * If a placement of domino D overlaps the only remaining placement
789 * for some square S which is not also for domino D, then placing D
790 * here would require another copy of it in S, so we can rule it out.
791 */
792static bool deduce_local_duplicate(struct solver_scratch *sc, int pi)
793{
794 struct solver_placement *p = &sc->placements[pi];
795 struct solver_domino *d = p->domino;
796 int i, j;
797
798 if (!p->active)
799 return false;
800
801 for (i = 0; i < p->noverlaps; i++) {
802 struct solver_placement *q = p->overlaps[i];
803 struct solver_square *sq;
804
805 if (!q->active)
806 continue;
807
808 /* Find the square of q that _isn't_ part of p */
809 sq = q->squares[1 - common_square_index(q, p)];
810
811 for (j = 0; j < sq->nplacements; j++)
812 if (sq->placements[j] != q && sq->placements[j]->domino != d)
813 goto no;
814
815 /* If we get here, every possible placement for sq is either q
816 * itself, or another copy of d. Success! We can rule out p. */
817#ifdef SOLVER_DIAGNOSTICS
818 if (solver_diagnostics) {
819 printf("placement %s of domino %s would force another copy of %s "
820 "in square %s\n", p->name, d->name, d->name, sq->name);
821 }
822#endif
823
824 rule_out_placement(sc, p);
825 return true;
826
827 no:;
828 }
829
830 return false;
831}
832
833/*
834 * If placement P overlaps one placement for each of two squares S,T
835 * such that all the remaining placements for both S and T are the
836 * same domino D (and none of those placements joins S and T to each
837 * other), then P can't be placed, because it would leave S,T each
838 * having to be a copy of D, i.e. duplicates.
839 */
840static bool deduce_local_duplicate_2(struct solver_scratch *sc, int pi)
841{
842 struct solver_placement *p = &sc->placements[pi];
843 int i, j, k;
844
845 if (!p->active)
846 return false;
847
848 /*
849 * Iterate over pairs of placements qi,qj overlapping p.
850 */
851 for (i = 0; i < p->noverlaps; i++) {
852 struct solver_placement *qi = p->overlaps[i];
853 struct solver_square *sqi;
854 struct solver_domino *di = NULL;
855
856 if (!qi->active)
857 continue;
858
859 /* Find the square of qi that _isn't_ part of p */
860 sqi = qi->squares[1 - common_square_index(qi, p)];
861
862 /*
863 * Identify the unique domino involved in all possible
864 * placements of sqi other than qi. If there isn't a unique
865 * one (either too many or too few), move on and try the next
866 * qi.
867 */
868 for (k = 0; k < sqi->nplacements; k++) {
869 struct solver_placement *pk = sqi->placements[k];
870 if (sqi->placements[k] == qi)
871 continue; /* not counting qi itself */
872 if (!di)
873 di = pk->domino;
874 else if (di != pk->domino)
875 goto done_qi;
876 }
877 if (!di)
878 goto done_qi;
879
880 /*
881 * Now find an appropriate qj != qi.
882 */
883 for (j = 0; j < p->noverlaps; j++) {
884 struct solver_placement *qj = p->overlaps[j];
885 struct solver_square *sqj;
886 bool found_di = false;
887
888 if (j == i || !qj->active)
889 continue;
890
891 sqj = qj->squares[1 - common_square_index(qj, p)];
892
893 /*
894 * As above, we want the same domino di to be the only one
895 * sqj can be if placement qj is ruled out. But also we
896 * need no placement of sqj to overlap sqi.
897 */
898 for (k = 0; k < sqj->nplacements; k++) {
899 struct solver_placement *pk = sqj->placements[k];
900 if (pk == qj)
901 continue; /* not counting qj itself */
902 if (pk->domino != di)
903 goto done_qj; /* found a different domino */
904 if (pk->squares[0] == sqi || pk->squares[1] == sqi)
905 goto done_qj; /* sqi,sqj can be joined to each other */
906 found_di = true;
907 }
908 if (!found_di)
909 goto done_qj;
910
911 /* If we get here, then every placement for either of sqi
912 * and sqj is a copy of di, except for the ones that
913 * overlap p. Success! We can rule out p. */
914#ifdef SOLVER_DIAGNOSTICS
915 if (solver_diagnostics) {
916 printf("placement %s of domino %s would force squares "
917 "%s and %s to both be domino %s\n",
918 p->name, p->domino->name,
919 sqi->name, sqj->name, di->name);
920 }
921#endif
922 rule_out_placement(sc, p);
923 return true;
924
925 done_qj:;
926 }
927
928 done_qi:;
929 }
930
931 return false;
932}
933
934struct parity_findloop_ctx {
935 struct solver_scratch *sc;
936 struct solver_square *sq;
937 int i;
938};
939
940static int parity_neighbour(int vertex, void *vctx)
941{
942 struct parity_findloop_ctx *ctx = (struct parity_findloop_ctx *)vctx;
943 struct solver_placement *p;
944
945 if (vertex >= 0) {
946 ctx->sq = &ctx->sc->squares[vertex];
947 ctx->i = 0;
948 } else {
949 assert(ctx->sq);
950 }
951
952 if (ctx->i >= ctx->sq->nplacements) {
953 ctx->sq = NULL;
954 return -1;
955 }
956
957 p = ctx->sq->placements[ctx->i++];
958 return p->squares[0]->index + p->squares[1]->index - ctx->sq->index;
959}
960
961/*
962 * Look for dominoes whose placement would disconnect the unfilled
963 * area of the grid into pieces with odd area. Such a domino can't be
964 * placed, because then the area on each side of it would be
965 * untileable.
966 */
967static bool deduce_parity(struct solver_scratch *sc)
968{
969 struct parity_findloop_ctx pflctx;
970 bool done_something = false;
971 int pi;
972
973 /*
974 * Run findloop, aka Tarjan's bridge-finding algorithm, on the
975 * graph whose vertices are squares, with two vertices separated
976 * by an edge iff some not-yet-ruled-out domino placement covers
977 * them both. (So each edge itself corresponds to a domino
978 * placement.)
979 *
980 * The effect is that any bridge in this graph is a domino whose
981 * placement would separate two previously connected areas of the
982 * unfilled squares of the grid.
983 *
984 * Placing that domino would not just disconnect those areas from
985 * each other, but also use up one square of each. So if we want
986 * to avoid leaving two odd areas after placing the domino, it
987 * follows that we want to avoid the bridge having an _even_
988 * number of vertices on each side.
989 */
990 pflctx.sc = sc;
991 findloop_run(sc->fls, sc->wh, parity_neighbour, &pflctx);
992
993 for (pi = 0; pi < sc->pc; pi++) {
994 struct solver_placement *p = &sc->placements[pi];
995 int size0, size1;
996
997 if (!p->active)
998 continue;
999 if (!findloop_is_bridge(
1000 sc->fls, p->squares[0]->index, p->squares[1]->index,
1001 &size0, &size1))
1002 continue;
1003 /* To make a deduction, size0 and size1 must both be even,
1004 * i.e. after placing this domino decrements each by 1 they
1005 * would both become odd and untileable areas. */
1006 if ((size0 | size1) & 1)
1007 continue;
1008
1009#ifdef SOLVER_DIAGNOSTICS
1010 if (solver_diagnostics) {
1011 printf("placement %s of domino %s would create two odd-sized "
1012 "areas\n", p->name, p->domino->name);
1013 }
1014#endif
1015 rule_out_placement(sc, p);
1016 done_something = true;
1017 }
1018
1019 return done_something;
1020}
1021
1022/*
1023 * Try to find a set of squares all containing the same number, such
1024 * that the set of possible dominoes for all the squares in that set
1025 * is small enough to let us rule out placements of those dominoes
1026 * elsewhere.
1027 */
1028static bool deduce_set(struct solver_scratch *sc, bool doubles)
1029{
1030 struct solver_square **sqs, **sqp, **sqe;
1031 int num, nsq, i, j;
1032 unsigned long domino_sets[16], adjacent[16];
1033 struct solver_domino *ds[16];
1034 bool done_something = false;
1035
1036 if (!sc->squares_by_number)
1037 sc->squares_by_number = snewn(sc->wh, struct solver_square *);
1038 if (!sc->wh_scratch)
1039 sc->wh_scratch = snewn(sc->wh, int);
1040
1041 if (!sc->squares_by_number_initialised) {
1042 /*
1043 * If this is the first call to this function for a given
1044 * grid, start by sorting the squares by their containing
1045 * number.
1046 */
1047 for (i = 0; i < sc->wh; i++)
1048 sc->squares_by_number[i] = &sc->squares[i];
1049 qsort(sc->squares_by_number, sc->wh, sizeof(*sc->squares_by_number),
1050 squares_by_number_cmpfn);
1051 }
1052
1053 sqp = sc->squares_by_number;
1054 sqe = sc->squares_by_number + sc->wh;
1055 for (num = 0; num <= sc->n; num++) {
1056 unsigned long squares;
1057 unsigned long squares_done;
1058
1059 /* Find the bounds of the subinterval of squares_by_number
1060 * containing squares with this particular number. */
1061 sqs = sqp;
1062 while (sqp < sqe && (*sqp)->number == num)
1063 sqp++;
1064 nsq = sqp - sqs;
1065
1066 /*
1067 * Now sqs[0], ..., sqs[nsq-1] are the squares containing 'num'.
1068 */
1069
1070 if (nsq > lenof(domino_sets)) {
1071 /*
1072 * Abort this analysis if we're trying to enumerate all
1073 * the subsets of a too-large base set.
1074 *
1075 * This _shouldn't_ happen, at the time of writing this
1076 * code, because the largest puzzle we support is only
1077 * supposed to have 10 instances of each number, and part
1078 * of our input grid validation checks that each number
1079 * does appear the right number of times. But just in case
1080 * weird test input makes its way to this function, or the
1081 * puzzle sizes are expanded later, it's easy enough to
1082 * just rule out doing this analysis for overlarge sets of
1083 * numbers.
1084 */
1085 continue;
1086 }
1087
1088 /*
1089 * Index the squares in wh_scratch, which we're using as a
1090 * lookup table to map the official index of a square back to
1091 * its value in our local indexing scheme.
1092 */
1093 for (i = 0; i < nsq; i++)
1094 sc->wh_scratch[sqs[i]->index] = i;
1095
1096 /*
1097 * For each square, make a bit mask of the dominoes that can
1098 * overlap it, by finding the number at the other end of each
1099 * one.
1100 *
1101 * Also, for each square, make a bit mask of other squares in
1102 * the current list that might occupy the _same_ domino
1103 * (because a possible placement of a double overlaps both).
1104 * We'll need that for evaluating whether sets are properly
1105 * exhaustive.
1106 */
1107 for (i = 0; i < nsq; i++)
1108 adjacent[i] = 0;
1109
1110 for (i = 0; i < nsq; i++) {
1111 struct solver_square *sq = sqs[i];
1112 unsigned long mask = 0;
1113
1114 for (j = 0; j < sq->nplacements; j++) {
1115 struct solver_placement *p = sq->placements[j];
1116 int othernum = p->domino->lo + p->domino->hi - num;
1117 mask |= 1UL << othernum;
1118 ds[othernum] = p->domino; /* so we can find them later */
1119
1120 if (othernum == num) {
1121 /*
1122 * Special case: this is a double, so it gives
1123 * rise to entries in adjacent[].
1124 */
1125 int i2 = sc->wh_scratch[p->squares[0]->index +
1126 p->squares[1]->index - sq->index];
1127 adjacent[i] |= 1UL << i2;
1128 adjacent[i2] |= 1UL << i;
1129 }
1130 }
1131
1132 domino_sets[i] = mask;
1133
1134 }
1135
1136 squares_done = 0;
1137
1138 for (squares = 0; squares < (1UL << nsq); squares++) {
1139 unsigned long dominoes = 0;
1140 int bitpos, nsquares, ndominoes;
1141 bool got_adj_squares = false;
1142 bool reported = false;
1143 bool rule_out_nondoubles;
1144 int min_nused_for_double;
1145#ifdef SOLVER_DIAGNOSTICS
1146 const char *rule_out_text;
1147#endif
1148
1149 /*
1150 * We don't do set analysis on the same square of the grid
1151 * more than once in this loop. Otherwise you generate
1152 * pointlessly overcomplicated diagnostics for simpler
1153 * follow-up deductions. For example, suppose squares
1154 * {A,B} must go with dominoes {X,Y}. So you rule out X,Y
1155 * elsewhere, and then it turns out square C (from which
1156 * one of those was eliminated) has only one remaining
1157 * possibility Z. What you _don't_ want to do is
1158 * triumphantly report a second case of set elimination
1159 * where you say 'And also, squares {A,B,C} have to be
1160 * {X,Y,Z}!' You'd prefer to give 'now C has to be Z' as a
1161 * separate deduction later, more simply phrased.
1162 */
1163 if (squares & squares_done)
1164 continue;
1165
1166 nsquares = 0;
1167
1168 /* Make the set of dominoes that these squares can inhabit. */
1169 for (bitpos = 0; bitpos < nsq; bitpos++) {
1170 if (!(1 & (squares >> bitpos)))
1171 continue; /* this bit isn't set in the mask */
1172
1173 if (adjacent[bitpos] & squares)
1174 got_adj_squares = true;
1175
1176 dominoes |= domino_sets[bitpos];
1177 nsquares++;
1178 }
1179
1180 /* Count them. */
1181 ndominoes = 0;
1182 for (bitpos = 0; bitpos < nsq; bitpos++)
1183 ndominoes += 1 & (dominoes >> bitpos);
1184
1185 /*
1186 * Do the two sets have the right relative size?
1187 */
1188 if (!got_adj_squares) {
1189 /*
1190 * The normal case, in which every possible domino
1191 * placement involves at most _one_ of these squares.
1192 *
1193 * This is exactly analogous to the set analysis
1194 * deductions in many other puzzles: if our N squares
1195 * between them have to account for N distinct
1196 * dominoes, with exactly one of those dominoes to
1197 * each square, then all those dominoes correspond to
1198 * all those squares and we can rule out any
1199 * placements of the same dominoes appearing
1200 * elsewhere.
1201 */
1202 if (ndominoes != nsquares)
1203 continue;
1204 rule_out_nondoubles = true;
1205 min_nused_for_double = 1;
1206#ifdef SOLVER_DIAGNOSTICS
1207 rule_out_text = "all of them elsewhere";
1208#endif
1209 } else {
1210 if (!doubles)
1211 continue; /* not at this difficulty level */
1212
1213 /*
1214 * But in Dominosa, there's a special case if _two_
1215 * squares in this set can possibly both be covered by
1216 * the same double domino. (I.e. if they are adjacent,
1217 * and moreover, the double-domino placement
1218 * containing both is not yet ruled out.)
1219 *
1220 * In that situation, the simple argument doesn't hold
1221 * up, because the N squares might be covered by N-1
1222 * dominoes - or, put another way, if you list the
1223 * containing domino for each of the squares, they
1224 * might not be all distinct.
1225 *
1226 * In that situation, we can still do something, but
1227 * the details vary, and there are two further cases.
1228 */
1229 if (ndominoes == nsquares-1) {
1230 /*
1231 * Suppose there is one _more_ square in our set
1232 * than there are dominoes it can involve. For
1233 * example, suppose we had four '0' squares which
1234 * between them could contain only the 0-0, 0-1
1235 * and 0-2 dominoes.
1236 *
1237 * Then that can only work at all if the 0-0
1238 * covers two of those squares - and in that
1239 * situation that _must_ be what's happened.
1240 *
1241 * So we can rule out the 0-1 and 0-2 dominoes (in
1242 * this example) in any placement that doesn't use
1243 * one of the squares in this set. And we can rule
1244 * out a placement of the 0-0 even if it uses
1245 * _one_ square from this set: in this situation,
1246 * we have to insist on it using _two_.
1247 */
1248 rule_out_nondoubles = true;
1249 min_nused_for_double = 2;
1250#ifdef SOLVER_DIAGNOSTICS
1251 rule_out_text = "all of them elsewhere "
1252 "(including the double if it fails to use both)";
1253#endif
1254 } else if (ndominoes == nsquares) {
1255 /*
1256 * A restricted form of the deduction is still
1257 * possible if we have the same number of dominoes
1258 * as squares.
1259 *
1260 * If we have _three_ '0' squares none of which
1261 * can be any domino other than 0-0, 0-1 and 0-2,
1262 * and there's still a possibility of an 0-0
1263 * domino using up two of them, then we can't rule
1264 * out 0-1 or 0-2 anywhere else, because it's
1265 * possible that these three squares only use two
1266 * of the dominoes between them.
1267 *
1268 * But we _can_ rule out the double 0-0, in any
1269 * placement that uses _none_ of our three
1270 * squares. Because we do know that _at least one_
1271 * of our squares must be involved in the 0-0, or
1272 * else the three of them would only have the
1273 * other two dominoes left.
1274 */
1275 rule_out_nondoubles = false;
1276 min_nused_for_double = 1;
1277#ifdef SOLVER_DIAGNOSTICS
1278 rule_out_text = "the double elsewhere";
1279#endif
1280 } else {
1281 /*
1282 * If none of those cases has happened, then our
1283 * set admits no deductions at all.
1284 */
1285 continue;
1286 }
1287 }
1288
1289 /* Skip sets of size 1, or whose complement has size 1.
1290 * Those can be handled by a simpler analysis, and should
1291 * be, for more sensible solver diagnostics. */
1292 if (ndominoes <= 1 || ndominoes >= nsq-1)
1293 continue;
1294
1295 /*
1296 * We've found a set! That means we can rule out any
1297 * placement of any domino in that set which would leave
1298 * the squares in the set with too few dominoes between
1299 * them.
1300 *
1301 * We may or may not actually end up ruling anything out
1302 * here. But even if we don't, we should record that these
1303 * squares form a self-contained set, so that we don't
1304 * pointlessly report a superset of them later which could
1305 * instead be reported as just the other ones.
1306 *
1307 * Or rather, we do that for the main cases that let us
1308 * rule out lots of dominoes. We only do this with the
1309 * borderline case where we can only rule out a double if
1310 * we _actually_ rule something out. Otherwise we'll never
1311 * even _find_ a larger set with the same number of
1312 * dominoes!
1313 */
1314 if (rule_out_nondoubles)
1315 squares_done |= squares;
1316
1317 for (bitpos = 0; bitpos < nsq; bitpos++) {
1318 struct solver_domino *d;
1319
1320 if (!(1 & (dominoes >> bitpos)))
1321 continue;
1322 d = ds[bitpos];
1323
1324 for (i = d->nplacements; i-- > 0 ;) {
1325 struct solver_placement *p = d->placements[i];
1326 int si, nused;
1327
1328 /* Count how many of our squares this placement uses. */
1329 for (si = nused = 0; si < 2; si++) {
1330 struct solver_square *sq2 = p->squares[si];
1331 if (sq2->number == num &&
1332 (1 & (squares >> sc->wh_scratch[sq2->index])))
1333 nused++;
1334 }
1335
1336 /* See if that's too many to rule it out. */
1337 if (d->lo == d->hi) {
1338 if (nused >= min_nused_for_double)
1339 continue;
1340 } else {
1341 if (nused > 0 || !rule_out_nondoubles)
1342 continue;
1343 }
1344
1345 if (!reported) {
1346 reported = true;
1347 done_something = true;
1348
1349 /* In case we didn't do this above */
1350 squares_done |= squares;
1351
1352#ifdef SOLVER_DIAGNOSTICS
1353 if (solver_diagnostics) {
1354 int b;
1355 const char *sep;
1356 printf("squares {");
1357 for (sep = "", b = 0; b < nsq; b++)
1358 if (1 & (squares >> b)) {
1359 printf("%s%s", sep, sqs[b]->name);
1360 sep = ",";
1361 }
1362 printf("} can contain only dominoes {");
1363 for (sep = "", b = 0; b < nsq; b++)
1364 if (1 & (dominoes >> b)) {
1365 printf("%s%s", sep, ds[b]->name);
1366 sep = ",";
1367 }
1368 printf("}, so rule out %s", rule_out_text);
1369 printf("\n");
1370 }
1371#endif
1372 }
1373
1374 rule_out_placement(sc, p);
1375 }
1376 }
1377 }
1378
1379 }
1380
1381 return done_something;
1382}
1383
1384static int forcing_chain_dup_cmp(const void *av, const void *bv, void *ctx)
1385{
1386 struct solver_scratch *sc = (struct solver_scratch *)ctx;
1387 int a = *(const int *)av, b = *(const int *)bv;
1388 int ac, bc;
1389
1390 ac = sc->pc_scratch[a];
1391 bc = sc->pc_scratch[b];
1392 if (ac != bc) return ac > bc ? +1 : -1;
1393
1394 ac = sc->placements[a].domino->index;
1395 bc = sc->placements[b].domino->index;
1396 if (ac != bc) return ac > bc ? +1 : -1;
1397
1398 return 0;
1399}
1400
1401static int forcing_chain_sq_cmp(const void *av, const void *bv, void *ctx)
1402{
1403 struct solver_scratch *sc = (struct solver_scratch *)ctx;
1404 int a = *(const int *)av, b = *(const int *)bv;
1405 int ac, bc;
1406
1407 ac = sc->placements[a].domino->index;
1408 bc = sc->placements[b].domino->index;
1409 if (ac != bc) return ac > bc ? +1 : -1;
1410
1411 ac = sc->pc_scratch[a];
1412 bc = sc->pc_scratch[b];
1413 if (ac != bc) return ac > bc ? +1 : -1;
1414
1415 return 0;
1416}
1417
1418static bool deduce_forcing_chain(struct solver_scratch *sc)
1419{
1420 int si, pi, di, j, k, m;
1421 bool done_something = false;
1422
1423 if (!sc->wh_scratch)
1424 sc->wh_scratch = snewn(sc->wh, int);
1425 if (!sc->pc_scratch)
1426 sc->pc_scratch = snewn(sc->pc, int);
1427 if (!sc->pc_scratch2)
1428 sc->pc_scratch2 = snewn(sc->pc, int);
1429 if (!sc->dc_scratch)
1430 sc->dc_scratch = snewn(sc->dc, int);
1431 if (!sc->dsf_scratch)
1432 sc->dsf_scratch = dsf_new_flip(sc->pc);
1433
1434 /*
1435 * Start by identifying chains of placements which must all occur
1436 * together if any of them occurs. We do this by making
1437 * dsf_scratch a flip dsf binding the placements into an equivalence
1438 * class for each entire forcing chain, with the two possible sets
1439 * of dominoes for the chain listed as inverses.
1440 */
1441 dsf_reinit(sc->dsf_scratch);
1442 for (si = 0; si < sc->wh; si++) {
1443 struct solver_square *sq = &sc->squares[si];
1444 if (sq->nplacements == 2)
1445 dsf_merge_flip(sc->dsf_scratch,
1446 sq->placements[0]->index,
1447 sq->placements[1]->index, true);
1448 }
1449 /*
1450 * Now read out the whole dsf into pc_scratch, flattening its
1451 * structured data into a simple integer id per chain of dominoes
1452 * that must occur together.
1453 *
1454 * The integer ids have the property that any two that differ only
1455 * in the lowest bit (i.e. of the form {2n,2n+1}) represent
1456 * complementary chains, each of which rules out the other.
1457 */
1458 for (pi = 0; pi < sc->pc; pi++) {
1459 bool inv;
1460 int c = dsf_canonify_flip(sc->dsf_scratch, pi, &inv);
1461 sc->pc_scratch[pi] = c * 2 + (inv ? 1 : 0);
1462 }
1463
1464 /*
1465 * Identify chains that contain a duplicate domino, and rule them
1466 * out. We do this by making a list of the placement indices in
1467 * pc_scratch2, sorted by (chain id, domino id), so that dupes
1468 * become adjacent.
1469 */
1470 for (pi = 0; pi < sc->pc; pi++)
1471 sc->pc_scratch2[pi] = pi;
1472 arraysort(sc->pc_scratch2, sc->pc, forcing_chain_dup_cmp, sc);
1473
1474 for (j = 0; j < sc->pc ;) {
1475 struct solver_domino *duplicated_domino = NULL;
1476
1477 /*
1478 * This loop iterates once per contiguous segment of the same
1479 * value in pc_scratch2, i.e. once per chain.
1480 */
1481 int ci = sc->pc_scratch[sc->pc_scratch2[j]];
1482 int climit, cstart = j;
1483 while (j < sc->pc && sc->pc_scratch[sc->pc_scratch2[j]] == ci)
1484 j++;
1485 climit = j;
1486
1487 /*
1488 * Now look for a duplicate domino within that chain.
1489 */
1490 for (k = cstart; k + 1 < climit; k++) {
1491 struct solver_placement *p = &sc->placements[sc->pc_scratch2[k]];
1492 struct solver_placement *q = &sc->placements[sc->pc_scratch2[k+1]];
1493 if (p->domino == q->domino) {
1494 duplicated_domino = p->domino;
1495 break;
1496 }
1497 }
1498
1499 if (!duplicated_domino)
1500 continue;
1501
1502#ifdef SOLVER_DIAGNOSTICS
1503 if (solver_diagnostics) {
1504 printf("domino %s occurs more than once in forced chain:",
1505 duplicated_domino->name);
1506 for (k = cstart; k < climit; k++)
1507 printf(" %s", sc->placements[sc->pc_scratch2[k]].name);
1508 printf("\n");
1509 }
1510#endif
1511
1512 for (k = cstart; k < climit; k++)
1513 rule_out_placement(sc, &sc->placements[sc->pc_scratch2[k]]);
1514
1515 done_something = true;
1516 }
1517
1518 if (done_something)
1519 return true;
1520
1521 /*
1522 * A second way in which a whole forcing chain can be ruled out is
1523 * if it contains all the dominoes that can occupy some other
1524 * square, so that if the domnioes in the chain were all laid, the
1525 * other square would be left without any choices.
1526 *
1527 * To detect this, we sort the placements again, this time by
1528 * (domino index, chain index), so that we can easily find a
1529 * sorted list of chains per domino. That allows us to iterate
1530 * over the squares and check for a chain id common to all the
1531 * placements of that square.
1532 */
1533 for (pi = 0; pi < sc->pc; pi++)
1534 sc->pc_scratch2[pi] = pi;
1535 arraysort(sc->pc_scratch2, sc->pc, forcing_chain_sq_cmp, sc);
1536
1537 /* Store a lookup table of the first entry in pc_scratch2
1538 * corresponding to each domino. */
1539 for (di = j = 0; j < sc->pc; j++) {
1540 while (di <= sc->placements[sc->pc_scratch2[j]].domino->index) {
1541 assert(di < sc->dc);
1542 sc->dc_scratch[di++] = j;
1543 }
1544 }
1545 assert(di == sc->dc);
1546
1547 for (si = 0; si < sc->wh; si++) {
1548 struct solver_square *sq = &sc->squares[si];
1549 int listpos = 0, listsize = 0, listout = 0;
1550 int exclude[4];
1551 int n_exclude;
1552
1553 if (sq->nplacements < 2)
1554 continue; /* too simple to be worth trying */
1555
1556 /*
1557 * Start by checking for chains this square can actually form
1558 * part of. We won't consider those. (The aim is to find a
1559 * completely _different_ square whose placements are all
1560 * ruled out by a chain.)
1561 */
1562 assert(sq->nplacements <= lenof(exclude));
1563 for (j = n_exclude = 0; j < sq->nplacements; j++)
1564 exclude[n_exclude++] = sc->pc_scratch[sq->placements[j]->index];
1565
1566 for (j = 0; j < sq->nplacements; j++) {
1567 struct solver_domino *d = sq->placements[j]->domino;
1568
1569 listout = listpos = 0;
1570
1571 for (k = sc->dc_scratch[d->index];
1572 k < sc->pc && sc->placements[sc->pc_scratch2[k]].domino == d;
1573 k++) {
1574 int chain = sc->pc_scratch[sc->pc_scratch2[k]];
1575 bool keep;
1576
1577 if (!sc->placements[sc->pc_scratch2[k]].active)
1578 continue;
1579
1580 if (j == 0) {
1581 keep = true;
1582 } else {
1583 while (listpos < listsize &&
1584 sc->wh_scratch[listpos] < chain)
1585 listpos++;
1586 keep = (listpos < listsize &&
1587 sc->wh_scratch[listpos] == chain);
1588 }
1589
1590 for (m = 0; m < n_exclude; m++)
1591 if (chain == exclude[m])
1592 keep = false;
1593
1594 if (keep)
1595 sc->wh_scratch[listout++] = chain;
1596 }
1597
1598 listsize = listout;
1599 if (listsize == 0)
1600 break; /* ruled out all chains; terminate loop early */
1601 }
1602
1603 for (listpos = 0; listpos < listsize; listpos++) {
1604 int chain = sc->wh_scratch[listpos];
1605
1606 /*
1607 * We've found a chain we can rule out.
1608 */
1609#ifdef SOLVER_DIAGNOSTICS
1610 if (solver_diagnostics) {
1611 printf("all choices for square %s would be ruled out "
1612 "by forced chain:", sq->name);
1613 for (pi = 0; pi < sc->pc; pi++)
1614 if (sc->pc_scratch[pi] == chain)
1615 printf(" %s", sc->placements[pi].name);
1616 printf("\n");
1617 }
1618#endif
1619
1620 for (pi = 0; pi < sc->pc; pi++)
1621 if (sc->pc_scratch[pi] == chain)
1622 rule_out_placement(sc, &sc->placements[pi]);
1623
1624 done_something = true;
1625 }
1626 }
1627
1628 /*
1629 * Another thing you can do with forcing chains, besides ruling
1630 * out a whole one at a time, is to look at each pair of chains
1631 * that overlap each other. Each such pair gives you two sets of
1632 * domino placements, such that if either set is not placed, then
1633 * the other one must be.
1634 *
1635 * This means that any domino which has a placement in _both_
1636 * chains of a pair must occupy one of those two placements, i.e.
1637 * we can rule that domino out anywhere else it might appear.
1638 */
1639 for (di = 0; di < sc->dc; di++) {
1640 struct solver_domino *d = &sc->dominoes[di];
1641
1642 if (d->nplacements <= 2)
1643 continue; /* not enough placements to rule one out */
1644
1645 for (j = 0; j+1 < d->nplacements; j++) {
1646 int ij = d->placements[j]->index;
1647 int cj = sc->pc_scratch[ij];
1648 for (k = j+1; k < d->nplacements; k++) {
1649 int ik = d->placements[k]->index;
1650 int ck = sc->pc_scratch[ik];
1651 if ((cj ^ ck) == 1) {
1652 /*
1653 * Placements j,k of domino d are in complementary
1654 * chains, so we can rule out all the others.
1655 */
1656 int i;
1657
1658#ifdef SOLVER_DIAGNOSTICS
1659 if (solver_diagnostics) {
1660 printf("domino %s occurs in both complementary "
1661 "forced chains:", d->name);
1662 for (i = 0; i < sc->pc; i++)
1663 if (sc->pc_scratch[i] == cj)
1664 printf(" %s", sc->placements[i].name);
1665 printf(" and");
1666 for (i = 0; i < sc->pc; i++)
1667 if (sc->pc_scratch[i] == ck)
1668 printf(" %s", sc->placements[i].name);
1669 printf("\n");
1670 }
1671#endif
1672
1673 for (i = d->nplacements; i-- > 0 ;)
1674 if (i != j && i != k)
1675 rule_out_placement(sc, d->placements[i]);
1676
1677 done_something = true;
1678 goto done_this_domino;
1679 }
1680 }
1681 }
1682
1683 done_this_domino:;
1684 }
1685
1686 return done_something;
1687}
1688
1689/*
1690 * Run the solver until it can't make any more progress.
1691 *
1692 * Return value is:
1693 * 0 = no solution exists (puzzle clues are unsatisfiable)
1694 * 1 = unique solution found (success!)
1695 * 2 = multiple possibilities remain (puzzle is ambiguous or solver is not
1696 * smart enough)
1697 */
1698static int run_solver(struct solver_scratch *sc, int max_diff_allowed)
1699{
1700 int di, si, pi;
1701 bool done_something;
1702
1703#ifdef SOLVER_DIAGNOSTICS
1704 if (solver_diagnostics) {
1705 int di, j;
1706 printf("Initial possible placements:\n");
1707 for (di = 0; di < sc->dc; di++) {
1708 struct solver_domino *d = &sc->dominoes[di];
1709 printf(" %s:", d->name);
1710 for (j = 0; j < d->nplacements; j++)
1711 printf(" %s", d->placements[j]->name);
1712 printf("\n");
1713 }
1714 }
1715#endif
1716
1717 do {
1718 done_something = false;
1719
1720 for (di = 0; di < sc->dc; di++)
1721 if (deduce_domino_single_placement(sc, di))
1722 done_something = true;
1723 if (done_something) {
1724 sc->max_diff_used = max(sc->max_diff_used, DIFF_TRIVIAL);
1725 continue;
1726 }
1727
1728 for (si = 0; si < sc->wh; si++)
1729 if (deduce_square_single_placement(sc, si))
1730 done_something = true;
1731 if (done_something) {
1732 sc->max_diff_used = max(sc->max_diff_used, DIFF_TRIVIAL);
1733 continue;
1734 }
1735
1736 if (max_diff_allowed <= DIFF_TRIVIAL)
1737 continue;
1738
1739 for (si = 0; si < sc->wh; si++)
1740 if (deduce_square_single_domino(sc, si))
1741 done_something = true;
1742 if (done_something) {
1743 sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
1744 continue;
1745 }
1746
1747 for (di = 0; di < sc->dc; di++)
1748 if (deduce_domino_must_overlap(sc, di))
1749 done_something = true;
1750 if (done_something) {
1751 sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
1752 continue;
1753 }
1754
1755 for (pi = 0; pi < sc->pc; pi++)
1756 if (deduce_local_duplicate(sc, pi))
1757 done_something = true;
1758 if (done_something) {
1759 sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
1760 continue;
1761 }
1762
1763 for (pi = 0; pi < sc->pc; pi++)
1764 if (deduce_local_duplicate_2(sc, pi))
1765 done_something = true;
1766 if (done_something) {
1767 sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
1768 continue;
1769 }
1770
1771 if (deduce_parity(sc))
1772 done_something = true;
1773 if (done_something) {
1774 sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
1775 continue;
1776 }
1777
1778 if (max_diff_allowed <= DIFF_BASIC)
1779 continue;
1780
1781 if (deduce_set(sc, false))
1782 done_something = true;
1783 if (done_something) {
1784 sc->max_diff_used = max(sc->max_diff_used, DIFF_HARD);
1785 continue;
1786 }
1787
1788 if (max_diff_allowed <= DIFF_HARD)
1789 continue;
1790
1791 if (deduce_set(sc, true))
1792 done_something = true;
1793 if (done_something) {
1794 sc->max_diff_used = max(sc->max_diff_used, DIFF_EXTREME);
1795 continue;
1796 }
1797
1798 if (deduce_forcing_chain(sc))
1799 done_something = true;
1800 if (done_something) {
1801 sc->max_diff_used = max(sc->max_diff_used, DIFF_EXTREME);
1802 continue;
1803 }
1804
1805 } while (done_something);
1806
1807#ifdef SOLVER_DIAGNOSTICS
1808 if (solver_diagnostics) {
1809 int di, j;
1810 printf("Final possible placements:\n");
1811 for (di = 0; di < sc->dc; di++) {
1812 struct solver_domino *d = &sc->dominoes[di];
1813 printf(" %s:", d->name);
1814 for (j = 0; j < d->nplacements; j++)
1815 printf(" %s", d->placements[j]->name);
1816 printf("\n");
1817 }
1818 }
1819#endif
1820
1821 for (di = 0; di < sc->dc; di++)
1822 if (sc->dominoes[di].nplacements == 0)
1823 return 0;
1824 for (di = 0; di < sc->dc; di++)
1825 if (sc->dominoes[di].nplacements > 1)
1826 return 2;
1827 return 1;
1828}
1829
1830/* ----------------------------------------------------------------------
1831 * Functions for generating a candidate puzzle (before we run the
1832 * solver to check it's soluble at the right difficulty level).
1833 */
1834
1835struct alloc_val;
1836struct alloc_loc;
1837
1838struct alloc_scratch {
1839 /* Game parameters. */
1840 int n, w, h, wh, dc;
1841
1842 /* The domino layout. Indexed by squares in the usual y*w+x raster
1843 * order: layout[i] gives the index of the other square in the
1844 * same domino as square i. */
1845 int *layout;
1846
1847 /* The output array, containing a number in every square. */
1848 int *numbers;
1849
1850 /* List of domino values (i.e. number pairs), indexed by DINDEX. */
1851 struct alloc_val *vals;
1852
1853 /* List of domino locations, indexed arbitrarily. */
1854 struct alloc_loc *locs;
1855
1856 /* Preallocated scratch spaces. */
1857 int *wh_scratch; /* size wh */
1858 int *wh2_scratch; /* size 2*wh */
1859};
1860
1861struct alloc_val {
1862 int lo, hi;
1863 bool confounder;
1864};
1865
1866struct alloc_loc {
1867 int sq[2];
1868};
1869
1870static struct alloc_scratch *alloc_make_scratch(int n)
1871{
1872 struct alloc_scratch *as = snew(struct alloc_scratch);
1873 int lo, hi;
1874
1875 as->n = n;
1876 as->w = n+2;
1877 as->h = n+1;
1878 as->wh = as->w * as->h;
1879 as->dc = DCOUNT(n);
1880
1881 as->layout = snewn(as->wh, int);
1882 as->numbers = snewn(as->wh, int);
1883 as->vals = snewn(as->dc, struct alloc_val);
1884 as->locs = snewn(as->dc, struct alloc_loc);
1885 as->wh_scratch = snewn(as->wh, int);
1886 as->wh2_scratch = snewn(as->wh * 2, int);
1887
1888 for (hi = 0; hi <= n; hi++)
1889 for (lo = 0; lo <= hi; lo++) {
1890 struct alloc_val *v = &as->vals[DINDEX(hi, lo)];
1891 v->lo = lo;
1892 v->hi = hi;
1893 }
1894
1895 return as;
1896}
1897
1898static void alloc_free_scratch(struct alloc_scratch *as)
1899{
1900 sfree(as->layout);
1901 sfree(as->numbers);
1902 sfree(as->vals);
1903 sfree(as->locs);
1904 sfree(as->wh_scratch);
1905 sfree(as->wh2_scratch);
1906 sfree(as);
1907}
1908
1909static void alloc_make_layout(struct alloc_scratch *as, random_state *rs)
1910{
1911 int i, pos;
1912
1913 domino_layout_prealloc(as->w, as->h, rs,
1914 as->layout, as->wh_scratch, as->wh2_scratch);
1915
1916 for (i = pos = 0; i < as->wh; i++) {
1917 if (as->layout[i] > i) {
1918 struct alloc_loc *loc;
1919 assert(pos < as->dc);
1920
1921 loc = &as->locs[pos++];
1922 loc->sq[0] = i;
1923 loc->sq[1] = as->layout[i];
1924 }
1925 }
1926 assert(pos == as->dc);
1927}
1928
1929static void alloc_trivial(struct alloc_scratch *as, random_state *rs)
1930{
1931 int i;
1932 for (i = 0; i < as->dc; i++)
1933 as->wh_scratch[i] = i;
1934 shuffle(as->wh_scratch, as->dc, sizeof(*as->wh_scratch), rs);
1935
1936 for (i = 0; i < as->dc; i++) {
1937 struct alloc_val *val = &as->vals[as->wh_scratch[i]];
1938 struct alloc_loc *loc = &as->locs[i];
1939 int which_lo = random_upto(rs, 2), which_hi = 1 - which_lo;
1940 as->numbers[loc->sq[which_lo]] = val->lo;
1941 as->numbers[loc->sq[which_hi]] = val->hi;
1942 }
1943}
1944
1945/*
1946 * Given a domino location in the form of two square indices, compute
1947 * the square indices of the domino location that would lie on one
1948 * side of it. Returns false if the location would be outside the
1949 * grid, or if it isn't actually a domino in the layout.
1950 */
1951static bool alloc_find_neighbour(
1952 struct alloc_scratch *as, int p0, int p1, int *n0, int *n1)
1953{
1954 int x0 = p0 % as->w, y0 = p0 / as->w, x1 = p1 % as->w, y1 = p1 / as->w;
1955 int dy = y1-y0, dx = x1-x0;
1956 int nx0 = x0 + dy, ny0 = y0 - dx, nx1 = x1 + dy, ny1 = y1 - dx;
1957 int np0, np1;
1958
1959 if (!(nx0 >= 0 && nx0 < as->w && ny0 >= 0 && ny0 < as->h &&
1960 nx1 >= 1 && nx1 < as->w && ny1 >= 1 && ny1 < as->h))
1961 return false; /* out of bounds */
1962
1963 np0 = ny0 * as->w + nx0;
1964 np1 = ny1 * as->w + nx1;
1965 if (as->layout[np0] != np1)
1966 return false; /* not a domino */
1967
1968 *n0 = np0;
1969 *n1 = np1;
1970 return true;
1971}
1972
1973static bool alloc_try_unique(struct alloc_scratch *as, random_state *rs)
1974{
1975 int i;
1976 for (i = 0; i < as->dc; i++)
1977 as->wh_scratch[i] = i;
1978 shuffle(as->wh_scratch, as->dc, sizeof(*as->wh_scratch), rs);
1979 for (i = 0; i < as->dc; i++)
1980 as->wh2_scratch[i] = i;
1981 shuffle(as->wh2_scratch, as->dc, sizeof(*as->wh2_scratch), rs);
1982
1983 for (i = 0; i < as->wh; i++)
1984 as->numbers[i] = -1;
1985
1986 for (i = 0; i < as->dc; i++) {
1987 struct alloc_val *val = &as->vals[as->wh_scratch[i]];
1988 struct alloc_loc *loc = &as->locs[as->wh2_scratch[i]];
1989 int which_lo, which_hi;
1990 bool can_lo_0 = true, can_lo_1 = true;
1991 int n0, n1;
1992
1993 /*
1994 * This is basically the same strategy as alloc_trivial:
1995 * simply iterate through the locations and values in random
1996 * relative order and pair them up. But we make sure to avoid
1997 * the most common, and also simplest, cause of a non-unique
1998 * solution:two dominoes side by side, sharing a number at
1999 * opposite ends. Any section of that form automatically leads
2000 * to an alternative solution:
2001 *
2002 * +-------+ +---+---+
2003 * | 1 2 | | 1 | 2 |
2004 * +-------+ <-> | | |
2005 * | 2 3 | | 2 | 3 |
2006 * +-------+ +---+---+
2007 *
2008 * So as we place each domino, we check for a neighbouring
2009 * domino on each side, and if there is one, rule out any
2010 * placement of _this_ domino that places a number diagonally
2011 * opposite the same number in the neighbour.
2012 *
2013 * Sometimes this can fail completely, if a domino on each
2014 * side is already placed and between them they rule out all
2015 * placements of this one. But it happens rarely enough that
2016 * it's fine to just abort and try the layout again.
2017 */
2018
2019 if (alloc_find_neighbour(as, loc->sq[0], loc->sq[1], &n0, &n1) &&
2020 (as->numbers[n0] == val->hi || as->numbers[n1] == val->lo))
2021 can_lo_0 = false;
2022 if (alloc_find_neighbour(as, loc->sq[1], loc->sq[0], &n0, &n1) &&
2023 (as->numbers[n0] == val->hi || as->numbers[n1] == val->lo))
2024 can_lo_1 = false;
2025
2026 if (!can_lo_0 && !can_lo_1)
2027 return false; /* layout failed */
2028 else if (can_lo_0 && can_lo_1)
2029 which_lo = random_upto(rs, 2);
2030 else
2031 which_lo = can_lo_0 ? 0 : 1;
2032
2033 which_hi = 1 - which_lo;
2034 as->numbers[loc->sq[which_lo]] = val->lo;
2035 as->numbers[loc->sq[which_hi]] = val->hi;
2036 }
2037
2038 return true;
2039}
2040
2041static bool alloc_try_hard(struct alloc_scratch *as, random_state *rs)
2042{
2043 int i, x, y, hi, lo, vals, locs, confounders_needed;
2044 bool ok;
2045
2046 for (i = 0; i < as->wh; i++)
2047 as->numbers[i] = -1;
2048
2049 /*
2050 * Shuffle the location indices.
2051 */
2052 for (i = 0; i < as->dc; i++)
2053 as->wh2_scratch[i] = i;
2054 shuffle(as->wh2_scratch, as->dc, sizeof(*as->wh2_scratch), rs);
2055
2056 /*
2057 * Start by randomly placing the double dominoes, to give a
2058 * starting instance of every number to try to put other things
2059 * next to.
2060 */
2061 for (i = 0; i <= as->n; i++)
2062 as->wh_scratch[i] = DINDEX(i, i);
2063 shuffle(as->wh_scratch, i, sizeof(*as->wh_scratch), rs);
2064 for (i = 0; i <= as->n; i++) {
2065 struct alloc_loc *loc = &as->locs[as->wh2_scratch[i]];
2066 as->numbers[loc->sq[0]] = as->numbers[loc->sq[1]] = i;
2067 }
2068
2069 /*
2070 * Find all the dominoes that don't yet have a _wrong_ placement
2071 * somewhere in the grid.
2072 */
2073 for (i = 0; i < as->dc; i++)
2074 as->vals[i].confounder = false;
2075 for (y = 0; y < as->h; y++) {
2076 for (x = 0; x < as->w; x++) {
2077 int p = y * as->w + x;
2078 if (as->numbers[p] == -1)
2079 continue;
2080
2081 if (x+1 < as->w) {
2082 int p1 = y * as->w + (x+1);
2083 if (as->layout[p] != p1 && as->numbers[p1] != -1)
2084 as->vals[DINDEX(as->numbers[p], as->numbers[p1])]
2085 .confounder = true;
2086 }
2087 if (y+1 < as->h) {
2088 int p1 = (y+1) * as->w + x;
2089 if (as->layout[p] != p1 && as->numbers[p1] != -1)
2090 as->vals[DINDEX(as->numbers[p], as->numbers[p1])]
2091 .confounder = true;
2092 }
2093 }
2094 }
2095
2096 for (i = confounders_needed = 0; i < as->dc; i++)
2097 if (!as->vals[i].confounder)
2098 confounders_needed++;
2099
2100 /*
2101 * Make a shuffled list of all the unplaced dominoes, and go
2102 * through it trying to find a placement for each one that also
2103 * fills in at least one of the needed confounders.
2104 */
2105 vals = 0;
2106 for (hi = 0; hi <= as->n; hi++)
2107 for (lo = 0; lo < hi; lo++)
2108 as->wh_scratch[vals++] = DINDEX(hi, lo);
2109 shuffle(as->wh_scratch, vals, sizeof(*as->wh_scratch), rs);
2110
2111 locs = as->dc;
2112
2113 while (vals > 0) {
2114 int valpos, valout, oldvals = vals;
2115
2116 for (valpos = valout = 0; valpos < vals; valpos++) {
2117 int validx = as->wh_scratch[valpos];
2118 struct alloc_val *val = &as->vals[validx];
2119 struct alloc_loc *loc;
2120 int locpos, si, which_lo;
2121
2122 for (locpos = 0; locpos < locs; locpos++) {
2123 int locidx = as->wh2_scratch[locpos];
2124 int wi, flip;
2125
2126 loc = &as->locs[locidx];
2127 if (as->numbers[loc->sq[0]] != -1)
2128 continue; /* this location is already filled */
2129
2130 flip = random_upto(rs, 2);
2131
2132 /* Try this location both ways round. */
2133 for (wi = 0; wi < 2; wi++) {
2134 int n0, n1;
2135
2136 which_lo = wi ^ flip;
2137
2138 /* First, do the same check as in alloc_try_unique, to
2139 * avoid making an obviously insoluble puzzle. */
2140 if (alloc_find_neighbour(as, loc->sq[which_lo],
2141 loc->sq[1-which_lo], &n0, &n1) &&
2142 (as->numbers[n0] == val->hi ||
2143 as->numbers[n1] == val->lo))
2144 break; /* can't place it this way round */
2145
2146 if (confounders_needed == 0)
2147 goto place_ok;
2148
2149 /* Look to see if we're adding at least one
2150 * previously absent confounder. */
2151 for (si = 0; si < 2; si++) {
2152 int x = loc->sq[si] % as->w, y = loc->sq[si] / as->w;
2153 int n = (si == which_lo ? val->lo : val->hi);
2154 int d;
2155 for (d = 0; d < 4; d++) {
2156 int dx = d==0 ? +1 : d==2 ? -1 : 0;
2157 int dy = d==1 ? +1 : d==3 ? -1 : 0;
2158 int x1 = x+dx, y1 = y+dy, p1 = y1 * as->w + x1;
2159 if (x1 >= 0 && x1 < as->w &&
2160 y1 >= 0 && y1 < as->h &&
2161 as->numbers[p1] != -1 &&
2162 !(as->vals[DINDEX(n, as->numbers[p1])]
2163 .confounder)) {
2164 /*
2165 * Place this domino.
2166 */
2167 goto place_ok;
2168 }
2169 }
2170 }
2171 }
2172 }
2173
2174 /* If we get here without executing 'goto place_ok', we
2175 * didn't find anywhere useful to put this domino. Put it
2176 * back on the list for the next pass. */
2177 as->wh_scratch[valout++] = validx;
2178 continue;
2179
2180 place_ok:;
2181
2182 /* We've found a domino to place. Place it, and fill in
2183 * all the confounders it adds. */
2184 as->numbers[loc->sq[which_lo]] = val->lo;
2185 as->numbers[loc->sq[1 - which_lo]] = val->hi;
2186
2187 for (si = 0; si < 2; si++) {
2188 int p = loc->sq[si];
2189 int n = as->numbers[p];
2190 int x = p % as->w, y = p / as->w;
2191 int d;
2192 for (d = 0; d < 4; d++) {
2193 int dx = d==0 ? +1 : d==2 ? -1 : 0;
2194 int dy = d==1 ? +1 : d==3 ? -1 : 0;
2195 int x1 = x+dx, y1 = y+dy, p1 = y1 * as->w + x1;
2196
2197 if (x1 >= 0 && x1 < as->w && y1 >= 0 && y1 < as->h &&
2198 p1 != loc->sq[1-si] && as->numbers[p1] != -1) {
2199 int di = DINDEX(n, as->numbers[p1]);
2200 if (!as->vals[di].confounder)
2201 confounders_needed--;
2202 as->vals[di].confounder = true;
2203 }
2204 }
2205 }
2206 }
2207
2208 vals = valout;
2209
2210 if (oldvals == vals)
2211 break;
2212 }
2213
2214 ok = true;
2215
2216 for (i = 0; i < as->dc; i++)
2217 if (!as->vals[i].confounder)
2218 ok = false;
2219 for (i = 0; i < as->wh; i++)
2220 if (as->numbers[i] == -1)
2221 ok = false;
2222
2223 return ok;
2224}
2225
2226static char *new_game_desc(const game_params *params, random_state *rs,
2227 char **aux, bool interactive)
2228{
2229 int n = params->n, w = n+2, h = n+1, wh = w*h, diff = params->diff;
2230 struct solver_scratch *sc;
2231 struct alloc_scratch *as;
2232 int i, j, k, len;
2233 char *ret;
2234
2235#ifndef OMIT_DIFFICULTY_CAP
2236 /*
2237 * Cap the difficulty level for small puzzles which would
2238 * otherwise become impossible to generate.
2239 *
2240 * Under an #ifndef, to make it easy to remove this cap for the
2241 * purpose of re-testing what it ought to be.
2242 */
2243 if (diff != DIFF_AMBIGUOUS) {
2244 if (n == 1 && diff > DIFF_TRIVIAL)
2245 diff = DIFF_TRIVIAL;
2246 if (n == 2 && diff > DIFF_BASIC)
2247 diff = DIFF_BASIC;
2248 }
2249#endif /* OMIT_DIFFICULTY_CAP */
2250
2251 /*
2252 * Allocate space in which to lay the grid out.
2253 */
2254 sc = solver_make_scratch(n);
2255 as = alloc_make_scratch(n);
2256
2257 /*
2258 * I haven't been able to think of any particularly clever
2259 * techniques for generating instances of Dominosa with a
2260 * unique solution. Many of the deductions used in this puzzle
2261 * are based on information involving half the grid at a time
2262 * (`of all the 6s, exactly one is next to a 3'), so a strategy
2263 * of partially solving the grid and then perturbing the place
2264 * where the solver got stuck seems particularly likely to
2265 * accidentally destroy the information which the solver had
2266 * used in getting that far. (Contrast with, say, Mines, in
2267 * which most deductions are local so this is an excellent
2268 * strategy.)
2269 *
2270 * Therefore I resort to the basest of brute force methods:
2271 * generate a random grid, see if it's solvable, throw it away
2272 * and try again if not. My only concession to sophistication
2273 * and cleverness is to at least _try_ not to generate obvious
2274 * 2x2 ambiguous sections (see comment below in the domino-
2275 * flipping section).
2276 *
2277 * During tests performed on 2005-07-15, I found that the brute
2278 * force approach without that tweak had to throw away about 87
2279 * grids on average (at the default n=6) before finding a
2280 * unique one, or a staggering 379 at n=9; good job the
2281 * generator and solver are fast! When I added the
2282 * ambiguous-section avoidance, those numbers came down to 19
2283 * and 26 respectively, which is a lot more sensible.
2284 */
2285
2286 while (1) {
2287 alloc_make_layout(as, rs);
2288
2289 if (diff == DIFF_AMBIGUOUS) {
2290 /* Just assign numbers to each domino completely at random. */
2291 alloc_trivial(as, rs);
2292 } else if (diff < DIFF_HARD) {
2293 /* Try to rule out the most common case of a non-unique solution */
2294 if (!alloc_try_unique(as, rs))
2295 continue;
2296 } else {
2297 /*
2298 * For Hard puzzles and above, we'd like there not to be
2299 * any easy toehold to start with.
2300 *
2301 * Mostly, that's arranged by alloc_try_hard, which will
2302 * ensure that no domino starts off with only one
2303 * potential placement. But a few other deductions
2304 * possible at Basic level can still sneak through the
2305 * cracks - for example, if the only two placements of one
2306 * domino overlap in a square, and you therefore rule out
2307 * some other domino that can use that square, you might
2308 * then find that _that_ domino now has only one
2309 * placement, and you've made a start.
2310 *
2311 * Of course, the main difficulty-level check will still
2312 * guarantee that you have to do a harder deduction
2313 * _somewhere_ in the grid. But it's more elegant if
2314 * there's nowhere obvious to get started at all.
2315 */
2316 int di;
2317 bool ok;
2318
2319 if (!alloc_try_hard(as, rs))
2320 continue;
2321
2322 solver_setup_grid(sc, as->numbers);
2323 if (run_solver(sc, DIFF_BASIC) < 2)
2324 continue;
2325
2326 ok = true;
2327 for (di = 0; di < sc->dc; di++)
2328 if (sc->dominoes[di].nplacements <= 1) {
2329 ok = false;
2330 break;
2331 }
2332
2333 if (!ok) {
2334 continue;
2335 }
2336 }
2337
2338 if (diff != DIFF_AMBIGUOUS) {
2339 int solver_result;
2340 solver_setup_grid(sc, as->numbers);
2341 solver_result = run_solver(sc, diff);
2342 if (solver_result > 1)
2343 continue; /* puzzle couldn't be solved at this difficulty */
2344 if (sc->max_diff_used < diff)
2345 continue; /* puzzle _could_ be solved at easier difficulty */
2346 }
2347
2348 break;
2349 }
2350
2351#ifdef GENERATION_DIAGNOSTICS
2352 for (j = 0; j < h; j++) {
2353 for (i = 0; i < w; i++) {
2354 putchar('0' + as->numbers[j*w+i]);
2355 }
2356 putchar('\n');
2357 }
2358 putchar('\n');
2359#endif
2360
2361 /*
2362 * Encode the resulting game state.
2363 *
2364 * Our encoding is a string of digits. Any number greater than
2365 * 9 is represented by a decimal integer within square
2366 * brackets. We know there are n+2 of every number (it's paired
2367 * with each number from 0 to n inclusive, and one of those is
2368 * itself so that adds another occurrence), so we can work out
2369 * the string length in advance.
2370 */
2371
2372 /*
2373 * To work out the total length of the decimal encodings of all
2374 * the numbers from 0 to n inclusive:
2375 * - every number has a units digit; total is n+1.
2376 * - all numbers above 9 have a tens digit; total is max(n+1-10,0).
2377 * - all numbers above 99 have a hundreds digit; total is max(n+1-100,0).
2378 * - and so on.
2379 */
2380 len = n+1;
2381 for (i = 10; i <= n; i *= 10)
2382 len += max(n + 1 - i, 0);
2383 /* Now add two square brackets for each number above 9. */
2384 len += 2 * max(n + 1 - 10, 0);
2385 /* And multiply by n+2 for the repeated occurrences of each number. */
2386 len *= n+2;
2387
2388 /*
2389 * Now actually encode the string.
2390 */
2391 ret = snewn(len+1, char);
2392 j = 0;
2393 for (i = 0; i < wh; i++) {
2394 k = as->numbers[i];
2395 if (k < 10)
2396 ret[j++] = '0' + k;
2397 else
2398 j += sprintf(ret+j, "[%d]", k);
2399 assert(j <= len);
2400 }
2401 assert(j == len);
2402 ret[j] = '\0';
2403
2404 /*
2405 * Encode the solved state as an aux_info.
2406 */
2407 {
2408 char *auxinfo = snewn(wh+1, char);
2409
2410 for (i = 0; i < wh; i++) {
2411 int v = as->layout[i];
2412 auxinfo[i] = (v == i+1 ? 'L' : v == i-1 ? 'R' :
2413 v == i+w ? 'T' : v == i-w ? 'B' : '.');
2414 }
2415 auxinfo[wh] = '\0';
2416
2417 *aux = auxinfo;
2418 }
2419
2420 solver_free_scratch(sc);
2421 alloc_free_scratch(as);
2422
2423 return ret;
2424}
2425
2426static const char *validate_desc(const game_params *params, const char *desc)
2427{
2428 int n = params->n, w = n+2, h = n+1, wh = w*h;
2429 int *occurrences;
2430 int i, j;
2431 const char *ret;
2432
2433 ret = NULL;
2434 occurrences = snewn(n+1, int);
2435 for (i = 0; i <= n; i++)
2436 occurrences[i] = 0;
2437
2438 for (i = 0; i < wh; i++) {
2439 if (!*desc) {
2440 ret = ret ? ret : "Game description is too short";
2441 } else {
2442 if (*desc >= '0' && *desc <= '9')
2443 j = *desc++ - '0';
2444 else if (*desc == '[') {
2445 desc++;
2446 j = atoi(desc);
2447 while (*desc && isdigit((unsigned char)*desc)) desc++;
2448 if (*desc != ']')
2449 ret = ret ? ret : "Missing ']' in game description";
2450 else
2451 desc++;
2452 } else {
2453 j = -1;
2454 ret = ret ? ret : "Invalid syntax in game description";
2455 }
2456 if (j < 0 || j > n)
2457 ret = ret ? ret : "Number out of range in game description";
2458 else
2459 occurrences[j]++;
2460 }
2461 }
2462
2463 if (*desc)
2464 ret = ret ? ret : "Game description is too long";
2465
2466 if (!ret) {
2467 for (i = 0; i <= n; i++)
2468 if (occurrences[i] != n+2)
2469 ret = "Incorrect number balance in game description";
2470 }
2471
2472 sfree(occurrences);
2473
2474 return ret;
2475}
2476
2477static game_state *new_game(midend *me, const game_params *params,
2478 const char *desc)
2479{
2480 int n = params->n, w = n+2, h = n+1, wh = w*h;
2481 game_state *state = snew(game_state);
2482 int i, j;
2483
2484 state->params = *params;
2485 state->w = w;
2486 state->h = h;
2487
2488 state->grid = snewn(wh, int);
2489 for (i = 0; i < wh; i++)
2490 state->grid[i] = i;
2491
2492 state->edges = snewn(wh, unsigned short);
2493 for (i = 0; i < wh; i++)
2494 state->edges[i] = 0;
2495
2496 state->numbers = snew(struct game_numbers);
2497 state->numbers->refcount = 1;
2498 state->numbers->numbers = snewn(wh, int);
2499
2500 for (i = 0; i < wh; i++) {
2501 assert(*desc);
2502 if (*desc >= '0' && *desc <= '9')
2503 j = *desc++ - '0';
2504 else {
2505 assert(*desc == '[');
2506 desc++;
2507 j = atoi(desc);
2508 while (*desc && isdigit((unsigned char)*desc)) desc++;
2509 assert(*desc == ']');
2510 desc++;
2511 }
2512 assert(j >= 0 && j <= n);
2513 state->numbers->numbers[i] = j;
2514 }
2515
2516 state->completed = false;
2517 state->cheated = false;
2518
2519 return state;
2520}
2521
2522static game_state *dup_game(const game_state *state)
2523{
2524 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
2525 game_state *ret = snew(game_state);
2526
2527 ret->params = state->params;
2528 ret->w = state->w;
2529 ret->h = state->h;
2530 ret->grid = snewn(wh, int);
2531 memcpy(ret->grid, state->grid, wh * sizeof(int));
2532 ret->edges = snewn(wh, unsigned short);
2533 memcpy(ret->edges, state->edges, wh * sizeof(unsigned short));
2534 ret->numbers = state->numbers;
2535 ret->numbers->refcount++;
2536 ret->completed = state->completed;
2537 ret->cheated = state->cheated;
2538
2539 return ret;
2540}
2541
2542static void free_game(game_state *state)
2543{
2544 sfree(state->grid);
2545 sfree(state->edges);
2546 if (--state->numbers->refcount <= 0) {
2547 sfree(state->numbers->numbers);
2548 sfree(state->numbers);
2549 }
2550 sfree(state);
2551}
2552
2553static char *solution_move_string(struct solver_scratch *sc)
2554{
2555 char *ret;
2556 int retlen, retsize;
2557 int i, pass;
2558
2559 /*
2560 * First make a pass putting in edges for -1, then make a pass
2561 * putting in dominoes for +1.
2562 */
2563 retsize = 256;
2564 ret = snewn(retsize, char);
2565 retlen = sprintf(ret, "S");
2566
2567 for (pass = 0; pass < 2; pass++) {
2568 char type = "ED"[pass];
2569
2570 for (i = 0; i < sc->pc; i++) {
2571 struct solver_placement *p = &sc->placements[i];
2572 char buf[80];
2573 int extra;
2574
2575 if (pass == 0) {
2576 /* Emit a barrier if this placement is ruled out for
2577 * the domino. */
2578 if (p->active)
2579 continue;
2580 } else {
2581 /* Emit a domino if this placement is the only one not
2582 * ruled out. */
2583 if (!p->active || p->domino->nplacements > 1)
2584 continue;
2585 }
2586
2587 extra = sprintf(buf, ";%c%d,%d", type,
2588 p->squares[0]->index, p->squares[1]->index);
2589
2590 if (retlen + extra + 1 >= retsize) {
2591 retsize = retlen + extra + 256;
2592 ret = sresize(ret, retsize, char);
2593 }
2594 strcpy(ret + retlen, buf);
2595 retlen += extra;
2596 }
2597 }
2598
2599 return ret;
2600}
2601
2602static char *solve_game(const game_state *state, const game_state *currstate,
2603 const char *aux, const char **error)
2604{
2605 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
2606 char *ret;
2607 int retlen, retsize;
2608 int i;
2609 char buf[80];
2610 int extra;
2611
2612 if (aux) {
2613 retsize = 256;
2614 ret = snewn(retsize, char);
2615 retlen = sprintf(ret, "S");
2616
2617 for (i = 0; i < wh; i++) {
2618 if (aux[i] == 'L')
2619 extra = sprintf(buf, ";D%d,%d", i, i+1);
2620 else if (aux[i] == 'T')
2621 extra = sprintf(buf, ";D%d,%d", i, i+w);
2622 else
2623 continue;
2624
2625 if (retlen + extra + 1 >= retsize) {
2626 retsize = retlen + extra + 256;
2627 ret = sresize(ret, retsize, char);
2628 }
2629 strcpy(ret + retlen, buf);
2630 retlen += extra;
2631 }
2632
2633 } else {
2634 struct solver_scratch *sc = solver_make_scratch(n);
2635 solver_setup_grid(sc, state->numbers->numbers);
2636 run_solver(sc, DIFFCOUNT);
2637 ret = solution_move_string(sc);
2638 solver_free_scratch(sc);
2639 }
2640
2641 return ret;
2642}
2643
2644static bool game_can_format_as_text_now(const game_params *params)
2645{
2646 return params->n < 1000;
2647}
2648
2649static void draw_domino(char *board, int start, char corner,
2650 int dshort, int nshort, char cshort,
2651 int dlong, int nlong, char clong)
2652{
2653 int go_short = nshort*dshort, go_long = nlong*dlong, i;
2654
2655 board[start] = corner;
2656 board[start + go_short] = corner;
2657 board[start + go_long] = corner;
2658 board[start + go_short + go_long] = corner;
2659
2660 for (i = 1; i < nshort; ++i) {
2661 int j = start + i*dshort, k = start + i*dshort + go_long;
2662 if (board[j] != corner) board[j] = cshort;
2663 if (board[k] != corner) board[k] = cshort;
2664 }
2665
2666 for (i = 1; i < nlong; ++i) {
2667 int j = start + i*dlong, k = start + i*dlong + go_short;
2668 if (board[j] != corner) board[j] = clong;
2669 if (board[k] != corner) board[k] = clong;
2670 }
2671}
2672
2673static char *game_text_format(const game_state *state)
2674{
2675 int w = state->w, h = state->h, r, c;
2676 int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh;
2677 char *board = snewn(len + 1, char);
2678
2679 memset(board, ' ', len);
2680
2681 for (r = 0; r < h; ++r) {
2682 for (c = 0; c < w; ++c) {
2683 int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
2684 int i = r*w + c, num = state->numbers->numbers[i];
2685
2686 if (num < 100) {
2687 board[center] = '0' + num % 10;
2688 if (num >= 10) board[center - 1] = '0' + num / 10;
2689 } else {
2690 board[center+1] = '0' + num % 10;
2691 board[center] = '0' + num / 10 % 10;
2692 board[center-1] = '0' + num / 100;
2693 }
2694
2695 if (state->edges[i] & EDGE_L) board[center - cw/2] = '|';
2696 if (state->edges[i] & EDGE_R) board[center + cw/2] = '|';
2697 if (state->edges[i] & EDGE_T) board[center - gw] = '-';
2698 if (state->edges[i] & EDGE_B) board[center + gw] = '-';
2699
2700 if (state->grid[i] == i) continue; /* no domino pairing */
2701 if (state->grid[i] < i) continue; /* already done */
2702 assert (state->grid[i] == i + 1 || state->grid[i] == i + w);
2703 if (state->grid[i] == i + 1)
2704 draw_domino(board, cell, '+', gw, ch, '|', +1, 2*cw, '-');
2705 else if (state->grid[i] == i + w)
2706 draw_domino(board, cell, '+', +1, cw, '-', gw, 2*ch, '|');
2707 }
2708 board[r*ch*gw + gw - 1] = '\n';
2709 board[r*ch*gw + gw + gw - 1] = '\n';
2710 }
2711 board[len - 1] = '\n';
2712 board[len] = '\0';
2713 return board;
2714}
2715
2716struct game_ui {
2717 int cur_x, cur_y, highlight_1, highlight_2;
2718 bool cur_visible;
2719};
2720
2721static game_ui *new_ui(const game_state *state)
2722{
2723 game_ui *ui = snew(game_ui);
2724 ui->cur_x = ui->cur_y = 0;
2725 ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false);
2726 ui->highlight_1 = ui->highlight_2 = -1;
2727 return ui;
2728}
2729
2730static void free_ui(game_ui *ui)
2731{
2732 sfree(ui);
2733}
2734
2735static void game_changed_state(game_ui *ui, const game_state *oldstate,
2736 const game_state *newstate)
2737{
2738 if (!oldstate->completed && newstate->completed)
2739 ui->cur_visible = false;
2740}
2741
2742static const char *current_key_label(const game_ui *ui,
2743 const game_state *state, int button)
2744{
2745 if (IS_CURSOR_SELECT(button)) {
2746 int d1, d2, w = state->w;
2747
2748 if (!((ui->cur_x ^ ui->cur_y) & 1))
2749 return ""; /* must have exactly one dimension odd */
2750 d1 = (ui->cur_y / 2) * w + (ui->cur_x / 2);
2751 d2 = ((ui->cur_y+1) / 2) * w + ((ui->cur_x+1) / 2);
2752
2753 /* We can't mark an edge next to any domino. */
2754 if (button == CURSOR_SELECT2 &&
2755 (state->grid[d1] != d1 || state->grid[d2] != d2))
2756 return "";
2757 if (button == CURSOR_SELECT) {
2758 if (state->grid[d1] == d2) return "Remove";
2759 return "Place";
2760 } else {
2761 int edge = d2 == d1 + 1 ? EDGE_R : EDGE_B;
2762 if (state->edges[d1] & edge) return "Remove";
2763 return "Line";
2764 }
2765 }
2766 return "";
2767}
2768
2769#define PREFERRED_TILESIZE 32
2770#define TILESIZE (ds->tilesize)
2771#define BORDER (TILESIZE * 3 / 4)
2772#define DOMINO_GUTTER (TILESIZE / 16)
2773#define DOMINO_RADIUS (TILESIZE / 8)
2774#define DOMINO_COFFSET (DOMINO_GUTTER + DOMINO_RADIUS)
2775#define CURSOR_RADIUS (TILESIZE / 4)
2776
2777#define COORD(x) ( (x) * TILESIZE + BORDER )
2778#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
2779
2780struct game_drawstate {
2781 int w, h, tilesize;
2782 unsigned long *visible;
2783};
2784
2785static char *interpret_move(const game_state *state, game_ui *ui,
2786 const game_drawstate *ds,
2787 int x, int y, int button)
2788{
2789 int w = state->w, h = state->h;
2790 char buf[80];
2791
2792 /*
2793 * A left-click between two numbers toggles a domino covering
2794 * them. A right-click toggles an edge.
2795 */
2796 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2797 int tx = FROMCOORD(x), ty = FROMCOORD(y), t = ty*w+tx;
2798 int dx, dy;
2799 int d1, d2;
2800
2801 if (tx < 0 || tx >= w || ty < 0 || ty >= h)
2802 return MOVE_UNUSED;
2803
2804 /*
2805 * Now we know which square the click was in, decide which
2806 * edge of the square it was closest to.
2807 */
2808 dx = 2 * (x - COORD(tx)) - TILESIZE;
2809 dy = 2 * (y - COORD(ty)) - TILESIZE;
2810
2811 if (abs(dx) > abs(dy) && dx < 0 && tx > 0)
2812 d1 = t - 1, d2 = t; /* clicked in right side of domino */
2813 else if (abs(dx) > abs(dy) && dx > 0 && tx+1 < w)
2814 d1 = t, d2 = t + 1; /* clicked in left side of domino */
2815 else if (abs(dy) > abs(dx) && dy < 0 && ty > 0)
2816 d1 = t - w, d2 = t; /* clicked in bottom half of domino */
2817 else if (abs(dy) > abs(dx) && dy > 0 && ty+1 < h)
2818 d1 = t, d2 = t + w; /* clicked in top half of domino */
2819 else
2820 return MOVE_NO_EFFECT; /* clicked precisely on a diagonal */
2821
2822 /*
2823 * We can't mark an edge next to any domino.
2824 */
2825 if (button == RIGHT_BUTTON &&
2826 (state->grid[d1] != d1 || state->grid[d2] != d2))
2827 return MOVE_NO_EFFECT;
2828
2829 ui->cur_visible = false;
2830 sprintf(buf, "%c%d,%d", (int)(button == RIGHT_BUTTON ? 'E' : 'D'), d1, d2);
2831 return dupstr(buf);
2832 } else if (IS_CURSOR_MOVE(button)) {
2833 return move_cursor(button, &ui->cur_x, &ui->cur_y, 2*w-1, 2*h-1, false,
2834 &ui->cur_visible);
2835 } else if (IS_CURSOR_SELECT(button)) {
2836 int d1, d2;
2837
2838 if (!((ui->cur_x ^ ui->cur_y) & 1))
2839 return MOVE_NO_EFFECT; /* must have exactly one dimension odd */
2840 d1 = (ui->cur_y / 2) * w + (ui->cur_x / 2);
2841 d2 = ((ui->cur_y+1) / 2) * w + ((ui->cur_x+1) / 2);
2842
2843 /*
2844 * We can't mark an edge next to any domino.
2845 */
2846 if (button == CURSOR_SELECT2 &&
2847 (state->grid[d1] != d1 || state->grid[d2] != d2))
2848 return MOVE_NO_EFFECT;
2849
2850 sprintf(buf, "%c%d,%d", (int)(button == CURSOR_SELECT2 ? 'E' : 'D'), d1, d2);
2851 return dupstr(buf);
2852 } else if (isdigit(button & ~MOD_NUM_KEYPAD)) {
2853 int n = state->params.n, num = (button & ~MOD_NUM_KEYPAD) - '0';
2854 if (num > n) {
2855 return MOVE_UNUSED;
2856 } else if (ui->highlight_1 == num) {
2857 ui->highlight_1 = -1;
2858 } else if (ui->highlight_2 == num) {
2859 ui->highlight_2 = -1;
2860 } else if (ui->highlight_1 == -1) {
2861 ui->highlight_1 = num;
2862 } else if (ui->highlight_2 == -1) {
2863 ui->highlight_2 = num;
2864 } else {
2865 return MOVE_NO_EFFECT;
2866 }
2867 return MOVE_UI_UPDATE;
2868 }
2869
2870 return MOVE_UNUSED;
2871}
2872
2873static game_state *execute_move(const game_state *state, const char *move)
2874{
2875 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
2876 int d1, d2, d3, p;
2877 game_state *ret = dup_game(state);
2878
2879 while (*move) {
2880 if (move[0] == 'S') {
2881 int i;
2882
2883 ret->cheated = true;
2884
2885 /*
2886 * Clear the existing edges and domino placements. We
2887 * expect the S to be followed by other commands.
2888 */
2889 for (i = 0; i < wh; i++) {
2890 ret->grid[i] = i;
2891 ret->edges[i] = 0;
2892 }
2893 move++;
2894 } else if (move[0] == 'D' &&
2895 sscanf(move+1, "%d,%d%n", &d1, &d2, &p) == 2 &&
2896 d1 >= 0 && d1 < wh && d2 >= 0 && d2 < wh && d1 < d2 &&
2897 (d2 - d1 == 1 || d2 - d1 == w)) {
2898
2899 /*
2900 * Toggle domino presence between d1 and d2.
2901 */
2902 if (ret->grid[d1] == d2) {
2903 assert(ret->grid[d2] == d1);
2904 ret->grid[d1] = d1;
2905 ret->grid[d2] = d2;
2906 } else {
2907 /*
2908 * Erase any dominoes that might overlap the new one.
2909 */
2910 d3 = ret->grid[d1];
2911 if (d3 != d1)
2912 ret->grid[d3] = d3;
2913 d3 = ret->grid[d2];
2914 if (d3 != d2)
2915 ret->grid[d3] = d3;
2916 /*
2917 * Place the new one.
2918 */
2919 ret->grid[d1] = d2;
2920 ret->grid[d2] = d1;
2921
2922 /*
2923 * Destroy any edges lurking around it.
2924 */
2925 if (ret->edges[d1] & EDGE_L) {
2926 assert(d1 - 1 >= 0);
2927 ret->edges[d1 - 1] &= ~EDGE_R;
2928 }
2929 if (ret->edges[d1] & EDGE_R) {
2930 assert(d1 + 1 < wh);
2931 ret->edges[d1 + 1] &= ~EDGE_L;
2932 }
2933 if (ret->edges[d1] & EDGE_T) {
2934 assert(d1 - w >= 0);
2935 ret->edges[d1 - w] &= ~EDGE_B;
2936 }
2937 if (ret->edges[d1] & EDGE_B) {
2938 assert(d1 + 1 < wh);
2939 ret->edges[d1 + w] &= ~EDGE_T;
2940 }
2941 ret->edges[d1] = 0;
2942 if (ret->edges[d2] & EDGE_L) {
2943 assert(d2 - 1 >= 0);
2944 ret->edges[d2 - 1] &= ~EDGE_R;
2945 }
2946 if (ret->edges[d2] & EDGE_R) {
2947 assert(d2 + 1 < wh);
2948 ret->edges[d2 + 1] &= ~EDGE_L;
2949 }
2950 if (ret->edges[d2] & EDGE_T) {
2951 assert(d2 - w >= 0);
2952 ret->edges[d2 - w] &= ~EDGE_B;
2953 }
2954 if (ret->edges[d2] & EDGE_B) {
2955 assert(d2 + 1 < wh);
2956 ret->edges[d2 + w] &= ~EDGE_T;
2957 }
2958 ret->edges[d2] = 0;
2959 }
2960
2961 move += p+1;
2962 } else if (move[0] == 'E' &&
2963 sscanf(move+1, "%d,%d%n", &d1, &d2, &p) == 2 &&
2964 d1 >= 0 && d1 < wh && d2 >= 0 && d2 < wh && d1 < d2 &&
2965 ret->grid[d1] == d1 && ret->grid[d2] == d2 &&
2966 (d2 - d1 == 1 || d2 - d1 == w)) {
2967
2968 /*
2969 * Toggle edge presence between d1 and d2.
2970 */
2971 if (d2 == d1 + 1) {
2972 ret->edges[d1] ^= EDGE_R;
2973 ret->edges[d2] ^= EDGE_L;
2974 } else {
2975 ret->edges[d1] ^= EDGE_B;
2976 ret->edges[d2] ^= EDGE_T;
2977 }
2978
2979 move += p+1;
2980 } else {
2981 free_game(ret);
2982 return NULL;
2983 }
2984
2985 if (*move) {
2986 if (*move != ';') {
2987 free_game(ret);
2988 return NULL;
2989 }
2990 move++;
2991 }
2992 }
2993
2994 /*
2995 * After modifying the grid, check completion.
2996 */
2997 if (!ret->completed) {
2998 int i, ok = 0;
2999 bool *used = snewn(TRI(n+1), bool);
3000
3001 memset(used, 0, TRI(n+1));
3002 for (i = 0; i < wh; i++)
3003 if (ret->grid[i] > i) {
3004 int n1, n2, di;
3005
3006 n1 = ret->numbers->numbers[i];
3007 n2 = ret->numbers->numbers[ret->grid[i]];
3008
3009 di = DINDEX(n1, n2);
3010 assert(di >= 0 && di < TRI(n+1));
3011
3012 if (!used[di]) {
3013 used[di] = true;
3014 ok++;
3015 }
3016 }
3017
3018 sfree(used);
3019 if (ok == DCOUNT(n))
3020 ret->completed = true;
3021 }
3022
3023 return ret;
3024}
3025
3026/* ----------------------------------------------------------------------
3027 * Drawing routines.
3028 */
3029
3030static void game_compute_size(const game_params *params, int tilesize,
3031 const game_ui *ui, int *x, int *y)
3032{
3033 int n = params->n, w = n+2, h = n+1;
3034
3035 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3036 struct { int tilesize; } ads, *ds = &ads;
3037 ads.tilesize = tilesize;
3038
3039 *x = w * TILESIZE + 2*BORDER;
3040 *y = h * TILESIZE + 2*BORDER;
3041}
3042
3043static void game_set_size(drawing *dr, game_drawstate *ds,
3044 const game_params *params, int tilesize)
3045{
3046 ds->tilesize = tilesize;
3047}
3048
3049static float *game_colours(frontend *fe, int *ncolours)
3050{
3051 float *ret = snewn(3 * NCOLOURS, float);
3052
3053 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
3054
3055 ret[COL_TEXT * 3 + 0] = 0.0F;
3056 ret[COL_TEXT * 3 + 1] = 0.0F;
3057 ret[COL_TEXT * 3 + 2] = 0.0F;
3058
3059 ret[COL_DOMINO * 3 + 0] = 0.0F;
3060 ret[COL_DOMINO * 3 + 1] = 0.0F;
3061 ret[COL_DOMINO * 3 + 2] = 0.0F;
3062
3063 ret[COL_DOMINOCLASH * 3 + 0] = 0.5F;
3064 ret[COL_DOMINOCLASH * 3 + 1] = 0.0F;
3065 ret[COL_DOMINOCLASH * 3 + 2] = 0.0F;
3066
3067 ret[COL_DOMINOTEXT * 3 + 0] = 1.0F;
3068 ret[COL_DOMINOTEXT * 3 + 1] = 1.0F;
3069 ret[COL_DOMINOTEXT * 3 + 2] = 1.0F;
3070
3071 ret[COL_EDGE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2 / 3;
3072 ret[COL_EDGE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2 / 3;
3073 ret[COL_EDGE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2 / 3;
3074
3075 ret[COL_HIGHLIGHT_1 * 3 + 0] = 0.85;
3076 ret[COL_HIGHLIGHT_1 * 3 + 1] = 0.20;
3077 ret[COL_HIGHLIGHT_1 * 3 + 2] = 0.20;
3078
3079 ret[COL_HIGHLIGHT_2 * 3 + 0] = 0.30;
3080 ret[COL_HIGHLIGHT_2 * 3 + 1] = 0.85;
3081 ret[COL_HIGHLIGHT_2 * 3 + 2] = 0.20;
3082
3083 *ncolours = NCOLOURS;
3084 return ret;
3085}
3086
3087static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
3088{
3089 struct game_drawstate *ds = snew(struct game_drawstate);
3090 int i;
3091
3092 ds->w = state->w;
3093 ds->h = state->h;
3094 ds->visible = snewn(ds->w * ds->h, unsigned long);
3095 ds->tilesize = 0; /* not decided yet */
3096 for (i = 0; i < ds->w * ds->h; i++)
3097 ds->visible[i] = 0xFFFF;
3098
3099 return ds;
3100}
3101
3102static void game_free_drawstate(drawing *dr, game_drawstate *ds)
3103{
3104 sfree(ds->visible);
3105 sfree(ds);
3106}
3107
3108enum {
3109 TYPE_L,
3110 TYPE_R,
3111 TYPE_T,
3112 TYPE_B,
3113 TYPE_BLANK,
3114 TYPE_MASK = 0x0F
3115};
3116
3117/* These flags must be disjoint with:
3118 * the above enum (TYPE_*) [0x000 -- 0x00F]
3119 * EDGE_* [0x100 -- 0xF00]
3120 * and must fit into an unsigned long (32 bits).
3121 */
3122#define DF_HIGHLIGHT_1 0x10
3123#define DF_HIGHLIGHT_2 0x20
3124#define DF_FLASH 0x40
3125#define DF_CLASH 0x80
3126
3127#define DF_CURSOR 0x01000
3128#define DF_CURSOR_USEFUL 0x02000
3129#define DF_CURSOR_XBASE 0x10000
3130#define DF_CURSOR_XMASK 0x30000
3131#define DF_CURSOR_YBASE 0x40000
3132#define DF_CURSOR_YMASK 0xC0000
3133
3134#define CEDGE_OFF (TILESIZE / 8)
3135#define IS_EMPTY(s,x,y) ((s)->grid[(y)*(s)->w+(x)] == ((y)*(s)->w+(x)))
3136
3137static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state,
3138 int x, int y, int type, int highlight_1, int highlight_2)
3139{
3140 int w = state->w /*, h = state->h */;
3141 int cx = COORD(x), cy = COORD(y);
3142 int nc;
3143 char str[80];
3144 int flags;
3145
3146 clip(dr, cx, cy, TILESIZE, TILESIZE);
3147 draw_rect(dr, cx, cy, TILESIZE, TILESIZE, COL_BACKGROUND);
3148
3149 flags = type &~ TYPE_MASK;
3150 type &= TYPE_MASK;
3151
3152 if (type != TYPE_BLANK) {
3153 int i, bg;
3154
3155 /*
3156 * Draw one end of a domino. This is composed of:
3157 *
3158 * - two filled circles (rounded corners)
3159 * - two rectangles
3160 * - a slight shift in the number
3161 */
3162
3163 if (flags & DF_CLASH)
3164 bg = COL_DOMINOCLASH;
3165 else
3166 bg = COL_DOMINO;
3167 nc = COL_DOMINOTEXT;
3168
3169 if (flags & DF_FLASH) {
3170 int tmp = nc;
3171 nc = bg;
3172 bg = tmp;
3173 }
3174
3175 if (type == TYPE_L || type == TYPE_T)
3176 draw_circle(dr, cx+DOMINO_COFFSET, cy+DOMINO_COFFSET,
3177 DOMINO_RADIUS, bg, bg);
3178 if (type == TYPE_R || type == TYPE_T)
3179 draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET, cy+DOMINO_COFFSET,
3180 DOMINO_RADIUS, bg, bg);
3181 if (type == TYPE_L || type == TYPE_B)
3182 draw_circle(dr, cx+DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET,
3183 DOMINO_RADIUS, bg, bg);
3184 if (type == TYPE_R || type == TYPE_B)
3185 draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET,
3186 cy+TILESIZE-1-DOMINO_COFFSET,
3187 DOMINO_RADIUS, bg, bg);
3188
3189 for (i = 0; i < 2; i++) {
3190 int x1, y1, x2, y2;
3191
3192 x1 = cx + (i ? DOMINO_GUTTER : DOMINO_COFFSET);
3193 y1 = cy + (i ? DOMINO_COFFSET : DOMINO_GUTTER);
3194 x2 = cx + TILESIZE-1 - (i ? DOMINO_GUTTER : DOMINO_COFFSET);
3195 y2 = cy + TILESIZE-1 - (i ? DOMINO_COFFSET : DOMINO_GUTTER);
3196 if (type == TYPE_L)
3197 x2 = cx + TILESIZE + TILESIZE/16;
3198 else if (type == TYPE_R)
3199 x1 = cx - TILESIZE/16;
3200 else if (type == TYPE_T)
3201 y2 = cy + TILESIZE + TILESIZE/16;
3202 else if (type == TYPE_B)
3203 y1 = cy - TILESIZE/16;
3204
3205 draw_rect(dr, x1, y1, x2-x1+1, y2-y1+1, bg);
3206 }
3207 } else {
3208 if (flags & EDGE_T)
3209 draw_rect(dr, cx+DOMINO_GUTTER, cy,
3210 TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE);
3211 if (flags & EDGE_B)
3212 draw_rect(dr, cx+DOMINO_GUTTER, cy+TILESIZE-1,
3213 TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE);
3214 if (flags & EDGE_L)
3215 draw_rect(dr, cx, cy+DOMINO_GUTTER,
3216 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE);
3217 if (flags & EDGE_R)
3218 draw_rect(dr, cx+TILESIZE-1, cy+DOMINO_GUTTER,
3219 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE);
3220 nc = COL_TEXT;
3221 }
3222
3223 if (flags & DF_CURSOR) {
3224 int curx = ((flags & DF_CURSOR_XMASK) / DF_CURSOR_XBASE) & 3;
3225 int cury = ((flags & DF_CURSOR_YMASK) / DF_CURSOR_YBASE) & 3;
3226 int ox = cx + curx*TILESIZE/2;
3227 int oy = cy + cury*TILESIZE/2;
3228
3229 draw_rect_corners(dr, ox, oy, CURSOR_RADIUS, nc);
3230 if (flags & DF_CURSOR_USEFUL)
3231 draw_rect_corners(dr, ox, oy, CURSOR_RADIUS+1, nc);
3232 }
3233
3234 if (flags & DF_HIGHLIGHT_1) {
3235 nc = COL_HIGHLIGHT_1;
3236 } else if (flags & DF_HIGHLIGHT_2) {
3237 nc = COL_HIGHLIGHT_2;
3238 }
3239
3240 sprintf(str, "%d", state->numbers->numbers[y*w+x]);
3241 draw_text(dr, cx+TILESIZE/2, cy+TILESIZE/2, FONT_VARIABLE, TILESIZE/2,
3242 ALIGN_HCENTRE | ALIGN_VCENTRE, nc, str);
3243
3244 draw_update(dr, cx, cy, TILESIZE, TILESIZE);
3245 unclip(dr);
3246}
3247
3248static void game_redraw(drawing *dr, game_drawstate *ds,
3249 const game_state *oldstate, const game_state *state,
3250 int dir, const game_ui *ui,
3251 float animtime, float flashtime)
3252{
3253 int n = state->params.n, w = state->w, h = state->h, wh = w*h;
3254 int x, y, i;
3255 unsigned char *used;
3256
3257 /*
3258 * See how many dominoes of each type there are, so we can
3259 * highlight clashes in red.
3260 */
3261 used = snewn(TRI(n+1), unsigned char);
3262 memset(used, 0, TRI(n+1));
3263 for (i = 0; i < wh; i++)
3264 if (state->grid[i] > i) {
3265 int n1, n2, di;
3266
3267 n1 = state->numbers->numbers[i];
3268 n2 = state->numbers->numbers[state->grid[i]];
3269
3270 di = DINDEX(n1, n2);
3271 assert(di >= 0 && di < TRI(n+1));
3272
3273 if (used[di] < 2)
3274 used[di]++;
3275 }
3276
3277 for (y = 0; y < h; y++)
3278 for (x = 0; x < w; x++) {
3279 int n = y*w+x;
3280 int n1, n2, di;
3281 unsigned long c;
3282
3283 if (state->grid[n] == n-1)
3284 c = TYPE_R;
3285 else if (state->grid[n] == n+1)
3286 c = TYPE_L;
3287 else if (state->grid[n] == n-w)
3288 c = TYPE_B;
3289 else if (state->grid[n] == n+w)
3290 c = TYPE_T;
3291 else
3292 c = TYPE_BLANK;
3293
3294 n1 = state->numbers->numbers[n];
3295 if (c != TYPE_BLANK) {
3296 n2 = state->numbers->numbers[state->grid[n]];
3297 di = DINDEX(n1, n2);
3298 if (used[di] > 1)
3299 c |= DF_CLASH; /* highlight a clash */
3300 } else {
3301 c |= state->edges[n];
3302 }
3303
3304 if (n1 == ui->highlight_1)
3305 c |= DF_HIGHLIGHT_1;
3306 if (n1 == ui->highlight_2)
3307 c |= DF_HIGHLIGHT_2;
3308
3309 if (flashtime != 0)
3310 c |= DF_FLASH; /* we're flashing */
3311
3312 if (ui->cur_visible) {
3313 unsigned curx = (unsigned)(ui->cur_x - (2*x-1));
3314 unsigned cury = (unsigned)(ui->cur_y - (2*y-1));
3315 if (curx < 3 && cury < 3) {
3316 c |= (DF_CURSOR |
3317 (curx * DF_CURSOR_XBASE) |
3318 (cury * DF_CURSOR_YBASE));
3319 if ((ui->cur_x ^ ui->cur_y) & 1)
3320 c |= DF_CURSOR_USEFUL;
3321 }
3322 }
3323
3324 if (ds->visible[n] != c) {
3325 draw_tile(dr, ds, state, x, y, c,
3326 ui->highlight_1, ui->highlight_2);
3327 ds->visible[n] = c;
3328 }
3329 }
3330
3331 sfree(used);
3332}
3333
3334static float game_anim_length(const game_state *oldstate,
3335 const game_state *newstate, int dir, game_ui *ui)
3336{
3337 return 0.0F;
3338}
3339
3340static float game_flash_length(const game_state *oldstate,
3341 const game_state *newstate, int dir, game_ui *ui)
3342{
3343 if (!oldstate->completed && newstate->completed &&
3344 !oldstate->cheated && !newstate->cheated)
3345 {
3346 ui->highlight_1 = ui->highlight_2 = -1;
3347 return FLASH_TIME;
3348 }
3349 return 0.0F;
3350}
3351
3352static void game_get_cursor_location(const game_ui *ui,
3353 const game_drawstate *ds,
3354 const game_state *state,
3355 const game_params *params,
3356 int *x, int *y, int *w, int *h)
3357{
3358 if(ui->cur_visible)
3359 {
3360 *x = BORDER + ((2 * ui->cur_x + 1) * TILESIZE) / 4;
3361 *y = BORDER + ((2 * ui->cur_y + 1) * TILESIZE) / 4;
3362 *w = *h = TILESIZE / 2 + 2;
3363 }
3364}
3365
3366static int game_status(const game_state *state)
3367{
3368 return state->completed ? +1 : 0;
3369}
3370
3371static void game_print_size(const game_params *params, const game_ui *ui,
3372 float *x, float *y)
3373{
3374 int pw, ph;
3375
3376 /*
3377 * I'll use 6mm squares by default.
3378 */
3379 game_compute_size(params, 600, ui, &pw, &ph);
3380 *x = pw / 100.0F;
3381 *y = ph / 100.0F;
3382}
3383
3384static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
3385 int tilesize)
3386{
3387 int w = state->w, h = state->h;
3388 int c, x, y;
3389
3390 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
3391 game_drawstate ads, *ds = &ads;
3392 game_set_size(dr, ds, NULL, tilesize);
3393
3394 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
3395 c = print_mono_colour(dr, 0); assert(c == COL_TEXT);
3396 c = print_mono_colour(dr, 0); assert(c == COL_DOMINO);
3397 c = print_mono_colour(dr, 0); assert(c == COL_DOMINOCLASH);
3398 c = print_mono_colour(dr, 1); assert(c == COL_DOMINOTEXT);
3399 c = print_mono_colour(dr, 0); assert(c == COL_EDGE);
3400
3401 for (y = 0; y < h; y++)
3402 for (x = 0; x < w; x++) {
3403 int n = y*w+x;
3404 unsigned long c;
3405
3406 if (state->grid[n] == n-1)
3407 c = TYPE_R;
3408 else if (state->grid[n] == n+1)
3409 c = TYPE_L;
3410 else if (state->grid[n] == n-w)
3411 c = TYPE_B;
3412 else if (state->grid[n] == n+w)
3413 c = TYPE_T;
3414 else
3415 c = TYPE_BLANK;
3416
3417 draw_tile(dr, ds, state, x, y, c, -1, -1);
3418 }
3419}
3420
3421#ifdef COMBINED
3422#define thegame dominosa
3423#endif
3424
3425const struct game thegame = {
3426 "Dominosa", "games.dominosa", "dominosa",
3427 default_params,
3428 game_fetch_preset, NULL,
3429 decode_params,
3430 encode_params,
3431 free_params,
3432 dup_params,
3433 true, game_configure, custom_params,
3434 validate_params,
3435 new_game_desc,
3436 validate_desc,
3437 new_game,
3438 dup_game,
3439 free_game,
3440 true, solve_game,
3441 true, game_can_format_as_text_now, game_text_format,
3442 NULL, NULL, /* get_prefs, set_prefs */
3443 new_ui,
3444 free_ui,
3445 NULL, /* encode_ui */
3446 NULL, /* decode_ui */
3447 NULL, /* game_request_keys */
3448 game_changed_state,
3449 current_key_label,
3450 interpret_move,
3451 execute_move,
3452 PREFERRED_TILESIZE, game_compute_size, game_set_size,
3453 game_colours,
3454 game_new_drawstate,
3455 game_free_drawstate,
3456 game_redraw,
3457 game_anim_length,
3458 game_flash_length,
3459 game_get_cursor_location,
3460 game_status,
3461 true, false, game_print_size, game_print,
3462 false, /* wants_statusbar */
3463 false, NULL, /* timing_state */
3464 0, /* flags */
3465};
3466
3467#ifdef STANDALONE_SOLVER
3468
3469int main(int argc, char **argv)
3470{
3471 game_params *p;
3472 game_state *s, *s2;
3473 char *id = NULL, *desc;
3474 int maxdiff = DIFFCOUNT;
3475 const char *err;
3476 bool grade = false, diagnostics = false;
3477 struct solver_scratch *sc;
3478 int retd;
3479
3480 while (--argc > 0) {
3481 char *p = *++argv;
3482 if (!strcmp(p, "-v")) {
3483 diagnostics = true;
3484 } else if (!strcmp(p, "-g")) {
3485 grade = true;
3486 } else if (!strncmp(p, "-d", 2) && p[2] && !p[3]) {
3487 int i;
3488 bool bad = true;
3489 for (i = 0; i < lenof(dominosa_diffchars); i++)
3490 if (dominosa_diffchars[i] != DIFF_AMBIGUOUS &&
3491 dominosa_diffchars[i] == p[2]) {
3492 bad = false;
3493 maxdiff = i;
3494 break;
3495 }
3496 if (bad) {
3497 fprintf(stderr, "%s: unrecognised difficulty `%c'\n",
3498 argv[0], p[2]);
3499 return 1;
3500 }
3501 } else if (*p == '-') {
3502 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
3503 return 1;
3504 } else {
3505 id = p;
3506 }
3507 }
3508
3509 if (!id) {
3510 fprintf(stderr, "usage: %s [-v | -g] <game_id>\n", argv[0]);
3511 return 1;
3512 }
3513
3514 desc = strchr(id, ':');
3515 if (!desc) {
3516 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3517 return 1;
3518 }
3519 *desc++ = '\0';
3520
3521 p = default_params();
3522 decode_params(p, id);
3523 err = validate_desc(p, desc);
3524 if (err) {
3525 fprintf(stderr, "%s: %s\n", argv[0], err);
3526 return 1;
3527 }
3528 s = new_game(NULL, p, desc);
3529
3530 solver_diagnostics = diagnostics;
3531 sc = solver_make_scratch(p->n);
3532 solver_setup_grid(sc, s->numbers->numbers);
3533 retd = run_solver(sc, maxdiff);
3534 if (retd == 0) {
3535 printf("Puzzle is inconsistent\n");
3536 } else if (grade) {
3537 printf("Difficulty rating: %s\n",
3538 dominosa_diffnames[sc->max_diff_used]);
3539 } else {
3540 char *move, *text;
3541 move = solution_move_string(sc);
3542 s2 = execute_move(s, move);
3543 text = game_text_format(s2);
3544 sfree(move);
3545 fputs(text, stdout);
3546 sfree(text);
3547 free_game(s2);
3548 if (retd > 1)
3549 printf("Could not deduce a unique solution\n");
3550 }
3551 solver_free_scratch(sc);
3552 free_game(s);
3553 free_params(p);
3554
3555 return 0;
3556}
3557
3558#endif
3559
3560/* vim: set shiftwidth=4 :set textwidth=80: */
3561