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