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