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