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