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