dominosa.c

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