~mdw / sgt / puzzles / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
New puzzle: Dominosa.
[sgt/puzzles] / dominosa.c
CommitLineData
6c04c334 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 * TODO:
9 *
10 * - improve solver so as to use more interesting forms of
11 * deduction
12 * * odd area
13 * * perhaps set analysis
14 */
15
16#include <stdio.h>
17#include <stdlib.h>
18#include <string.h>
19#include <assert.h>
20#include <ctype.h>
21#include <math.h>
22
23#include "puzzles.h"
24
25/* nth triangular number */
26#define TRI(n) ( (n) * ((n) + 1) / 2 )
27/* number of dominoes for value n */
28#define DCOUNT(n) TRI((n)+1)
29/* map a pair of numbers to a unique domino index from 0 upwards. */
30#define DINDEX(n1,n2) ( TRI(max(n1,n2)) + min(n1,n2) )
31
32#define FLASH_TIME 0.13F
33
34enum {
35 COL_BACKGROUND,
36 COL_TEXT,
37 COL_DOMINO,
38 COL_DOMINOCLASH,
39 COL_DOMINOTEXT,
40 COL_EDGE,
41 NCOLOURS
42};
43
44struct game_params {
45 int n;
46 int unique;
47};
48
49struct game_numbers {
50 int refcount;
51 int *numbers; /* h x w */
52};
53
54#define EDGE_L 0x100
55#define EDGE_R 0x200
56#define EDGE_T 0x400
57#define EDGE_B 0x800
58
59struct game_state {
60 game_params params;
61 int w, h;
62 struct game_numbers *numbers;
63 int *grid;
64 unsigned short *edges; /* h x w */
65 int completed, cheated;
66};
67
68static game_params *default_params(void)
69{
70 game_params *ret = snew(game_params);
71
72 ret->n = 6;
73 ret->unique = TRUE;
74
75 return ret;
76}
77
78static int game_fetch_preset(int i, char **name, game_params **params)
79{
80 game_params *ret;
81 int n;
82 char buf[80];
83
84 switch (i) {
85 case 0: n = 3; break;
86 case 1: n = 6; break;
87 case 2: n = 9; break;
88 default: return FALSE;
89 }
90
91 sprintf(buf, "Up to double-%d", n);
92 *name = dupstr(buf);
93
94 *params = ret = snew(game_params);
95 ret->n = n;
96 ret->unique = TRUE;
97
98 return TRUE;
99}
100
101static void free_params(game_params *params)
102{
103 sfree(params);
104}
105
106static game_params *dup_params(game_params *params)
107{
108 game_params *ret = snew(game_params);
109 *ret = *params; /* structure copy */
110 return ret;
111}
112
113static void decode_params(game_params *params, char const *string)
114{
115 params->n = atoi(string);
116 while (*string && isdigit((unsigned char)*string)) string++;
117 if (*string == 'a')
118 params->unique = FALSE;
119}
120
121static char *encode_params(game_params *params, int full)
122{
123 char buf[80];
124 sprintf(buf, "%d", params->n);
125 if (full && !params->unique)
126 strcat(buf, "a");
127 return dupstr(buf);
128}
129
130static config_item *game_configure(game_params *params)
131{
132 config_item *ret;
133 char buf[80];
134
135 ret = snewn(3, config_item);
136
137 ret[0].name = "Maximum number on dominoes";
138 ret[0].type = C_STRING;
139 sprintf(buf, "%d", params->n);
140 ret[0].sval = dupstr(buf);
141 ret[0].ival = 0;
142
143 ret[1].name = "Ensure unique solution";
144 ret[1].type = C_BOOLEAN;
145 ret[1].sval = NULL;
146 ret[1].ival = params->unique;
147
148 ret[2].name = NULL;
149 ret[2].type = C_END;
150 ret[2].sval = NULL;
151 ret[2].ival = 0;
152
153 return ret;
154}
155
156static game_params *custom_params(config_item *cfg)
157{
158 game_params *ret = snew(game_params);
159
160 ret->n = atoi(cfg[0].sval);
161 ret->unique = cfg[1].ival;
162
163 return ret;
164}
165
166static char *validate_params(game_params *params, int full)
167{
168 if (params->n < 1)
169 return "Maximum face number must be at least one";
170 return NULL;
171}
172
173/* ----------------------------------------------------------------------
174 * Solver.
175 */
176
177static int find_overlaps(int w, int h, int placement, int *set)
178{
179 int x, y, n;
180
181 n = 0; /* number of returned placements */
182
183 x = placement / 2;
184 y = x / w;
185 x %= w;
186
187 if (placement & 1) {
188 /*
189 * Horizontal domino, indexed by its left end.
190 */
191 if (x > 0)
192 set[n++] = placement-2; /* horizontal domino to the left */
193 if (y > 0)
194 set[n++] = placement-2*w-1;/* vertical domino above left side */
195 if (y+1 < h)
196 set[n++] = placement-1; /* vertical domino below left side */
197 if (x+2 < w)
198 set[n++] = placement+2; /* horizontal domino to the right */
199 if (y > 0)
200 set[n++] = placement-2*w+2-1;/* vertical domino above right side */
201 if (y+1 < h)
202 set[n++] = placement+2-1; /* vertical domino below right side */
203 } else {
204 /*
205 * Vertical domino, indexed by its top end.
206 */
207 if (y > 0)
208 set[n++] = placement-2*w; /* vertical domino above */
209 if (x > 0)
210 set[n++] = placement-2+1; /* horizontal domino left of top */
211 if (x+1 < w)
212 set[n++] = placement+1; /* horizontal domino right of top */
213 if (y+2 < h)
214 set[n++] = placement+2*w; /* vertical domino below */
215 if (x > 0)
216 set[n++] = placement-2+2*w+1;/* horizontal domino left of bottom */
217 if (x+1 < w)
218 set[n++] = placement+2*w+1;/* horizontal domino right of bottom */
219 }
220
221 return n;
222}
223
224/*
225 * Returns 0, 1 or 2 for number of solutions. 2 means `any number
226 * more than one', or more accurately `we were unable to prove
227 * there was only one'.
228 *
229 * Outputs in a `placements' array, indexed the same way as the one
230 * within this function (see below); entries in there are <0 for a
231 * placement ruled out, 0 for an uncertain placement, and 1 for a
232 * definite one.
233 */
234static int solver(int w, int h, int n, int *grid, int *output)
235{
236 int wh = w*h, dc = DCOUNT(n);
237 int *placements, *heads;
238 int i, j, x, y, ret;
239
240 /*
241 * This array has one entry for every possible domino
242 * placement. Vertical placements are indexed by their top
243 * half, at (y*w+x)*2; horizontal placements are indexed by
244 * their left half at (y*w+x)*2+1.
245 *
246 * This array is used to link domino placements together into
247 * linked lists, so that we can track all the possible
248 * placements of each different domino. It's also used as a
249 * quick means of looking up an individual placement to see
250 * whether we still think it's possible. Actual values stored
251 * in this array are -2 (placement not possible at all), -1
252 * (end of list), or the array index of the next item.
253 *
254 * Oh, and -3 for `not even valid', used for array indices
255 * which don't even represent a plausible placement.
256 */
257 placements = snewn(2*wh, int);
258 for (i = 0; i < 2*wh; i++)
259 placements[i] = -3; /* not even valid */
260
261 /*
262 * This array has one entry for every domino, and it is an
263 * index into `placements' denoting the head of the placement
264 * list for that domino.
265 */
266 heads = snewn(dc, int);
267 for (i = 0; i < dc; i++)
268 heads[i] = -1;
269
270 /*
271 * Set up the initial possibility lists by scanning the grid.
272 */
273 for (y = 0; y < h-1; y++)
274 for (x = 0; x < w; x++) {
275 int di = DINDEX(grid[y*w+x], grid[(y+1)*w+x]);
276 placements[(y*w+x)*2] = heads[di];
277 heads[di] = (y*w+x)*2;
278 }
279 for (y = 0; y < h; y++)
280 for (x = 0; x < w-1; x++) {
281 int di = DINDEX(grid[y*w+x], grid[y*w+(x+1)]);
282 placements[(y*w+x)*2+1] = heads[di];
283 heads[di] = (y*w+x)*2+1;
284 }
285
286#ifdef SOLVER_DIAGNOSTICS
287 printf("before solver:\n");
288 for (i = 0; i <= n; i++)
289 for (j = 0; j <= i; j++) {
290 int k, m;
291 m = 0;
292 printf("%2d [%d %d]:", DINDEX(i, j), i, j);
293 for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
294 printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');
295 printf("\n");
296 }
297#endif
298
299 while (1) {
300 int done_something = FALSE;
301
302 /*
303 * For each domino, look at its possible placements, and
304 * for each placement consider the placements (of any
305 * domino) it overlaps. Any placement overlapped by all
306 * placements of this domino can be ruled out.
307 *
308 * Each domino placement overlaps only six others, so we
309 * need not do serious set theory to work this out.
310 */
311 for (i = 0; i < dc; i++) {
312 int permset[6], permlen = 0, p;
313
314
315 if (heads[i] == -1) { /* no placement for this domino */
316 ret = 0; /* therefore puzzle is impossible */
317 goto done;
318 }
319 for (j = heads[i]; j >= 0; j = placements[j]) {
320 assert(placements[j] != -2);
321
322 if (j == heads[i]) {
323 permlen = find_overlaps(w, h, j, permset);
324 } else {
325 int tempset[6], templen, m, n, k;
326
327 templen = find_overlaps(w, h, j, tempset);
328
329 /*
330 * Pathetically primitive set intersection
331 * algorithm, which I'm only getting away with
332 * because I know my sets are bounded by a very
333 * small size.
334 */
335 for (m = n = 0; m < permlen; m++) {
336 for (k = 0; k < templen; k++)
337 if (tempset[k] == permset[m])
338 break;
339 if (k < templen)
340 permset[n++] = permset[m];
341 }
342 permlen = n;
343 }
344 }
345 for (p = 0; p < permlen; p++) {
346 j = permset[p];
347 if (placements[j] != -2) {
348 int p1, p2, di;
349
350 done_something = TRUE;
351
352 /*
353 * Rule out this placement. First find what
354 * domino it is...
355 */
356 p1 = j / 2;
357 p2 = (j & 1) ? p1 + 1 : p1 + w;
358 di = DINDEX(grid[p1], grid[p2]);
359#ifdef SOLVER_DIAGNOSTICS
360 printf("considering domino %d: ruling out placement %d"
361 " for %d\n", i, j, di);
362#endif
363
364 /*
365 * ... then walk that domino's placement list,
366 * removing this placement when we find it.
367 */
368 if (heads[di] == j)
369 heads[di] = placements[j];
370 else {
371 int k = heads[di];
372 while (placements[k] != -1 && placements[k] != j)
373 k = placements[k];
374 assert(placements[k] == j);
375 placements[k] = placements[j];
376 }
377 placements[j] = -2;
378 }
379 }
380 }
381
382 /*
383 * For each square, look at the available placements
384 * involving that square. If all of them are for the same
385 * domino, then rule out any placements for that domino
386 * _not_ involving this square.
387 */
388 for (i = 0; i < wh; i++) {
389 int list[4], k, n, adi;
390
391 x = i % w;
392 y = i / w;
393
394 j = 0;
395 if (x > 0)
396 list[j++] = 2*(i-1)+1;
397 if (x+1 < w)
398 list[j++] = 2*i+1;
399 if (y > 0)
400 list[j++] = 2*(i-w);
401 if (y+1 < h)
402 list[j++] = 2*i;
403
404 for (n = k = 0; k < j; k++)
405 if (placements[list[k]] >= -1)
406 list[n++] = list[k];
407
408 adi = -1;
409
410 for (j = 0; j < n; j++) {
411 int p1, p2, di;
412 k = list[j];
413
414 p1 = k / 2;
415 p2 = (k & 1) ? p1 + 1 : p1 + w;
416 di = DINDEX(grid[p1], grid[p2]);
417
418 if (adi == -1)
419 adi = di;
420 if (adi != di)
421 break;
422 }
423
424 if (j == n) {
425 int nn;
426
427 assert(adi >= 0);
428 /*
429 * We've found something. All viable placements
430 * involving this square are for domino `adi'. If
431 * the current placement list for that domino is
432 * longer than n, reduce it to precisely this
433 * placement list and we've done something.
434 */
435 nn = 0;
436 for (k = heads[adi]; k >= 0; k = placements[k])
437 nn++;
438 if (nn > n) {
439 done_something = TRUE;
440#ifdef SOLVER_DIAGNOSTICS
441 printf("considering square %d,%d: reducing placements "
442 "of domino %d\n", x, y, adi);
443#endif
444 /*
445 * Set all other placements on the list to
446 * impossible.
447 */
448 k = heads[adi];
449 while (k >= 0) {
450 int tmp = placements[k];
451 placements[k] = -2;
452 k = tmp;
453 }
454 /*
455 * Set up the new list.
456 */
457 heads[adi] = list[0];
458 for (k = 0; k < n; k++)
459 placements[list[k]] = (k+1 == n ? -1 : list[k+1]);
460 }
461 }
462 }
463
464 if (!done_something)
465 break;
466 }
467
468#ifdef SOLVER_DIAGNOSTICS
469 printf("after solver:\n");
470 for (i = 0; i <= n; i++)
471 for (j = 0; j <= i; j++) {
472 int k, m;
473 m = 0;
474 printf("%2d [%d %d]:", DINDEX(i, j), i, j);
475 for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
476 printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');
477 printf("\n");
478 }
479#endif
480
481 ret = 1;
482 for (i = 0; i < wh*2; i++) {
483 if (placements[i] == -2) {
484 if (output)
485 output[i] = -1; /* ruled out */
486 } else if (placements[i] != -3) {
487 int p1, p2, di;
488
489 p1 = i / 2;
490 p2 = (i & 1) ? p1 + 1 : p1 + w;
491 di = DINDEX(grid[p1], grid[p2]);
492
493 if (i == heads[di] && placements[i] == -1) {
494 if (output)
495 output[i] = 1; /* certain */
496 } else {
497 if (output)
498 output[i] = 0; /* uncertain */
499 ret = 2;
500 }
501 }
502 }
503
504 done:
505 /*
506 * Free working data.
507 */
508 sfree(placements);
509 sfree(heads);
510
511 return ret;
512}
513
514/* ----------------------------------------------------------------------
515 * End of solver code.
516 */
517
518static char *new_game_desc(game_params *params, random_state *rs,
519 char **aux, int interactive)
520{
521 int n = params->n, w = n+2, h = n+1, wh = w*h;
522 int *grid, *grid2, *list;
523 int i, j, k, m, todo, done, len;
524 char *ret;
525
526 /*
527 * Allocate space in which to lay the grid out.
528 */
529 grid = snewn(wh, int);
530 grid2 = snewn(wh, int);
531 list = snewn(2*wh, int);
532
533 do {
534 /*
535 * To begin with, set grid[i] = i for all i to indicate
536 * that all squares are currently singletons. Later we'll
537 * set grid[i] to be the index of the other end of the
538 * domino on i.
539 */
540 for (i = 0; i < wh; i++)
541 grid[i] = i;
542
543 /*
544 * Now prepare a list of the possible domino locations. There
545 * are w*(h-1) possible vertical locations, and (w-1)*h
546 * horizontal ones, for a total of 2*wh - h - w.
547 *
548 * I'm going to denote the vertical domino placement with
549 * its top in square i as 2*i, and the horizontal one with
550 * its left half in square i as 2*i+1.
551 */
552 k = 0;
553 for (j = 0; j < h-1; j++)
554 for (i = 0; i < w; i++)
555 list[k++] = 2 * (j*w+i); /* vertical positions */
556 for (j = 0; j < h; j++)
557 for (i = 0; i < w-1; i++)
558 list[k++] = 2 * (j*w+i) + 1; /* horizontal positions */
559 assert(k == 2*wh - h - w);
560
561 /*
562 * Shuffle the list.
563 */
564 shuffle(list, k, sizeof(*list), rs);
565
566 /*
567 * Work down the shuffled list, placing a domino everywhere
568 * we can.
569 */
570 for (i = 0; i < k; i++) {
571 int horiz, xy, xy2;
572
573 horiz = list[i] % 2;
574 xy = list[i] / 2;
575 xy2 = xy + (horiz ? 1 : w);
576
577 if (grid[xy] == xy && grid[xy2] == xy2) {
578 /*
579 * We can place this domino. Do so.
580 */
581 grid[xy] = xy2;
582 grid[xy2] = xy;
583 }
584 }
585
586#ifdef GENERATION_DIAGNOSTICS
587 printf("generated initial layout\n");
588#endif
589
590 /*
591 * Now we've placed as many dominoes as we can immediately
592 * manage. There will be squares remaining, but they'll be
593 * singletons. So loop round and deal with the singletons
594 * two by two.
595 */
596 while (1) {
597#ifdef GENERATION_DIAGNOSTICS
598 for (j = 0; j < h; j++) {
599 for (i = 0; i < w; i++) {
600 int xy = j*w+i;
601 int v = grid[xy];
602 int c = (v == xy+1 ? '[' : v == xy-1 ? ']' :
603 v == xy+w ? 'n' : v == xy-w ? 'U' : '.');
604 putchar(c);
605 }
606 putchar('\n');
607 }
608 putchar('\n');
609#endif
610
611 /*
612 * Our strategy is:
613 *
614 * First find a singleton square.
615 *
616 * Then breadth-first search out from the starting
617 * square. From that square (and any others we reach on
618 * the way), examine all four neighbours of the square.
619 * If one is an end of a domino, we move to the _other_
620 * end of that domino before looking at neighbours
621 * again. When we encounter another singleton on this
622 * search, stop.
623 *
624 * This will give us a path of adjacent squares such
625 * that all but the two ends are covered in dominoes.
626 * So we can now shuffle every domino on the path up by
627 * one.
628 *
629 * (Chessboard colours are mathematically important
630 * here: we always end up pairing each singleton with a
631 * singleton of the other colour. However, we never
632 * have to track this manually, since it's
633 * automatically taken care of by the fact that we
634 * always make an even number of orthogonal moves.)
635 */
636 for (i = 0; i < wh; i++)
637 if (grid[i] == i)
638 break;
639 if (i == wh)
640 break; /* no more singletons; we're done. */
641
642#ifdef GENERATION_DIAGNOSTICS
643 printf("starting b.f.s. at singleton %d\n", i);
644#endif
645 /*
646 * Set grid2 to -1 everywhere. It will hold our
647 * distance-from-start values, and also our
648 * backtracking data, during the b.f.s.
649 */
650 for (j = 0; j < wh; j++)
651 grid2[j] = -1;
652 grid2[i] = 0; /* starting square has distance zero */
653
654 /*
655 * Start our to-do list of squares. It'll live in
656 * `list'; since the b.f.s can cover every square at
657 * most once there is no need for it to be circular.
658 * We'll just have two counters tracking the end of the
659 * list and the squares we've already dealt with.
660 */
661 done = 0;
662 todo = 1;
663 list[0] = i;
664
665 /*
666 * Now begin the b.f.s. loop.
667 */
668 while (done < todo) {
669 int d[4], nd, x, y;
670
671 i = list[done++];
672
673#ifdef GENERATION_DIAGNOSTICS
674 printf("b.f.s. iteration from %d\n", i);
675#endif
676 x = i % w;
677 y = i / w;
678 nd = 0;
679 if (x > 0)
680 d[nd++] = i - 1;
681 if (x+1 < w)
682 d[nd++] = i + 1;
683 if (y > 0)
684 d[nd++] = i - w;
685 if (y+1 < h)
686 d[nd++] = i + w;
687 /*
688 * To avoid directional bias, process the
689 * neighbours of this square in a random order.
690 */
691 shuffle(d, nd, sizeof(*d), rs);
692
693 for (j = 0; j < nd; j++) {
694 k = d[j];
695 if (grid[k] == k) {
696#ifdef GENERATION_DIAGNOSTICS
697 printf("found neighbouring singleton %d\n", k);
698#endif
699 grid2[k] = i;
700 break; /* found a target singleton! */
701 }
702
703 /*
704 * We're moving through a domino here, so we
705 * have two entries in grid2 to fill with
706 * useful data. In grid[k] - the square
707 * adjacent to where we came from - I'm going
708 * to put the address _of_ the square we came
709 * from. In the other end of the domino - the
710 * square from which we will continue the
711 * search - I'm going to put the distance.
712 */
713 m = grid[k];
714
715 if (grid2[m] < 0 || grid2[m] > grid2[i]+1) {
716#ifdef GENERATION_DIAGNOSTICS
717 printf("found neighbouring domino %d/%d\n", k, m);
718#endif
719 grid2[m] = grid2[i]+1;
720 grid2[k] = i;
721 /*
722 * And since we've now visited a new
723 * domino, add m to the to-do list.
724 */
725 assert(todo < wh);
726 list[todo++] = m;
727 }
728 }
729
730 if (j < nd) {
731 i = k;
732#ifdef GENERATION_DIAGNOSTICS
733 printf("terminating b.f.s. loop, i = %d\n", i);
734#endif
735 break;
736 }
737
738 i = -1; /* just in case the loop terminates */
739 }
740
741 /*
742 * We expect this b.f.s. to have found us a target
743 * square.
744 */
745 assert(i >= 0);
746
747 /*
748 * Now we can follow the trail back to our starting
749 * singleton, re-laying dominoes as we go.
750 */
751 while (1) {
752 j = grid2[i];
753 assert(j >= 0 && j < wh);
754 k = grid[j];
755
756 grid[i] = j;
757 grid[j] = i;
758#ifdef GENERATION_DIAGNOSTICS
759 printf("filling in domino %d/%d (next %d)\n", i, j, k);
760#endif
761 if (j == k)
762 break; /* we've reached the other singleton */
763 i = k;
764 }
765#ifdef GENERATION_DIAGNOSTICS
766 printf("fixup path completed\n");
767#endif
768 }
769
770 /*
771 * Now we have a complete layout covering the whole
772 * rectangle with dominoes. So shuffle the actual domino
773 * values and fill the rectangle with numbers.
774 */
775 k = 0;
776 for (i = 0; i <= params->n; i++)
777 for (j = 0; j <= i; j++) {
778 list[k++] = i;
779 list[k++] = j;
780 }
781 shuffle(list, k/2, 2*sizeof(*list), rs);
782 j = 0;
783 for (i = 0; i < wh; i++)
784 if (grid[i] > i) {
785 /* Optionally flip the domino round. */
786 int flip = random_upto(rs, 2);
787 grid2[i] = list[j + flip];
788 grid2[grid[i]] = list[j + 1 - flip];
789 j += 2;
790 }
791 assert(j == k);
792 } while (params->unique && solver(w, h, n, grid2, NULL) > 1);
793
794#ifdef GENERATION_DIAGNOSTICS
795 for (j = 0; j < h; j++) {
796 for (i = 0; i < w; i++) {
797 putchar('0' + grid2[j*w+i]);
798 }
799 putchar('\n');
800 }
801 putchar('\n');
802#endif
803
804 /*
805 * Encode the resulting game state.
806 *
807 * Our encoding is a string of digits. Any number greater than
808 * 9 is represented by a decimal integer within square
809 * brackets. We know there are n+2 of every number (it's paired
810 * with each number from 0 to n inclusive, and one of those is
811 * itself so that adds another occurrence), so we can work out
812 * the string length in advance.
813 */
814
815 /*
816 * To work out the total length of the decimal encodings of all
817 * the numbers from 0 to n inclusive:
818 * - every number has a units digit; total is n+1.
819 * - all numbers above 9 have a tens digit; total is max(n+1-10,0).
820 * - all numbers above 99 have a hundreds digit; total is max(n+1-100,0).
821 * - and so on.
822 */
823 len = n+1;
824 for (i = 10; i <= n; i *= 10)
825 len += max(n + 1 - i, 0);
826 /* Now add two square brackets for each number above 9. */
827 len += 2 * max(n + 1 - 10, 0);
828 /* And multiply by n+2 for the repeated occurrences of each number. */
829 len *= n+2;
830
831 /*
832 * Now actually encode the string.
833 */
834 ret = snewn(len+1, char);
835 j = 0;
836 for (i = 0; i < wh; i++) {
837 k = grid2[i];
838 if (k < 10)
839 ret[j++] = '0' + k;
840 else
841 j += sprintf(ret+j, "[%d]", k);
842 assert(j <= len);
843 }
844 assert(j == len);
845 ret[j] = '\0';
846
847 /*
848 * Encode the solved state as an aux_info.
849 */
850 {
851 char *auxinfo = snewn(wh+1, char);
852
853 for (i = 0; i < wh; i++) {
854 int v = grid[i];
855 auxinfo[i] = (v == i+1 ? 'L' : v == i-1 ? 'R' :
856 v == i+w ? 'T' : v == i-w ? 'B' : '.');
857 }
858 auxinfo[wh] = '\0';
859
860 *aux = auxinfo;
861 }
862
863 sfree(list);
864 sfree(grid2);
865 sfree(grid);
866
867 return ret;
868}
869
870static char *validate_desc(game_params *params, char *desc)
871{
872 int n = params->n, w = n+2, h = n+1, wh = w*h;
873 int *occurrences;
874 int i, j;
875 char *ret;
876
877 ret = NULL;
878 occurrences = snewn(n+1, int);
879 for (i = 0; i <= n; i++)
880 occurrences[i] = 0;
881
882 for (i = 0; i < wh; i++) {
883 if (!*desc) {
884 ret = ret ? ret : "Game description is too short";
885 } else {
886 if (*desc >= '0' && *desc <= '9')
887 j = *desc++ - '0';
888 else if (*desc == '[') {
889 desc++;
890 j = atoi(desc);
891 while (*desc && isdigit((unsigned char)*desc)) desc++;
892 if (*desc != ']')
893 ret = ret ? ret : "Missing ']' in game description";
894 else
895 desc++;
896 } else {
897 j = -1;
898 ret = ret ? ret : "Invalid syntax in game description";
899 }
900 if (j < 0 || j > n)
901 ret = ret ? ret : "Number out of range in game description";
902 else
903 occurrences[j]++;
904 }
905 }
906
907 if (*desc)
908 ret = ret ? ret : "Game description is too long";
909
910 if (!ret) {
911 for (i = 0; i <= n; i++)
912 if (occurrences[i] != n+2)
913 ret = "Incorrect number balance in game description";
914 }
915
916 sfree(occurrences);
917
918 return ret;
919}
920
921static game_state *new_game(midend_data *me, game_params *params, char *desc)
922{
923 int n = params->n, w = n+2, h = n+1, wh = w*h;
924 game_state *state = snew(game_state);
925 int i, j;
926
927 state->params = *params;
928 state->w = w;
929 state->h = h;
930
931 state->grid = snewn(wh, int);
932 for (i = 0; i < wh; i++)
933 state->grid[i] = i;
934
935 state->edges = snewn(wh, unsigned short);
936 for (i = 0; i < wh; i++)
937 state->edges[i] = 0;
938
939 state->numbers = snew(struct game_numbers);
940 state->numbers->refcount = 1;
941 state->numbers->numbers = snewn(wh, int);
942
943 for (i = 0; i < wh; i++) {
944 assert(*desc);
945 if (*desc >= '0' && *desc <= '9')
946 j = *desc++ - '0';
947 else {
948 assert(*desc == '[');
949 desc++;
950 j = atoi(desc);
951 while (*desc && isdigit((unsigned char)*desc)) desc++;
952 assert(*desc == ']');
953 desc++;
954 }
955 assert(j >= 0 && j <= n);
956 state->numbers->numbers[i] = j;
957 }
958
959 state->completed = state->cheated = FALSE;
960
961 return state;
962}
963
964static game_state *dup_game(game_state *state)
965{
966 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
967 game_state *ret = snew(game_state);
968
969 ret->params = state->params;
970 ret->w = state->w;
971 ret->h = state->h;
972 ret->grid = snewn(wh, int);
973 memcpy(ret->grid, state->grid, wh * sizeof(int));
974 ret->edges = snewn(wh, unsigned short);
975 memcpy(ret->edges, state->edges, wh * sizeof(unsigned short));
976 ret->numbers = state->numbers;
977 ret->numbers->refcount++;
978 ret->completed = state->completed;
979 ret->cheated = state->cheated;
980
981 return ret;
982}
983
984static void free_game(game_state *state)
985{
986 sfree(state->grid);
987 if (--state->numbers->refcount <= 0) {
988 sfree(state->numbers->numbers);
989 sfree(state->numbers);
990 }
991 sfree(state);
992}
993
994static char *solve_game(game_state *state, game_state *currstate,
995 char *aux, char **error)
996{
997 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
998 int *placements;
999 char *ret;
1000 int retlen, retsize;
1001 int i, v;
1002 char buf[80];
1003 int extra;
1004
1005 if (aux) {
1006 retsize = 256;
1007 ret = snewn(retsize, char);
1008 retlen = sprintf(ret, "S");
1009
1010 for (i = 0; i < wh; i++) {
1011 if (aux[i] == 'L')
1012 extra = sprintf(buf, ";D%d,%d", i, i+1);
1013 else if (aux[i] == 'T')
1014 extra = sprintf(buf, ";D%d,%d", i, i+w);
1015 else
1016 continue;
1017
1018 if (retlen + extra + 1 >= retsize) {
1019 retsize = retlen + extra + 256;
1020 ret = sresize(ret, retsize, char);
1021 }
1022 strcpy(ret + retlen, buf);
1023 retlen += extra;
1024 }
1025
1026 } else {
1027
1028 placements = snewn(wh*2, int);
1029 for (i = 0; i < wh*2; i++)
1030 placements[i] = -3;
1031 solver(w, h, n, state->numbers->numbers, placements);
1032
1033 /*
1034 * First make a pass putting in edges for -1, then make a pass
1035 * putting in dominoes for +1.
1036 */
1037 retsize = 256;
1038 ret = snewn(retsize, char);
1039 retlen = sprintf(ret, "S");
1040
1041 for (v = -1; v <= +1; v += 2)
1042 for (i = 0; i < wh*2; i++)
1043 if (placements[i] == v) {
1044 int p1 = i / 2;
1045 int p2 = (i & 1) ? p1+1 : p1+w;
1046
1047 extra = sprintf(buf, ";%c%d,%d",
1048 v==-1 ? 'E' : 'D', p1, p2);
1049
1050 if (retlen + extra + 1 >= retsize) {
1051 retsize = retlen + extra + 256;
1052 ret = sresize(ret, retsize, char);
1053 }
1054 strcpy(ret + retlen, buf);
1055 retlen += extra;
1056 }
1057
1058 sfree(placements);
1059 }
1060
1061 return ret;
1062}
1063
1064static char *game_text_format(game_state *state)
1065{
1066 return NULL;
1067}
1068
1069static game_ui *new_ui(game_state *state)
1070{
1071 return NULL;
1072}
1073
1074static void free_ui(game_ui *ui)
1075{
1076}
1077
1078static char *encode_ui(game_ui *ui)
1079{
1080 return NULL;
1081}
1082
1083static void decode_ui(game_ui *ui, char *encoding)
1084{
1085}
1086
1087static void game_changed_state(game_ui *ui, game_state *oldstate,
1088 game_state *newstate)
1089{
1090}
1091
1092#define PREFERRED_TILESIZE 32
1093#define TILESIZE (ds->tilesize)
1094#define BORDER (TILESIZE * 3 / 4)
1095#define DOMINO_GUTTER (TILESIZE / 16)
1096#define DOMINO_RADIUS (TILESIZE / 8)
1097#define DOMINO_COFFSET (DOMINO_GUTTER + DOMINO_RADIUS)
1098
1099#define COORD(x) ( (x) * TILESIZE + BORDER )
1100#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1101
1102struct game_drawstate {
1103 int started;
1104 int w, h, tilesize;
1105 unsigned long *visible;
1106};
1107
1108static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1109 int x, int y, int button)
1110{
1111 int w = state->w, h = state->h;
1112 char buf[80];
1113
1114 /*
1115 * A left-click between two numbers toggles a domino covering
1116 * them. A right-click toggles an edge.
1117 */
1118 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1119 int tx = FROMCOORD(x), ty = FROMCOORD(y), t = ty*w+tx;
1120 int dx, dy;
1121 int d1, d2;
1122
1123 if (tx < 0 || tx >= w || ty < 0 || ty >= h)
1124 return NULL;
1125
1126 /*
1127 * Now we know which square the click was in, decide which
1128 * edge of the square it was closest to.
1129 */
1130 dx = 2 * (x - COORD(tx)) - TILESIZE;
1131 dy = 2 * (y - COORD(ty)) - TILESIZE;
1132
1133 if (abs(dx) > abs(dy) && dx < 0 && tx > 0)
1134 d1 = t - 1, d2 = t; /* clicked in right side of domino */
1135 else if (abs(dx) > abs(dy) && dx > 0 && tx+1 < w)
1136 d1 = t, d2 = t + 1; /* clicked in left side of domino */
1137 else if (abs(dy) > abs(dx) && dy < 0 && ty > 0)
1138 d1 = t - w, d2 = t; /* clicked in bottom half of domino */
1139 else if (abs(dy) > abs(dx) && dy > 0 && ty+1 < h)
1140 d1 = t, d2 = t + w; /* clicked in top half of domino */
1141 else
1142 return NULL;
1143
1144 /*
1145 * We can't mark an edge next to any domino.
1146 */
1147 if (button == RIGHT_BUTTON &&
1148 (state->grid[d1] != d1 || state->grid[d2] != d2))
1149 return NULL;
1150
1151 sprintf(buf, "%c%d,%d", button == RIGHT_BUTTON ? 'E' : 'D', d1, d2);
1152 return dupstr(buf);
1153 }
1154
1155 return NULL;
1156}
1157
1158static game_state *execute_move(game_state *state, char *move)
1159{
1160 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
1161 int d1, d2, d3, p;
1162 game_state *ret = dup_game(state);
1163
1164 while (*move) {
1165 if (move[0] == 'S') {
1166 int i;
1167
1168 ret->cheated = TRUE;
1169
1170 /*
1171 * Clear the existing edges and domino placements. We
1172 * expect the S to be followed by other commands.
1173 */
1174 for (i = 0; i < wh; i++) {
1175 ret->grid[i] = i;
1176 ret->edges[i] = 0;
1177 }
1178 move++;
1179 } else if (move[0] == 'D' &&
1180 sscanf(move+1, "%d,%d%n", &d1, &d2, &p) == 2 &&
1181 d1 >= 0 && d1 < wh && d2 >= 0 && d2 < wh && d1 < d2) {
1182
1183 /*
1184 * Toggle domino presence between d1 and d2.
1185 */
1186 if (ret->grid[d1] == d2) {
1187 assert(ret->grid[d2] == d1);
1188 ret->grid[d1] = d1;
1189 ret->grid[d2] = d2;
1190 } else {
1191 /*
1192 * Erase any dominoes that might overlap the new one.
1193 */
1194 d3 = ret->grid[d1];
1195 if (d3 != d1)
1196 ret->grid[d3] = d3;
1197 d3 = ret->grid[d2];
1198 if (d3 != d2)
1199 ret->grid[d3] = d3;
1200 /*
1201 * Place the new one.
1202 */
1203 ret->grid[d1] = d2;
1204 ret->grid[d2] = d1;
1205
1206 /*
1207 * Destroy any edges lurking around it.
1208 */
1209 if (ret->edges[d1] & EDGE_L) {
1210 assert(d1 - 1 >= 0);
1211 ret->edges[d1 - 1] &= ~EDGE_R;
1212 }
1213 if (ret->edges[d1] & EDGE_R) {
1214 assert(d1 + 1 < wh);
1215 ret->edges[d1 + 1] &= ~EDGE_L;
1216 }
1217 if (ret->edges[d1] & EDGE_T) {
1218 assert(d1 - w >= 0);
1219 ret->edges[d1 - w] &= ~EDGE_B;
1220 }
1221 if (ret->edges[d1] & EDGE_B) {
1222 assert(d1 + 1 < wh);
1223 ret->edges[d1 + w] &= ~EDGE_T;
1224 }
1225 ret->edges[d1] = 0;
1226 if (ret->edges[d2] & EDGE_L) {
1227 assert(d2 - 1 >= 0);
1228 ret->edges[d2 - 1] &= ~EDGE_R;
1229 }
1230 if (ret->edges[d2] & EDGE_R) {
1231 assert(d2 + 1 < wh);
1232 ret->edges[d2 + 1] &= ~EDGE_L;
1233 }
1234 if (ret->edges[d2] & EDGE_T) {
1235 assert(d2 - w >= 0);
1236 ret->edges[d2 - w] &= ~EDGE_B;
1237 }
1238 if (ret->edges[d2] & EDGE_B) {
1239 assert(d2 + 1 < wh);
1240 ret->edges[d2 + w] &= ~EDGE_T;
1241 }
1242 ret->edges[d2] = 0;
1243 }
1244
1245 move += p+1;
1246 } else if (move[0] == 'E' &&
1247 sscanf(move+1, "%d,%d%n", &d1, &d2, &p) == 2 &&
1248 d1 >= 0 && d1 < wh && d2 >= 0 && d2 < wh && d1 < d2 &&
1249 ret->grid[d1] == d1 && ret->grid[d2] == d2) {
1250
1251 /*
1252 * Toggle edge presence between d1 and d2.
1253 */
1254 if (d2 == d1 + 1) {
1255 ret->edges[d1] ^= EDGE_R;
1256 ret->edges[d2] ^= EDGE_L;
1257 } else {
1258 ret->edges[d1] ^= EDGE_B;
1259 ret->edges[d2] ^= EDGE_T;
1260 }
1261
1262 move += p+1;
1263 } else {
1264 free_game(ret);
1265 return NULL;
1266 }
1267
1268 if (*move) {
1269 if (*move != ';') {
1270 free_game(ret);
1271 return NULL;
1272 }
1273 move++;
1274 }
1275 }
1276
1277 /*
1278 * After modifying the grid, check completion.
1279 */
1280 if (!ret->completed) {
1281 int i, ok = 0;
1282 unsigned char *used = snewn(TRI(n+1), unsigned char);
1283
1284 memset(used, 0, TRI(n+1));
1285 for (i = 0; i < wh; i++)
1286 if (ret->grid[i] > i) {
1287 int n1, n2, di;
1288
1289 n1 = ret->numbers->numbers[i];
1290 n2 = ret->numbers->numbers[ret->grid[i]];
1291
1292 di = DINDEX(n1, n2);
1293 assert(di >= 0 && di < TRI(n+1));
1294
1295 if (!used[di]) {
1296 used[di] = 1;
1297 ok++;
1298 }
1299 }
1300
1301 sfree(used);
1302 if (ok == DCOUNT(n))
1303 ret->completed = TRUE;
1304 }
1305
1306 return ret;
1307}
1308
1309/* ----------------------------------------------------------------------
1310 * Drawing routines.
1311 */
1312
1313static void game_compute_size(game_params *params, int tilesize,
1314 int *x, int *y)
1315{
1316 int n = params->n, w = n+2, h = n+1;
1317
1318 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1319 struct { int tilesize; } ads, *ds = &ads;
1320 ads.tilesize = tilesize;
1321
1322 *x = w * TILESIZE + 2*BORDER;
1323 *y = h * TILESIZE + 2*BORDER;
1324}
1325
1326static void game_set_size(game_drawstate *ds, game_params *params,
1327 int tilesize)
1328{
1329 ds->tilesize = tilesize;
1330}
1331
1332static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1333{
1334 float *ret = snewn(3 * NCOLOURS, float);
1335
1336 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1337
1338 ret[COL_TEXT * 3 + 0] = 0.0F;
1339 ret[COL_TEXT * 3 + 1] = 0.0F;
1340 ret[COL_TEXT * 3 + 2] = 0.0F;
1341
1342 ret[COL_DOMINO * 3 + 0] = 0.0F;
1343 ret[COL_DOMINO * 3 + 1] = 0.0F;
1344 ret[COL_DOMINO * 3 + 2] = 0.0F;
1345
1346 ret[COL_DOMINOCLASH * 3 + 0] = 0.5F;
1347 ret[COL_DOMINOCLASH * 3 + 1] = 0.0F;
1348 ret[COL_DOMINOCLASH * 3 + 2] = 0.0F;
1349
1350 ret[COL_DOMINOTEXT * 3 + 0] = 1.0F;
1351 ret[COL_DOMINOTEXT * 3 + 1] = 1.0F;
1352 ret[COL_DOMINOTEXT * 3 + 2] = 1.0F;
1353
1354 ret[COL_EDGE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2 / 3;
1355 ret[COL_EDGE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2 / 3;
1356 ret[COL_EDGE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2 / 3;
1357
1358 *ncolours = NCOLOURS;
1359 return ret;
1360}
1361
1362static game_drawstate *game_new_drawstate(game_state *state)
1363{
1364 struct game_drawstate *ds = snew(struct game_drawstate);
1365 int i;
1366
1367 ds->started = FALSE;
1368 ds->w = state->w;
1369 ds->h = state->h;
1370 ds->visible = snewn(ds->w * ds->h, unsigned long);
1371 ds->tilesize = 0; /* not decided yet */
1372 for (i = 0; i < ds->w * ds->h; i++)
1373 ds->visible[i] = 0xFFFF;
1374
1375 return ds;
1376}
1377
1378static void game_free_drawstate(game_drawstate *ds)
1379{
1380 sfree(ds->visible);
1381 sfree(ds);
1382}
1383
1384enum {
1385 TYPE_L,
1386 TYPE_R,
1387 TYPE_T,
1388 TYPE_B,
1389 TYPE_BLANK,
1390 TYPE_MASK = 0x0F
1391};
1392
1393static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state,
1394 int x, int y, int type)
1395{
1396 int w = state->w /*, h = state->h */;
1397 int cx = COORD(x), cy = COORD(y);
1398 int nc;
1399 char str[80];
1400 int flags;
1401
1402 draw_rect(fe, cx, cy, TILESIZE, TILESIZE, COL_BACKGROUND);
1403
1404 flags = type &~ TYPE_MASK;
1405 type &= TYPE_MASK;
1406
1407 if (type != TYPE_BLANK) {
1408 int i, bg;
1409
1410 /*
1411 * Draw one end of a domino. This is composed of:
1412 *
1413 * - two filled circles (rounded corners)
1414 * - two rectangles
1415 * - a slight shift in the number
1416 */
1417
1418 if (flags & 0x80)
1419 bg = COL_DOMINOCLASH;
1420 else
1421 bg = COL_DOMINO;
1422 nc = COL_DOMINOTEXT;
1423
1424 if (flags & 0x40) {
1425 int tmp = nc;
1426 nc = bg;
1427 bg = tmp;
1428 }
1429
1430 if (type == TYPE_L || type == TYPE_T)
1431 draw_circle(fe, cx+DOMINO_COFFSET, cy+DOMINO_COFFSET,
1432 DOMINO_RADIUS, bg, bg);
1433 if (type == TYPE_R || type == TYPE_T)
1434 draw_circle(fe, cx+TILESIZE-1-DOMINO_COFFSET, cy+DOMINO_COFFSET,
1435 DOMINO_RADIUS, bg, bg);
1436 if (type == TYPE_L || type == TYPE_B)
1437 draw_circle(fe, cx+DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET,
1438 DOMINO_RADIUS, bg, bg);
1439 if (type == TYPE_R || type == TYPE_B)
1440 draw_circle(fe, cx+TILESIZE-1-DOMINO_COFFSET,
1441 cy+TILESIZE-1-DOMINO_COFFSET,
1442 DOMINO_RADIUS, bg, bg);
1443
1444 for (i = 0; i < 2; i++) {
1445 int x1, y1, x2, y2;
1446
1447 x1 = cx + (i ? DOMINO_GUTTER : DOMINO_COFFSET);
1448 y1 = cy + (i ? DOMINO_COFFSET : DOMINO_GUTTER);
1449 x2 = cx + TILESIZE-1 - (i ? DOMINO_GUTTER : DOMINO_COFFSET);
1450 y2 = cy + TILESIZE-1 - (i ? DOMINO_COFFSET : DOMINO_GUTTER);
1451 if (type == TYPE_L)
1452 x2 = cx + TILESIZE-1;
1453 else if (type == TYPE_R)
1454 x1 = cx;
1455 else if (type == TYPE_T)
1456 y2 = cy + TILESIZE-1;
1457 else if (type == TYPE_B)
1458 y1 = cy;
1459
1460 draw_rect(fe, x1, y1, x2-x1+1, y2-y1+1, bg);
1461 }
1462 } else {
1463 if (flags & EDGE_T)
1464 draw_rect(fe, cx+DOMINO_GUTTER, cy,
1465 TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE);
1466 if (flags & EDGE_B)
1467 draw_rect(fe, cx+DOMINO_GUTTER, cy+TILESIZE-1,
1468 TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE);
1469 if (flags & EDGE_L)
1470 draw_rect(fe, cx, cy+DOMINO_GUTTER,
1471 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE);
1472 if (flags & EDGE_R)
1473 draw_rect(fe, cx+TILESIZE-1, cy+DOMINO_GUTTER,
1474 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE);
1475 nc = COL_TEXT;
1476 }
1477
1478 sprintf(str, "%d", state->numbers->numbers[y*w+x]);
1479 draw_text(fe, cx+TILESIZE/2, cy+TILESIZE/2, FONT_VARIABLE, TILESIZE/2,
1480 ALIGN_HCENTRE | ALIGN_VCENTRE, nc, str);
1481
1482 draw_update(fe, cx, cy, TILESIZE, TILESIZE);
1483}
1484
1485static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1486 game_state *state, int dir, game_ui *ui,
1487 float animtime, float flashtime)
1488{
1489 int n = state->params.n, w = state->w, h = state->h, wh = w*h;
1490 int x, y, i;
1491 unsigned char *used;
1492
1493 if (!ds->started) {
1494 int pw, ph;
1495 game_compute_size(&state->params, TILESIZE, &pw, &ph);
1496 draw_rect(fe, 0, 0, pw, ph, COL_BACKGROUND);
1497 draw_update(fe, 0, 0, pw, ph);
1498 ds->started = TRUE;
1499 }
1500
1501 /*
1502 * See how many dominoes of each type there are, so we can
1503 * highlight clashes in red.
1504 */
1505 used = snewn(TRI(n+1), unsigned char);
1506 memset(used, 0, TRI(n+1));
1507 for (i = 0; i < wh; i++)
1508 if (state->grid[i] > i) {
1509 int n1, n2, di;
1510
1511 n1 = state->numbers->numbers[i];
1512 n2 = state->numbers->numbers[state->grid[i]];
1513
1514 di = DINDEX(n1, n2);
1515 assert(di >= 0 && di < TRI(n+1));
1516
1517 if (used[di] < 2)
1518 used[di]++;
1519 }
1520
1521 for (y = 0; y < h; y++)
1522 for (x = 0; x < w; x++) {
1523 int n = y*w+x;
1524 int n1, n2, di;
1525 unsigned long c;
1526
1527 if (state->grid[n] == n-1)
1528 c = TYPE_R;
1529 else if (state->grid[n] == n+1)
1530 c = TYPE_L;
1531 else if (state->grid[n] == n-w)
1532 c = TYPE_B;
1533 else if (state->grid[n] == n+w)
1534 c = TYPE_T;
1535 else
1536 c = TYPE_BLANK;
1537
1538 if (c != TYPE_BLANK) {
1539 n1 = state->numbers->numbers[n];
1540 n2 = state->numbers->numbers[state->grid[n]];
1541 di = DINDEX(n1, n2);
1542 if (used[di] > 1)
1543 c |= 0x80; /* highlight a clash */
1544 } else {
1545 c |= state->edges[n];
1546 }
1547
1548 if (flashtime != 0)
1549 c |= 0x40; /* we're flashing */
1550
1551 if (ds->visible[n] != c) {
1552 draw_tile(fe, ds, state, x, y, c);
1553 ds->visible[n] = c;
1554 }
1555 }
1556
1557 sfree(used);
1558}
1559
1560static float game_anim_length(game_state *oldstate, game_state *newstate,
1561 int dir, game_ui *ui)
1562{
1563 return 0.0F;
1564}
1565
1566static float game_flash_length(game_state *oldstate, game_state *newstate,
1567 int dir, game_ui *ui)
1568{
1569 if (!oldstate->completed && newstate->completed &&
1570 !oldstate->cheated && !newstate->cheated)
1571 return FLASH_TIME;
1572 return 0.0F;
1573}
1574
1575static int game_wants_statusbar(void)
1576{
1577 return FALSE;
1578}
1579
1580static int game_timing_state(game_state *state, game_ui *ui)
1581{
1582 return TRUE;
1583}
1584
1585#ifdef COMBINED
1586#define thegame dominosa
1587#endif
1588
1589const struct game thegame = {
1590 "Dominosa", "games.dominosa",
1591 default_params,
1592 game_fetch_preset,
1593 decode_params,
1594 encode_params,
1595 free_params,
1596 dup_params,
1597 TRUE, game_configure, custom_params,
1598 validate_params,
1599 new_game_desc,
1600 validate_desc,
1601 new_game,
1602 dup_game,
1603 free_game,
1604 TRUE, solve_game,
1605 FALSE, game_text_format,
1606 new_ui,
1607 free_ui,
1608 encode_ui,
1609 decode_ui,
1610 game_changed_state,
1611 interpret_move,
1612 execute_move,
1613 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1614 game_colours,
1615 game_new_drawstate,
1616 game_free_drawstate,
1617 game_redraw,
1618 game_anim_length,
1619 game_flash_length,
1620 game_wants_statusbar,
1621 FALSE, game_timing_state,
1622 0, /* mouse_priorities */
1623};
Simon Tatham's portable puzzles collection; import of svn://svn.tartarus.org/sgt/puzzles