rect.c

   1 /*
   2  * rect.c: Puzzle from nikoli.co.jp. You have a square grid with
   3  * numbers in some squares; you must divide the square grid up into
   4  * variously sized rectangles, such that every rectangle contains
   5  * exactly one numbered square and the area of each rectangle is
   6  * equal to the number contained in it.
   7  */
   8
   9 /*
  10  * TODO:
  11  *
  12  *  - Improve singleton removal.
  13  *     + It would be nice to limit the size of the generated
  14  *       rectangles in accordance with existing constraints such as
  15  *       the maximum rectangle size and the one about not
  16  *       generating a rectangle the full width or height of the
  17  *       grid.
  18  *     + This could be achieved by making a less random choice
  19  *       about which of the available options to use.
  20  *     + Alternatively, we could create our rectangle and then
  21  *       split it up.
  22  */
  23
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <assert.h>
  28 #include <ctype.h>
  29 #include <math.h>
  30
  31 #include "puzzles.h"
  32
  33 enum {
  34     COL_BACKGROUND,
  35     COL_CORRECT,
  36     COL_LINE,
  37     COL_TEXT,
  38     COL_GRID,
  39     COL_DRAG,
  40     NCOLOURS
  41 };
  42
  43 struct game_params {
  44     int w, h;
  45     float expandfactor;
  46     int unique;
  47 };
  48
  49 #define INDEX(state, x, y)    (((y) * (state)->w) + (x))
  50 #define index(state, a, x, y) ((a) [ INDEX(state,x,y) ])
  51 #define grid(state,x,y)       index(state, (state)->grid, x, y)
  52 #define vedge(state,x,y)      index(state, (state)->vedge, x, y)
  53 #define hedge(state,x,y)      index(state, (state)->hedge, x, y)
  54
  55 #define CRANGE(state,x,y,dx,dy) ( (x) >= dx && (x) < (state)->w && \
  56                                 (y) >= dy && (y) < (state)->h )
  57 #define RANGE(state,x,y)  CRANGE(state,x,y,0,0)
  58 #define HRANGE(state,x,y) CRANGE(state,x,y,0,1)
  59 #define VRANGE(state,x,y) CRANGE(state,x,y,1,0)
  60
  61 #define PREFERRED_TILE_SIZE 24
  62 #define TILE_SIZE (ds->tilesize)
  63 #define BORDER (TILE_SIZE * 3 / 4)
  64
  65 #define CORNER_TOLERANCE 0.15F
  66 #define CENTRE_TOLERANCE 0.15F
  67
  68 #define FLASH_TIME 0.13F
  69
  70 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
  71 #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE )
  72
  73 struct game_state {
  74     int w, h;
  75     int *grid;                         /* contains the numbers */
  76     unsigned char *vedge;              /* (w+1) x h */
  77     unsigned char *hedge;              /* w x (h+1) */
  78     int completed, cheated;
  79     unsigned char *correct;
  80 };
  81
  82 static game_params *default_params(void)
  83 {
  84     game_params *ret = snew(game_params);
  85
  86     ret->w = ret->h = 7;
  87     ret->expandfactor = 0.0F;
  88     ret->unique = TRUE;
  89
  90     return ret;
  91 }
  92
  93 static int game_fetch_preset(int i, char **name, game_params **params)
  94 {
  95     game_params *ret;
  96     int w, h;
  97     char buf[80];
  98
  99     switch (i) {
 100       case 0: w = 7, h = 7; break;
 101       case 1: w = 9, h = 9; break;
 102       case 2: w = 11, h = 11; break;
 103       case 3: w = 13, h = 13; break;
 104       case 4: w = 15, h = 15; break;
 105       case 5: w = 17, h = 17; break;
 106       case 6: w = 19, h = 19; break;
 107       default: return FALSE;
 108     }
 109
 110     sprintf(buf, "%dx%d", w, h);
 111     *name = dupstr(buf);
 112     *params = ret = snew(game_params);
 113     ret->w = w;
 114     ret->h = h;
 115     ret->expandfactor = 0.0F;
 116     ret->unique = TRUE;
 117     return TRUE;
 118 }
 119
 120 static void free_params(game_params *params)
 121 {
 122     sfree(params);
 123 }
 124
 125 static game_params *dup_params(game_params *params)
 126 {
 127     game_params *ret = snew(game_params);
 128     *ret = *params;                    /* structure copy */
 129     return ret;
 130 }
 131
 132 static void decode_params(game_params *ret, char const *string)
 133 {
 134     ret->w = ret->h = atoi(string);
 135     while (*string && isdigit((unsigned char)*string)) string++;
 136     if (*string == 'x') {
 137         string++;
 138         ret->h = atoi(string);
 139         while (*string && isdigit((unsigned char)*string)) string++;
 140     }
 141     if (*string == 'e') {
 142         string++;
 143         ret->expandfactor = atof(string);
 144         while (*string &&
 145                (*string == '.' || isdigit((unsigned char)*string))) string++;
 146     }
 147     if (*string == 'a') {
 148         string++;
 149         ret->unique = FALSE;
 150     }
 151 }
 152
 153 static char *encode_params(game_params *params, int full)
 154 {
 155     char data[256];
 156
 157     sprintf(data, "%dx%d", params->w, params->h);
 158     if (full && params->expandfactor)
 159         sprintf(data + strlen(data), "e%g", params->expandfactor);
 160     if (full && !params->unique)
 161         strcat(data, "a");
 162
 163     return dupstr(data);
 164 }
 165
 166 static config_item *game_configure(game_params *params)
 167 {
 168     config_item *ret;
 169     char buf[80];
 170
 171     ret = snewn(5, config_item);
 172
 173     ret[0].name = "Width";
 174     ret[0].type = C_STRING;
 175     sprintf(buf, "%d", params->w);
 176     ret[0].sval = dupstr(buf);
 177     ret[0].ival = 0;
 178
 179     ret[1].name = "Height";
 180     ret[1].type = C_STRING;
 181     sprintf(buf, "%d", params->h);
 182     ret[1].sval = dupstr(buf);
 183     ret[1].ival = 0;
 184
 185     ret[2].name = "Expansion factor";
 186     ret[2].type = C_STRING;
 187     sprintf(buf, "%g", params->expandfactor);
 188     ret[2].sval = dupstr(buf);
 189     ret[2].ival = 0;
 190
 191     ret[3].name = "Ensure unique solution";
 192     ret[3].type = C_BOOLEAN;
 193     ret[3].sval = NULL;
 194     ret[3].ival = params->unique;
 195
 196     ret[4].name = NULL;
 197     ret[4].type = C_END;
 198     ret[4].sval = NULL;
 199     ret[4].ival = 0;
 200
 201     return ret;
 202 }
 203
 204 static game_params *custom_params(config_item *cfg)
 205 {
 206     game_params *ret = snew(game_params);
 207
 208     ret->w = atoi(cfg[0].sval);
 209     ret->h = atoi(cfg[1].sval);
 210     ret->expandfactor = atof(cfg[2].sval);
 211     ret->unique = cfg[3].ival;
 212
 213     return ret;
 214 }
 215
 216 static char *validate_params(game_params *params, int full)
 217 {
 218     if (params->w <= 0 || params->h <= 0)
 219         return "Width and height must both be greater than zero";
 220     if (params->w*params->h < 2)
 221         return "Grid area must be greater than one";
 222     if (params->expandfactor < 0.0F)
 223         return "Expansion factor may not be negative";
 224     return NULL;
 225 }
 226
 227 struct point {
 228     int x, y;
 229 };
 230
 231 struct rect {
 232     int x, y;
 233     int w, h;
 234 };
 235
 236 struct rectlist {
 237     struct rect *rects;
 238     int n;
 239 };
 240
 241 struct numberdata {
 242     int area;
 243     int npoints;
 244     struct point *points;
 245 };
 246
 247 /* ----------------------------------------------------------------------
 248  * Solver for Rectangles games.
 249  *
 250  * This solver is souped up beyond the needs of actually _solving_
 251  * a puzzle. It is also designed to cope with uncertainty about
 252  * where the numbers have been placed. This is because I run it on
 253  * my generated grids _before_ placing the numbers, and have it
 254  * tell me where I need to place the numbers to ensure a unique
 255  * solution.
 256  */
 257
 258 static void remove_rect_placement(int w, int h,
 259                                   struct rectlist *rectpositions,
 260                                   int *overlaps,
 261                                   int rectnum, int placement)
 262 {
 263     int x, y, xx, yy;
 264
 265 #ifdef SOLVER_DIAGNOSTICS
 266     printf("ruling out rect %d placement at %d,%d w=%d h=%d\n", rectnum,
 267            rectpositions[rectnum].rects[placement].x,
 268            rectpositions[rectnum].rects[placement].y,
 269            rectpositions[rectnum].rects[placement].w,
 270            rectpositions[rectnum].rects[placement].h);
 271 #endif
 272
 273     /*
 274      * Decrement each entry in the overlaps array to reflect the
 275      * removal of this rectangle placement.
 276      */
 277     for (yy = 0; yy < rectpositions[rectnum].rects[placement].h; yy++) {
 278         y = yy + rectpositions[rectnum].rects[placement].y;
 279         for (xx = 0; xx < rectpositions[rectnum].rects[placement].w; xx++) {
 280             x = xx + rectpositions[rectnum].rects[placement].x;
 281
 282             assert(overlaps[(rectnum * h + y) * w + x] != 0);
 283
 284             if (overlaps[(rectnum * h + y) * w + x] > 0)
 285                 overlaps[(rectnum * h + y) * w + x]--;
 286         }
 287     }
 288
 289     /*
 290      * Remove the placement from the list of positions for that
 291      * rectangle, by interchanging it with the one on the end.
 292      */
 293     if (placement < rectpositions[rectnum].n - 1) {
 294         struct rect t;
 295
 296         t = rectpositions[rectnum].rects[rectpositions[rectnum].n - 1];
 297         rectpositions[rectnum].rects[rectpositions[rectnum].n - 1] =
 298             rectpositions[rectnum].rects[placement];
 299         rectpositions[rectnum].rects[placement] = t;
 300     }
 301     rectpositions[rectnum].n--;
 302 }
 303
 304 static void remove_number_placement(int w, int h, struct numberdata *number,
 305                                     int index, int *rectbyplace)
 306 {
 307     /*
 308      * Remove the entry from the rectbyplace array.
 309      */
 310     rectbyplace[number->points[index].y * w + number->points[index].x] = -1;
 311
 312     /*
 313      * Remove the placement from the list of candidates for that
 314      * number, by interchanging it with the one on the end.
 315      */
 316     if (index < number->npoints - 1) {
 317         struct point t;
 318
 319         t = number->points[number->npoints - 1];
 320         number->points[number->npoints - 1] = number->points[index];
 321         number->points[index] = t;
 322     }
 323     number->npoints--;
 324 }
 325
 326 static int rect_solver(int w, int h, int nrects, struct numberdata *numbers,
 327                        unsigned char *hedge, unsigned char *vedge,
 328                        random_state *rs)
 329 {
 330     struct rectlist *rectpositions;
 331     int *overlaps, *rectbyplace, *workspace;
 332     int i, ret;
 333
 334     /*
 335      * Start by setting up a list of candidate positions for each
 336      * rectangle.
 337      */
 338     rectpositions = snewn(nrects, struct rectlist);
 339     for (i = 0; i < nrects; i++) {
 340         int rw, rh, area = numbers[i].area;
 341         int j, minx, miny, maxx, maxy;
 342         struct rect *rlist;
 343         int rlistn, rlistsize;
 344
 345         /*
 346          * For each rectangle, begin by finding the bounding
 347          * rectangle of its candidate number placements.
 348          */
 349         maxx = maxy = -1;
 350         minx = w;
 351         miny = h;
 352         for (j = 0; j < numbers[i].npoints; j++) {
 353             if (minx > numbers[i].points[j].x) minx = numbers[i].points[j].x;
 354             if (miny > numbers[i].points[j].y) miny = numbers[i].points[j].y;
 355             if (maxx < numbers[i].points[j].x) maxx = numbers[i].points[j].x;
 356             if (maxy < numbers[i].points[j].y) maxy = numbers[i].points[j].y;
 357         }
 358
 359         /*
 360          * Now loop over all possible rectangle placements
 361          * overlapping a point within that bounding rectangle;
 362          * ensure each one actually contains a candidate number
 363          * placement, and add it to the list.
 364          */
 365         rlist = NULL;
 366         rlistn = rlistsize = 0;
 367
 368         for (rw = 1; rw <= area && rw <= w; rw++) {
 369             int x, y;
 370
 371             if (area % rw)
 372                 continue;
 373             rh = area / rw;
 374             if (rh > h)
 375                 continue;
 376
 377             for (y = miny - rh + 1; y <= maxy; y++) {
 378                 if (y < 0 || y+rh > h)
 379                     continue;
 380
 381                 for (x = minx - rw + 1; x <= maxx; x++) {
 382                     if (x < 0 || x+rw > w)
 383                         continue;
 384
 385                     /*
 386                      * See if we can find a candidate number
 387                      * placement within this rectangle.
 388                      */
 389                     for (j = 0; j < numbers[i].npoints; j++)
 390                         if (numbers[i].points[j].x >= x &&
 391                             numbers[i].points[j].x < x+rw &&
 392                             numbers[i].points[j].y >= y &&
 393                             numbers[i].points[j].y < y+rh)
 394                             break;
 395
 396                     if (j < numbers[i].npoints) {
 397                         /*
 398                          * Add this to the list of candidate
 399                          * placements for this rectangle.
 400                          */
 401                         if (rlistn >= rlistsize) {
 402                             rlistsize = rlistn + 32;
 403                             rlist = sresize(rlist, rlistsize, struct rect);
 404                         }
 405                         rlist[rlistn].x = x;
 406                         rlist[rlistn].y = y;
 407                         rlist[rlistn].w = rw;
 408                         rlist[rlistn].h = rh;
 409 #ifdef SOLVER_DIAGNOSTICS
 410                         printf("rect %d [area %d]: candidate position at"
 411                                " %d,%d w=%d h=%d\n",
 412                                i, area, x, y, rw, rh);
 413 #endif
 414                         rlistn++;
 415                     }
 416                 }
 417             }
 418         }
 419
 420         rectpositions[i].rects = rlist;
 421         rectpositions[i].n = rlistn;
 422     }
 423
 424     /*
 425      * Next, construct a multidimensional array tracking how many
 426      * candidate positions for each rectangle overlap each square.
 427      *
 428      * Indexing of this array is by the formula
 429      *
 430      *   overlaps[(rectindex * h + y) * w + x]
 431      */
 432     overlaps = snewn(nrects * w * h, int);
 433     memset(overlaps, 0, nrects * w * h * sizeof(int));
 434     for (i = 0; i < nrects; i++) {
 435         int j;
 436
 437         for (j = 0; j < rectpositions[i].n; j++) {
 438             int xx, yy;
 439
 440             for (yy = 0; yy < rectpositions[i].rects[j].h; yy++)
 441                 for (xx = 0; xx < rectpositions[i].rects[j].w; xx++)
 442                     overlaps[(i * h + yy+rectpositions[i].rects[j].y) * w +
 443                              xx+rectpositions[i].rects[j].x]++;
 444         }
 445     }
 446
 447     /*
 448      * Also we want an array covering the grid once, to make it
 449      * easy to figure out which squares are candidate number
 450      * placements for which rectangles. (The existence of this
 451      * single array assumes that no square starts off as a
 452      * candidate number placement for more than one rectangle. This
 453      * assumption is justified, because this solver is _either_
 454      * used to solve real problems - in which case there is a
 455      * single placement for every number - _or_ used to decide on
 456      * number placements for a new puzzle, in which case each
 457      * number's placements are confined to the intended position of
 458      * the rectangle containing that number.)
 459      */
 460     rectbyplace = snewn(w * h, int);
 461     for (i = 0; i < w*h; i++)
 462         rectbyplace[i] = -1;
 463
 464     for (i = 0; i < nrects; i++) {
 465         int j;
 466
 467         for (j = 0; j < numbers[i].npoints; j++) {
 468             int x = numbers[i].points[j].x;
 469             int y = numbers[i].points[j].y;
 470
 471             assert(rectbyplace[y * w + x] == -1);
 472             rectbyplace[y * w + x] = i;
 473         }
 474     }
 475
 476     workspace = snewn(nrects, int);
 477
 478     /*
 479      * Now run the actual deduction loop.
 480      */
 481     while (1) {
 482         int done_something = FALSE;
 483
 484 #ifdef SOLVER_DIAGNOSTICS
 485         printf("starting deduction loop\n");
 486
 487         for (i = 0; i < nrects; i++) {
 488             printf("rect %d overlaps:\n", i);
 489             {
 490                 int x, y;
 491                 for (y = 0; y < h; y++) {
 492                     for (x = 0; x < w; x++) {
 493                         printf("%3d", overlaps[(i * h + y) * w + x]);
 494                     }
 495                     printf("\n");
 496                 }
 497             }
 498         }
 499         printf("rectbyplace:\n");
 500         {
 501             int x, y;
 502             for (y = 0; y < h; y++) {
 503                 for (x = 0; x < w; x++) {
 504                     printf("%3d", rectbyplace[y * w + x]);
 505                 }
 506                 printf("\n");
 507             }
 508         }
 509 #endif
 510
 511         /*
 512          * Housekeeping. Look for rectangles whose number has only
 513          * one candidate position left, and mark that square as
 514          * known if it isn't already.
 515          */
 516         for (i = 0; i < nrects; i++) {
 517             if (numbers[i].npoints == 1) {
 518                 int x = numbers[i].points[0].x;
 519                 int y = numbers[i].points[0].y;
 520                 if (overlaps[(i * h + y) * w + x] >= -1) {
 521                     int j;
 522
 523                     assert(overlaps[(i * h + y) * w + x] > 0);
 524 #ifdef SOLVER_DIAGNOSTICS
 525                     printf("marking %d,%d as known for rect %d"
 526                            " (sole remaining number position)\n", x, y, i);
 527 #endif
 528
 529                     for (j = 0; j < nrects; j++)
 530                         overlaps[(j * h + y) * w + x] = -1;
 531
 532                     overlaps[(i * h + y) * w + x] = -2;
 533                 }
 534             }
 535         }
 536
 537         /*
 538          * Now look at the intersection of all possible placements
 539          * for each rectangle, and mark all squares in that
 540          * intersection as known for that rectangle if they aren't
 541          * already.
 542          */
 543         for (i = 0; i < nrects; i++) {
 544             int minx, miny, maxx, maxy, xx, yy, j;
 545
 546             minx = miny = 0;
 547             maxx = w;
 548             maxy = h;
 549
 550             for (j = 0; j < rectpositions[i].n; j++) {
 551                 int x = rectpositions[i].rects[j].x;
 552                 int y = rectpositions[i].rects[j].y;
 553                 int w = rectpositions[i].rects[j].w;
 554                 int h = rectpositions[i].rects[j].h;
 555
 556                 if (minx < x) minx = x;
 557                 if (miny < y) miny = y;
 558                 if (maxx > x+w) maxx = x+w;
 559                 if (maxy > y+h) maxy = y+h;
 560             }
 561
 562             for (yy = miny; yy < maxy; yy++)
 563                 for (xx = minx; xx < maxx; xx++)
 564                     if (overlaps[(i * h + yy) * w + xx] >= -1) {
 565                         assert(overlaps[(i * h + yy) * w + xx] > 0);
 566 #ifdef SOLVER_DIAGNOSTICS
 567                         printf("marking %d,%d as known for rect %d"
 568                                " (intersection of all placements)\n",
 569                                xx, yy, i);
 570 #endif
 571
 572                         for (j = 0; j < nrects; j++)
 573                             overlaps[(j * h + yy) * w + xx] = -1;
 574
 575                         overlaps[(i * h + yy) * w + xx] = -2;
 576                     }
 577         }
 578
 579         /*
 580          * Rectangle-focused deduction. Look at each rectangle in
 581          * turn and try to rule out some of its candidate
 582          * placements.
 583          */
 584         for (i = 0; i < nrects; i++) {
 585             int j;
 586
 587             for (j = 0; j < rectpositions[i].n; j++) {
 588                 int xx, yy, k;
 589                 int del = FALSE;
 590
 591                 for (k = 0; k < nrects; k++)
 592                     workspace[k] = 0;
 593
 594                 for (yy = 0; yy < rectpositions[i].rects[j].h; yy++) {
 595                     int y = yy + rectpositions[i].rects[j].y;
 596                     for (xx = 0; xx < rectpositions[i].rects[j].w; xx++) {
 597                         int x = xx + rectpositions[i].rects[j].x;
 598
 599                         if (overlaps[(i * h + y) * w + x] == -1) {
 600                             /*
 601                              * This placement overlaps a square
 602                              * which is _known_ to be part of
 603                              * another rectangle. Therefore we must
 604                              * rule it out.
 605                              */
 606 #ifdef SOLVER_DIAGNOSTICS
 607                             printf("rect %d placement at %d,%d w=%d h=%d "
 608                                    "contains %d,%d which is known-other\n", i,
 609                                    rectpositions[i].rects[j].x,
 610                                    rectpositions[i].rects[j].y,
 611                                    rectpositions[i].rects[j].w,
 612                                    rectpositions[i].rects[j].h,
 613                                    x, y);
 614 #endif
 615                             del = TRUE;
 616                         }
 617
 618                         if (rectbyplace[y * w + x] != -1) {
 619                             /*
 620                              * This placement overlaps one of the
 621                              * candidate number placements for some
 622                              * rectangle. Count it.
 623                              */
 624                             workspace[rectbyplace[y * w + x]]++;
 625                         }
 626                     }
 627                 }
 628
 629                 if (!del) {
 630                     /*
 631                      * If we haven't ruled this placement out
 632                      * already, see if it overlaps _all_ of the
 633                      * candidate number placements for any
 634                      * rectangle. If so, we can rule it out.
 635                      */
 636                     for (k = 0; k < nrects; k++)
 637                         if (k != i && workspace[k] == numbers[k].npoints) {
 638 #ifdef SOLVER_DIAGNOSTICS
 639                             printf("rect %d placement at %d,%d w=%d h=%d "
 640                                    "contains all number points for rect %d\n",
 641                                    i,
 642                                    rectpositions[i].rects[j].x,
 643                                    rectpositions[i].rects[j].y,
 644                                    rectpositions[i].rects[j].w,
 645                                    rectpositions[i].rects[j].h,
 646                                    k);
 647 #endif
 648                             del = TRUE;
 649                             break;
 650                         }
 651
 652                     /*
 653                      * Failing that, see if it overlaps at least
 654                      * one of the candidate number placements for
 655                      * itself! (This might not be the case if one
 656                      * of those number placements has been removed
 657                      * recently.).
 658                      */
 659                     if (!del && workspace[i] == 0) {
 660 #ifdef SOLVER_DIAGNOSTICS
 661                         printf("rect %d placement at %d,%d w=%d h=%d "
 662                                "contains none of its own number points\n",
 663                                i,
 664                                rectpositions[i].rects[j].x,
 665                                rectpositions[i].rects[j].y,
 666                                rectpositions[i].rects[j].w,
 667                                rectpositions[i].rects[j].h);
 668 #endif
 669                         del = TRUE;
 670                     }
 671                 }
 672
 673                 if (del) {
 674                     remove_rect_placement(w, h, rectpositions, overlaps, i, j);
 675
 676                     j--;               /* don't skip over next placement */
 677
 678                     done_something = TRUE;
 679                 }
 680             }
 681         }
 682
 683         /*
 684          * Square-focused deduction. Look at each square not marked
 685          * as known, and see if there are any which can only be
 686          * part of a single rectangle.
 687          */
 688         {
 689             int x, y, n, index;
 690             for (y = 0; y < h; y++) for (x = 0; x < w; x++) {
 691                 /* Known squares are marked as <0 everywhere, so we only need
 692                  * to check the overlaps entry for rect 0. */
 693                 if (overlaps[y * w + x] < 0)
 694                     continue;          /* known already */
 695
 696                 n = 0;
 697                 index = -1;
 698                 for (i = 0; i < nrects; i++)
 699                     if (overlaps[(i * h + y) * w + x] > 0)
 700                         n++, index = i;
 701
 702                 if (n == 1) {
 703                     int j;
 704
 705                     /*
 706                      * Now we can rule out all placements for
 707                      * rectangle `index' which _don't_ contain
 708                      * square x,y.
 709                      */
 710 #ifdef SOLVER_DIAGNOSTICS
 711                     printf("square %d,%d can only be in rectangle %d\n",
 712                            x, y, index);
 713 #endif
 714                     for (j = 0; j < rectpositions[index].n; j++) {
 715                         struct rect *r = &rectpositions[index].rects[j];
 716                         if (x >= r->x && x < r->x + r->w &&
 717                             y >= r->y && y < r->y + r->h)
 718                             continue;  /* this one is OK */
 719                         remove_rect_placement(w, h, rectpositions, overlaps,
 720                                               index, j);
 721                         j--;           /* don't skip over next placement */
 722                         done_something = TRUE;
 723                     }
 724                 }
 725             }
 726         }
 727
 728         /*
 729          * If we've managed to deduce anything by normal means,
 730          * loop round again and see if there's more to be done.
 731          * Only if normal deduction has completely failed us should
 732          * we now move on to narrowing down the possible number
 733          * placements.
 734          */
 735         if (done_something)
 736             continue;
 737
 738         /*
 739          * Now we have done everything we can with the current set
 740          * of number placements. So we need to winnow the number
 741          * placements so as to narrow down the possibilities. We do
 742          * this by searching for a candidate placement (of _any_
 743          * rectangle) which overlaps a candidate placement of the
 744          * number for some other rectangle.
 745          */
 746         if (rs) {
 747             struct rpn {
 748                 int rect;
 749                 int placement;
 750                 int number;
 751             } *rpns = NULL;
 752             size_t nrpns = 0, rpnsize = 0;
 753             int j;
 754
 755             for (i = 0; i < nrects; i++) {
 756                 for (j = 0; j < rectpositions[i].n; j++) {
 757                     int xx, yy;
 758
 759                     for (yy = 0; yy < rectpositions[i].rects[j].h; yy++) {
 760                         int y = yy + rectpositions[i].rects[j].y;
 761                         for (xx = 0; xx < rectpositions[i].rects[j].w; xx++) {
 762                             int x = xx + rectpositions[i].rects[j].x;
 763
 764                             if (rectbyplace[y * w + x] >= 0 &&
 765                                 rectbyplace[y * w + x] != i) {
 766                                 /*
 767                                  * Add this to the list of
 768                                  * winnowing possibilities.
 769                                  */
 770                                 if (nrpns >= rpnsize) {
 771                                     rpnsize = rpnsize * 3 / 2 + 32;
 772                                     rpns = sresize(rpns, rpnsize, struct rpn);
 773                                 }
 774                                 rpns[nrpns].rect = i;
 775                                 rpns[nrpns].placement = j;
 776                                 rpns[nrpns].number = rectbyplace[y * w + x];
 777                                 nrpns++;
 778                             }
 779                         }
 780                     }
 781
 782                 }
 783             }
 784
 785 #ifdef SOLVER_DIAGNOSTICS
 786             printf("%d candidate rect placements we could eliminate\n", nrpns);
 787 #endif
 788             if (nrpns > 0) {
 789                 /*
 790                  * Now choose one of these unwanted rectangle
 791                  * placements, and eliminate it.
 792                  */
 793                 int index = random_upto(rs, nrpns);
 794                 int k, m;
 795                 struct rpn rpn = rpns[index];
 796                 struct rect r;
 797                 sfree(rpns);
 798
 799                 i = rpn.rect;
 800                 j = rpn.placement;
 801                 k = rpn.number;
 802                 r = rectpositions[i].rects[j];
 803
 804                 /*
 805                  * We rule out placement j of rectangle i by means
 806                  * of removing all of rectangle k's candidate
 807                  * number placements which do _not_ overlap it.
 808                  * This will ensure that it is eliminated during
 809                  * the next pass of rectangle-focused deduction.
 810                  */
 811 #ifdef SOLVER_DIAGNOSTICS
 812                 printf("ensuring number for rect %d is within"
 813                        " rect %d's placement at %d,%d w=%d h=%d\n",
 814                        k, i, r.x, r.y, r.w, r.h);
 815 #endif
 816
 817                 for (m = 0; m < numbers[k].npoints; m++) {
 818                     int x = numbers[k].points[m].x;
 819                     int y = numbers[k].points[m].y;
 820
 821                     if (x < r.x || x >= r.x + r.w ||
 822                         y < r.y || y >= r.y + r.h) {
 823 #ifdef SOLVER_DIAGNOSTICS
 824                         printf("eliminating number for rect %d at %d,%d\n",
 825                                k, x, y);
 826 #endif
 827                         remove_number_placement(w, h, &numbers[k],
 828                                                 m, rectbyplace);
 829                         m--;           /* don't skip the next one */
 830                         done_something = TRUE;
 831                     }
 832                 }
 833             }
 834         }
 835
 836         if (!done_something) {
 837 #ifdef SOLVER_DIAGNOSTICS
 838             printf("terminating deduction loop\n");
 839 #endif
 840             break;
 841         }
 842     }
 843
 844     ret = TRUE;
 845     for (i = 0; i < nrects; i++) {
 846 #ifdef SOLVER_DIAGNOSTICS
 847         printf("rect %d has %d possible placements\n",
 848                i, rectpositions[i].n);
 849 #endif
 850         assert(rectpositions[i].n > 0);
 851         if (rectpositions[i].n > 1) {
 852             ret = FALSE;
 853         } else if (hedge && vedge) {
 854             /*
 855              * Place the rectangle in its only possible position.
 856              */
 857             int x, y;
 858             struct rect *r = &rectpositions[i].rects[0];
 859
 860             for (y = 0; y < r->h; y++) {
 861                 if (r->x > 0)
 862                     vedge[(r->y+y) * w + r->x] = 1;
 863                 if (r->x+r->w < w)
 864                     vedge[(r->y+y) * w + r->x+r->w] = 1;
 865             }
 866             for (x = 0; x < r->w; x++) {
 867                 if (r->y > 0)
 868                     hedge[r->y * w + r->x+x] = 1;
 869                 if (r->y+r->h < h)
 870                     hedge[(r->y+r->h) * w + r->x+x] = 1;
 871             }
 872         }
 873     }
 874
 875     /*
 876      * Free up all allocated storage.
 877      */
 878     sfree(workspace);
 879     sfree(rectbyplace);
 880     sfree(overlaps);
 881     for (i = 0; i < nrects; i++)
 882         sfree(rectpositions[i].rects);
 883     sfree(rectpositions);
 884
 885     return ret;
 886 }
 887
 888 /* ----------------------------------------------------------------------
 889  * Grid generation code.
 890  */
 891
 892 /*
 893  * This function does one of two things. If passed r==NULL, it
 894  * counts the number of possible rectangles which cover the given
 895  * square, and returns it in *n. If passed r!=NULL then it _reads_
 896  * *n to find an index, counts the possible rectangles until it
 897  * reaches the nth, and writes it into r.
 898  *
 899  * `scratch' is expected to point to an array of 2 * params->w
 900  * ints, used internally as scratch space (and passed in like this
 901  * to avoid re-allocating and re-freeing it every time round a
 902  * tight loop).
 903  */
 904 static void enum_rects(game_params *params, int *grid, struct rect *r, int *n,
 905                        int sx, int sy, int *scratch)
 906 {
 907     int rw, rh, mw, mh;
 908     int x, y, dx, dy;
 909     int maxarea, realmaxarea;
 910     int index = 0;
 911     int *top, *bottom;
 912
 913     /*
 914      * Maximum rectangle area is 1/6 of total grid size, unless
 915      * this means we can't place any rectangles at all in which
 916      * case we set it to 2 at minimum.
 917      */
 918     maxarea = params->w * params->h / 6;
 919     if (maxarea < 2)
 920         maxarea = 2;
 921
 922     /*
 923      * Scan the grid to find the limits of the region within which
 924      * any rectangle containing this point must fall. This will
 925      * save us trawling the inside of every rectangle later on to
 926      * see if it contains any used squares.
 927      */
 928     top = scratch;
 929     bottom = scratch + params->w;
 930     for (dy = -1; dy <= +1; dy += 2) {
 931         int *array = (dy == -1 ? top : bottom);
 932         for (dx = -1; dx <= +1; dx += 2) {
 933             for (x = sx; x >= 0 && x < params->w; x += dx) {
 934                 array[x] = -2 * params->h * dy;
 935                 for (y = sy; y >= 0 && y < params->h; y += dy) {
 936                     if (index(params, grid, x, y) == -1 &&
 937                         (x == sx || dy*y <= dy*array[x-dx]))
 938                         array[x] = y;
 939                     else
 940                         break;
 941                 }
 942             }
 943         }
 944     }
 945
 946     /*
 947      * Now scan again to work out the largest rectangles we can fit
 948      * in the grid, so that we can terminate the following loops
 949      * early once we get down to not having much space left in the
 950      * grid.
 951      */
 952     realmaxarea = 0;
 953     for (x = 0; x < params->w; x++) {
 954         int x2;
 955
 956         rh = bottom[x] - top[x] + 1;
 957         if (rh <= 0)
 958             continue;                  /* no rectangles can start here */
 959
 960         dx = (x > sx ? -1 : +1);
 961         for (x2 = x; x2 >= 0 && x2 < params->w; x2 += dx)
 962             if (bottom[x2] < bottom[x] || top[x2] > top[x])
 963                 break;
 964
 965         rw = abs(x2 - x);
 966         if (realmaxarea < rw * rh)
 967             realmaxarea = rw * rh;
 968     }
 969
 970     if (realmaxarea > maxarea)
 971         realmaxarea = maxarea;
 972
 973     /*
 974      * Rectangles which go right the way across the grid are
 975      * boring, although they can't be helped in the case of
 976      * extremely small grids. (Also they might be generated later
 977      * on by the singleton-removal process; we can't help that.)
 978      */
 979     mw = params->w - 1;
 980     if (mw < 3) mw++;
 981     mh = params->h - 1;
 982     if (mh < 3) mh++;
 983
 984     for (rw = 1; rw <= mw; rw++)
 985         for (rh = 1; rh <= mh; rh++) {
 986             if (rw * rh > realmaxarea)
 987                 continue;
 988             if (rw * rh == 1)
 989                 continue;
 990             for (x = max(sx - rw + 1, 0); x <= min(sx, params->w - rw); x++)
 991                 for (y = max(sy - rh + 1, 0); y <= min(sy, params->h - rh);
 992                      y++) {
 993                     /*
 994                      * Check this rectangle against the region we
 995                      * defined above.
 996                      */
 997                     if (top[x] <= y && top[x+rw-1] <= y &&
 998                         bottom[x] >= y+rh-1 && bottom[x+rw-1] >= y+rh-1) {
 999                         if (r && index == *n) {
1000                             r->x = x;
1001                             r->y = y;
1002                             r->w = rw;
1003                             r->h = rh;
1004                             return;
1005                         }
1006                         index++;
1007                     }
1008                 }
1009         }
1010
1011     assert(!r);
1012     *n = index;
1013 }
1014
1015 static void place_rect(game_params *params, int *grid, struct rect r)
1016 {
1017     int idx = INDEX(params, r.x, r.y);
1018     int x, y;
1019
1020     for (x = r.x; x < r.x+r.w; x++)
1021         for (y = r.y; y < r.y+r.h; y++) {
1022             index(params, grid, x, y) = idx;
1023         }
1024 #ifdef GENERATION_DIAGNOSTICS
1025     printf("    placing rectangle at (%d,%d) size %d x %d\n",
1026            r.x, r.y, r.w, r.h);
1027 #endif
1028 }
1029
1030 static struct rect find_rect(game_params *params, int *grid, int x, int y)
1031 {
1032     int idx, w, h;
1033     struct rect r;
1034
1035     /*
1036      * Find the top left of the rectangle.
1037      */
1038     idx = index(params, grid, x, y);
1039
1040     if (idx < 0) {
1041         r.x = x;
1042         r.y = y;
1043         r.w = r.h = 1;
1044         return r;                      /* 1x1 singleton here */
1045     }
1046
1047     y = idx / params->w;
1048     x = idx % params->w;
1049
1050     /*
1051      * Find the width and height of the rectangle.
1052      */
1053     for (w = 1;
1054          (x+w < params->w && index(params,grid,x+w,y)==idx);
1055          w++);
1056     for (h = 1;
1057          (y+h < params->h && index(params,grid,x,y+h)==idx);
1058          h++);
1059
1060     r.x = x;
1061     r.y = y;
1062     r.w = w;
1063     r.h = h;
1064
1065     return r;
1066 }
1067
1068 #ifdef GENERATION_DIAGNOSTICS
1069 static void display_grid(game_params *params, int *grid, int *numbers, int all)
1070 {
1071     unsigned char *egrid = snewn((params->w*2+3) * (params->h*2+3),
1072                                  unsigned char);
1073     int x, y;
1074     int r = (params->w*2+3);
1075
1076     memset(egrid, 0, (params->w*2+3) * (params->h*2+3));
1077
1078     for (x = 0; x < params->w; x++)
1079         for (y = 0; y < params->h; y++) {
1080             int i = index(params, grid, x, y);
1081             if (x == 0 || index(params, grid, x-1, y) != i)
1082                 egrid[(2*y+2) * r + (2*x+1)] = 1;
1083             if (x == params->w-1 || index(params, grid, x+1, y) != i)
1084                 egrid[(2*y+2) * r + (2*x+3)] = 1;
1085             if (y == 0 || index(params, grid, x, y-1) != i)
1086                 egrid[(2*y+1) * r + (2*x+2)] = 1;
1087             if (y == params->h-1 || index(params, grid, x, y+1) != i)
1088                 egrid[(2*y+3) * r + (2*x+2)] = 1;
1089         }
1090
1091     for (y = 1; y < 2*params->h+2; y++) {
1092         for (x = 1; x < 2*params->w+2; x++) {
1093             if (!((y|x)&1)) {
1094                 int k = numbers ? index(params, numbers, x/2-1, y/2-1) : 0;
1095                 if (k || (all && numbers)) printf("%2d", k); else printf("  ");
1096             } else if (!((y&x)&1)) {
1097                 int v = egrid[y*r+x];
1098                 if ((y&1) && v) v = '-';
1099                 if ((x&1) && v) v = '|';
1100                 if (!v) v = ' ';
1101                 putchar(v);
1102                 if (!(x&1)) putchar(v);
1103             } else {
1104                 int c, d = 0;
1105                 if (egrid[y*r+(x+1)]) d |= 1;
1106                 if (egrid[(y-1)*r+x]) d |= 2;
1107                 if (egrid[y*r+(x-1)]) d |= 4;
1108                 if (egrid[(y+1)*r+x]) d |= 8;
1109                 c = " ??+?-++?+|+++++"[d];
1110                 putchar(c);
1111                 if (!(x&1)) putchar(c);
1112             }
1113         }
1114         putchar('\n');
1115     }
1116
1117     sfree(egrid);
1118 }
1119 #endif
1120
1121 static char *new_game_desc(game_params *params, random_state *rs,
1122                            char **aux, int interactive)
1123 {
1124     int *grid, *numbers = NULL;
1125     int x, y, y2, y2last, yx, run, i, nsquares;
1126     char *desc, *p;
1127     int *enum_rects_scratch;
1128     game_params params2real, *params2 = &params2real;
1129
1130     while (1) {
1131         /*
1132          * Set up the smaller width and height which we will use to
1133          * generate the base grid.
1134          */
1135         params2->w = params->w / (1.0F + params->expandfactor);
1136         if (params2->w < 2 && params->w >= 2) params2->w = 2;
1137         params2->h = params->h / (1.0F + params->expandfactor);
1138         if (params2->h < 2 && params->h >= 2) params2->h = 2;
1139
1140         grid = snewn(params2->w * params2->h, int);
1141
1142         enum_rects_scratch = snewn(2 * params2->w, int);
1143
1144         nsquares = 0;
1145         for (y = 0; y < params2->h; y++)
1146             for (x = 0; x < params2->w; x++) {
1147                 index(params2, grid, x, y) = -1;
1148                 nsquares++;
1149             }
1150
1151         /*
1152          * Place rectangles until we can't any more. We do this by
1153          * finding a square we haven't yet covered, and randomly
1154          * choosing a rectangle to cover it.
1155          */
1156
1157         while (nsquares > 0) {
1158             int square = random_upto(rs, nsquares);
1159             int n;
1160             struct rect r;
1161
1162             x = params2->w;
1163             y = params2->h;
1164             for (y = 0; y < params2->h; y++) {
1165                 for (x = 0; x < params2->w; x++) {
1166                     if (index(params2, grid, x, y) == -1 && square-- == 0)
1167                         break;
1168                 }
1169                 if (x < params2->w)
1170                     break;
1171             }
1172             assert(x < params2->w && y < params2->h);
1173
1174             /*
1175              * Now see how many rectangles fit around this one.
1176              */
1177             enum_rects(params2, grid, NULL, &n, x, y, enum_rects_scratch);
1178
1179             if (!n) {
1180                 /*
1181                  * There are no possible rectangles covering this
1182                  * square, meaning it must be a singleton. Mark it
1183                  * -2 so we know not to keep trying.
1184                  */
1185                 index(params2, grid, x, y) = -2;
1186                 nsquares--;
1187             } else {
1188                 /*
1189                  * Pick one at random.
1190                  */
1191                 n = random_upto(rs, n);
1192                 enum_rects(params2, grid, &r, &n, x, y, enum_rects_scratch);
1193
1194                 /*
1195                  * Place it.
1196                  */
1197                 place_rect(params2, grid, r);
1198                 nsquares -= r.w * r.h;
1199             }
1200         }
1201
1202         sfree(enum_rects_scratch);
1203
1204         /*
1205          * Deal with singleton spaces remaining in the grid, one by
1206          * one.
1207          *
1208          * We do this by making a local change to the layout. There are
1209          * several possibilities:
1210          *
1211          *     +-----+-----+    Here, we can remove the singleton by
1212          *     |     |     |    extending the 1x2 rectangle below it
1213          *     +--+--+-----+    into a 1x3.
1214          *     |  |  |     |
1215          *     |  +--+     |
1216          *     |  |  |     |
1217          *     |  |  |     |
1218          *     |  |  |     |
1219          *     +--+--+-----+
1220          *
1221          *     +--+--+--+       Here, that trick doesn't work: there's no
1222          *     |     |  |       1 x n rectangle with the singleton at one
1223          *     |     |  |       end. Instead, we extend a 1 x n rectangle
1224          *     |     |  |       _out_ from the singleton, shaving a layer
1225          *     +--+--+  |       off the end of another rectangle. So if we
1226          *     |  |  |  |       extended up, we'd make our singleton part
1227          *     |  +--+--+       of a 1x3 and generate a 1x2 where the 2x2
1228          *     |  |     |       used to be; or we could extend right into
1229          *     +--+-----+       a 2x1, turning the 1x3 into a 1x2.
1230          *
1231          *     +-----+--+       Here, we can't even do _that_, since any
1232          *     |     |  |       direction we choose to extend the singleton
1233          *     +--+--+  |       will produce a new singleton as a result of
1234          *     |  |  |  |       truncating one of the size-2 rectangles.
1235          *     |  +--+--+       Fortunately, this case can _only_ occur when
1236          *     |  |     |       a singleton is surrounded by four size-2s
1237          *     +--+-----+       in this fashion; so instead we can simply
1238          *                      replace the whole section with a single 3x3.
1239          */
1240         for (x = 0; x < params2->w; x++) {
1241             for (y = 0; y < params2->h; y++) {
1242                 if (index(params2, grid, x, y) < 0) {
1243                     int dirs[4], ndirs;
1244
1245 #ifdef GENERATION_DIAGNOSTICS
1246                     display_grid(params2, grid, NULL, FALSE);
1247                     printf("singleton at %d,%d\n", x, y);
1248 #endif
1249
1250                     /*
1251                      * Check in which directions we can feasibly extend
1252                      * the singleton. We can extend in a particular
1253                      * direction iff either:
1254                      *
1255                      *  - the rectangle on that side of the singleton
1256                      *    is not 2x1, and we are at one end of the edge
1257                      *    of it we are touching
1258                      *
1259                      *  - it is 2x1 but we are on its short side.
1260                      *
1261                      * FIXME: we could plausibly choose between these
1262                      * based on the sizes of the rectangles they would
1263                      * create?
1264                      */
1265                     ndirs = 0;
1266                     if (x < params2->w-1) {
1267                         struct rect r = find_rect(params2, grid, x+1, y);
1268                         if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
1269                             dirs[ndirs++] = 1;   /* right */
1270                     }
1271                     if (y > 0) {
1272                         struct rect r = find_rect(params2, grid, x, y-1);
1273                         if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
1274                             dirs[ndirs++] = 2;   /* up */
1275                     }
1276                     if (x > 0) {
1277                         struct rect r = find_rect(params2, grid, x-1, y);
1278                         if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
1279                             dirs[ndirs++] = 4;   /* left */
1280                     }
1281                     if (y < params2->h-1) {
1282                         struct rect r = find_rect(params2, grid, x, y+1);
1283                         if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
1284                             dirs[ndirs++] = 8;   /* down */
1285                     }
1286
1287                     if (ndirs > 0) {
1288                         int which, dir;
1289                         struct rect r1, r2;
1290
1291                         which = random_upto(rs, ndirs);
1292                         dir = dirs[which];
1293
1294                         switch (dir) {
1295                           case 1:          /* right */
1296                             assert(x < params2->w+1);
1297 #ifdef GENERATION_DIAGNOSTICS
1298                             printf("extending right\n");
1299 #endif
1300                             r1 = find_rect(params2, grid, x+1, y);
1301                             r2.x = x;
1302                             r2.y = y;
1303                             r2.w = 1 + r1.w;
1304                             r2.h = 1;
1305                             if (r1.y == y)
1306                                 r1.y++;
1307                             r1.h--;
1308                             break;
1309                           case 2:          /* up */
1310                             assert(y > 0);
1311 #ifdef GENERATION_DIAGNOSTICS
1312                             printf("extending up\n");
1313 #endif
1314                             r1 = find_rect(params2, grid, x, y-1);
1315                             r2.x = x;
1316                             r2.y = r1.y;
1317                             r2.w = 1;
1318                             r2.h = 1 + r1.h;
1319                             if (r1.x == x)
1320                                 r1.x++;
1321                             r1.w--;
1322                             break;
1323                           case 4:          /* left */
1324                             assert(x > 0);
1325 #ifdef GENERATION_DIAGNOSTICS
1326                             printf("extending left\n");
1327 #endif
1328                             r1 = find_rect(params2, grid, x-1, y);
1329                             r2.x = r1.x;
1330                             r2.y = y;
1331                             r2.w = 1 + r1.w;
1332                             r2.h = 1;
1333                             if (r1.y == y)
1334                                 r1.y++;
1335                             r1.h--;
1336                             break;
1337                           case 8:          /* down */
1338                             assert(y < params2->h+1);
1339 #ifdef GENERATION_DIAGNOSTICS
1340                             printf("extending down\n");
1341 #endif
1342                             r1 = find_rect(params2, grid, x, y+1);
1343                             r2.x = x;
1344                             r2.y = y;
1345                             r2.w = 1;
1346                             r2.h = 1 + r1.h;
1347                             if (r1.x == x)
1348                                 r1.x++;
1349                             r1.w--;
1350                             break;
1351                         }
1352                         if (r1.h > 0 && r1.w > 0)
1353                             place_rect(params2, grid, r1);
1354                         place_rect(params2, grid, r2);
1355                     } else {
1356 #ifndef NDEBUG
1357                         /*
1358                          * Sanity-check that there really is a 3x3
1359                          * rectangle surrounding this singleton and it
1360                          * contains absolutely everything we could
1361                          * possibly need.
1362                          */
1363                         {
1364                             int xx, yy;
1365                             assert(x > 0 && x < params2->w-1);
1366                             assert(y > 0 && y < params2->h-1);
1367
1368                             for (xx = x-1; xx <= x+1; xx++)
1369                                 for (yy = y-1; yy <= y+1; yy++) {
1370                                     struct rect r = find_rect(params2,grid,xx,yy);
1371                                     assert(r.x >= x-1);
1372                                     assert(r.y >= y-1);
1373                                     assert(r.x+r.w-1 <= x+1);
1374                                     assert(r.y+r.h-1 <= y+1);
1375                                 }
1376                         }
1377 #endif
1378
1379 #ifdef GENERATION_DIAGNOSTICS
1380                         printf("need the 3x3 trick\n");
1381 #endif
1382
1383                         /*
1384                          * FIXME: If the maximum rectangle area for
1385                          * this grid is less than 9, we ought to
1386                          * subdivide the 3x3 in some fashion. There are
1387                          * five other possibilities:
1388                          *
1389                          *  - a 6 and a 3
1390                          *  - a 4, a 3 and a 2
1391                          *  - three 3s
1392                          *  - a 3 and three 2s (two different arrangements).
1393                          */
1394
1395                         {
1396                             struct rect r;
1397                             r.x = x-1;
1398                             r.y = y-1;
1399                             r.w = r.h = 3;
1400                             place_rect(params2, grid, r);
1401                         }
1402                     }
1403                 }
1404             }
1405         }
1406
1407         /*
1408          * We have now constructed a grid of the size specified in
1409          * params2. Now we extend it into a grid of the size specified
1410          * in params. We do this in two passes: we extend it vertically
1411          * until it's the right height, then we transpose it, then
1412          * extend it vertically again (getting it effectively the right
1413          * width), then finally transpose again.
1414          */
1415         for (i = 0; i < 2; i++) {
1416             int *grid2, *expand, *where;
1417             game_params params3real, *params3 = &params3real;
1418
1419 #ifdef GENERATION_DIAGNOSTICS
1420             printf("before expansion:\n");
1421             display_grid(params2, grid, NULL, TRUE);
1422 #endif
1423
1424             /*
1425              * Set up the new grid.
1426              */
1427             grid2 = snewn(params2->w * params->h, int);
1428             expand = snewn(params2->h-1, int);
1429             where = snewn(params2->w, int);
1430             params3->w = params2->w;
1431             params3->h = params->h;
1432
1433             /*
1434              * Decide which horizontal edges are going to get expanded,
1435              * and by how much.
1436              */
1437             for (y = 0; y < params2->h-1; y++)
1438                 expand[y] = 0;
1439             for (y = params2->h; y < params->h; y++) {
1440                 x = random_upto(rs, params2->h-1);
1441                 expand[x]++;
1442             }
1443
1444 #ifdef GENERATION_DIAGNOSTICS
1445             printf("expand[] = {");
1446             for (y = 0; y < params2->h-1; y++)
1447                 printf(" %d", expand[y]);
1448             printf(" }\n");
1449 #endif
1450
1451             /*
1452              * Perform the expansion. The way this works is that we
1453              * alternately:
1454              *
1455              *  - copy a row from grid into grid2
1456              *
1457              *  - invent some number of additional rows in grid2 where
1458              *    there was previously only a horizontal line between
1459              *    rows in grid, and make random decisions about where
1460              *    among these to place each rectangle edge that ran
1461              *    along this line.
1462              */
1463             for (y = y2 = y2last = 0; y < params2->h; y++) {
1464                 /*
1465                  * Copy a single line from row y of grid into row y2 of
1466                  * grid2.
1467                  */
1468                 for (x = 0; x < params2->w; x++) {
1469                     int val = index(params2, grid, x, y);
1470                     if (val / params2->w == y &&   /* rect starts on this line */
1471                         (y2 == 0 ||            /* we're at the very top, or... */
1472                          index(params3, grid2, x, y2-1) / params3->w < y2last
1473                          /* this rect isn't already started */))
1474                         index(params3, grid2, x, y2) =
1475                         INDEX(params3, val % params2->w, y2);
1476                     else
1477                         index(params3, grid2, x, y2) =
1478                         index(params3, grid2, x, y2-1);
1479                 }
1480
1481                 /*
1482                  * If that was the last line, terminate the loop early.
1483                  */
1484                 if (++y2 == params3->h)
1485                     break;
1486
1487                 y2last = y2;
1488
1489                 /*
1490                  * Invent some number of additional lines. First walk
1491                  * along this line working out where to put all the
1492                  * edges that coincide with it.
1493                  */
1494                 yx = -1;
1495                 for (x = 0; x < params2->w; x++) {
1496                     if (index(params2, grid, x, y) !=
1497                         index(params2, grid, x, y+1)) {
1498                         /*
1499                          * This is a horizontal edge, so it needs
1500                          * placing.
1501                          */
1502                         if (x == 0 ||
1503                             (index(params2, grid, x-1, y) !=
1504                              index(params2, grid, x, y) &&
1505                              index(params2, grid, x-1, y+1) !=
1506                              index(params2, grid, x, y+1))) {
1507                             /*
1508                              * Here we have the chance to make a new
1509                              * decision.
1510                              */
1511                             yx = random_upto(rs, expand[y]+1);
1512                         } else {
1513                             /*
1514                              * Here we just reuse the previous value of
1515                              * yx.
1516                              */
1517                         }
1518                     } else
1519                         yx = -1;
1520                     where[x] = yx;
1521                 }
1522
1523                 for (yx = 0; yx < expand[y]; yx++) {
1524                     /*
1525                      * Invent a single row. For each square in the row,
1526                      * we copy the grid entry from the square above it,
1527                      * unless we're starting the new rectangle here.
1528                      */
1529                     for (x = 0; x < params2->w; x++) {
1530                         if (yx == where[x]) {
1531                             int val = index(params2, grid, x, y+1);
1532                             val %= params2->w;
1533                             val = INDEX(params3, val, y2);
1534                             index(params3, grid2, x, y2) = val;
1535                         } else
1536                             index(params3, grid2, x, y2) =
1537                             index(params3, grid2, x, y2-1);
1538                     }
1539
1540                     y2++;
1541                 }
1542             }
1543
1544             sfree(expand);
1545             sfree(where);
1546
1547 #ifdef GENERATION_DIAGNOSTICS
1548             printf("after expansion:\n");
1549             display_grid(params3, grid2, NULL, TRUE);
1550 #endif
1551             /*
1552              * Transpose.
1553              */
1554             params2->w = params3->h;
1555             params2->h = params3->w;
1556             sfree(grid);
1557             grid = snewn(params2->w * params2->h, int);
1558             for (x = 0; x < params2->w; x++)
1559                 for (y = 0; y < params2->h; y++) {
1560                     int idx1 = INDEX(params2, x, y);
1561                     int idx2 = INDEX(params3, y, x);
1562                     int tmp;
1563
1564                     tmp = grid2[idx2];
1565                     tmp = (tmp % params3->w) * params2->w + (tmp / params3->w);
1566                     grid[idx1] = tmp;
1567                 }
1568
1569             sfree(grid2);
1570
1571             {
1572                 int tmp;
1573                 tmp = params->w;
1574                 params->w = params->h;
1575                 params->h = tmp;
1576             }
1577
1578 #ifdef GENERATION_DIAGNOSTICS
1579             printf("after transposition:\n");
1580             display_grid(params2, grid, NULL, TRUE);
1581 #endif
1582         }
1583
1584         /*
1585          * Run the solver to narrow down the possible number
1586          * placements.
1587          */
1588         {
1589             struct numberdata *nd;
1590             int nnumbers, i, ret;
1591
1592             /* Count the rectangles. */
1593             nnumbers = 0;
1594             for (y = 0; y < params->h; y++) {
1595                 for (x = 0; x < params->w; x++) {
1596                     int idx = INDEX(params, x, y);
1597                     if (index(params, grid, x, y) == idx)
1598                         nnumbers++;
1599                 }
1600             }
1601
1602             nd = snewn(nnumbers, struct numberdata);
1603
1604             /* Now set up each number's candidate position list. */
1605             i = 0;
1606             for (y = 0; y < params->h; y++) {
1607                 for (x = 0; x < params->w; x++) {
1608                     int idx = INDEX(params, x, y);
1609                     if (index(params, grid, x, y) == idx) {
1610                         struct rect r = find_rect(params, grid, x, y);
1611                         int j, k, m;
1612
1613                         nd[i].area = r.w * r.h;
1614                         nd[i].npoints = nd[i].area;
1615                         nd[i].points = snewn(nd[i].npoints, struct point);
1616                         m = 0;
1617                         for (j = 0; j < r.h; j++)
1618                             for (k = 0; k < r.w; k++) {
1619                                 nd[i].points[m].x = k + r.x;
1620                                 nd[i].points[m].y = j + r.y;
1621                                 m++;
1622                             }
1623                         assert(m == nd[i].npoints);
1624
1625                         i++;
1626                     }
1627                 }
1628             }
1629
1630             if (params->unique)
1631                 ret = rect_solver(params->w, params->h, nnumbers, nd,
1632                                   NULL, NULL, rs);
1633             else
1634                 ret = TRUE;            /* allow any number placement at all */
1635
1636             if (ret) {
1637                 /*
1638                  * Now place the numbers according to the solver's
1639                  * recommendations.
1640                  */
1641                 numbers = snewn(params->w * params->h, int);
1642
1643                 for (y = 0; y < params->h; y++)
1644                     for (x = 0; x < params->w; x++) {
1645                         index(params, numbers, x, y) = 0;
1646                     }
1647
1648                 for (i = 0; i < nnumbers; i++) {
1649                     int idx = random_upto(rs, nd[i].npoints);
1650                     int x = nd[i].points[idx].x;
1651                     int y = nd[i].points[idx].y;
1652                     index(params,numbers,x,y) = nd[i].area;
1653                 }
1654             }
1655
1656             /*
1657              * Clean up.
1658              */
1659             for (i = 0; i < nnumbers; i++)
1660                 sfree(nd[i].points);
1661             sfree(nd);
1662
1663             /*
1664              * If we've succeeded, then terminate the loop.
1665              */
1666             if (ret)
1667                 break;
1668         }
1669
1670         /*
1671          * Give up and go round again.
1672          */
1673         sfree(grid);
1674     }
1675
1676     /*
1677      * Store the solution in aux.
1678      */
1679     {
1680         char *ai;
1681         int len;
1682
1683         len = 2 + (params->w-1)*params->h + (params->h-1)*params->w;
1684         ai = snewn(len, char);
1685
1686         ai[0] = 'S';
1687
1688         p = ai+1;
1689
1690         for (y = 0; y < params->h; y++)
1691             for (x = 1; x < params->w; x++)
1692                 *p++ = (index(params, grid, x, y) !=
1693                         index(params, grid, x-1, y) ? '1' : '0');
1694
1695         for (y = 1; y < params->h; y++)
1696             for (x = 0; x < params->w; x++)
1697                 *p++ = (index(params, grid, x, y) !=
1698                         index(params, grid, x, y-1) ? '1' : '0');
1699
1700         assert(p - ai == len-1);
1701         *p = '\0';
1702
1703         *aux = ai;
1704     }
1705
1706 #ifdef GENERATION_DIAGNOSTICS
1707     display_grid(params, grid, numbers, FALSE);
1708 #endif
1709
1710     desc = snewn(11 * params->w * params->h, char);
1711     p = desc;
1712     run = 0;
1713     for (i = 0; i <= params->w * params->h; i++) {
1714         int n = (i < params->w * params->h ? numbers[i] : -1);
1715
1716         if (!n)
1717             run++;
1718         else {
1719             if (run) {
1720                 while (run > 0) {
1721                     int c = 'a' - 1 + run;
1722                     if (run > 26)
1723                         c = 'z';
1724                     *p++ = c;
1725                     run -= c - ('a' - 1);
1726                 }
1727             } else {
1728                 /*
1729                  * If there's a number in the very top left or
1730                  * bottom right, there's no point putting an
1731                  * unnecessary _ before or after it.
1732                  */
1733                 if (p > desc && n > 0)
1734                     *p++ = '_';
1735             }
1736             if (n > 0)
1737                 p += sprintf(p, "%d", n);
1738             run = 0;
1739         }
1740     }
1741     *p = '\0';
1742
1743     sfree(grid);
1744     sfree(numbers);
1745
1746     return desc;
1747 }
1748
1749 static char *validate_desc(game_params *params, char *desc)
1750 {
1751     int area = params->w * params->h;
1752     int squares = 0;
1753
1754     while (*desc) {
1755         int n = *desc++;
1756         if (n >= 'a' && n <= 'z') {
1757             squares += n - 'a' + 1;
1758         } else if (n == '_') {
1759             /* do nothing */;
1760         } else if (n > '0' && n <= '9') {
1761             squares++;
1762             while (*desc >= '0' && *desc <= '9')
1763                 desc++;
1764         } else
1765             return "Invalid character in game description";
1766     }
1767
1768     if (squares < area)
1769         return "Not enough data to fill grid";
1770
1771     if (squares > area)
1772         return "Too much data to fit in grid";
1773
1774     return NULL;
1775 }
1776
1777 static unsigned char *get_correct(game_state *state)
1778 {
1779     unsigned char *ret;
1780     int x, y;
1781
1782     ret = snewn(state->w * state->h, unsigned char);
1783     memset(ret, 0xFF, state->w * state->h);
1784
1785     for (x = 0; x < state->w; x++)
1786         for (y = 0; y < state->h; y++)
1787             if (index(state,ret,x,y) == 0xFF) {
1788                 int rw, rh;
1789                 int xx, yy;
1790                 int num, area, valid;
1791
1792                 /*
1793                  * Find a rectangle starting at this point.
1794                  */
1795                 rw = 1;
1796                 while (x+rw < state->w && !vedge(state,x+rw,y))
1797                     rw++;
1798                 rh = 1;
1799                 while (y+rh < state->h && !hedge(state,x,y+rh))
1800                     rh++;
1801
1802                 /*
1803                  * We know what the dimensions of the rectangle
1804                  * should be if it's there at all. Find out if we
1805                  * really have a valid rectangle.
1806                  */
1807                 valid = TRUE;
1808                 /* Check the horizontal edges. */
1809                 for (xx = x; xx < x+rw; xx++) {
1810                     for (yy = y; yy <= y+rh; yy++) {
1811                         int e = !HRANGE(state,xx,yy) || hedge(state,xx,yy);
1812                         int ec = (yy == y || yy == y+rh);
1813                         if (e != ec)
1814                             valid = FALSE;
1815                     }
1816                 }
1817                 /* Check the vertical edges. */
1818                 for (yy = y; yy < y+rh; yy++) {
1819                     for (xx = x; xx <= x+rw; xx++) {
1820                         int e = !VRANGE(state,xx,yy) || vedge(state,xx,yy);
1821                         int ec = (xx == x || xx == x+rw);
1822                         if (e != ec)
1823                             valid = FALSE;
1824                     }
1825                 }
1826
1827                 /*
1828                  * If this is not a valid rectangle with no other
1829                  * edges inside it, we just mark this square as not
1830                  * complete and proceed to the next square.
1831                  */
1832                 if (!valid) {
1833                     index(state, ret, x, y) = 0;
1834                     continue;
1835                 }
1836
1837                 /*
1838                  * We have a rectangle. Now see what its area is,
1839                  * and how many numbers are in it.
1840                  */
1841                 num = 0;
1842                 area = 0;
1843                 for (xx = x; xx < x+rw; xx++) {
1844                     for (yy = y; yy < y+rh; yy++) {
1845                         area++;
1846                         if (grid(state,xx,yy)) {
1847                             if (num > 0)
1848                                 valid = FALSE;   /* two numbers */
1849                             num = grid(state,xx,yy);
1850                         }
1851                     }
1852                 }
1853                 if (num != area)
1854                     valid = FALSE;
1855
1856                 /*
1857                  * Now fill in the whole rectangle based on the
1858                  * value of `valid'.
1859                  */
1860                 for (xx = x; xx < x+rw; xx++) {
1861                     for (yy = y; yy < y+rh; yy++) {
1862                         index(state, ret, xx, yy) = valid;
1863                     }
1864                 }
1865             }
1866
1867     return ret;
1868 }
1869
1870 static game_state *new_game(midend_data *me, game_params *params, char *desc)
1871 {
1872     game_state *state = snew(game_state);
1873     int x, y, i, area;
1874
1875     state->w = params->w;
1876     state->h = params->h;
1877
1878     area = state->w * state->h;
1879
1880     state->grid = snewn(area, int);
1881     state->vedge = snewn(area, unsigned char);
1882     state->hedge = snewn(area, unsigned char);
1883     state->completed = state->cheated = FALSE;
1884
1885     i = 0;
1886     while (*desc) {
1887         int n = *desc++;
1888         if (n >= 'a' && n <= 'z') {
1889             int run = n - 'a' + 1;
1890             assert(i + run <= area);
1891             while (run-- > 0)
1892                 state->grid[i++] = 0;
1893         } else if (n == '_') {
1894             /* do nothing */;
1895         } else if (n > '0' && n <= '9') {
1896             assert(i < area);
1897             state->grid[i++] = atoi(desc-1);
1898             while (*desc >= '0' && *desc <= '9')
1899                 desc++;
1900         } else {
1901             assert(!"We can't get here");
1902         }
1903     }
1904     assert(i == area);
1905
1906     for (y = 0; y < state->h; y++)
1907         for (x = 0; x < state->w; x++)
1908             vedge(state,x,y) = hedge(state,x,y) = 0;
1909
1910     state->correct = get_correct(state);
1911
1912     return state;
1913 }
1914
1915 static game_state *dup_game(game_state *state)
1916 {
1917     game_state *ret = snew(game_state);
1918
1919     ret->w = state->w;
1920     ret->h = state->h;
1921
1922     ret->vedge = snewn(state->w * state->h, unsigned char);
1923     ret->hedge = snewn(state->w * state->h, unsigned char);
1924     ret->grid = snewn(state->w * state->h, int);
1925     ret->correct = snewn(ret->w * ret->h, unsigned char);
1926
1927     ret->completed = state->completed;
1928     ret->cheated = state->cheated;
1929
1930     memcpy(ret->grid, state->grid, state->w * state->h * sizeof(int));
1931     memcpy(ret->vedge, state->vedge, state->w*state->h*sizeof(unsigned char));
1932     memcpy(ret->hedge, state->hedge, state->w*state->h*sizeof(unsigned char));
1933
1934     memcpy(ret->correct, state->correct, state->w*state->h*sizeof(unsigned char));
1935
1936     return ret;
1937 }
1938
1939 static void free_game(game_state *state)
1940 {
1941     sfree(state->grid);
1942     sfree(state->vedge);
1943     sfree(state->hedge);
1944     sfree(state->correct);
1945     sfree(state);
1946 }
1947
1948 static char *solve_game(game_state *state, game_state *currstate,
1949                         char *ai, char **error)
1950 {
1951     unsigned char *vedge, *hedge;
1952     int x, y, len;
1953     char *ret, *p;
1954     int i, j, n;
1955     struct numberdata *nd;
1956
1957     if (ai)
1958         return dupstr(ai);
1959
1960     /*
1961      * Attempt the in-built solver.
1962      */
1963
1964     /* Set up each number's (very short) candidate position list. */
1965     for (i = n = 0; i < state->h * state->w; i++)
1966         if (state->grid[i])
1967             n++;
1968
1969     nd = snewn(n, struct numberdata);
1970
1971     for (i = j = 0; i < state->h * state->w; i++)
1972         if (state->grid[i]) {
1973             nd[j].area = state->grid[i];
1974             nd[j].npoints = 1;
1975             nd[j].points = snewn(1, struct point);
1976             nd[j].points[0].x = i % state->w;
1977             nd[j].points[0].y = i / state->w;
1978             j++;
1979         }
1980
1981     assert(j == n);
1982
1983     vedge = snewn(state->w * state->h, unsigned char);
1984     hedge = snewn(state->w * state->h, unsigned char);
1985     memset(vedge, 0, state->w * state->h);
1986     memset(hedge, 0, state->w * state->h);
1987
1988     rect_solver(state->w, state->h, n, nd, hedge, vedge, NULL);
1989
1990     /*
1991      * Clean up.
1992      */
1993     for (i = 0; i < n; i++)
1994         sfree(nd[i].points);
1995     sfree(nd);
1996
1997     len = 2 + (state->w-1)*state->h + (state->h-1)*state->w;
1998     ret = snewn(len, char);
1999
2000     p = ret;
2001     *p++ = 'S';
2002     for (y = 0; y < state->h; y++)
2003         for (x = 1; x < state->w; x++)
2004             *p++ = vedge[y*state->w+x] ? '1' : '0';
2005     for (y = 1; y < state->h; y++)
2006         for (x = 0; x < state->w; x++)
2007             *p++ = hedge[y*state->w+x] ? '1' : '0';
2008     *p++ = '\0';
2009     assert(p - ret == len);
2010
2011     sfree(vedge);
2012     sfree(hedge);
2013
2014     return ret;
2015 }
2016
2017 static char *game_text_format(game_state *state)
2018 {
2019     char *ret, *p, buf[80];
2020     int i, x, y, col, maxlen;
2021
2022     /*
2023      * First determine the number of spaces required to display a
2024      * number. We'll use at least two, because one looks a bit
2025      * silly.
2026      */
2027     col = 2;
2028     for (i = 0; i < state->w * state->h; i++) {
2029         x = sprintf(buf, "%d", state->grid[i]);
2030         if (col < x) col = x;
2031     }
2032
2033     /*
2034      * Now we know the exact total size of the grid we're going to
2035      * produce: it's got 2*h+1 rows, each containing w lots of col,
2036      * w+1 boundary characters and a trailing newline.
2037      */
2038     maxlen = (2*state->h+1) * (state->w * (col+1) + 2);
2039
2040     ret = snewn(maxlen+1, char);
2041     p = ret;
2042
2043     for (y = 0; y <= 2*state->h; y++) {
2044         for (x = 0; x <= 2*state->w; x++) {
2045             if (x & y & 1) {
2046                 /*
2047                  * Display a number.
2048                  */
2049                 int v = grid(state, x/2, y/2);
2050                 if (v)
2051                     sprintf(buf, "%*d", col, v);
2052                 else
2053                     sprintf(buf, "%*s", col, "");
2054                 memcpy(p, buf, col);
2055                 p += col;
2056             } else if (x & 1) {
2057                 /*
2058                  * Display a horizontal edge or nothing.
2059                  */
2060                 int h = (y==0 || y==2*state->h ? 1 :
2061                          HRANGE(state, x/2, y/2) && hedge(state, x/2, y/2));
2062                 int i;
2063                 if (h)
2064                     h = '-';
2065                 else
2066                     h = ' ';
2067                 for (i = 0; i < col; i++)
2068                     *p++ = h;
2069             } else if (y & 1) {
2070                 /*
2071                  * Display a vertical edge or nothing.
2072                  */
2073                 int v = (x==0 || x==2*state->w ? 1 :
2074                          VRANGE(state, x/2, y/2) && vedge(state, x/2, y/2));
2075                 if (v)
2076                     *p++ = '|';
2077                 else
2078                     *p++ = ' ';
2079             } else {
2080                 /*
2081                  * Display a corner, or a vertical edge, or a
2082                  * horizontal edge, or nothing.
2083                  */
2084                 int hl = (y==0 || y==2*state->h ? 1 :
2085                           HRANGE(state, (x-1)/2, y/2) && hedge(state, (x-1)/2, y/2));
2086                 int hr = (y==0 || y==2*state->h ? 1 :
2087                           HRANGE(state, (x+1)/2, y/2) && hedge(state, (x+1)/2, y/2));
2088                 int vu = (x==0 || x==2*state->w ? 1 :
2089                           VRANGE(state, x/2, (y-1)/2) && vedge(state, x/2, (y-1)/2));
2090                 int vd = (x==0 || x==2*state->w ? 1 :
2091                           VRANGE(state, x/2, (y+1)/2) && vedge(state, x/2, (y+1)/2));
2092                 if (!hl && !hr && !vu && !vd)
2093                     *p++ = ' ';
2094                 else if (hl && hr && !vu && !vd)
2095                     *p++ = '-';
2096                 else if (!hl && !hr && vu && vd)
2097                     *p++ = '|';
2098                 else
2099                     *p++ = '+';
2100             }
2101         }
2102         *p++ = '\n';
2103     }
2104
2105     assert(p - ret == maxlen);
2106     *p = '\0';
2107     return ret;
2108 }
2109
2110 struct game_ui {
2111     /*
2112      * These coordinates are 2 times the obvious grid coordinates.
2113      * Hence, the top left of the grid is (0,0), the grid point to
2114      * the right of that is (2,0), the one _below that_ is (2,2)
2115      * and so on. This is so that we can specify a drag start point
2116      * on an edge (one odd coordinate) or in the middle of a square
2117      * (two odd coordinates) rather than always at a corner.
2118      *
2119      * -1,-1 means no drag is in progress.
2120      */
2121     int drag_start_x;
2122     int drag_start_y;
2123     int drag_end_x;
2124     int drag_end_y;
2125     /*
2126      * This flag is set as soon as a dragging action moves the
2127      * mouse pointer away from its starting point, so that even if
2128      * the pointer _returns_ to its starting point the action is
2129      * treated as a small drag rather than a click.
2130      */
2131     int dragged;
2132     /*
2133      * These are the co-ordinates of the top-left and bottom-right squares
2134      * in the drag box, respectively, or -1 otherwise.
2135      */
2136     int x1;
2137     int y1;
2138     int x2;
2139     int y2;
2140 };
2141
2142 static game_ui *new_ui(game_state *state)
2143 {
2144     game_ui *ui = snew(game_ui);
2145     ui->drag_start_x = -1;
2146     ui->drag_start_y = -1;
2147     ui->drag_end_x = -1;
2148     ui->drag_end_y = -1;
2149     ui->dragged = FALSE;
2150     ui->x1 = -1;
2151     ui->y1 = -1;
2152     ui->x2 = -1;
2153     ui->y2 = -1;
2154     return ui;
2155 }
2156
2157 static void free_ui(game_ui *ui)
2158 {
2159     sfree(ui);
2160 }
2161
2162 static char *encode_ui(game_ui *ui)
2163 {
2164     return NULL;
2165 }
2166
2167 static void decode_ui(game_ui *ui, char *encoding)
2168 {
2169 }
2170
2171 static void coord_round(float x, float y, int *xr, int *yr)
2172 {
2173     float xs, ys, xv, yv, dx, dy, dist;
2174
2175     /*
2176      * Find the nearest square-centre.
2177      */
2178     xs = (float)floor(x) + 0.5F;
2179     ys = (float)floor(y) + 0.5F;
2180
2181     /*
2182      * And find the nearest grid vertex.
2183      */
2184     xv = (float)floor(x + 0.5F);
2185     yv = (float)floor(y + 0.5F);
2186
2187     /*
2188      * We allocate clicks in parts of the grid square to either
2189      * corners, edges or square centres, as follows:
2190      *
2191      *   +--+--------+--+
2192      *   |  |        |  |
2193      *   +--+        +--+
2194      *   |   `.    ,'   |
2195      *   |     +--+     |
2196      *   |     |  |     |
2197      *   |     +--+     |
2198      *   |   ,'    `.   |
2199      *   +--+        +--+
2200      *   |  |        |  |
2201      *   +--+--------+--+
2202      *
2203      * (Not to scale!)
2204      *
2205      * In other words: we measure the square distance (i.e.
2206      * max(dx,dy)) from the click to the nearest corner, and if
2207      * it's within CORNER_TOLERANCE then we return a corner click.
2208      * We measure the square distance from the click to the nearest
2209      * centre, and if that's within CENTRE_TOLERANCE we return a
2210      * centre click. Failing that, we find which of the two edge
2211      * centres is nearer to the click and return that edge.
2212      */
2213
2214     /*
2215      * Check for corner click.
2216      */
2217     dx = (float)fabs(x - xv);
2218     dy = (float)fabs(y - yv);
2219     dist = (dx > dy ? dx : dy);
2220     if (dist < CORNER_TOLERANCE) {
2221         *xr = 2 * (int)xv;
2222         *yr = 2 * (int)yv;
2223     } else {
2224         /*
2225          * Check for centre click.
2226          */
2227         dx = (float)fabs(x - xs);
2228         dy = (float)fabs(y - ys);
2229         dist = (dx > dy ? dx : dy);
2230         if (dist < CENTRE_TOLERANCE) {
2231             *xr = 1 + 2 * (int)xs;
2232             *yr = 1 + 2 * (int)ys;
2233         } else {
2234             /*
2235              * Failing both of those, see which edge we're closer to.
2236              * Conveniently, this is simply done by testing the relative
2237              * magnitude of dx and dy (which are currently distances from
2238              * the square centre).
2239              */
2240             if (dx > dy) {
2241                 /* Vertical edge: x-coord of corner,
2242                  * y-coord of square centre. */
2243                 *xr = 2 * (int)xv;
2244                 *yr = 1 + 2 * (int)floor(ys);
2245             } else {
2246                 /* Horizontal edge: x-coord of square centre,
2247                  * y-coord of corner. */
2248                 *xr = 1 + 2 * (int)floor(xs);
2249                 *yr = 2 * (int)yv;
2250             }
2251         }
2252     }
2253 }
2254
2255 /*
2256  * Returns TRUE if it has made any change to the grid.
2257  */
2258 static int grid_draw_rect(game_state *state,
2259                           unsigned char *hedge, unsigned char *vedge,
2260                           int c, int really,
2261                           int x1, int y1, int x2, int y2)
2262 {
2263     int x, y;
2264     int changed = FALSE;
2265
2266     /*
2267      * Draw horizontal edges of rectangles.
2268      */
2269     for (x = x1; x < x2; x++)
2270         for (y = y1; y <= y2; y++)
2271             if (HRANGE(state,x,y)) {
2272                 int val = index(state,hedge,x,y);
2273                 if (y == y1 || y == y2)
2274                     val = c;
2275                 else if (c == 1)
2276                     val = 0;
2277                 changed = changed || (index(state,hedge,x,y) != val);
2278                 if (really)
2279                     index(state,hedge,x,y) = val;
2280             }
2281
2282     /*
2283      * Draw vertical edges of rectangles.
2284      */
2285     for (y = y1; y < y2; y++)
2286         for (x = x1; x <= x2; x++)
2287             if (VRANGE(state,x,y)) {
2288                 int val = index(state,vedge,x,y);
2289                 if (x == x1 || x == x2)
2290                     val = c;
2291                 else if (c == 1)
2292                     val = 0;
2293                 changed = changed || (index(state,vedge,x,y) != val);
2294                 if (really)
2295                     index(state,vedge,x,y) = val;
2296             }
2297
2298     return changed;
2299 }
2300
2301 static int ui_draw_rect(game_state *state, game_ui *ui,
2302                         unsigned char *hedge, unsigned char *vedge, int c,
2303                         int really)
2304 {
2305     return grid_draw_rect(state, hedge, vedge, c, really,
2306                           ui->x1, ui->y1, ui->x2, ui->y2);
2307 }
2308
2309 static void game_changed_state(game_ui *ui, game_state *oldstate,
2310                                game_state *newstate)
2311 {
2312 }
2313
2314 struct game_drawstate {
2315     int started;
2316     int w, h, tilesize;
2317     unsigned long *visible;
2318 };
2319
2320 static char *interpret_move(game_state *from, game_ui *ui, game_drawstate *ds,
2321                             int x, int y, int button)
2322 {
2323     int xc, yc;
2324     int startdrag = FALSE, enddrag = FALSE, active = FALSE;
2325     char buf[80], *ret;
2326
2327     button &= ~MOD_MASK;
2328
2329     if (button == LEFT_BUTTON) {
2330         startdrag = TRUE;
2331     } else if (button == LEFT_RELEASE) {
2332         enddrag = TRUE;
2333     } else if (button != LEFT_DRAG) {
2334         return NULL;
2335     }
2336
2337     coord_round(FROMCOORD((float)x), FROMCOORD((float)y), &xc, &yc);
2338
2339     if (startdrag &&
2340         xc >= 0 && xc <= 2*from->w &&
2341         yc >= 0 && yc <= 2*from->h) {
2342
2343         ui->drag_start_x = xc;
2344         ui->drag_start_y = yc;
2345         ui->drag_end_x = xc;
2346         ui->drag_end_y = yc;
2347         ui->dragged = FALSE;
2348         active = TRUE;
2349     }
2350
2351     if (ui->drag_start_x >= 0 &&
2352         (xc != ui->drag_end_x || yc != ui->drag_end_y)) {
2353         int t;
2354
2355         ui->drag_end_x = xc;
2356         ui->drag_end_y = yc;
2357         ui->dragged = TRUE;
2358         active = TRUE;
2359
2360         if (xc >= 0 && xc <= 2*from->w &&
2361             yc >= 0 && yc <= 2*from->h) {
2362             ui->x1 = ui->drag_start_x;
2363             ui->x2 = ui->drag_end_x;
2364             if (ui->x2 < ui->x1) { t = ui->x1; ui->x1 = ui->x2; ui->x2 = t; }
2365
2366             ui->y1 = ui->drag_start_y;
2367             ui->y2 = ui->drag_end_y;
2368             if (ui->y2 < ui->y1) { t = ui->y1; ui->y1 = ui->y2; ui->y2 = t; }
2369
2370             ui->x1 = ui->x1 / 2;               /* rounds down */
2371             ui->x2 = (ui->x2+1) / 2;           /* rounds up */
2372             ui->y1 = ui->y1 / 2;               /* rounds down */
2373             ui->y2 = (ui->y2+1) / 2;           /* rounds up */
2374         } else {
2375             ui->x1 = -1;
2376             ui->y1 = -1;
2377             ui->x2 = -1;
2378             ui->y2 = -1;
2379         }
2380     }
2381
2382     ret = NULL;
2383
2384     if (enddrag && (ui->drag_start_x >= 0)) {
2385         if (xc >= 0 && xc <= 2*from->w &&
2386             yc >= 0 && yc <= 2*from->h) {
2387
2388             if (ui->dragged) {
2389                 if (ui_draw_rect(from, ui, from->hedge,
2390                                  from->vedge, 1, FALSE)) {
2391                     sprintf(buf, "R%d,%d,%d,%d",
2392                             ui->x1, ui->y1, ui->x2 - ui->x1, ui->y2 - ui->y1);
2393                     ret = dupstr(buf);
2394                 }
2395             } else {
2396                 if ((xc & 1) && !(yc & 1) && HRANGE(from,xc/2,yc/2)) {
2397                     sprintf(buf, "H%d,%d", xc/2, yc/2);
2398                     ret = dupstr(buf);
2399                 }
2400                 if ((yc & 1) && !(xc & 1) && VRANGE(from,xc/2,yc/2)) {
2401                     sprintf(buf, "V%d,%d", xc/2, yc/2);
2402                     ret = dupstr(buf);
2403                 }
2404             }
2405         }
2406
2407         ui->drag_start_x = -1;
2408         ui->drag_start_y = -1;
2409         ui->drag_end_x = -1;
2410         ui->drag_end_y = -1;
2411         ui->x1 = -1;
2412         ui->y1 = -1;
2413         ui->x2 = -1;
2414         ui->y2 = -1;
2415         ui->dragged = FALSE;
2416         active = TRUE;
2417     }
2418
2419     if (ret)
2420         return ret;                    /* a move has been made */
2421     else if (active)
2422         return "";                     /* UI activity has occurred */
2423     else
2424         return NULL;
2425 }
2426
2427 static game_state *execute_move(game_state *from, char *move)
2428 {
2429     game_state *ret;
2430     int x1, y1, x2, y2, mode;
2431
2432     if (move[0] == 'S') {
2433         char *p = move+1;
2434         int x, y;
2435
2436         ret = dup_game(from);
2437         ret->cheated = TRUE;
2438
2439         for (y = 0; y < ret->h; y++)
2440             for (x = 1; x < ret->w; x++) {
2441                 vedge(ret, x, y) = (*p == '1');
2442                 if (*p) p++;
2443             }
2444         for (y = 1; y < ret->h; y++)
2445             for (x = 0; x < ret->w; x++) {
2446                 hedge(ret, x, y) = (*p == '1');
2447                 if (*p) p++;
2448             }
2449
2450         sfree(ret->correct);
2451         ret->correct = get_correct(ret);
2452
2453         return ret;
2454
2455     } else if (move[0] == 'R' &&
2456         sscanf(move+1, "%d,%d,%d,%d", &x1, &y1, &x2, &y2) == 4 &&
2457         x1 >= 0 && x2 >= 0 && x1+x2 <= from->w &&
2458         y1 >= 0 && y2 >= 0 && y1+y2 <= from->h) {
2459         x2 += x1;
2460         y2 += y1;
2461         mode = move[0];
2462     } else if ((move[0] == 'H' || move[0] == 'V') &&
2463                sscanf(move+1, "%d,%d", &x1, &y1) == 2 &&
2464                (move[0] == 'H' ? HRANGE(from, x1, y1) :
2465                 VRANGE(from, x1, y1))) {
2466         mode = move[0];
2467     } else
2468         return NULL;                   /* can't parse move string */
2469
2470     ret = dup_game(from);
2471
2472     if (mode == 'R') {
2473         grid_draw_rect(ret, ret->hedge, ret->vedge, 1, TRUE, x1, y1, x2, y2);
2474     } else if (mode == 'H') {
2475         hedge(ret,x1,y1) = !hedge(ret,x1,y1);
2476     } else if (mode == 'V') {
2477         vedge(ret,x1,y1) = !vedge(ret,x1,y1);
2478     }
2479
2480     /*
2481      * We've made a real change to the grid. Check to see
2482      * if the game has been completed.
2483      */
2484     if (!ret->completed) {
2485         int x, y, ok;
2486
2487         ok = TRUE;
2488         for (x = 0; x < ret->w; x++)
2489             for (y = 0; y < ret->h; y++)
2490                 if (!index(ret, ret->correct, x, y))
2491                     ok = FALSE;
2492
2493         if (ok)
2494             ret->completed = TRUE;
2495     }
2496
2497     sfree(ret->correct);
2498     ret->correct = get_correct(ret);
2499
2500     return ret;
2501 }
2502
2503 /* ----------------------------------------------------------------------
2504  * Drawing routines.
2505  */
2506
2507 #define CORRECT (1L<<16)
2508
2509 #define COLOUR(k) ( (k)==1 ? COL_LINE : COL_DRAG )
2510 #define MAX4(x,y,z,w) ( max(max(x,y),max(z,w)) )
2511
2512 static void game_compute_size(game_params *params, int tilesize,
2513                               int *x, int *y)
2514 {
2515     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2516     struct { int tilesize; } ads, *ds = &ads;
2517     ads.tilesize = tilesize;
2518
2519     *x = params->w * TILE_SIZE + 2*BORDER + 1;
2520     *y = params->h * TILE_SIZE + 2*BORDER + 1;
2521 }
2522
2523 static void game_set_size(game_drawstate *ds, game_params *params,
2524                           int tilesize)
2525 {
2526     ds->tilesize = tilesize;
2527 }
2528
2529 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
2530 {
2531     float *ret = snewn(3 * NCOLOURS, float);
2532
2533     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2534
2535     ret[COL_GRID * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
2536     ret[COL_GRID * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
2537     ret[COL_GRID * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
2538
2539     ret[COL_DRAG * 3 + 0] = 1.0F;
2540     ret[COL_DRAG * 3 + 1] = 0.0F;
2541     ret[COL_DRAG * 3 + 2] = 0.0F;
2542
2543     ret[COL_CORRECT * 3 + 0] = 0.75F * ret[COL_BACKGROUND * 3 + 0];
2544     ret[COL_CORRECT * 3 + 1] = 0.75F * ret[COL_BACKGROUND * 3 + 1];
2545     ret[COL_CORRECT * 3 + 2] = 0.75F * ret[COL_BACKGROUND * 3 + 2];
2546
2547     ret[COL_LINE * 3 + 0] = 0.0F;
2548     ret[COL_LINE * 3 + 1] = 0.0F;
2549     ret[COL_LINE * 3 + 2] = 0.0F;
2550
2551     ret[COL_TEXT * 3 + 0] = 0.0F;
2552     ret[COL_TEXT * 3 + 1] = 0.0F;
2553     ret[COL_TEXT * 3 + 2] = 0.0F;
2554
2555     *ncolours = NCOLOURS;
2556     return ret;
2557 }
2558
2559 static game_drawstate *game_new_drawstate(game_state *state)
2560 {
2561     struct game_drawstate *ds = snew(struct game_drawstate);
2562     int i;
2563
2564     ds->started = FALSE;
2565     ds->w = state->w;
2566     ds->h = state->h;
2567     ds->visible = snewn(ds->w * ds->h, unsigned long);
2568     ds->tilesize = 0;                  /* not decided yet */
2569     for (i = 0; i < ds->w * ds->h; i++)
2570         ds->visible[i] = 0xFFFF;
2571
2572     return ds;
2573 }
2574
2575 static void game_free_drawstate(game_drawstate *ds)
2576 {
2577     sfree(ds->visible);
2578     sfree(ds);
2579 }
2580
2581 static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state,
2582                       int x, int y, unsigned char *hedge, unsigned char *vedge,
2583                       unsigned char *corners, int correct)
2584 {
2585     int cx = COORD(x), cy = COORD(y);
2586     char str[80];
2587
2588     draw_rect(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1, COL_GRID);
2589     draw_rect(fe, cx+1, cy+1, TILE_SIZE-1, TILE_SIZE-1,
2590               correct ? COL_CORRECT : COL_BACKGROUND);
2591
2592     if (grid(state,x,y)) {
2593         sprintf(str, "%d", grid(state,x,y));
2594         draw_text(fe, cx+TILE_SIZE/2, cy+TILE_SIZE/2, FONT_VARIABLE,
2595                   TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, COL_TEXT, str);
2596     }
2597
2598     /*
2599      * Draw edges.
2600      */
2601     if (!HRANGE(state,x,y) || index(state,hedge,x,y))
2602         draw_rect(fe, cx, cy, TILE_SIZE+1, 2,
2603                   HRANGE(state,x,y) ? COLOUR(index(state,hedge,x,y)) :
2604                   COL_LINE);
2605     if (!HRANGE(state,x,y+1) || index(state,hedge,x,y+1))
2606         draw_rect(fe, cx, cy+TILE_SIZE-1, TILE_SIZE+1, 2,
2607                   HRANGE(state,x,y+1) ? COLOUR(index(state,hedge,x,y+1)) :
2608                   COL_LINE);
2609     if (!VRANGE(state,x,y) || index(state,vedge,x,y))
2610         draw_rect(fe, cx, cy, 2, TILE_SIZE+1,
2611                   VRANGE(state,x,y) ? COLOUR(index(state,vedge,x,y)) :
2612                   COL_LINE);
2613     if (!VRANGE(state,x+1,y) || index(state,vedge,x+1,y))
2614         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, TILE_SIZE+1,
2615                   VRANGE(state,x+1,y) ? COLOUR(index(state,vedge,x+1,y)) :
2616                   COL_LINE);
2617
2618     /*
2619      * Draw corners.
2620      */
2621     if (index(state,corners,x,y))
2622         draw_rect(fe, cx, cy, 2, 2,
2623                   COLOUR(index(state,corners,x,y)));
2624     if (x+1 < state->w && index(state,corners,x+1,y))
2625         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, 2,
2626                   COLOUR(index(state,corners,x+1,y)));
2627     if (y+1 < state->h && index(state,corners,x,y+1))
2628         draw_rect(fe, cx, cy+TILE_SIZE-1, 2, 2,
2629                   COLOUR(index(state,corners,x,y+1)));
2630     if (x+1 < state->w && y+1 < state->h && index(state,corners,x+1,y+1))
2631         draw_rect(fe, cx+TILE_SIZE-1, cy+TILE_SIZE-1, 2, 2,
2632                   COLOUR(index(state,corners,x+1,y+1)));
2633
2634     draw_update(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1);
2635 }
2636
2637 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
2638                  game_state *state, int dir, game_ui *ui,
2639                  float animtime, float flashtime)
2640 {
2641     int x, y;
2642     unsigned char *hedge, *vedge, *corners;
2643
2644     if (ui->dragged) {
2645         hedge = snewn(state->w*state->h, unsigned char);
2646         vedge = snewn(state->w*state->h, unsigned char);
2647         memcpy(hedge, state->hedge, state->w*state->h);
2648         memcpy(vedge, state->vedge, state->w*state->h);
2649         ui_draw_rect(state, ui, hedge, vedge, 2, TRUE);
2650     } else {
2651         hedge = state->hedge;
2652         vedge = state->vedge;
2653     }
2654
2655     corners = snewn(state->w * state->h, unsigned char);
2656     memset(corners, 0, state->w * state->h);
2657     for (x = 0; x < state->w; x++)
2658         for (y = 0; y < state->h; y++) {
2659             if (x > 0) {
2660                 int e = index(state, vedge, x, y);
2661                 if (index(state,corners,x,y) < e)
2662                     index(state,corners,x,y) = e;
2663                 if (y+1 < state->h &&
2664                     index(state,corners,x,y+1) < e)
2665                     index(state,corners,x,y+1) = e;
2666             }
2667             if (y > 0) {
2668                 int e = index(state, hedge, x, y);
2669                 if (index(state,corners,x,y) < e)
2670                     index(state,corners,x,y) = e;
2671                 if (x+1 < state->w &&
2672                     index(state,corners,x+1,y) < e)
2673                     index(state,corners,x+1,y) = e;
2674             }
2675         }
2676
2677     if (!ds->started) {
2678         draw_rect(fe, 0, 0,
2679                   state->w * TILE_SIZE + 2*BORDER + 1,
2680                   state->h * TILE_SIZE + 2*BORDER + 1, COL_BACKGROUND);
2681         draw_rect(fe, COORD(0)-1, COORD(0)-1,
2682                   ds->w*TILE_SIZE+3, ds->h*TILE_SIZE+3, COL_LINE);
2683         ds->started = TRUE;
2684         draw_update(fe, 0, 0,
2685                     state->w * TILE_SIZE + 2*BORDER + 1,
2686                     state->h * TILE_SIZE + 2*BORDER + 1);
2687     }
2688
2689     for (x = 0; x < state->w; x++)
2690         for (y = 0; y < state->h; y++) {
2691             unsigned long c = 0;
2692
2693             if (HRANGE(state,x,y))
2694                 c |= index(state,hedge,x,y);
2695             if (HRANGE(state,x,y+1))
2696                 c |= index(state,hedge,x,y+1) << 2;
2697             if (VRANGE(state,x,y))
2698                 c |= index(state,vedge,x,y) << 4;
2699             if (VRANGE(state,x+1,y))
2700                 c |= index(state,vedge,x+1,y) << 6;
2701             c |= index(state,corners,x,y) << 8;
2702             if (x+1 < state->w)
2703                 c |= index(state,corners,x+1,y) << 10;
2704             if (y+1 < state->h)
2705                 c |= index(state,corners,x,y+1) << 12;
2706             if (x+1 < state->w && y+1 < state->h)
2707                 /* cast to prevent 2<<14 sign-extending on promotion to long */
2708                 c |= (unsigned long)index(state,corners,x+1,y+1) << 14;
2709             if (index(state, state->correct, x, y) && !flashtime)
2710                 c |= CORRECT;
2711
2712             if (index(ds,ds->visible,x,y) != c) {
2713                 draw_tile(fe, ds, state, x, y, hedge, vedge, corners,
2714                           (c & CORRECT) ? 1 : 0);
2715                 index(ds,ds->visible,x,y) = c;
2716             }
2717         }
2718
2719     {
2720         char buf[256];
2721
2722         if (ui->x1 >= 0 && ui->y1 >= 0 &&
2723             ui->x2 >= 0 && ui->y2 >= 0) {
2724             sprintf(buf, "%dx%d ",
2725                     ui->x2-ui->x1,
2726                     ui->y2-ui->y1);
2727         } else {
2728             buf[0] = '\0';
2729         }
2730
2731         if (state->cheated)
2732             strcat(buf, "Auto-solved.");
2733         else if (state->completed)
2734             strcat(buf, "COMPLETED!");
2735
2736         status_bar(fe, buf);
2737     }
2738
2739     if (hedge != state->hedge) {
2740         sfree(hedge);
2741         sfree(vedge);
2742     }
2743
2744     sfree(corners);
2745 }
2746
2747 static float game_anim_length(game_state *oldstate,
2748                               game_state *newstate, int dir, game_ui *ui)
2749 {
2750     return 0.0F;
2751 }
2752
2753 static float game_flash_length(game_state *oldstate,
2754                                game_state *newstate, int dir, game_ui *ui)
2755 {
2756     if (!oldstate->completed && newstate->completed &&
2757         !oldstate->cheated && !newstate->cheated)
2758         return FLASH_TIME;
2759     return 0.0F;
2760 }
2761
2762 static int game_wants_statusbar(void)
2763 {
2764     return TRUE;
2765 }
2766
2767 static int game_timing_state(game_state *state, game_ui *ui)
2768 {
2769     return TRUE;
2770 }
2771
2772 #ifdef COMBINED
2773 #define thegame rect
2774 #endif
2775
2776 const struct game thegame = {
2777     "Rectangles", "games.rectangles",
2778     default_params,
2779     game_fetch_preset,
2780     decode_params,
2781     encode_params,
2782     free_params,
2783     dup_params,
2784     TRUE, game_configure, custom_params,
2785     validate_params,
2786     new_game_desc,
2787     validate_desc,
2788     new_game,
2789     dup_game,
2790     free_game,
2791     TRUE, solve_game,
2792     TRUE, game_text_format,
2793     new_ui,
2794     free_ui,
2795     encode_ui,
2796     decode_ui,
2797     game_changed_state,
2798     interpret_move,
2799     execute_move,
2800     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2801     game_colours,
2802     game_new_drawstate,
2803     game_free_drawstate,
2804     game_redraw,
2805     game_anim_length,
2806     game_flash_length,
2807     game_wants_statusbar,
2808     FALSE, game_timing_state,
2809     0,                                 /* mouse_priorities */
2810 };