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.
10 * - improve solver so as to use more interesting forms of
13 * * rule out a domino placement if it would divide an unfilled
14 * region such that at least one resulting region had an odd
16 * + use b.f.s. to determine the area of an unfilled region
17 * + a square is unfilled iff it has at least two possible
18 * placements, and two adjacent unfilled squares are part
19 * of the same region iff the domino placement joining
22 * * perhaps set analysis
23 * + look at all unclaimed squares containing a given number
24 * + for each one, find the set of possible numbers that it
25 * can connect to (i.e. each neighbouring tile such that
26 * the placement between it and that neighbour has not yet
28 * + now proceed similarly to Solo set analysis: try to find
29 * a subset of the squares such that the union of their
30 * possible numbers is the same size as the subset. If so,
31 * rule out those possible numbers for all other squares.
32 * * important wrinkle: the double dominoes complicate
33 * matters. Connecting a number to itself uses up _two_
34 * of the unclaimed squares containing a number. Thus,
35 * when finding the initial subset we must never
36 * include two adjacent squares; and also, when ruling
37 * things out after finding the subset, we must be
38 * careful that we don't rule out precisely the domino
39 * placement that was _included_ in our set!
51 /* nth triangular number */
52 #define TRI(n) ( (n) * ((n) + 1) / 2 )
53 /* number of dominoes for value n */
54 #define DCOUNT(n) TRI((n)+1)
55 /* map a pair of numbers to a unique domino index from 0 upwards. */
56 #define DINDEX(n1,n2) ( TRI(max(n1,n2)) + min(n1,n2) )
58 #define FLASH_TIME 0.13F
77 int *numbers
; /* h x w */
88 struct game_numbers
*numbers
;
90 unsigned short *edges
; /* h x w */
91 int completed
, cheated
;
94 static game_params
*default_params(void)
96 game_params
*ret
= snew(game_params
);
104 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
111 case 0: n
= 3; break;
112 case 1: n
= 6; break;
113 case 2: n
= 9; break;
114 default: return FALSE
;
117 sprintf(buf
, "Up to double-%d", n
);
120 *params
= ret
= snew(game_params
);
127 static void free_params(game_params
*params
)
132 static game_params
*dup_params(game_params
*params
)
134 game_params
*ret
= snew(game_params
);
135 *ret
= *params
; /* structure copy */
139 static void decode_params(game_params
*params
, char const *string
)
141 params
->n
= atoi(string
);
142 while (*string
&& isdigit((unsigned char)*string
)) string
++;
144 params
->unique
= FALSE
;
147 static char *encode_params(game_params
*params
, int full
)
150 sprintf(buf
, "%d", params
->n
);
151 if (full
&& !params
->unique
)
156 static config_item
*game_configure(game_params
*params
)
161 ret
= snewn(3, config_item
);
163 ret
[0].name
= "Maximum number on dominoes";
164 ret
[0].type
= C_STRING
;
165 sprintf(buf
, "%d", params
->n
);
166 ret
[0].sval
= dupstr(buf
);
169 ret
[1].name
= "Ensure unique solution";
170 ret
[1].type
= C_BOOLEAN
;
172 ret
[1].ival
= params
->unique
;
182 static game_params
*custom_params(config_item
*cfg
)
184 game_params
*ret
= snew(game_params
);
186 ret
->n
= atoi(cfg
[0].sval
);
187 ret
->unique
= cfg
[1].ival
;
192 static char *validate_params(game_params
*params
, int full
)
195 return "Maximum face number must be at least one";
199 /* ----------------------------------------------------------------------
203 static int find_overlaps(int w
, int h
, int placement
, int *set
)
207 n
= 0; /* number of returned placements */
215 * Horizontal domino, indexed by its left end.
218 set
[n
++] = placement
-2; /* horizontal domino to the left */
220 set
[n
++] = placement
-2*w
-1;/* vertical domino above left side */
222 set
[n
++] = placement
-1; /* vertical domino below left side */
224 set
[n
++] = placement
+2; /* horizontal domino to the right */
226 set
[n
++] = placement
-2*w
+2-1;/* vertical domino above right side */
228 set
[n
++] = placement
+2-1; /* vertical domino below right side */
231 * Vertical domino, indexed by its top end.
234 set
[n
++] = placement
-2*w
; /* vertical domino above */
236 set
[n
++] = placement
-2+1; /* horizontal domino left of top */
238 set
[n
++] = placement
+1; /* horizontal domino right of top */
240 set
[n
++] = placement
+2*w
; /* vertical domino below */
242 set
[n
++] = placement
-2+2*w
+1;/* horizontal domino left of bottom */
244 set
[n
++] = placement
+2*w
+1;/* horizontal domino right of bottom */
251 * Returns 0, 1 or 2 for number of solutions. 2 means `any number
252 * more than one', or more accurately `we were unable to prove
253 * there was only one'.
255 * Outputs in a `placements' array, indexed the same way as the one
256 * within this function (see below); entries in there are <0 for a
257 * placement ruled out, 0 for an uncertain placement, and 1 for a
260 static int solver(int w
, int h
, int n
, int *grid
, int *output
)
262 int wh
= w
*h
, dc
= DCOUNT(n
);
263 int *placements
, *heads
;
267 * This array has one entry for every possible domino
268 * placement. Vertical placements are indexed by their top
269 * half, at (y*w+x)*2; horizontal placements are indexed by
270 * their left half at (y*w+x)*2+1.
272 * This array is used to link domino placements together into
273 * linked lists, so that we can track all the possible
274 * placements of each different domino. It's also used as a
275 * quick means of looking up an individual placement to see
276 * whether we still think it's possible. Actual values stored
277 * in this array are -2 (placement not possible at all), -1
278 * (end of list), or the array index of the next item.
280 * Oh, and -3 for `not even valid', used for array indices
281 * which don't even represent a plausible placement.
283 placements
= snewn(2*wh
, int);
284 for (i
= 0; i
< 2*wh
; i
++)
285 placements
[i
] = -3; /* not even valid */
288 * This array has one entry for every domino, and it is an
289 * index into `placements' denoting the head of the placement
290 * list for that domino.
292 heads
= snewn(dc
, int);
293 for (i
= 0; i
< dc
; i
++)
297 * Set up the initial possibility lists by scanning the grid.
299 for (y
= 0; y
< h
-1; y
++)
300 for (x
= 0; x
< w
; x
++) {
301 int di
= DINDEX(grid
[y
*w
+x
], grid
[(y
+1)*w
+x
]);
302 placements
[(y
*w
+x
)*2] = heads
[di
];
303 heads
[di
] = (y
*w
+x
)*2;
305 for (y
= 0; y
< h
; y
++)
306 for (x
= 0; x
< w
-1; x
++) {
307 int di
= DINDEX(grid
[y
*w
+x
], grid
[y
*w
+(x
+1)]);
308 placements
[(y
*w
+x
)*2+1] = heads
[di
];
309 heads
[di
] = (y
*w
+x
)*2+1;
312 #ifdef SOLVER_DIAGNOSTICS
313 printf("before solver:\n");
314 for (i
= 0; i
<= n
; i
++)
315 for (j
= 0; j
<= i
; j
++) {
318 printf("%2d [%d %d]:", DINDEX(i
, j
), i
, j
);
319 for (k
= heads
[DINDEX(i
,j
)]; k
>= 0; k
= placements
[k
])
320 printf(" %3d [%d,%d,%c]", k
, k
/2%w
, k
/2/w
, k
%2?
'h':'v');
326 int done_something
= FALSE
;
329 * For each domino, look at its possible placements, and
330 * for each placement consider the placements (of any
331 * domino) it overlaps. Any placement overlapped by all
332 * placements of this domino can be ruled out.
334 * Each domino placement overlaps only six others, so we
335 * need not do serious set theory to work this out.
337 for (i
= 0; i
< dc
; i
++) {
338 int permset
[6], permlen
= 0, p
;
341 if (heads
[i
] == -1) { /* no placement for this domino */
342 ret
= 0; /* therefore puzzle is impossible */
345 for (j
= heads
[i
]; j
>= 0; j
= placements
[j
]) {
346 assert(placements
[j
] != -2);
349 permlen
= find_overlaps(w
, h
, j
, permset
);
351 int tempset
[6], templen
, m
, n
, k
;
353 templen
= find_overlaps(w
, h
, j
, tempset
);
356 * Pathetically primitive set intersection
357 * algorithm, which I'm only getting away with
358 * because I know my sets are bounded by a very
361 for (m
= n
= 0; m
< permlen
; m
++) {
362 for (k
= 0; k
< templen
; k
++)
363 if (tempset
[k
] == permset
[m
])
366 permset
[n
++] = permset
[m
];
371 for (p
= 0; p
< permlen
; p
++) {
373 if (placements
[j
] != -2) {
376 done_something
= TRUE
;
379 * Rule out this placement. First find what
383 p2
= (j
& 1) ? p1
+ 1 : p1
+ w
;
384 di
= DINDEX(grid
[p1
], grid
[p2
]);
385 #ifdef SOLVER_DIAGNOSTICS
386 printf("considering domino %d: ruling out placement %d"
387 " for %d\n", i
, j
, di
);
391 * ... then walk that domino's placement list,
392 * removing this placement when we find it.
395 heads
[di
] = placements
[j
];
398 while (placements
[k
] != -1 && placements
[k
] != j
)
400 assert(placements
[k
] == j
);
401 placements
[k
] = placements
[j
];
409 * For each square, look at the available placements
410 * involving that square. If all of them are for the same
411 * domino, then rule out any placements for that domino
412 * _not_ involving this square.
414 for (i
= 0; i
< wh
; i
++) {
415 int list
[4], k
, n
, adi
;
422 list
[j
++] = 2*(i
-1)+1;
430 for (n
= k
= 0; k
< j
; k
++)
431 if (placements
[list
[k
]] >= -1)
436 for (j
= 0; j
< n
; j
++) {
441 p2
= (k
& 1) ? p1
+ 1 : p1
+ w
;
442 di
= DINDEX(grid
[p1
], grid
[p2
]);
455 * We've found something. All viable placements
456 * involving this square are for domino `adi'. If
457 * the current placement list for that domino is
458 * longer than n, reduce it to precisely this
459 * placement list and we've done something.
462 for (k
= heads
[adi
]; k
>= 0; k
= placements
[k
])
465 done_something
= TRUE
;
466 #ifdef SOLVER_DIAGNOSTICS
467 printf("considering square %d,%d: reducing placements "
468 "of domino %d\n", x
, y
, adi
);
471 * Set all other placements on the list to
476 int tmp
= placements
[k
];
481 * Set up the new list.
483 heads
[adi
] = list
[0];
484 for (k
= 0; k
< n
; k
++)
485 placements
[list
[k
]] = (k
+1 == n ?
-1 : list
[k
+1]);
494 #ifdef SOLVER_DIAGNOSTICS
495 printf("after solver:\n");
496 for (i
= 0; i
<= n
; i
++)
497 for (j
= 0; j
<= i
; j
++) {
500 printf("%2d [%d %d]:", DINDEX(i
, j
), i
, j
);
501 for (k
= heads
[DINDEX(i
,j
)]; k
>= 0; k
= placements
[k
])
502 printf(" %3d [%d,%d,%c]", k
, k
/2%w
, k
/2/w
, k
%2?
'h':'v');
508 for (i
= 0; i
< wh
*2; i
++) {
509 if (placements
[i
] == -2) {
511 output
[i
] = -1; /* ruled out */
512 } else if (placements
[i
] != -3) {
516 p2
= (i
& 1) ? p1
+ 1 : p1
+ w
;
517 di
= DINDEX(grid
[p1
], grid
[p2
]);
519 if (i
== heads
[di
] && placements
[i
] == -1) {
521 output
[i
] = 1; /* certain */
524 output
[i
] = 0; /* uncertain */
540 /* ----------------------------------------------------------------------
541 * End of solver code.
544 static char *new_game_desc(game_params
*params
, random_state
*rs
,
545 char **aux
, int interactive
)
547 int n
= params
->n
, w
= n
+2, h
= n
+1, wh
= w
*h
;
548 int *grid
, *grid2
, *list
;
549 int i
, j
, k
, m
, todo
, done
, len
;
553 * Allocate space in which to lay the grid out.
555 grid
= snewn(wh
, int);
556 grid2
= snewn(wh
, int);
557 list
= snewn(2*wh
, int);
560 * I haven't been able to think of any particularly clever
561 * techniques for generating instances of Dominosa with a
562 * unique solution. Many of the deductions used in this puzzle
563 * are based on information involving half the grid at a time
564 * (`of all the 6s, exactly one is next to a 3'), so a strategy
565 * of partially solving the grid and then perturbing the place
566 * where the solver got stuck seems particularly likely to
567 * accidentally destroy the information which the solver had
568 * used in getting that far. (Contrast with, say, Mines, in
569 * which most deductions are local so this is an excellent
572 * Therefore I resort to the basest of brute force methods:
573 * generate a random grid, see if it's solvable, throw it away
574 * and try again if not. My only concession to sophistication
575 * and cleverness is to at least _try_ not to generate obvious
576 * 2x2 ambiguous sections (see comment below in the domino-
579 * During tests performed on 2005-07-15, I found that the brute
580 * force approach without that tweak had to throw away about 87
581 * grids on average (at the default n=6) before finding a
582 * unique one, or a staggering 379 at n=9; good job the
583 * generator and solver are fast! When I added the
584 * ambiguous-section avoidance, those numbers came down to 19
585 * and 26 respectively, which is a lot more sensible.
590 * To begin with, set grid[i] = i for all i to indicate
591 * that all squares are currently singletons. Later we'll
592 * set grid[i] to be the index of the other end of the
595 for (i
= 0; i
< wh
; i
++)
599 * Now prepare a list of the possible domino locations. There
600 * are w*(h-1) possible vertical locations, and (w-1)*h
601 * horizontal ones, for a total of 2*wh - h - w.
603 * I'm going to denote the vertical domino placement with
604 * its top in square i as 2*i, and the horizontal one with
605 * its left half in square i as 2*i+1.
608 for (j
= 0; j
< h
-1; j
++)
609 for (i
= 0; i
< w
; i
++)
610 list
[k
++] = 2 * (j
*w
+i
); /* vertical positions */
611 for (j
= 0; j
< h
; j
++)
612 for (i
= 0; i
< w
-1; i
++)
613 list
[k
++] = 2 * (j
*w
+i
) + 1; /* horizontal positions */
614 assert(k
== 2*wh
- h
- w
);
619 shuffle(list
, k
, sizeof(*list
), rs
);
622 * Work down the shuffled list, placing a domino everywhere
625 for (i
= 0; i
< k
; i
++) {
630 xy2
= xy
+ (horiz ?
1 : w
);
632 if (grid
[xy
] == xy
&& grid
[xy2
] == xy2
) {
634 * We can place this domino. Do so.
641 #ifdef GENERATION_DIAGNOSTICS
642 printf("generated initial layout\n");
646 * Now we've placed as many dominoes as we can immediately
647 * manage. There will be squares remaining, but they'll be
648 * singletons. So loop round and deal with the singletons
652 #ifdef GENERATION_DIAGNOSTICS
653 for (j
= 0; j
< h
; j
++) {
654 for (i
= 0; i
< w
; i
++) {
657 int c
= (v
== xy
+1 ?
'[' : v
== xy
-1 ?
']' :
658 v
== xy
+w ?
'n' : v
== xy
-w ?
'U' : '.');
669 * First find a singleton square.
671 * Then breadth-first search out from the starting
672 * square. From that square (and any others we reach on
673 * the way), examine all four neighbours of the square.
674 * If one is an end of a domino, we move to the _other_
675 * end of that domino before looking at neighbours
676 * again. When we encounter another singleton on this
679 * This will give us a path of adjacent squares such
680 * that all but the two ends are covered in dominoes.
681 * So we can now shuffle every domino on the path up by
684 * (Chessboard colours are mathematically important
685 * here: we always end up pairing each singleton with a
686 * singleton of the other colour. However, we never
687 * have to track this manually, since it's
688 * automatically taken care of by the fact that we
689 * always make an even number of orthogonal moves.)
691 for (i
= 0; i
< wh
; i
++)
695 break; /* no more singletons; we're done. */
697 #ifdef GENERATION_DIAGNOSTICS
698 printf("starting b.f.s. at singleton %d\n", i
);
701 * Set grid2 to -1 everywhere. It will hold our
702 * distance-from-start values, and also our
703 * backtracking data, during the b.f.s.
705 for (j
= 0; j
< wh
; j
++)
707 grid2
[i
] = 0; /* starting square has distance zero */
710 * Start our to-do list of squares. It'll live in
711 * `list'; since the b.f.s can cover every square at
712 * most once there is no need for it to be circular.
713 * We'll just have two counters tracking the end of the
714 * list and the squares we've already dealt with.
721 * Now begin the b.f.s. loop.
723 while (done
< todo
) {
728 #ifdef GENERATION_DIAGNOSTICS
729 printf("b.f.s. iteration from %d\n", i
);
743 * To avoid directional bias, process the
744 * neighbours of this square in a random order.
746 shuffle(d
, nd
, sizeof(*d
), rs
);
748 for (j
= 0; j
< nd
; j
++) {
751 #ifdef GENERATION_DIAGNOSTICS
752 printf("found neighbouring singleton %d\n", k
);
755 break; /* found a target singleton! */
759 * We're moving through a domino here, so we
760 * have two entries in grid2 to fill with
761 * useful data. In grid[k] - the square
762 * adjacent to where we came from - I'm going
763 * to put the address _of_ the square we came
764 * from. In the other end of the domino - the
765 * square from which we will continue the
766 * search - I'm going to put the distance.
770 if (grid2
[m
] < 0 || grid2
[m
] > grid2
[i
]+1) {
771 #ifdef GENERATION_DIAGNOSTICS
772 printf("found neighbouring domino %d/%d\n", k
, m
);
774 grid2
[m
] = grid2
[i
]+1;
777 * And since we've now visited a new
778 * domino, add m to the to-do list.
787 #ifdef GENERATION_DIAGNOSTICS
788 printf("terminating b.f.s. loop, i = %d\n", i
);
793 i
= -1; /* just in case the loop terminates */
797 * We expect this b.f.s. to have found us a target
803 * Now we can follow the trail back to our starting
804 * singleton, re-laying dominoes as we go.
808 assert(j
>= 0 && j
< wh
);
813 #ifdef GENERATION_DIAGNOSTICS
814 printf("filling in domino %d/%d (next %d)\n", i
, j
, k
);
817 break; /* we've reached the other singleton */
820 #ifdef GENERATION_DIAGNOSTICS
821 printf("fixup path completed\n");
826 * Now we have a complete layout covering the whole
827 * rectangle with dominoes. So shuffle the actual domino
828 * values and fill the rectangle with numbers.
831 for (i
= 0; i
<= params
->n
; i
++)
832 for (j
= 0; j
<= i
; j
++) {
836 shuffle(list
, k
/2, 2*sizeof(*list
), rs
);
838 for (i
= 0; i
< wh
; i
++)
840 /* Optionally flip the domino round. */
843 if (params
->unique
) {
846 * If we're after a unique solution, we can do
847 * something here to improve the chances. If
848 * we're placing a domino so that it forms a
849 * 2x2 rectangle with one we've already placed,
850 * and if that domino and this one share a
851 * number, we can try not to put them so that
852 * the identical numbers are diagonally
853 * separated, because that automatically causes
864 if (t2
== t1
+ w
) { /* this domino is vertical */
865 if (t1
% w
> 0 &&/* and not on the left hand edge */
866 grid
[t1
-1] == t2
-1 &&/* alongside one to left */
867 (grid2
[t1
-1] == list
[j
] || /* and has a number */
868 grid2
[t1
-1] == list
[j
+1] || /* in common */
869 grid2
[t2
-1] == list
[j
] ||
870 grid2
[t2
-1] == list
[j
+1])) {
871 if (grid2
[t1
-1] == list
[j
] ||
872 grid2
[t2
-1] == list
[j
+1])
877 } else { /* this domino is horizontal */
878 if (t1
/ w
> 0 &&/* and not on the top edge */
879 grid
[t1
-w
] == t2
-w
&&/* alongside one above */
880 (grid2
[t1
-w
] == list
[j
] || /* and has a number */
881 grid2
[t1
-w
] == list
[j
+1] || /* in common */
882 grid2
[t2
-w
] == list
[j
] ||
883 grid2
[t2
-w
] == list
[j
+1])) {
884 if (grid2
[t1
-w
] == list
[j
] ||
885 grid2
[t2
-w
] == list
[j
+1])
894 flip
= random_upto(rs
, 2);
896 grid2
[i
] = list
[j
+ flip
];
897 grid2
[grid
[i
]] = list
[j
+ 1 - flip
];
901 } while (params
->unique
&& solver(w
, h
, n
, grid2
, NULL
) > 1);
903 #ifdef GENERATION_DIAGNOSTICS
904 for (j
= 0; j
< h
; j
++) {
905 for (i
= 0; i
< w
; i
++) {
906 putchar('0' + grid2
[j
*w
+i
]);
914 * Encode the resulting game state.
916 * Our encoding is a string of digits. Any number greater than
917 * 9 is represented by a decimal integer within square
918 * brackets. We know there are n+2 of every number (it's paired
919 * with each number from 0 to n inclusive, and one of those is
920 * itself so that adds another occurrence), so we can work out
921 * the string length in advance.
925 * To work out the total length of the decimal encodings of all
926 * the numbers from 0 to n inclusive:
927 * - every number has a units digit; total is n+1.
928 * - all numbers above 9 have a tens digit; total is max(n+1-10,0).
929 * - all numbers above 99 have a hundreds digit; total is max(n+1-100,0).
933 for (i
= 10; i
<= n
; i
*= 10)
934 len
+= max(n
+ 1 - i
, 0);
935 /* Now add two square brackets for each number above 9. */
936 len
+= 2 * max(n
+ 1 - 10, 0);
937 /* And multiply by n+2 for the repeated occurrences of each number. */
941 * Now actually encode the string.
943 ret
= snewn(len
+1, char);
945 for (i
= 0; i
< wh
; i
++) {
950 j
+= sprintf(ret
+j
, "[%d]", k
);
957 * Encode the solved state as an aux_info.
960 char *auxinfo
= snewn(wh
+1, char);
962 for (i
= 0; i
< wh
; i
++) {
964 auxinfo
[i
] = (v
== i
+1 ?
'L' : v
== i
-1 ?
'R' :
965 v
== i
+w ?
'T' : v
== i
-w ?
'B' : '.');
979 static char *validate_desc(game_params
*params
, char *desc
)
981 int n
= params
->n
, w
= n
+2, h
= n
+1, wh
= w
*h
;
987 occurrences
= snewn(n
+1, int);
988 for (i
= 0; i
<= n
; i
++)
991 for (i
= 0; i
< wh
; i
++) {
993 ret
= ret ? ret
: "Game description is too short";
995 if (*desc
>= '0' && *desc
<= '9')
997 else if (*desc
== '[') {
1000 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1002 ret
= ret ? ret
: "Missing ']' in game description";
1007 ret
= ret ? ret
: "Invalid syntax in game description";
1010 ret
= ret ? ret
: "Number out of range in game description";
1017 ret
= ret ? ret
: "Game description is too long";
1020 for (i
= 0; i
<= n
; i
++)
1021 if (occurrences
[i
] != n
+2)
1022 ret
= "Incorrect number balance in game description";
1030 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1032 int n
= params
->n
, w
= n
+2, h
= n
+1, wh
= w
*h
;
1033 game_state
*state
= snew(game_state
);
1036 state
->params
= *params
;
1040 state
->grid
= snewn(wh
, int);
1041 for (i
= 0; i
< wh
; i
++)
1044 state
->edges
= snewn(wh
, unsigned short);
1045 for (i
= 0; i
< wh
; i
++)
1046 state
->edges
[i
] = 0;
1048 state
->numbers
= snew(struct game_numbers
);
1049 state
->numbers
->refcount
= 1;
1050 state
->numbers
->numbers
= snewn(wh
, int);
1052 for (i
= 0; i
< wh
; i
++) {
1054 if (*desc
>= '0' && *desc
<= '9')
1057 assert(*desc
== '[');
1060 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1061 assert(*desc
== ']');
1064 assert(j
>= 0 && j
<= n
);
1065 state
->numbers
->numbers
[i
] = j
;
1068 state
->completed
= state
->cheated
= FALSE
;
1073 static game_state
*dup_game(game_state
*state
)
1075 int n
= state
->params
.n
, w
= n
+2, h
= n
+1, wh
= w
*h
;
1076 game_state
*ret
= snew(game_state
);
1078 ret
->params
= state
->params
;
1081 ret
->grid
= snewn(wh
, int);
1082 memcpy(ret
->grid
, state
->grid
, wh
* sizeof(int));
1083 ret
->edges
= snewn(wh
, unsigned short);
1084 memcpy(ret
->edges
, state
->edges
, wh
* sizeof(unsigned short));
1085 ret
->numbers
= state
->numbers
;
1086 ret
->numbers
->refcount
++;
1087 ret
->completed
= state
->completed
;
1088 ret
->cheated
= state
->cheated
;
1093 static void free_game(game_state
*state
)
1096 sfree(state
->edges
);
1097 if (--state
->numbers
->refcount
<= 0) {
1098 sfree(state
->numbers
->numbers
);
1099 sfree(state
->numbers
);
1104 static char *solve_game(game_state
*state
, game_state
*currstate
,
1105 char *aux
, char **error
)
1107 int n
= state
->params
.n
, w
= n
+2, h
= n
+1, wh
= w
*h
;
1110 int retlen
, retsize
;
1117 ret
= snewn(retsize
, char);
1118 retlen
= sprintf(ret
, "S");
1120 for (i
= 0; i
< wh
; i
++) {
1122 extra
= sprintf(buf
, ";D%d,%d", i
, i
+1);
1123 else if (aux
[i
] == 'T')
1124 extra
= sprintf(buf
, ";D%d,%d", i
, i
+w
);
1128 if (retlen
+ extra
+ 1 >= retsize
) {
1129 retsize
= retlen
+ extra
+ 256;
1130 ret
= sresize(ret
, retsize
, char);
1132 strcpy(ret
+ retlen
, buf
);
1138 placements
= snewn(wh
*2, int);
1139 for (i
= 0; i
< wh
*2; i
++)
1141 solver(w
, h
, n
, state
->numbers
->numbers
, placements
);
1144 * First make a pass putting in edges for -1, then make a pass
1145 * putting in dominoes for +1.
1148 ret
= snewn(retsize
, char);
1149 retlen
= sprintf(ret
, "S");
1151 for (v
= -1; v
<= +1; v
+= 2)
1152 for (i
= 0; i
< wh
*2; i
++)
1153 if (placements
[i
] == v
) {
1155 int p2
= (i
& 1) ? p1
+1 : p1
+w
;
1157 extra
= sprintf(buf
, ";%c%d,%d",
1158 (int)(v
==-1 ?
'E' : 'D'), p1
, p2
);
1160 if (retlen
+ extra
+ 1 >= retsize
) {
1161 retsize
= retlen
+ extra
+ 256;
1162 ret
= sresize(ret
, retsize
, char);
1164 strcpy(ret
+ retlen
, buf
);
1174 static int game_can_format_as_text_now(game_params
*params
)
1179 static char *game_text_format(game_state
*state
)
1184 static game_ui
*new_ui(game_state
*state
)
1189 static void free_ui(game_ui
*ui
)
1193 static char *encode_ui(game_ui
*ui
)
1198 static void decode_ui(game_ui
*ui
, char *encoding
)
1202 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1203 game_state
*newstate
)
1207 #define PREFERRED_TILESIZE 32
1208 #define TILESIZE (ds->tilesize)
1209 #define BORDER (TILESIZE * 3 / 4)
1210 #define DOMINO_GUTTER (TILESIZE / 16)
1211 #define DOMINO_RADIUS (TILESIZE / 8)
1212 #define DOMINO_COFFSET (DOMINO_GUTTER + DOMINO_RADIUS)
1214 #define COORD(x) ( (x) * TILESIZE + BORDER )
1215 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1217 struct game_drawstate
{
1220 unsigned long *visible
;
1223 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1224 int x
, int y
, int button
)
1226 int w
= state
->w
, h
= state
->h
;
1230 * A left-click between two numbers toggles a domino covering
1231 * them. A right-click toggles an edge.
1233 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
1234 int tx
= FROMCOORD(x
), ty
= FROMCOORD(y
), t
= ty
*w
+tx
;
1238 if (tx
< 0 || tx
>= w
|| ty
< 0 || ty
>= h
)
1242 * Now we know which square the click was in, decide which
1243 * edge of the square it was closest to.
1245 dx
= 2 * (x
- COORD(tx
)) - TILESIZE
;
1246 dy
= 2 * (y
- COORD(ty
)) - TILESIZE
;
1248 if (abs(dx
) > abs(dy
) && dx
< 0 && tx
> 0)
1249 d1
= t
- 1, d2
= t
; /* clicked in right side of domino */
1250 else if (abs(dx
) > abs(dy
) && dx
> 0 && tx
+1 < w
)
1251 d1
= t
, d2
= t
+ 1; /* clicked in left side of domino */
1252 else if (abs(dy
) > abs(dx
) && dy
< 0 && ty
> 0)
1253 d1
= t
- w
, d2
= t
; /* clicked in bottom half of domino */
1254 else if (abs(dy
) > abs(dx
) && dy
> 0 && ty
+1 < h
)
1255 d1
= t
, d2
= t
+ w
; /* clicked in top half of domino */
1260 * We can't mark an edge next to any domino.
1262 if (button
== RIGHT_BUTTON
&&
1263 (state
->grid
[d1
] != d1
|| state
->grid
[d2
] != d2
))
1266 sprintf(buf
, "%c%d,%d", (int)(button
== RIGHT_BUTTON ?
'E' : 'D'), d1
, d2
);
1273 static game_state
*execute_move(game_state
*state
, char *move
)
1275 int n
= state
->params
.n
, w
= n
+2, h
= n
+1, wh
= w
*h
;
1277 game_state
*ret
= dup_game(state
);
1280 if (move
[0] == 'S') {
1283 ret
->cheated
= TRUE
;
1286 * Clear the existing edges and domino placements. We
1287 * expect the S to be followed by other commands.
1289 for (i
= 0; i
< wh
; i
++) {
1294 } else if (move
[0] == 'D' &&
1295 sscanf(move
+1, "%d,%d%n", &d1
, &d2
, &p
) == 2 &&
1296 d1
>= 0 && d1
< wh
&& d2
>= 0 && d2
< wh
&& d1
< d2
) {
1299 * Toggle domino presence between d1 and d2.
1301 if (ret
->grid
[d1
] == d2
) {
1302 assert(ret
->grid
[d2
] == d1
);
1307 * Erase any dominoes that might overlap the new one.
1316 * Place the new one.
1322 * Destroy any edges lurking around it.
1324 if (ret
->edges
[d1
] & EDGE_L
) {
1325 assert(d1
- 1 >= 0);
1326 ret
->edges
[d1
- 1] &= ~EDGE_R
;
1328 if (ret
->edges
[d1
] & EDGE_R
) {
1329 assert(d1
+ 1 < wh
);
1330 ret
->edges
[d1
+ 1] &= ~EDGE_L
;
1332 if (ret
->edges
[d1
] & EDGE_T
) {
1333 assert(d1
- w
>= 0);
1334 ret
->edges
[d1
- w
] &= ~EDGE_B
;
1336 if (ret
->edges
[d1
] & EDGE_B
) {
1337 assert(d1
+ 1 < wh
);
1338 ret
->edges
[d1
+ w
] &= ~EDGE_T
;
1341 if (ret
->edges
[d2
] & EDGE_L
) {
1342 assert(d2
- 1 >= 0);
1343 ret
->edges
[d2
- 1] &= ~EDGE_R
;
1345 if (ret
->edges
[d2
] & EDGE_R
) {
1346 assert(d2
+ 1 < wh
);
1347 ret
->edges
[d2
+ 1] &= ~EDGE_L
;
1349 if (ret
->edges
[d2
] & EDGE_T
) {
1350 assert(d2
- w
>= 0);
1351 ret
->edges
[d2
- w
] &= ~EDGE_B
;
1353 if (ret
->edges
[d2
] & EDGE_B
) {
1354 assert(d2
+ 1 < wh
);
1355 ret
->edges
[d2
+ w
] &= ~EDGE_T
;
1361 } else if (move
[0] == 'E' &&
1362 sscanf(move
+1, "%d,%d%n", &d1
, &d2
, &p
) == 2 &&
1363 d1
>= 0 && d1
< wh
&& d2
>= 0 && d2
< wh
&& d1
< d2
&&
1364 ret
->grid
[d1
] == d1
&& ret
->grid
[d2
] == d2
) {
1367 * Toggle edge presence between d1 and d2.
1370 ret
->edges
[d1
] ^= EDGE_R
;
1371 ret
->edges
[d2
] ^= EDGE_L
;
1373 ret
->edges
[d1
] ^= EDGE_B
;
1374 ret
->edges
[d2
] ^= EDGE_T
;
1393 * After modifying the grid, check completion.
1395 if (!ret
->completed
) {
1397 unsigned char *used
= snewn(TRI(n
+1), unsigned char);
1399 memset(used
, 0, TRI(n
+1));
1400 for (i
= 0; i
< wh
; i
++)
1401 if (ret
->grid
[i
] > i
) {
1404 n1
= ret
->numbers
->numbers
[i
];
1405 n2
= ret
->numbers
->numbers
[ret
->grid
[i
]];
1407 di
= DINDEX(n1
, n2
);
1408 assert(di
>= 0 && di
< TRI(n
+1));
1417 if (ok
== DCOUNT(n
))
1418 ret
->completed
= TRUE
;
1424 /* ----------------------------------------------------------------------
1428 static void game_compute_size(game_params
*params
, int tilesize
,
1431 int n
= params
->n
, w
= n
+2, h
= n
+1;
1433 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1434 struct { int tilesize
; } ads
, *ds
= &ads
;
1435 ads
.tilesize
= tilesize
;
1437 *x
= w
* TILESIZE
+ 2*BORDER
;
1438 *y
= h
* TILESIZE
+ 2*BORDER
;
1441 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1442 game_params
*params
, int tilesize
)
1444 ds
->tilesize
= tilesize
;
1447 static float *game_colours(frontend
*fe
, int *ncolours
)
1449 float *ret
= snewn(3 * NCOLOURS
, float);
1451 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1453 ret
[COL_TEXT
* 3 + 0] = 0.0F
;
1454 ret
[COL_TEXT
* 3 + 1] = 0.0F
;
1455 ret
[COL_TEXT
* 3 + 2] = 0.0F
;
1457 ret
[COL_DOMINO
* 3 + 0] = 0.0F
;
1458 ret
[COL_DOMINO
* 3 + 1] = 0.0F
;
1459 ret
[COL_DOMINO
* 3 + 2] = 0.0F
;
1461 ret
[COL_DOMINOCLASH
* 3 + 0] = 0.5F
;
1462 ret
[COL_DOMINOCLASH
* 3 + 1] = 0.0F
;
1463 ret
[COL_DOMINOCLASH
* 3 + 2] = 0.0F
;
1465 ret
[COL_DOMINOTEXT
* 3 + 0] = 1.0F
;
1466 ret
[COL_DOMINOTEXT
* 3 + 1] = 1.0F
;
1467 ret
[COL_DOMINOTEXT
* 3 + 2] = 1.0F
;
1469 ret
[COL_EDGE
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 2 / 3;
1470 ret
[COL_EDGE
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 1] * 2 / 3;
1471 ret
[COL_EDGE
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2] * 2 / 3;
1473 *ncolours
= NCOLOURS
;
1477 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1479 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1482 ds
->started
= FALSE
;
1485 ds
->visible
= snewn(ds
->w
* ds
->h
, unsigned long);
1486 ds
->tilesize
= 0; /* not decided yet */
1487 for (i
= 0; i
< ds
->w
* ds
->h
; i
++)
1488 ds
->visible
[i
] = 0xFFFF;
1493 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1508 static void draw_tile(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
1509 int x
, int y
, int type
)
1511 int w
= state
->w
/*, h = state->h */;
1512 int cx
= COORD(x
), cy
= COORD(y
);
1517 draw_rect(dr
, cx
, cy
, TILESIZE
, TILESIZE
, COL_BACKGROUND
);
1519 flags
= type
&~ TYPE_MASK
;
1522 if (type
!= TYPE_BLANK
) {
1526 * Draw one end of a domino. This is composed of:
1528 * - two filled circles (rounded corners)
1530 * - a slight shift in the number
1534 bg
= COL_DOMINOCLASH
;
1537 nc
= COL_DOMINOTEXT
;
1545 if (type
== TYPE_L
|| type
== TYPE_T
)
1546 draw_circle(dr
, cx
+DOMINO_COFFSET
, cy
+DOMINO_COFFSET
,
1547 DOMINO_RADIUS
, bg
, bg
);
1548 if (type
== TYPE_R
|| type
== TYPE_T
)
1549 draw_circle(dr
, cx
+TILESIZE
-1-DOMINO_COFFSET
, cy
+DOMINO_COFFSET
,
1550 DOMINO_RADIUS
, bg
, bg
);
1551 if (type
== TYPE_L
|| type
== TYPE_B
)
1552 draw_circle(dr
, cx
+DOMINO_COFFSET
, cy
+TILESIZE
-1-DOMINO_COFFSET
,
1553 DOMINO_RADIUS
, bg
, bg
);
1554 if (type
== TYPE_R
|| type
== TYPE_B
)
1555 draw_circle(dr
, cx
+TILESIZE
-1-DOMINO_COFFSET
,
1556 cy
+TILESIZE
-1-DOMINO_COFFSET
,
1557 DOMINO_RADIUS
, bg
, bg
);
1559 for (i
= 0; i
< 2; i
++) {
1562 x1
= cx
+ (i ? DOMINO_GUTTER
: DOMINO_COFFSET
);
1563 y1
= cy
+ (i ? DOMINO_COFFSET
: DOMINO_GUTTER
);
1564 x2
= cx
+ TILESIZE
-1 - (i ? DOMINO_GUTTER
: DOMINO_COFFSET
);
1565 y2
= cy
+ TILESIZE
-1 - (i ? DOMINO_COFFSET
: DOMINO_GUTTER
);
1567 x2
= cx
+ TILESIZE
+ TILESIZE
/16;
1568 else if (type
== TYPE_R
)
1569 x1
= cx
- TILESIZE
/16;
1570 else if (type
== TYPE_T
)
1571 y2
= cy
+ TILESIZE
+ TILESIZE
/16;
1572 else if (type
== TYPE_B
)
1573 y1
= cy
- TILESIZE
/16;
1575 draw_rect(dr
, x1
, y1
, x2
-x1
+1, y2
-y1
+1, bg
);
1579 draw_rect(dr
, cx
+DOMINO_GUTTER
, cy
,
1580 TILESIZE
-2*DOMINO_GUTTER
, 1, COL_EDGE
);
1582 draw_rect(dr
, cx
+DOMINO_GUTTER
, cy
+TILESIZE
-1,
1583 TILESIZE
-2*DOMINO_GUTTER
, 1, COL_EDGE
);
1585 draw_rect(dr
, cx
, cy
+DOMINO_GUTTER
,
1586 1, TILESIZE
-2*DOMINO_GUTTER
, COL_EDGE
);
1588 draw_rect(dr
, cx
+TILESIZE
-1, cy
+DOMINO_GUTTER
,
1589 1, TILESIZE
-2*DOMINO_GUTTER
, COL_EDGE
);
1593 sprintf(str
, "%d", state
->numbers
->numbers
[y
*w
+x
]);
1594 draw_text(dr
, cx
+TILESIZE
/2, cy
+TILESIZE
/2, FONT_VARIABLE
, TILESIZE
/2,
1595 ALIGN_HCENTRE
| ALIGN_VCENTRE
, nc
, str
);
1597 draw_update(dr
, cx
, cy
, TILESIZE
, TILESIZE
);
1600 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1601 game_state
*state
, int dir
, game_ui
*ui
,
1602 float animtime
, float flashtime
)
1604 int n
= state
->params
.n
, w
= state
->w
, h
= state
->h
, wh
= w
*h
;
1606 unsigned char *used
;
1610 game_compute_size(&state
->params
, TILESIZE
, &pw
, &ph
);
1611 draw_rect(dr
, 0, 0, pw
, ph
, COL_BACKGROUND
);
1612 draw_update(dr
, 0, 0, pw
, ph
);
1617 * See how many dominoes of each type there are, so we can
1618 * highlight clashes in red.
1620 used
= snewn(TRI(n
+1), unsigned char);
1621 memset(used
, 0, TRI(n
+1));
1622 for (i
= 0; i
< wh
; i
++)
1623 if (state
->grid
[i
] > i
) {
1626 n1
= state
->numbers
->numbers
[i
];
1627 n2
= state
->numbers
->numbers
[state
->grid
[i
]];
1629 di
= DINDEX(n1
, n2
);
1630 assert(di
>= 0 && di
< TRI(n
+1));
1636 for (y
= 0; y
< h
; y
++)
1637 for (x
= 0; x
< w
; x
++) {
1642 if (state
->grid
[n
] == n
-1)
1644 else if (state
->grid
[n
] == n
+1)
1646 else if (state
->grid
[n
] == n
-w
)
1648 else if (state
->grid
[n
] == n
+w
)
1653 if (c
!= TYPE_BLANK
) {
1654 n1
= state
->numbers
->numbers
[n
];
1655 n2
= state
->numbers
->numbers
[state
->grid
[n
]];
1656 di
= DINDEX(n1
, n2
);
1658 c
|= 0x80; /* highlight a clash */
1660 c
|= state
->edges
[n
];
1664 c
|= 0x40; /* we're flashing */
1666 if (ds
->visible
[n
] != c
) {
1667 draw_tile(dr
, ds
, state
, x
, y
, c
);
1675 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1676 int dir
, game_ui
*ui
)
1681 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1682 int dir
, game_ui
*ui
)
1684 if (!oldstate
->completed
&& newstate
->completed
&&
1685 !oldstate
->cheated
&& !newstate
->cheated
)
1690 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1695 static void game_print_size(game_params
*params
, float *x
, float *y
)
1700 * I'll use 6mm squares by default.
1702 game_compute_size(params
, 600, &pw
, &ph
);
1707 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1709 int w
= state
->w
, h
= state
->h
;
1712 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1713 game_drawstate ads
, *ds
= &ads
;
1714 game_set_size(dr
, ds
, NULL
, tilesize
);
1716 c
= print_mono_colour(dr
, 1); assert(c
== COL_BACKGROUND
);
1717 c
= print_mono_colour(dr
, 0); assert(c
== COL_TEXT
);
1718 c
= print_mono_colour(dr
, 0); assert(c
== COL_DOMINO
);
1719 c
= print_mono_colour(dr
, 0); assert(c
== COL_DOMINOCLASH
);
1720 c
= print_mono_colour(dr
, 1); assert(c
== COL_DOMINOTEXT
);
1721 c
= print_mono_colour(dr
, 0); assert(c
== COL_EDGE
);
1723 for (y
= 0; y
< h
; y
++)
1724 for (x
= 0; x
< w
; x
++) {
1728 if (state
->grid
[n
] == n
-1)
1730 else if (state
->grid
[n
] == n
+1)
1732 else if (state
->grid
[n
] == n
-w
)
1734 else if (state
->grid
[n
] == n
+w
)
1739 draw_tile(dr
, ds
, state
, x
, y
, c
);
1744 #define thegame dominosa
1747 const struct game thegame
= {
1748 "Dominosa", "games.dominosa", "dominosa",
1755 TRUE
, game_configure
, custom_params
,
1763 FALSE
, game_can_format_as_text_now
, game_text_format
,
1771 PREFERRED_TILESIZE
, game_compute_size
, game_set_size
,
1774 game_free_drawstate
,
1778 TRUE
, FALSE
, game_print_size
, game_print
,
1779 FALSE
, /* wants_statusbar */
1780 FALSE
, game_timing_state
,