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 = 4; break;
113 case 2: n = 5; break;
114 case 3: n = 6; break;
115 case 4: n = 7; break;
116 case 5: n = 8; break;
117 case 6: n = 9; break;
118 default: return FALSE;
121 sprintf(buf, "Up to double-%d", n);
124 *params = ret = snew(game_params);
131 static void free_params(game_params *params)
136 static game_params *dup_params(game_params *params)
138 game_params *ret = snew(game_params);
139 *ret = *params; /* structure copy */
143 static void decode_params(game_params *params, char const *string)
145 params->n = atoi(string);
146 while (*string && isdigit((unsigned char)*string)) string++;
148 params->unique = FALSE;
151 static char *encode_params(game_params *params, int full)
154 sprintf(buf, "%d", params->n);
155 if (full && !params->unique)
160 static config_item *game_configure(game_params *params)
165 ret = snewn(3, config_item);
167 ret[0].name = "Maximum number on dominoes";
168 ret[0].type = C_STRING;
169 sprintf(buf, "%d", params->n);
170 ret[0].sval = dupstr(buf);
173 ret[1].name = "Ensure unique solution";
174 ret[1].type = C_BOOLEAN;
176 ret[1].ival = params->unique;
186 static game_params *custom_params(config_item *cfg)
188 game_params *ret = snew(game_params);
190 ret->n = atoi(cfg[0].sval);
191 ret->unique = cfg[1].ival;
196 static char *validate_params(game_params *params, int full)
199 return "Maximum face number must be at least one";
203 /* ----------------------------------------------------------------------
207 static int find_overlaps(int w, int h, int placement, int *set)
211 n = 0; /* number of returned placements */
219 * Horizontal domino, indexed by its left end.
222 set[n++] = placement-2; /* horizontal domino to the left */
224 set[n++] = placement-2*w-1;/* vertical domino above left side */
226 set[n++] = placement-1; /* vertical domino below left side */
228 set[n++] = placement+2; /* horizontal domino to the right */
230 set[n++] = placement-2*w+2-1;/* vertical domino above right side */
232 set[n++] = placement+2-1; /* vertical domino below right side */
235 * Vertical domino, indexed by its top end.
238 set[n++] = placement-2*w; /* vertical domino above */
240 set[n++] = placement-2+1; /* horizontal domino left of top */
242 set[n++] = placement+1; /* horizontal domino right of top */
244 set[n++] = placement+2*w; /* vertical domino below */
246 set[n++] = placement-2+2*w+1;/* horizontal domino left of bottom */
248 set[n++] = placement+2*w+1;/* horizontal domino right of bottom */
255 * Returns 0, 1 or 2 for number of solutions. 2 means `any number
256 * more than one', or more accurately `we were unable to prove
257 * there was only one'.
259 * Outputs in a `placements' array, indexed the same way as the one
260 * within this function (see below); entries in there are <0 for a
261 * placement ruled out, 0 for an uncertain placement, and 1 for a
264 static int solver(int w, int h, int n, int *grid, int *output)
266 int wh = w*h, dc = DCOUNT(n);
267 int *placements, *heads;
271 * This array has one entry for every possible domino
272 * placement. Vertical placements are indexed by their top
273 * half, at (y*w+x)*2; horizontal placements are indexed by
274 * their left half at (y*w+x)*2+1.
276 * This array is used to link domino placements together into
277 * linked lists, so that we can track all the possible
278 * placements of each different domino. It's also used as a
279 * quick means of looking up an individual placement to see
280 * whether we still think it's possible. Actual values stored
281 * in this array are -2 (placement not possible at all), -1
282 * (end of list), or the array index of the next item.
284 * Oh, and -3 for `not even valid', used for array indices
285 * which don't even represent a plausible placement.
287 placements = snewn(2*wh, int);
288 for (i = 0; i < 2*wh; i++)
289 placements[i] = -3; /* not even valid */
292 * This array has one entry for every domino, and it is an
293 * index into `placements' denoting the head of the placement
294 * list for that domino.
296 heads = snewn(dc, int);
297 for (i = 0; i < dc; i++)
301 * Set up the initial possibility lists by scanning the grid.
303 for (y = 0; y < h-1; y++)
304 for (x = 0; x < w; x++) {
305 int di = DINDEX(grid[y*w+x], grid[(y+1)*w+x]);
306 placements[(y*w+x)*2] = heads[di];
307 heads[di] = (y*w+x)*2;
309 for (y = 0; y < h; y++)
310 for (x = 0; x < w-1; x++) {
311 int di = DINDEX(grid[y*w+x], grid[y*w+(x+1)]);
312 placements[(y*w+x)*2+1] = heads[di];
313 heads[di] = (y*w+x)*2+1;
316 #ifdef SOLVER_DIAGNOSTICS
317 printf("before solver:\n");
318 for (i = 0; i <= n; i++)
319 for (j = 0; j <= i; j++) {
322 printf("%2d [%d %d]:", DINDEX(i, j), i, j);
323 for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
324 printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');
330 int done_something = FALSE;
333 * For each domino, look at its possible placements, and
334 * for each placement consider the placements (of any
335 * domino) it overlaps. Any placement overlapped by all
336 * placements of this domino can be ruled out.
338 * Each domino placement overlaps only six others, so we
339 * need not do serious set theory to work this out.
341 for (i = 0; i < dc; i++) {
342 int permset[6], permlen = 0, p;
345 if (heads[i] == -1) { /* no placement for this domino */
346 ret = 0; /* therefore puzzle is impossible */
349 for (j = heads[i]; j >= 0; j = placements[j]) {
350 assert(placements[j] != -2);
353 permlen = find_overlaps(w, h, j, permset);
355 int tempset[6], templen, m, n, k;
357 templen = find_overlaps(w, h, j, tempset);
360 * Pathetically primitive set intersection
361 * algorithm, which I'm only getting away with
362 * because I know my sets are bounded by a very
365 for (m = n = 0; m < permlen; m++) {
366 for (k = 0; k < templen; k++)
367 if (tempset[k] == permset[m])
370 permset[n++] = permset[m];
375 for (p = 0; p < permlen; p++) {
377 if (placements[j] != -2) {
380 done_something = TRUE;
383 * Rule out this placement. First find what
387 p2 = (j & 1) ? p1 + 1 : p1 + w;
388 di = DINDEX(grid[p1], grid[p2]);
389 #ifdef SOLVER_DIAGNOSTICS
390 printf("considering domino %d: ruling out placement %d"
391 " for %d\n", i, j, di);
395 * ... then walk that domino's placement list,
396 * removing this placement when we find it.
399 heads[di] = placements[j];
402 while (placements[k] != -1 && placements[k] != j)
404 assert(placements[k] == j);
405 placements[k] = placements[j];
413 * For each square, look at the available placements
414 * involving that square. If all of them are for the same
415 * domino, then rule out any placements for that domino
416 * _not_ involving this square.
418 for (i = 0; i < wh; i++) {
419 int list[4], k, n, adi;
426 list[j++] = 2*(i-1)+1;
434 for (n = k = 0; k < j; k++)
435 if (placements[list[k]] >= -1)
440 for (j = 0; j < n; j++) {
445 p2 = (k & 1) ? p1 + 1 : p1 + w;
446 di = DINDEX(grid[p1], grid[p2]);
459 * We've found something. All viable placements
460 * involving this square are for domino `adi'. If
461 * the current placement list for that domino is
462 * longer than n, reduce it to precisely this
463 * placement list and we've done something.
466 for (k = heads[adi]; k >= 0; k = placements[k])
469 done_something = TRUE;
470 #ifdef SOLVER_DIAGNOSTICS
471 printf("considering square %d,%d: reducing placements "
472 "of domino %d\n", x, y, adi);
475 * Set all other placements on the list to
480 int tmp = placements[k];
485 * Set up the new list.
487 heads[adi] = list[0];
488 for (k = 0; k < n; k++)
489 placements[list[k]] = (k+1 == n ? -1 : list[k+1]);
498 #ifdef SOLVER_DIAGNOSTICS
499 printf("after solver:\n");
500 for (i = 0; i <= n; i++)
501 for (j = 0; j <= i; j++) {
504 printf("%2d [%d %d]:", DINDEX(i, j), i, j);
505 for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
506 printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');
512 for (i = 0; i < wh*2; i++) {
513 if (placements[i] == -2) {
515 output[i] = -1; /* ruled out */
516 } else if (placements[i] != -3) {
520 p2 = (i & 1) ? p1 + 1 : p1 + w;
521 di = DINDEX(grid[p1], grid[p2]);
523 if (i == heads[di] && placements[i] == -1) {
525 output[i] = 1; /* certain */
528 output[i] = 0; /* uncertain */
544 /* ----------------------------------------------------------------------
545 * End of solver code.
548 static char *new_game_desc(game_params *params, random_state *rs,
549 char **aux, int interactive)
551 int n = params->n, w = n+2, h = n+1, wh = w*h;
552 int *grid, *grid2, *list;
553 int i, j, k, m, todo, done, len;
557 * Allocate space in which to lay the grid out.
559 grid = snewn(wh, int);
560 grid2 = snewn(wh, int);
561 list = snewn(2*wh, int);
564 * I haven't been able to think of any particularly clever
565 * techniques for generating instances of Dominosa with a
566 * unique solution. Many of the deductions used in this puzzle
567 * are based on information involving half the grid at a time
568 * (`of all the 6s, exactly one is next to a 3'), so a strategy
569 * of partially solving the grid and then perturbing the place
570 * where the solver got stuck seems particularly likely to
571 * accidentally destroy the information which the solver had
572 * used in getting that far. (Contrast with, say, Mines, in
573 * which most deductions are local so this is an excellent
576 * Therefore I resort to the basest of brute force methods:
577 * generate a random grid, see if it's solvable, throw it away
578 * and try again if not. My only concession to sophistication
579 * and cleverness is to at least _try_ not to generate obvious
580 * 2x2 ambiguous sections (see comment below in the domino-
583 * During tests performed on 2005-07-15, I found that the brute
584 * force approach without that tweak had to throw away about 87
585 * grids on average (at the default n=6) before finding a
586 * unique one, or a staggering 379 at n=9; good job the
587 * generator and solver are fast! When I added the
588 * ambiguous-section avoidance, those numbers came down to 19
589 * and 26 respectively, which is a lot more sensible.
594 * To begin with, set grid[i] = i for all i to indicate
595 * that all squares are currently singletons. Later we'll
596 * set grid[i] to be the index of the other end of the
599 for (i = 0; i < wh; i++)
603 * Now prepare a list of the possible domino locations. There
604 * are w*(h-1) possible vertical locations, and (w-1)*h
605 * horizontal ones, for a total of 2*wh - h - w.
607 * I'm going to denote the vertical domino placement with
608 * its top in square i as 2*i, and the horizontal one with
609 * its left half in square i as 2*i+1.
612 for (j = 0; j < h-1; j++)
613 for (i = 0; i < w; i++)
614 list[k++] = 2 * (j*w+i); /* vertical positions */
615 for (j = 0; j < h; j++)
616 for (i = 0; i < w-1; i++)
617 list[k++] = 2 * (j*w+i) + 1; /* horizontal positions */
618 assert(k == 2*wh - h - w);
623 shuffle(list, k, sizeof(*list), rs);
626 * Work down the shuffled list, placing a domino everywhere
629 for (i = 0; i < k; i++) {
634 xy2 = xy + (horiz ? 1 : w);
636 if (grid[xy] == xy && grid[xy2] == xy2) {
638 * We can place this domino. Do so.
645 #ifdef GENERATION_DIAGNOSTICS
646 printf("generated initial layout\n");
650 * Now we've placed as many dominoes as we can immediately
651 * manage. There will be squares remaining, but they'll be
652 * singletons. So loop round and deal with the singletons
656 #ifdef GENERATION_DIAGNOSTICS
657 for (j = 0; j < h; j++) {
658 for (i = 0; i < w; i++) {
661 int c = (v == xy+1 ? '[' : v == xy-1 ? ']' :
662 v == xy+w ? 'n' : v == xy-w ? 'U' : '.');
673 * First find a singleton square.
675 * Then breadth-first search out from the starting
676 * square. From that square (and any others we reach on
677 * the way), examine all four neighbours of the square.
678 * If one is an end of a domino, we move to the _other_
679 * end of that domino before looking at neighbours
680 * again. When we encounter another singleton on this
683 * This will give us a path of adjacent squares such
684 * that all but the two ends are covered in dominoes.
685 * So we can now shuffle every domino on the path up by
688 * (Chessboard colours are mathematically important
689 * here: we always end up pairing each singleton with a
690 * singleton of the other colour. However, we never
691 * have to track this manually, since it's
692 * automatically taken care of by the fact that we
693 * always make an even number of orthogonal moves.)
695 for (i = 0; i < wh; i++)
699 break; /* no more singletons; we're done. */
701 #ifdef GENERATION_DIAGNOSTICS
702 printf("starting b.f.s. at singleton %d\n", i);
705 * Set grid2 to -1 everywhere. It will hold our
706 * distance-from-start values, and also our
707 * backtracking data, during the b.f.s.
709 for (j = 0; j < wh; j++)
711 grid2[i] = 0; /* starting square has distance zero */
714 * Start our to-do list of squares. It'll live in
715 * `list'; since the b.f.s can cover every square at
716 * most once there is no need for it to be circular.
717 * We'll just have two counters tracking the end of the
718 * list and the squares we've already dealt with.
725 * Now begin the b.f.s. loop.
727 while (done < todo) {
732 #ifdef GENERATION_DIAGNOSTICS
733 printf("b.f.s. iteration from %d\n", i);
747 * To avoid directional bias, process the
748 * neighbours of this square in a random order.
750 shuffle(d, nd, sizeof(*d), rs);
752 for (j = 0; j < nd; j++) {
755 #ifdef GENERATION_DIAGNOSTICS
756 printf("found neighbouring singleton %d\n", k);
759 break; /* found a target singleton! */
763 * We're moving through a domino here, so we
764 * have two entries in grid2 to fill with
765 * useful data. In grid[k] - the square
766 * adjacent to where we came from - I'm going
767 * to put the address _of_ the square we came
768 * from. In the other end of the domino - the
769 * square from which we will continue the
770 * search - I'm going to put the distance.
774 if (grid2[m] < 0 || grid2[m] > grid2[i]+1) {
775 #ifdef GENERATION_DIAGNOSTICS
776 printf("found neighbouring domino %d/%d\n", k, m);
778 grid2[m] = grid2[i]+1;
781 * And since we've now visited a new
782 * domino, add m to the to-do list.
791 #ifdef GENERATION_DIAGNOSTICS
792 printf("terminating b.f.s. loop, i = %d\n", i);
797 i = -1; /* just in case the loop terminates */
801 * We expect this b.f.s. to have found us a target
807 * Now we can follow the trail back to our starting
808 * singleton, re-laying dominoes as we go.
812 assert(j >= 0 && j < wh);
817 #ifdef GENERATION_DIAGNOSTICS
818 printf("filling in domino %d/%d (next %d)\n", i, j, k);
821 break; /* we've reached the other singleton */
824 #ifdef GENERATION_DIAGNOSTICS
825 printf("fixup path completed\n");
830 * Now we have a complete layout covering the whole
831 * rectangle with dominoes. So shuffle the actual domino
832 * values and fill the rectangle with numbers.
835 for (i = 0; i <= params->n; i++)
836 for (j = 0; j <= i; j++) {
840 shuffle(list, k/2, 2*sizeof(*list), rs);
842 for (i = 0; i < wh; i++)
844 /* Optionally flip the domino round. */
847 if (params->unique) {
850 * If we're after a unique solution, we can do
851 * something here to improve the chances. If
852 * we're placing a domino so that it forms a
853 * 2x2 rectangle with one we've already placed,
854 * and if that domino and this one share a
855 * number, we can try not to put them so that
856 * the identical numbers are diagonally
857 * separated, because that automatically causes
868 if (t2 == t1 + w) { /* this domino is vertical */
869 if (t1 % w > 0 &&/* and not on the left hand edge */
870 grid[t1-1] == t2-1 &&/* alongside one to left */
871 (grid2[t1-1] == list[j] || /* and has a number */
872 grid2[t1-1] == list[j+1] || /* in common */
873 grid2[t2-1] == list[j] ||
874 grid2[t2-1] == list[j+1])) {
875 if (grid2[t1-1] == list[j] ||
876 grid2[t2-1] == list[j+1])
881 } else { /* this domino is horizontal */
882 if (t1 / w > 0 &&/* and not on the top edge */
883 grid[t1-w] == t2-w &&/* alongside one above */
884 (grid2[t1-w] == list[j] || /* and has a number */
885 grid2[t1-w] == list[j+1] || /* in common */
886 grid2[t2-w] == list[j] ||
887 grid2[t2-w] == list[j+1])) {
888 if (grid2[t1-w] == list[j] ||
889 grid2[t2-w] == list[j+1])
898 flip = random_upto(rs, 2);
900 grid2[i] = list[j + flip];
901 grid2[grid[i]] = list[j + 1 - flip];
905 } while (params->unique && solver(w, h, n, grid2, NULL) > 1);
907 #ifdef GENERATION_DIAGNOSTICS
908 for (j = 0; j < h; j++) {
909 for (i = 0; i < w; i++) {
910 putchar('0' + grid2[j*w+i]);
918 * Encode the resulting game state.
920 * Our encoding is a string of digits. Any number greater than
921 * 9 is represented by a decimal integer within square
922 * brackets. We know there are n+2 of every number (it's paired
923 * with each number from 0 to n inclusive, and one of those is
924 * itself so that adds another occurrence), so we can work out
925 * the string length in advance.
929 * To work out the total length of the decimal encodings of all
930 * the numbers from 0 to n inclusive:
931 * - every number has a units digit; total is n+1.
932 * - all numbers above 9 have a tens digit; total is max(n+1-10,0).
933 * - all numbers above 99 have a hundreds digit; total is max(n+1-100,0).
937 for (i = 10; i <= n; i *= 10)
938 len += max(n + 1 - i, 0);
939 /* Now add two square brackets for each number above 9. */
940 len += 2 * max(n + 1 - 10, 0);
941 /* And multiply by n+2 for the repeated occurrences of each number. */
945 * Now actually encode the string.
947 ret = snewn(len+1, char);
949 for (i = 0; i < wh; i++) {
954 j += sprintf(ret+j, "[%d]", k);
961 * Encode the solved state as an aux_info.
964 char *auxinfo = snewn(wh+1, char);
966 for (i = 0; i < wh; i++) {
968 auxinfo[i] = (v == i+1 ? 'L' : v == i-1 ? 'R' :
969 v == i+w ? 'T' : v == i-w ? 'B' : '.');
983 static char *validate_desc(game_params *params, char *desc)
985 int n = params->n, w = n+2, h = n+1, wh = w*h;
991 occurrences = snewn(n+1, int);
992 for (i = 0; i <= n; i++)
995 for (i = 0; i < wh; i++) {
997 ret = ret ? ret : "Game description is too short";
999 if (*desc >= '0' && *desc <= '9')
1001 else if (*desc == '[') {
1004 while (*desc && isdigit((unsigned char)*desc)) desc++;
1006 ret = ret ? ret : "Missing ']' in game description";
1011 ret = ret ? ret : "Invalid syntax in game description";
1014 ret = ret ? ret : "Number out of range in game description";
1021 ret = ret ? ret : "Game description is too long";
1024 for (i = 0; i <= n; i++)
1025 if (occurrences[i] != n+2)
1026 ret = "Incorrect number balance in game description";
1034 static game_state *new_game(midend *me, game_params *params, char *desc)
1036 int n = params->n, w = n+2, h = n+1, wh = w*h;
1037 game_state *state = snew(game_state);
1040 state->params = *params;
1044 state->grid = snewn(wh, int);
1045 for (i = 0; i < wh; i++)
1048 state->edges = snewn(wh, unsigned short);
1049 for (i = 0; i < wh; i++)
1050 state->edges[i] = 0;
1052 state->numbers = snew(struct game_numbers);
1053 state->numbers->refcount = 1;
1054 state->numbers->numbers = snewn(wh, int);
1056 for (i = 0; i < wh; i++) {
1058 if (*desc >= '0' && *desc <= '9')
1061 assert(*desc == '[');
1064 while (*desc && isdigit((unsigned char)*desc)) desc++;
1065 assert(*desc == ']');
1068 assert(j >= 0 && j <= n);
1069 state->numbers->numbers[i] = j;
1072 state->completed = state->cheated = FALSE;
1077 static game_state *dup_game(game_state *state)
1079 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
1080 game_state *ret = snew(game_state);
1082 ret->params = state->params;
1085 ret->grid = snewn(wh, int);
1086 memcpy(ret->grid, state->grid, wh * sizeof(int));
1087 ret->edges = snewn(wh, unsigned short);
1088 memcpy(ret->edges, state->edges, wh * sizeof(unsigned short));
1089 ret->numbers = state->numbers;
1090 ret->numbers->refcount++;
1091 ret->completed = state->completed;
1092 ret->cheated = state->cheated;
1097 static void free_game(game_state *state)
1100 sfree(state->edges);
1101 if (--state->numbers->refcount <= 0) {
1102 sfree(state->numbers->numbers);
1103 sfree(state->numbers);
1108 static char *solve_game(game_state *state, game_state *currstate,
1109 char *aux, char **error)
1111 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
1114 int retlen, retsize;
1121 ret = snewn(retsize, char);
1122 retlen = sprintf(ret, "S");
1124 for (i = 0; i < wh; i++) {
1126 extra = sprintf(buf, ";D%d,%d", i, i+1);
1127 else if (aux[i] == 'T')
1128 extra = sprintf(buf, ";D%d,%d", i, i+w);
1132 if (retlen + extra + 1 >= retsize) {
1133 retsize = retlen + extra + 256;
1134 ret = sresize(ret, retsize, char);
1136 strcpy(ret + retlen, buf);
1142 placements = snewn(wh*2, int);
1143 for (i = 0; i < wh*2; i++)
1145 solver(w, h, n, state->numbers->numbers, placements);
1148 * First make a pass putting in edges for -1, then make a pass
1149 * putting in dominoes for +1.
1152 ret = snewn(retsize, char);
1153 retlen = sprintf(ret, "S");
1155 for (v = -1; v <= +1; v += 2)
1156 for (i = 0; i < wh*2; i++)
1157 if (placements[i] == v) {
1159 int p2 = (i & 1) ? p1+1 : p1+w;
1161 extra = sprintf(buf, ";%c%d,%d",
1162 (int)(v==-1 ? 'E' : 'D'), p1, p2);
1164 if (retlen + extra + 1 >= retsize) {
1165 retsize = retlen + extra + 256;
1166 ret = sresize(ret, retsize, char);
1168 strcpy(ret + retlen, buf);
1178 static int game_can_format_as_text_now(game_params *params)
1183 static char *game_text_format(game_state *state)
1188 static game_ui *new_ui(game_state *state)
1193 static void free_ui(game_ui *ui)
1197 static char *encode_ui(game_ui *ui)
1202 static void decode_ui(game_ui *ui, char *encoding)
1206 static void game_changed_state(game_ui *ui, game_state *oldstate,
1207 game_state *newstate)
1211 #define PREFERRED_TILESIZE 32
1212 #define TILESIZE (ds->tilesize)
1213 #define BORDER (TILESIZE * 3 / 4)
1214 #define DOMINO_GUTTER (TILESIZE / 16)
1215 #define DOMINO_RADIUS (TILESIZE / 8)
1216 #define DOMINO_COFFSET (DOMINO_GUTTER + DOMINO_RADIUS)
1218 #define COORD(x) ( (x) * TILESIZE + BORDER )
1219 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1221 struct game_drawstate {
1224 unsigned long *visible;
1227 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1228 int x, int y, int button)
1230 int w = state->w, h = state->h;
1234 * A left-click between two numbers toggles a domino covering
1235 * them. A right-click toggles an edge.
1237 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1238 int tx = FROMCOORD(x), ty = FROMCOORD(y), t = ty*w+tx;
1242 if (tx < 0 || tx >= w || ty < 0 || ty >= h)
1246 * Now we know which square the click was in, decide which
1247 * edge of the square it was closest to.
1249 dx = 2 * (x - COORD(tx)) - TILESIZE;
1250 dy = 2 * (y - COORD(ty)) - TILESIZE;
1252 if (abs(dx) > abs(dy) && dx < 0 && tx > 0)
1253 d1 = t - 1, d2 = t; /* clicked in right side of domino */
1254 else if (abs(dx) > abs(dy) && dx > 0 && tx+1 < w)
1255 d1 = t, d2 = t + 1; /* clicked in left side of domino */
1256 else if (abs(dy) > abs(dx) && dy < 0 && ty > 0)
1257 d1 = t - w, d2 = t; /* clicked in bottom half of domino */
1258 else if (abs(dy) > abs(dx) && dy > 0 && ty+1 < h)
1259 d1 = t, d2 = t + w; /* clicked in top half of domino */
1264 * We can't mark an edge next to any domino.
1266 if (button == RIGHT_BUTTON &&
1267 (state->grid[d1] != d1 || state->grid[d2] != d2))
1270 sprintf(buf, "%c%d,%d", (int)(button == RIGHT_BUTTON ? 'E' : 'D'), d1, d2);
1277 static game_state *execute_move(game_state *state, char *move)
1279 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
1281 game_state *ret = dup_game(state);
1284 if (move[0] == 'S') {
1287 ret->cheated = TRUE;
1290 * Clear the existing edges and domino placements. We
1291 * expect the S to be followed by other commands.
1293 for (i = 0; i < wh; i++) {
1298 } else if (move[0] == 'D' &&
1299 sscanf(move+1, "%d,%d%n", &d1, &d2, &p) == 2 &&
1300 d1 >= 0 && d1 < wh && d2 >= 0 && d2 < wh && d1 < d2) {
1303 * Toggle domino presence between d1 and d2.
1305 if (ret->grid[d1] == d2) {
1306 assert(ret->grid[d2] == d1);
1311 * Erase any dominoes that might overlap the new one.
1320 * Place the new one.
1326 * Destroy any edges lurking around it.
1328 if (ret->edges[d1] & EDGE_L) {
1329 assert(d1 - 1 >= 0);
1330 ret->edges[d1 - 1] &= ~EDGE_R;
1332 if (ret->edges[d1] & EDGE_R) {
1333 assert(d1 + 1 < wh);
1334 ret->edges[d1 + 1] &= ~EDGE_L;
1336 if (ret->edges[d1] & EDGE_T) {
1337 assert(d1 - w >= 0);
1338 ret->edges[d1 - w] &= ~EDGE_B;
1340 if (ret->edges[d1] & EDGE_B) {
1341 assert(d1 + 1 < wh);
1342 ret->edges[d1 + w] &= ~EDGE_T;
1345 if (ret->edges[d2] & EDGE_L) {
1346 assert(d2 - 1 >= 0);
1347 ret->edges[d2 - 1] &= ~EDGE_R;
1349 if (ret->edges[d2] & EDGE_R) {
1350 assert(d2 + 1 < wh);
1351 ret->edges[d2 + 1] &= ~EDGE_L;
1353 if (ret->edges[d2] & EDGE_T) {
1354 assert(d2 - w >= 0);
1355 ret->edges[d2 - w] &= ~EDGE_B;
1357 if (ret->edges[d2] & EDGE_B) {
1358 assert(d2 + 1 < wh);
1359 ret->edges[d2 + w] &= ~EDGE_T;
1365 } else if (move[0] == 'E' &&
1366 sscanf(move+1, "%d,%d%n", &d1, &d2, &p) == 2 &&
1367 d1 >= 0 && d1 < wh && d2 >= 0 && d2 < wh && d1 < d2 &&
1368 ret->grid[d1] == d1 && ret->grid[d2] == d2) {
1371 * Toggle edge presence between d1 and d2.
1374 ret->edges[d1] ^= EDGE_R;
1375 ret->edges[d2] ^= EDGE_L;
1377 ret->edges[d1] ^= EDGE_B;
1378 ret->edges[d2] ^= EDGE_T;
1397 * After modifying the grid, check completion.
1399 if (!ret->completed) {
1401 unsigned char *used = snewn(TRI(n+1), unsigned char);
1403 memset(used, 0, TRI(n+1));
1404 for (i = 0; i < wh; i++)
1405 if (ret->grid[i] > i) {
1408 n1 = ret->numbers->numbers[i];
1409 n2 = ret->numbers->numbers[ret->grid[i]];
1411 di = DINDEX(n1, n2);
1412 assert(di >= 0 && di < TRI(n+1));
1421 if (ok == DCOUNT(n))
1422 ret->completed = TRUE;
1428 /* ----------------------------------------------------------------------
1432 static void game_compute_size(game_params *params, int tilesize,
1435 int n = params->n, w = n+2, h = n+1;
1437 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1438 struct { int tilesize; } ads, *ds = &ads;
1439 ads.tilesize = tilesize;
1441 *x = w * TILESIZE + 2*BORDER;
1442 *y = h * TILESIZE + 2*BORDER;
1445 static void game_set_size(drawing *dr, game_drawstate *ds,
1446 game_params *params, int tilesize)
1448 ds->tilesize = tilesize;
1451 static float *game_colours(frontend *fe, int *ncolours)
1453 float *ret = snewn(3 * NCOLOURS, float);
1455 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1457 ret[COL_TEXT * 3 + 0] = 0.0F;
1458 ret[COL_TEXT * 3 + 1] = 0.0F;
1459 ret[COL_TEXT * 3 + 2] = 0.0F;
1461 ret[COL_DOMINO * 3 + 0] = 0.0F;
1462 ret[COL_DOMINO * 3 + 1] = 0.0F;
1463 ret[COL_DOMINO * 3 + 2] = 0.0F;
1465 ret[COL_DOMINOCLASH * 3 + 0] = 0.5F;
1466 ret[COL_DOMINOCLASH * 3 + 1] = 0.0F;
1467 ret[COL_DOMINOCLASH * 3 + 2] = 0.0F;
1469 ret[COL_DOMINOTEXT * 3 + 0] = 1.0F;
1470 ret[COL_DOMINOTEXT * 3 + 1] = 1.0F;
1471 ret[COL_DOMINOTEXT * 3 + 2] = 1.0F;
1473 ret[COL_EDGE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2 / 3;
1474 ret[COL_EDGE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2 / 3;
1475 ret[COL_EDGE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2 / 3;
1477 *ncolours = NCOLOURS;
1481 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1483 struct game_drawstate *ds = snew(struct game_drawstate);
1486 ds->started = FALSE;
1489 ds->visible = snewn(ds->w * ds->h, unsigned long);
1490 ds->tilesize = 0; /* not decided yet */
1491 for (i = 0; i < ds->w * ds->h; i++)
1492 ds->visible[i] = 0xFFFF;
1497 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1512 static void draw_tile(drawing *dr, game_drawstate *ds, game_state *state,
1513 int x, int y, int type)
1515 int w = state->w /*, h = state->h */;
1516 int cx = COORD(x), cy = COORD(y);
1521 draw_rect(dr, cx, cy, TILESIZE, TILESIZE, COL_BACKGROUND);
1523 flags = type &~ TYPE_MASK;
1526 if (type != TYPE_BLANK) {
1530 * Draw one end of a domino. This is composed of:
1532 * - two filled circles (rounded corners)
1534 * - a slight shift in the number
1538 bg = COL_DOMINOCLASH;
1541 nc = COL_DOMINOTEXT;
1549 if (type == TYPE_L || type == TYPE_T)
1550 draw_circle(dr, cx+DOMINO_COFFSET, cy+DOMINO_COFFSET,
1551 DOMINO_RADIUS, bg, bg);
1552 if (type == TYPE_R || type == TYPE_T)
1553 draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET, cy+DOMINO_COFFSET,
1554 DOMINO_RADIUS, bg, bg);
1555 if (type == TYPE_L || type == TYPE_B)
1556 draw_circle(dr, cx+DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET,
1557 DOMINO_RADIUS, bg, bg);
1558 if (type == TYPE_R || type == TYPE_B)
1559 draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET,
1560 cy+TILESIZE-1-DOMINO_COFFSET,
1561 DOMINO_RADIUS, bg, bg);
1563 for (i = 0; i < 2; i++) {
1566 x1 = cx + (i ? DOMINO_GUTTER : DOMINO_COFFSET);
1567 y1 = cy + (i ? DOMINO_COFFSET : DOMINO_GUTTER);
1568 x2 = cx + TILESIZE-1 - (i ? DOMINO_GUTTER : DOMINO_COFFSET);
1569 y2 = cy + TILESIZE-1 - (i ? DOMINO_COFFSET : DOMINO_GUTTER);
1571 x2 = cx + TILESIZE + TILESIZE/16;
1572 else if (type == TYPE_R)
1573 x1 = cx - TILESIZE/16;
1574 else if (type == TYPE_T)
1575 y2 = cy + TILESIZE + TILESIZE/16;
1576 else if (type == TYPE_B)
1577 y1 = cy - TILESIZE/16;
1579 draw_rect(dr, x1, y1, x2-x1+1, y2-y1+1, bg);
1583 draw_rect(dr, cx+DOMINO_GUTTER, cy,
1584 TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE);
1586 draw_rect(dr, cx+DOMINO_GUTTER, cy+TILESIZE-1,
1587 TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE);
1589 draw_rect(dr, cx, cy+DOMINO_GUTTER,
1590 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE);
1592 draw_rect(dr, cx+TILESIZE-1, cy+DOMINO_GUTTER,
1593 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE);
1597 sprintf(str, "%d", state->numbers->numbers[y*w+x]);
1598 draw_text(dr, cx+TILESIZE/2, cy+TILESIZE/2, FONT_VARIABLE, TILESIZE/2,
1599 ALIGN_HCENTRE | ALIGN_VCENTRE, nc, str);
1601 draw_update(dr, cx, cy, TILESIZE, TILESIZE);
1604 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1605 game_state *state, int dir, game_ui *ui,
1606 float animtime, float flashtime)
1608 int n = state->params.n, w = state->w, h = state->h, wh = w*h;
1610 unsigned char *used;
1614 game_compute_size(&state->params, TILESIZE, &pw, &ph);
1615 draw_rect(dr, 0, 0, pw, ph, COL_BACKGROUND);
1616 draw_update(dr, 0, 0, pw, ph);
1621 * See how many dominoes of each type there are, so we can
1622 * highlight clashes in red.
1624 used = snewn(TRI(n+1), unsigned char);
1625 memset(used, 0, TRI(n+1));
1626 for (i = 0; i < wh; i++)
1627 if (state->grid[i] > i) {
1630 n1 = state->numbers->numbers[i];
1631 n2 = state->numbers->numbers[state->grid[i]];
1633 di = DINDEX(n1, n2);
1634 assert(di >= 0 && di < TRI(n+1));
1640 for (y = 0; y < h; y++)
1641 for (x = 0; x < w; x++) {
1646 if (state->grid[n] == n-1)
1648 else if (state->grid[n] == n+1)
1650 else if (state->grid[n] == n-w)
1652 else if (state->grid[n] == n+w)
1657 if (c != TYPE_BLANK) {
1658 n1 = state->numbers->numbers[n];
1659 n2 = state->numbers->numbers[state->grid[n]];
1660 di = DINDEX(n1, n2);
1662 c |= 0x80; /* highlight a clash */
1664 c |= state->edges[n];
1668 c |= 0x40; /* we're flashing */
1670 if (ds->visible[n] != c) {
1671 draw_tile(dr, ds, state, x, y, c);
1679 static float game_anim_length(game_state *oldstate, game_state *newstate,
1680 int dir, game_ui *ui)
1685 static float game_flash_length(game_state *oldstate, game_state *newstate,
1686 int dir, game_ui *ui)
1688 if (!oldstate->completed && newstate->completed &&
1689 !oldstate->cheated && !newstate->cheated)
1694 static int game_timing_state(game_state *state, game_ui *ui)
1699 static void game_print_size(game_params *params, float *x, float *y)
1704 * I'll use 6mm squares by default.
1706 game_compute_size(params, 600, &pw, &ph);
1711 static void game_print(drawing *dr, game_state *state, int tilesize)
1713 int w = state->w, h = state->h;
1716 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1717 game_drawstate ads, *ds = &ads;
1718 game_set_size(dr, ds, NULL, tilesize);
1720 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1721 c = print_mono_colour(dr, 0); assert(c == COL_TEXT);
1722 c = print_mono_colour(dr, 0); assert(c == COL_DOMINO);
1723 c = print_mono_colour(dr, 0); assert(c == COL_DOMINOCLASH);
1724 c = print_mono_colour(dr, 1); assert(c == COL_DOMINOTEXT);
1725 c = print_mono_colour(dr, 0); assert(c == COL_EDGE);
1727 for (y = 0; y < h; y++)
1728 for (x = 0; x < w; x++) {
1732 if (state->grid[n] == n-1)
1734 else if (state->grid[n] == n+1)
1736 else if (state->grid[n] == n-w)
1738 else if (state->grid[n] == n+w)
1743 draw_tile(dr, ds, state, x, y, c);
1748 #define thegame dominosa
1751 const struct game thegame = {
1752 "Dominosa", "games.dominosa", "dominosa",
1759 TRUE, game_configure, custom_params,
1767 FALSE, game_can_format_as_text_now, game_text_format,
1775 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1778 game_free_drawstate,
1782 TRUE, FALSE, game_print_size, game_print,
1783 FALSE, /* wants_statusbar */
1784 FALSE, game_timing_state,