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 char *game_text_format(game_state *state)
1179 static game_ui *new_ui(game_state *state)
1184 static void free_ui(game_ui *ui)
1188 static char *encode_ui(game_ui *ui)
1193 static void decode_ui(game_ui *ui, char *encoding)
1197 static void game_changed_state(game_ui *ui, game_state *oldstate,
1198 game_state *newstate)
1202 #define PREFERRED_TILESIZE 32
1203 #define TILESIZE (ds->tilesize)
1204 #define BORDER (TILESIZE * 3 / 4)
1205 #define DOMINO_GUTTER (TILESIZE / 16)
1206 #define DOMINO_RADIUS (TILESIZE / 8)
1207 #define DOMINO_COFFSET (DOMINO_GUTTER + DOMINO_RADIUS)
1209 #define COORD(x) ( (x) * TILESIZE + BORDER )
1210 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1212 struct game_drawstate {
1215 unsigned long *visible;
1218 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1219 int x, int y, int button)
1221 int w = state->w, h = state->h;
1225 * A left-click between two numbers toggles a domino covering
1226 * them. A right-click toggles an edge.
1228 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1229 int tx = FROMCOORD(x), ty = FROMCOORD(y), t = ty*w+tx;
1233 if (tx < 0 || tx >= w || ty < 0 || ty >= h)
1237 * Now we know which square the click was in, decide which
1238 * edge of the square it was closest to.
1240 dx = 2 * (x - COORD(tx)) - TILESIZE;
1241 dy = 2 * (y - COORD(ty)) - TILESIZE;
1243 if (abs(dx) > abs(dy) && dx < 0 && tx > 0)
1244 d1 = t - 1, d2 = t; /* clicked in right side of domino */
1245 else if (abs(dx) > abs(dy) && dx > 0 && tx+1 < w)
1246 d1 = t, d2 = t + 1; /* clicked in left side of domino */
1247 else if (abs(dy) > abs(dx) && dy < 0 && ty > 0)
1248 d1 = t - w, d2 = t; /* clicked in bottom half of domino */
1249 else if (abs(dy) > abs(dx) && dy > 0 && ty+1 < h)
1250 d1 = t, d2 = t + w; /* clicked in top half of domino */
1255 * We can't mark an edge next to any domino.
1257 if (button == RIGHT_BUTTON &&
1258 (state->grid[d1] != d1 || state->grid[d2] != d2))
1261 sprintf(buf, "%c%d,%d", (int)(button == RIGHT_BUTTON ? 'E' : 'D'), d1, d2);
1268 static game_state *execute_move(game_state *state, char *move)
1270 int n = state->params.n, w = n+2, h = n+1, wh = w*h;
1272 game_state *ret = dup_game(state);
1275 if (move[0] == 'S') {
1278 ret->cheated = TRUE;
1281 * Clear the existing edges and domino placements. We
1282 * expect the S to be followed by other commands.
1284 for (i = 0; i < wh; i++) {
1289 } else if (move[0] == 'D' &&
1290 sscanf(move+1, "%d,%d%n", &d1, &d2, &p) == 2 &&
1291 d1 >= 0 && d1 < wh && d2 >= 0 && d2 < wh && d1 < d2) {
1294 * Toggle domino presence between d1 and d2.
1296 if (ret->grid[d1] == d2) {
1297 assert(ret->grid[d2] == d1);
1302 * Erase any dominoes that might overlap the new one.
1311 * Place the new one.
1317 * Destroy any edges lurking around it.
1319 if (ret->edges[d1] & EDGE_L) {
1320 assert(d1 - 1 >= 0);
1321 ret->edges[d1 - 1] &= ~EDGE_R;
1323 if (ret->edges[d1] & EDGE_R) {
1324 assert(d1 + 1 < wh);
1325 ret->edges[d1 + 1] &= ~EDGE_L;
1327 if (ret->edges[d1] & EDGE_T) {
1328 assert(d1 - w >= 0);
1329 ret->edges[d1 - w] &= ~EDGE_B;
1331 if (ret->edges[d1] & EDGE_B) {
1332 assert(d1 + 1 < wh);
1333 ret->edges[d1 + w] &= ~EDGE_T;
1336 if (ret->edges[d2] & EDGE_L) {
1337 assert(d2 - 1 >= 0);
1338 ret->edges[d2 - 1] &= ~EDGE_R;
1340 if (ret->edges[d2] & EDGE_R) {
1341 assert(d2 + 1 < wh);
1342 ret->edges[d2 + 1] &= ~EDGE_L;
1344 if (ret->edges[d2] & EDGE_T) {
1345 assert(d2 - w >= 0);
1346 ret->edges[d2 - w] &= ~EDGE_B;
1348 if (ret->edges[d2] & EDGE_B) {
1349 assert(d2 + 1 < wh);
1350 ret->edges[d2 + w] &= ~EDGE_T;
1356 } else if (move[0] == 'E' &&
1357 sscanf(move+1, "%d,%d%n", &d1, &d2, &p) == 2 &&
1358 d1 >= 0 && d1 < wh && d2 >= 0 && d2 < wh && d1 < d2 &&
1359 ret->grid[d1] == d1 && ret->grid[d2] == d2) {
1362 * Toggle edge presence between d1 and d2.
1365 ret->edges[d1] ^= EDGE_R;
1366 ret->edges[d2] ^= EDGE_L;
1368 ret->edges[d1] ^= EDGE_B;
1369 ret->edges[d2] ^= EDGE_T;
1388 * After modifying the grid, check completion.
1390 if (!ret->completed) {
1392 unsigned char *used = snewn(TRI(n+1), unsigned char);
1394 memset(used, 0, TRI(n+1));
1395 for (i = 0; i < wh; i++)
1396 if (ret->grid[i] > i) {
1399 n1 = ret->numbers->numbers[i];
1400 n2 = ret->numbers->numbers[ret->grid[i]];
1402 di = DINDEX(n1, n2);
1403 assert(di >= 0 && di < TRI(n+1));
1412 if (ok == DCOUNT(n))
1413 ret->completed = TRUE;
1419 /* ----------------------------------------------------------------------
1423 static void game_compute_size(game_params *params, int tilesize,
1426 int n = params->n, w = n+2, h = n+1;
1428 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1429 struct { int tilesize; } ads, *ds = &ads;
1430 ads.tilesize = tilesize;
1432 *x = w * TILESIZE + 2*BORDER;
1433 *y = h * TILESIZE + 2*BORDER;
1436 static void game_set_size(drawing *dr, game_drawstate *ds,
1437 game_params *params, int tilesize)
1439 ds->tilesize = tilesize;
1442 static float *game_colours(frontend *fe, int *ncolours)
1444 float *ret = snewn(3 * NCOLOURS, float);
1446 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1448 ret[COL_TEXT * 3 + 0] = 0.0F;
1449 ret[COL_TEXT * 3 + 1] = 0.0F;
1450 ret[COL_TEXT * 3 + 2] = 0.0F;
1452 ret[COL_DOMINO * 3 + 0] = 0.0F;
1453 ret[COL_DOMINO * 3 + 1] = 0.0F;
1454 ret[COL_DOMINO * 3 + 2] = 0.0F;
1456 ret[COL_DOMINOCLASH * 3 + 0] = 0.5F;
1457 ret[COL_DOMINOCLASH * 3 + 1] = 0.0F;
1458 ret[COL_DOMINOCLASH * 3 + 2] = 0.0F;
1460 ret[COL_DOMINOTEXT * 3 + 0] = 1.0F;
1461 ret[COL_DOMINOTEXT * 3 + 1] = 1.0F;
1462 ret[COL_DOMINOTEXT * 3 + 2] = 1.0F;
1464 ret[COL_EDGE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2 / 3;
1465 ret[COL_EDGE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2 / 3;
1466 ret[COL_EDGE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2 / 3;
1468 *ncolours = NCOLOURS;
1472 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1474 struct game_drawstate *ds = snew(struct game_drawstate);
1477 ds->started = FALSE;
1480 ds->visible = snewn(ds->w * ds->h, unsigned long);
1481 ds->tilesize = 0; /* not decided yet */
1482 for (i = 0; i < ds->w * ds->h; i++)
1483 ds->visible[i] = 0xFFFF;
1488 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1503 static void draw_tile(drawing *dr, game_drawstate *ds, game_state *state,
1504 int x, int y, int type)
1506 int w = state->w /*, h = state->h */;
1507 int cx = COORD(x), cy = COORD(y);
1512 draw_rect(dr, cx, cy, TILESIZE, TILESIZE, COL_BACKGROUND);
1514 flags = type &~ TYPE_MASK;
1517 if (type != TYPE_BLANK) {
1521 * Draw one end of a domino. This is composed of:
1523 * - two filled circles (rounded corners)
1525 * - a slight shift in the number
1529 bg = COL_DOMINOCLASH;
1532 nc = COL_DOMINOTEXT;
1540 if (type == TYPE_L || type == TYPE_T)
1541 draw_circle(dr, cx+DOMINO_COFFSET, cy+DOMINO_COFFSET,
1542 DOMINO_RADIUS, bg, bg);
1543 if (type == TYPE_R || type == TYPE_T)
1544 draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET, cy+DOMINO_COFFSET,
1545 DOMINO_RADIUS, bg, bg);
1546 if (type == TYPE_L || type == TYPE_B)
1547 draw_circle(dr, cx+DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET,
1548 DOMINO_RADIUS, bg, bg);
1549 if (type == TYPE_R || type == TYPE_B)
1550 draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET,
1551 cy+TILESIZE-1-DOMINO_COFFSET,
1552 DOMINO_RADIUS, bg, bg);
1554 for (i = 0; i < 2; i++) {
1557 x1 = cx + (i ? DOMINO_GUTTER : DOMINO_COFFSET);
1558 y1 = cy + (i ? DOMINO_COFFSET : DOMINO_GUTTER);
1559 x2 = cx + TILESIZE-1 - (i ? DOMINO_GUTTER : DOMINO_COFFSET);
1560 y2 = cy + TILESIZE-1 - (i ? DOMINO_COFFSET : DOMINO_GUTTER);
1562 x2 = cx + TILESIZE + TILESIZE/16;
1563 else if (type == TYPE_R)
1564 x1 = cx - TILESIZE/16;
1565 else if (type == TYPE_T)
1566 y2 = cy + TILESIZE + TILESIZE/16;
1567 else if (type == TYPE_B)
1568 y1 = cy - TILESIZE/16;
1570 draw_rect(dr, x1, y1, x2-x1+1, y2-y1+1, bg);
1574 draw_rect(dr, cx+DOMINO_GUTTER, cy,
1575 TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE);
1577 draw_rect(dr, cx+DOMINO_GUTTER, cy+TILESIZE-1,
1578 TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE);
1580 draw_rect(dr, cx, cy+DOMINO_GUTTER,
1581 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE);
1583 draw_rect(dr, cx+TILESIZE-1, cy+DOMINO_GUTTER,
1584 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE);
1588 sprintf(str, "%d", state->numbers->numbers[y*w+x]);
1589 draw_text(dr, cx+TILESIZE/2, cy+TILESIZE/2, FONT_VARIABLE, TILESIZE/2,
1590 ALIGN_HCENTRE | ALIGN_VCENTRE, nc, str);
1592 draw_update(dr, cx, cy, TILESIZE, TILESIZE);
1595 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1596 game_state *state, int dir, game_ui *ui,
1597 float animtime, float flashtime)
1599 int n = state->params.n, w = state->w, h = state->h, wh = w*h;
1601 unsigned char *used;
1605 game_compute_size(&state->params, TILESIZE, &pw, &ph);
1606 draw_rect(dr, 0, 0, pw, ph, COL_BACKGROUND);
1607 draw_update(dr, 0, 0, pw, ph);
1612 * See how many dominoes of each type there are, so we can
1613 * highlight clashes in red.
1615 used = snewn(TRI(n+1), unsigned char);
1616 memset(used, 0, TRI(n+1));
1617 for (i = 0; i < wh; i++)
1618 if (state->grid[i] > i) {
1621 n1 = state->numbers->numbers[i];
1622 n2 = state->numbers->numbers[state->grid[i]];
1624 di = DINDEX(n1, n2);
1625 assert(di >= 0 && di < TRI(n+1));
1631 for (y = 0; y < h; y++)
1632 for (x = 0; x < w; x++) {
1637 if (state->grid[n] == n-1)
1639 else if (state->grid[n] == n+1)
1641 else if (state->grid[n] == n-w)
1643 else if (state->grid[n] == n+w)
1648 if (c != TYPE_BLANK) {
1649 n1 = state->numbers->numbers[n];
1650 n2 = state->numbers->numbers[state->grid[n]];
1651 di = DINDEX(n1, n2);
1653 c |= 0x80; /* highlight a clash */
1655 c |= state->edges[n];
1659 c |= 0x40; /* we're flashing */
1661 if (ds->visible[n] != c) {
1662 draw_tile(dr, ds, state, x, y, c);
1670 static float game_anim_length(game_state *oldstate, game_state *newstate,
1671 int dir, game_ui *ui)
1676 static float game_flash_length(game_state *oldstate, game_state *newstate,
1677 int dir, game_ui *ui)
1679 if (!oldstate->completed && newstate->completed &&
1680 !oldstate->cheated && !newstate->cheated)
1685 static int game_timing_state(game_state *state, game_ui *ui)
1690 static void game_print_size(game_params *params, float *x, float *y)
1695 * I'll use 6mm squares by default.
1697 game_compute_size(params, 600, &pw, &ph);
1702 static void game_print(drawing *dr, game_state *state, int tilesize)
1704 int w = state->w, h = state->h;
1707 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1708 game_drawstate ads, *ds = &ads;
1709 game_set_size(dr, ds, NULL, tilesize);
1711 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1712 c = print_mono_colour(dr, 0); assert(c == COL_TEXT);
1713 c = print_mono_colour(dr, 0); assert(c == COL_DOMINO);
1714 c = print_mono_colour(dr, 0); assert(c == COL_DOMINOCLASH);
1715 c = print_mono_colour(dr, 1); assert(c == COL_DOMINOTEXT);
1716 c = print_mono_colour(dr, 0); assert(c == COL_EDGE);
1718 for (y = 0; y < h; y++)
1719 for (x = 0; x < w; x++) {
1723 if (state->grid[n] == n-1)
1725 else if (state->grid[n] == n+1)
1727 else if (state->grid[n] == n-w)
1729 else if (state->grid[n] == n+w)
1734 draw_tile(dr, ds, state, x, y, c);
1739 #define thegame dominosa
1742 const struct game thegame = {
1743 "Dominosa", "games.dominosa", "dominosa",
1750 TRUE, game_configure, custom_params,
1758 FALSE, game_text_format,
1766 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1769 game_free_drawstate,
1773 TRUE, FALSE, game_print_size, game_print,
1774 FALSE, /* wants_statusbar */
1775 FALSE, game_timing_state,