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                           default:     /* should never happen */
1352                             assert(!"invalid direction");
1353                         }
1354                         if (r1.h > 0 && r1.w > 0)
1355                             place_rect(params2, grid, r1);
1356                         place_rect(params2, grid, r2);
1357                     } else {
1358 #ifndef NDEBUG
1359                         /*
1360                          * Sanity-check that there really is a 3x3
1361                          * rectangle surrounding this singleton and it
1362                          * contains absolutely everything we could
1363                          * possibly need.
1364                          */
1365                         {
1366                             int xx, yy;
1367                             assert(x > 0 && x < params2->w-1);
1368                             assert(y > 0 && y < params2->h-1);
1369
1370                             for (xx = x-1; xx <= x+1; xx++)
1371                                 for (yy = y-1; yy <= y+1; yy++) {
1372                                     struct rect r = find_rect(params2,grid,xx,yy);
1373                                     assert(r.x >= x-1);
1374                                     assert(r.y >= y-1);
1375                                     assert(r.x+r.w-1 <= x+1);
1376                                     assert(r.y+r.h-1 <= y+1);
1377                                 }
1378                         }
1379 #endif
1380
1381 #ifdef GENERATION_DIAGNOSTICS
1382                         printf("need the 3x3 trick\n");
1383 #endif
1384
1385                         /*
1386                          * FIXME: If the maximum rectangle area for
1387                          * this grid is less than 9, we ought to
1388                          * subdivide the 3x3 in some fashion. There are
1389                          * five other possibilities:
1390                          *
1391                          *  - a 6 and a 3
1392                          *  - a 4, a 3 and a 2
1393                          *  - three 3s
1394                          *  - a 3 and three 2s (two different arrangements).
1395                          */
1396
1397                         {
1398                             struct rect r;
1399                             r.x = x-1;
1400                             r.y = y-1;
1401                             r.w = r.h = 3;
1402                             place_rect(params2, grid, r);
1403                         }
1404                     }
1405                 }
1406             }
1407         }
1408
1409         /*
1410          * We have now constructed a grid of the size specified in
1411          * params2. Now we extend it into a grid of the size specified
1412          * in params. We do this in two passes: we extend it vertically
1413          * until it's the right height, then we transpose it, then
1414          * extend it vertically again (getting it effectively the right
1415          * width), then finally transpose again.
1416          */
1417         for (i = 0; i < 2; i++) {
1418             int *grid2, *expand, *where;
1419             game_params params3real, *params3 = &params3real;
1420
1421 #ifdef GENERATION_DIAGNOSTICS
1422             printf("before expansion:\n");
1423             display_grid(params2, grid, NULL, TRUE);
1424 #endif
1425
1426             /*
1427              * Set up the new grid.
1428              */
1429             grid2 = snewn(params2->w * params->h, int);
1430             expand = snewn(params2->h-1, int);
1431             where = snewn(params2->w, int);
1432             params3->w = params2->w;
1433             params3->h = params->h;
1434
1435             /*
1436              * Decide which horizontal edges are going to get expanded,
1437              * and by how much.
1438              */
1439             for (y = 0; y < params2->h-1; y++)
1440                 expand[y] = 0;
1441             for (y = params2->h; y < params->h; y++) {
1442                 x = random_upto(rs, params2->h-1);
1443                 expand[x]++;
1444             }
1445
1446 #ifdef GENERATION_DIAGNOSTICS
1447             printf("expand[] = {");
1448             for (y = 0; y < params2->h-1; y++)
1449                 printf(" %d", expand[y]);
1450             printf(" }\n");
1451 #endif
1452
1453             /*
1454              * Perform the expansion. The way this works is that we
1455              * alternately:
1456              *
1457              *  - copy a row from grid into grid2
1458              *
1459              *  - invent some number of additional rows in grid2 where
1460              *    there was previously only a horizontal line between
1461              *    rows in grid, and make random decisions about where
1462              *    among these to place each rectangle edge that ran
1463              *    along this line.
1464              */
1465             for (y = y2 = y2last = 0; y < params2->h; y++) {
1466                 /*
1467                  * Copy a single line from row y of grid into row y2 of
1468                  * grid2.
1469                  */
1470                 for (x = 0; x < params2->w; x++) {
1471                     int val = index(params2, grid, x, y);
1472                     if (val / params2->w == y &&   /* rect starts on this line */
1473                         (y2 == 0 ||            /* we're at the very top, or... */
1474                          index(params3, grid2, x, y2-1) / params3->w < y2last
1475                          /* this rect isn't already started */))
1476                         index(params3, grid2, x, y2) =
1477                         INDEX(params3, val % params2->w, y2);
1478                     else
1479                         index(params3, grid2, x, y2) =
1480                         index(params3, grid2, x, y2-1);
1481                 }
1482
1483                 /*
1484                  * If that was the last line, terminate the loop early.
1485                  */
1486                 if (++y2 == params3->h)
1487                     break;
1488
1489                 y2last = y2;
1490
1491                 /*
1492                  * Invent some number of additional lines. First walk
1493                  * along this line working out where to put all the
1494                  * edges that coincide with it.
1495                  */
1496                 yx = -1;
1497                 for (x = 0; x < params2->w; x++) {
1498                     if (index(params2, grid, x, y) !=
1499                         index(params2, grid, x, y+1)) {
1500                         /*
1501                          * This is a horizontal edge, so it needs
1502                          * placing.
1503                          */
1504                         if (x == 0 ||
1505                             (index(params2, grid, x-1, y) !=
1506                              index(params2, grid, x, y) &&
1507                              index(params2, grid, x-1, y+1) !=
1508                              index(params2, grid, x, y+1))) {
1509                             /*
1510                              * Here we have the chance to make a new
1511                              * decision.
1512                              */
1513                             yx = random_upto(rs, expand[y]+1);
1514                         } else {
1515                             /*
1516                              * Here we just reuse the previous value of
1517                              * yx.
1518                              */
1519                         }
1520                     } else
1521                         yx = -1;
1522                     where[x] = yx;
1523                 }
1524
1525                 for (yx = 0; yx < expand[y]; yx++) {
1526                     /*
1527                      * Invent a single row. For each square in the row,
1528                      * we copy the grid entry from the square above it,
1529                      * unless we're starting the new rectangle here.
1530                      */
1531                     for (x = 0; x < params2->w; x++) {
1532                         if (yx == where[x]) {
1533                             int val = index(params2, grid, x, y+1);
1534                             val %= params2->w;
1535                             val = INDEX(params3, val, y2);
1536                             index(params3, grid2, x, y2) = val;
1537                         } else
1538                             index(params3, grid2, x, y2) =
1539                             index(params3, grid2, x, y2-1);
1540                     }
1541
1542                     y2++;
1543                 }
1544             }
1545
1546             sfree(expand);
1547             sfree(where);
1548
1549 #ifdef GENERATION_DIAGNOSTICS
1550             printf("after expansion:\n");
1551             display_grid(params3, grid2, NULL, TRUE);
1552 #endif
1553             /*
1554              * Transpose.
1555              */
1556             params2->w = params3->h;
1557             params2->h = params3->w;
1558             sfree(grid);
1559             grid = snewn(params2->w * params2->h, int);
1560             for (x = 0; x < params2->w; x++)
1561                 for (y = 0; y < params2->h; y++) {
1562                     int idx1 = INDEX(params2, x, y);
1563                     int idx2 = INDEX(params3, y, x);
1564                     int tmp;
1565
1566                     tmp = grid2[idx2];
1567                     tmp = (tmp % params3->w) * params2->w + (tmp / params3->w);
1568                     grid[idx1] = tmp;
1569                 }
1570
1571             sfree(grid2);
1572
1573             {
1574                 int tmp;
1575                 tmp = params->w;
1576                 params->w = params->h;
1577                 params->h = tmp;
1578             }
1579
1580 #ifdef GENERATION_DIAGNOSTICS
1581             printf("after transposition:\n");
1582             display_grid(params2, grid, NULL, TRUE);
1583 #endif
1584         }
1585
1586         /*
1587          * Run the solver to narrow down the possible number
1588          * placements.
1589          */
1590         {
1591             struct numberdata *nd;
1592             int nnumbers, i, ret;
1593
1594             /* Count the rectangles. */
1595             nnumbers = 0;
1596             for (y = 0; y < params->h; y++) {
1597                 for (x = 0; x < params->w; x++) {
1598                     int idx = INDEX(params, x, y);
1599                     if (index(params, grid, x, y) == idx)
1600                         nnumbers++;
1601                 }
1602             }
1603
1604             nd = snewn(nnumbers, struct numberdata);
1605
1606             /* Now set up each number's candidate position list. */
1607             i = 0;
1608             for (y = 0; y < params->h; y++) {
1609                 for (x = 0; x < params->w; x++) {
1610                     int idx = INDEX(params, x, y);
1611                     if (index(params, grid, x, y) == idx) {
1612                         struct rect r = find_rect(params, grid, x, y);
1613                         int j, k, m;
1614
1615                         nd[i].area = r.w * r.h;
1616                         nd[i].npoints = nd[i].area;
1617                         nd[i].points = snewn(nd[i].npoints, struct point);
1618                         m = 0;
1619                         for (j = 0; j < r.h; j++)
1620                             for (k = 0; k < r.w; k++) {
1621                                 nd[i].points[m].x = k + r.x;
1622                                 nd[i].points[m].y = j + r.y;
1623                                 m++;
1624                             }
1625                         assert(m == nd[i].npoints);
1626
1627                         i++;
1628                     }
1629                 }
1630             }
1631
1632             if (params->unique)
1633                 ret = rect_solver(params->w, params->h, nnumbers, nd,
1634                                   NULL, NULL, rs);
1635             else
1636                 ret = TRUE;            /* allow any number placement at all */
1637
1638             if (ret) {
1639                 /*
1640                  * Now place the numbers according to the solver's
1641                  * recommendations.
1642                  */
1643                 numbers = snewn(params->w * params->h, int);
1644
1645                 for (y = 0; y < params->h; y++)
1646                     for (x = 0; x < params->w; x++) {
1647                         index(params, numbers, x, y) = 0;
1648                     }
1649
1650                 for (i = 0; i < nnumbers; i++) {
1651                     int idx = random_upto(rs, nd[i].npoints);
1652                     int x = nd[i].points[idx].x;
1653                     int y = nd[i].points[idx].y;
1654                     index(params,numbers,x,y) = nd[i].area;
1655                 }
1656             }
1657
1658             /*
1659              * Clean up.
1660              */
1661             for (i = 0; i < nnumbers; i++)
1662                 sfree(nd[i].points);
1663             sfree(nd);
1664
1665             /*
1666              * If we've succeeded, then terminate the loop.
1667              */
1668             if (ret)
1669                 break;
1670         }
1671
1672         /*
1673          * Give up and go round again.
1674          */
1675         sfree(grid);
1676     }
1677
1678     /*
1679      * Store the solution in aux.
1680      */
1681     {
1682         char *ai;
1683         int len;
1684
1685         len = 2 + (params->w-1)*params->h + (params->h-1)*params->w;
1686         ai = snewn(len, char);
1687
1688         ai[0] = 'S';
1689
1690         p = ai+1;
1691
1692         for (y = 0; y < params->h; y++)
1693             for (x = 1; x < params->w; x++)
1694                 *p++ = (index(params, grid, x, y) !=
1695                         index(params, grid, x-1, y) ? '1' : '0');
1696
1697         for (y = 1; y < params->h; y++)
1698             for (x = 0; x < params->w; x++)
1699                 *p++ = (index(params, grid, x, y) !=
1700                         index(params, grid, x, y-1) ? '1' : '0');
1701
1702         assert(p - ai == len-1);
1703         *p = '\0';
1704
1705         *aux = ai;
1706     }
1707
1708 #ifdef GENERATION_DIAGNOSTICS
1709     display_grid(params, grid, numbers, FALSE);
1710 #endif
1711
1712     desc = snewn(11 * params->w * params->h, char);
1713     p = desc;
1714     run = 0;
1715     for (i = 0; i <= params->w * params->h; i++) {
1716         int n = (i < params->w * params->h ? numbers[i] : -1);
1717
1718         if (!n)
1719             run++;
1720         else {
1721             if (run) {
1722                 while (run > 0) {
1723                     int c = 'a' - 1 + run;
1724                     if (run > 26)
1725                         c = 'z';
1726                     *p++ = c;
1727                     run -= c - ('a' - 1);
1728                 }
1729             } else {
1730                 /*
1731                  * If there's a number in the very top left or
1732                  * bottom right, there's no point putting an
1733                  * unnecessary _ before or after it.
1734                  */
1735                 if (p > desc && n > 0)
1736                     *p++ = '_';
1737             }
1738             if (n > 0)
1739                 p += sprintf(p, "%d", n);
1740             run = 0;
1741         }
1742     }
1743     *p = '\0';
1744
1745     sfree(grid);
1746     sfree(numbers);
1747
1748     return desc;
1749 }
1750
1751 static char *validate_desc(game_params *params, char *desc)
1752 {
1753     int area = params->w * params->h;
1754     int squares = 0;
1755
1756     while (*desc) {
1757         int n = *desc++;
1758         if (n >= 'a' && n <= 'z') {
1759             squares += n - 'a' + 1;
1760         } else if (n == '_') {
1761             /* do nothing */;
1762         } else if (n > '0' && n <= '9') {
1763             squares++;
1764             while (*desc >= '0' && *desc <= '9')
1765                 desc++;
1766         } else
1767             return "Invalid character in game description";
1768     }
1769
1770     if (squares < area)
1771         return "Not enough data to fill grid";
1772
1773     if (squares > area)
1774         return "Too much data to fit in grid";
1775
1776     return NULL;
1777 }
1778
1779 static unsigned char *get_correct(game_state *state)
1780 {
1781     unsigned char *ret;
1782     int x, y;
1783
1784     ret = snewn(state->w * state->h, unsigned char);
1785     memset(ret, 0xFF, state->w * state->h);
1786
1787     for (x = 0; x < state->w; x++)
1788         for (y = 0; y < state->h; y++)
1789             if (index(state,ret,x,y) == 0xFF) {
1790                 int rw, rh;
1791                 int xx, yy;
1792                 int num, area, valid;
1793
1794                 /*
1795                  * Find a rectangle starting at this point.
1796                  */
1797                 rw = 1;
1798                 while (x+rw < state->w && !vedge(state,x+rw,y))
1799                     rw++;
1800                 rh = 1;
1801                 while (y+rh < state->h && !hedge(state,x,y+rh))
1802                     rh++;
1803
1804                 /*
1805                  * We know what the dimensions of the rectangle
1806                  * should be if it's there at all. Find out if we
1807                  * really have a valid rectangle.
1808                  */
1809                 valid = TRUE;
1810                 /* Check the horizontal edges. */
1811                 for (xx = x; xx < x+rw; xx++) {
1812                     for (yy = y; yy <= y+rh; yy++) {
1813                         int e = !HRANGE(state,xx,yy) || hedge(state,xx,yy);
1814                         int ec = (yy == y || yy == y+rh);
1815                         if (e != ec)
1816                             valid = FALSE;
1817                     }
1818                 }
1819                 /* Check the vertical edges. */
1820                 for (yy = y; yy < y+rh; yy++) {
1821                     for (xx = x; xx <= x+rw; xx++) {
1822                         int e = !VRANGE(state,xx,yy) || vedge(state,xx,yy);
1823                         int ec = (xx == x || xx == x+rw);
1824                         if (e != ec)
1825                             valid = FALSE;
1826                     }
1827                 }
1828
1829                 /*
1830                  * If this is not a valid rectangle with no other
1831                  * edges inside it, we just mark this square as not
1832                  * complete and proceed to the next square.
1833                  */
1834                 if (!valid) {
1835                     index(state, ret, x, y) = 0;
1836                     continue;
1837                 }
1838
1839                 /*
1840                  * We have a rectangle. Now see what its area is,
1841                  * and how many numbers are in it.
1842                  */
1843                 num = 0;
1844                 area = 0;
1845                 for (xx = x; xx < x+rw; xx++) {
1846                     for (yy = y; yy < y+rh; yy++) {
1847                         area++;
1848                         if (grid(state,xx,yy)) {
1849                             if (num > 0)
1850                                 valid = FALSE;   /* two numbers */
1851                             num = grid(state,xx,yy);
1852                         }
1853                     }
1854                 }
1855                 if (num != area)
1856                     valid = FALSE;
1857
1858                 /*
1859                  * Now fill in the whole rectangle based on the
1860                  * value of `valid'.
1861                  */
1862                 for (xx = x; xx < x+rw; xx++) {
1863                     for (yy = y; yy < y+rh; yy++) {
1864                         index(state, ret, xx, yy) = valid;
1865                     }
1866                 }
1867             }
1868
1869     return ret;
1870 }
1871
1872 static game_state *new_game(midend_data *me, game_params *params, char *desc)
1873 {
1874     game_state *state = snew(game_state);
1875     int x, y, i, area;
1876
1877     state->w = params->w;
1878     state->h = params->h;
1879
1880     area = state->w * state->h;
1881
1882     state->grid = snewn(area, int);
1883     state->vedge = snewn(area, unsigned char);
1884     state->hedge = snewn(area, unsigned char);
1885     state->completed = state->cheated = FALSE;
1886
1887     i = 0;
1888     while (*desc) {
1889         int n = *desc++;
1890         if (n >= 'a' && n <= 'z') {
1891             int run = n - 'a' + 1;
1892             assert(i + run <= area);
1893             while (run-- > 0)
1894                 state->grid[i++] = 0;
1895         } else if (n == '_') {
1896             /* do nothing */;
1897         } else if (n > '0' && n <= '9') {
1898             assert(i < area);
1899             state->grid[i++] = atoi(desc-1);
1900             while (*desc >= '0' && *desc <= '9')
1901                 desc++;
1902         } else {
1903             assert(!"We can't get here");
1904         }
1905     }
1906     assert(i == area);
1907
1908     for (y = 0; y < state->h; y++)
1909         for (x = 0; x < state->w; x++)
1910             vedge(state,x,y) = hedge(state,x,y) = 0;
1911
1912     state->correct = get_correct(state);
1913
1914     return state;
1915 }
1916
1917 static game_state *dup_game(game_state *state)
1918 {
1919     game_state *ret = snew(game_state);
1920
1921     ret->w = state->w;
1922     ret->h = state->h;
1923
1924     ret->vedge = snewn(state->w * state->h, unsigned char);
1925     ret->hedge = snewn(state->w * state->h, unsigned char);
1926     ret->grid = snewn(state->w * state->h, int);
1927     ret->correct = snewn(ret->w * ret->h, unsigned char);
1928
1929     ret->completed = state->completed;
1930     ret->cheated = state->cheated;
1931
1932     memcpy(ret->grid, state->grid, state->w * state->h * sizeof(int));
1933     memcpy(ret->vedge, state->vedge, state->w*state->h*sizeof(unsigned char));
1934     memcpy(ret->hedge, state->hedge, state->w*state->h*sizeof(unsigned char));
1935
1936     memcpy(ret->correct, state->correct, state->w*state->h*sizeof(unsigned char));
1937
1938     return ret;
1939 }
1940
1941 static void free_game(game_state *state)
1942 {
1943     sfree(state->grid);
1944     sfree(state->vedge);
1945     sfree(state->hedge);
1946     sfree(state->correct);
1947     sfree(state);
1948 }
1949
1950 static char *solve_game(game_state *state, game_state *currstate,
1951                         char *ai, char **error)
1952 {
1953     unsigned char *vedge, *hedge;
1954     int x, y, len;
1955     char *ret, *p;
1956     int i, j, n;
1957     struct numberdata *nd;
1958
1959     if (ai)
1960         return dupstr(ai);
1961
1962     /*
1963      * Attempt the in-built solver.
1964      */
1965
1966     /* Set up each number's (very short) candidate position list. */
1967     for (i = n = 0; i < state->h * state->w; i++)
1968         if (state->grid[i])
1969             n++;
1970
1971     nd = snewn(n, struct numberdata);
1972
1973     for (i = j = 0; i < state->h * state->w; i++)
1974         if (state->grid[i]) {
1975             nd[j].area = state->grid[i];
1976             nd[j].npoints = 1;
1977             nd[j].points = snewn(1, struct point);
1978             nd[j].points[0].x = i % state->w;
1979             nd[j].points[0].y = i / state->w;
1980             j++;
1981         }
1982
1983     assert(j == n);
1984
1985     vedge = snewn(state->w * state->h, unsigned char);
1986     hedge = snewn(state->w * state->h, unsigned char);
1987     memset(vedge, 0, state->w * state->h);
1988     memset(hedge, 0, state->w * state->h);
1989
1990     rect_solver(state->w, state->h, n, nd, hedge, vedge, NULL);
1991
1992     /*
1993      * Clean up.
1994      */
1995     for (i = 0; i < n; i++)
1996         sfree(nd[i].points);
1997     sfree(nd);
1998
1999     len = 2 + (state->w-1)*state->h + (state->h-1)*state->w;
2000     ret = snewn(len, char);
2001
2002     p = ret;
2003     *p++ = 'S';
2004     for (y = 0; y < state->h; y++)
2005         for (x = 1; x < state->w; x++)
2006             *p++ = vedge[y*state->w+x] ? '1' : '0';
2007     for (y = 1; y < state->h; y++)
2008         for (x = 0; x < state->w; x++)
2009             *p++ = hedge[y*state->w+x] ? '1' : '0';
2010     *p++ = '\0';
2011     assert(p - ret == len);
2012
2013     sfree(vedge);
2014     sfree(hedge);
2015
2016     return ret;
2017 }
2018
2019 static char *game_text_format(game_state *state)
2020 {
2021     char *ret, *p, buf[80];
2022     int i, x, y, col, maxlen;
2023
2024     /*
2025      * First determine the number of spaces required to display a
2026      * number. We'll use at least two, because one looks a bit
2027      * silly.
2028      */
2029     col = 2;
2030     for (i = 0; i < state->w * state->h; i++) {
2031         x = sprintf(buf, "%d", state->grid[i]);
2032         if (col < x) col = x;
2033     }
2034
2035     /*
2036      * Now we know the exact total size of the grid we're going to
2037      * produce: it's got 2*h+1 rows, each containing w lots of col,
2038      * w+1 boundary characters and a trailing newline.
2039      */
2040     maxlen = (2*state->h+1) * (state->w * (col+1) + 2);
2041
2042     ret = snewn(maxlen+1, char);
2043     p = ret;
2044
2045     for (y = 0; y <= 2*state->h; y++) {
2046         for (x = 0; x <= 2*state->w; x++) {
2047             if (x & y & 1) {
2048                 /*
2049                  * Display a number.
2050                  */
2051                 int v = grid(state, x/2, y/2);
2052                 if (v)
2053                     sprintf(buf, "%*d", col, v);
2054                 else
2055                     sprintf(buf, "%*s", col, "");
2056                 memcpy(p, buf, col);
2057                 p += col;
2058             } else if (x & 1) {
2059                 /*
2060                  * Display a horizontal edge or nothing.
2061                  */
2062                 int h = (y==0 || y==2*state->h ? 1 :
2063                          HRANGE(state, x/2, y/2) && hedge(state, x/2, y/2));
2064                 int i;
2065                 if (h)
2066                     h = '-';
2067                 else
2068                     h = ' ';
2069                 for (i = 0; i < col; i++)
2070                     *p++ = h;
2071             } else if (y & 1) {
2072                 /*
2073                  * Display a vertical edge or nothing.
2074                  */
2075                 int v = (x==0 || x==2*state->w ? 1 :
2076                          VRANGE(state, x/2, y/2) && vedge(state, x/2, y/2));
2077                 if (v)
2078                     *p++ = '|';
2079                 else
2080                     *p++ = ' ';
2081             } else {
2082                 /*
2083                  * Display a corner, or a vertical edge, or a
2084                  * horizontal edge, or nothing.
2085                  */
2086                 int hl = (y==0 || y==2*state->h ? 1 :
2087                           HRANGE(state, (x-1)/2, y/2) && hedge(state, (x-1)/2, y/2));
2088                 int hr = (y==0 || y==2*state->h ? 1 :
2089                           HRANGE(state, (x+1)/2, y/2) && hedge(state, (x+1)/2, y/2));
2090                 int vu = (x==0 || x==2*state->w ? 1 :
2091                           VRANGE(state, x/2, (y-1)/2) && vedge(state, x/2, (y-1)/2));
2092                 int vd = (x==0 || x==2*state->w ? 1 :
2093                           VRANGE(state, x/2, (y+1)/2) && vedge(state, x/2, (y+1)/2));
2094                 if (!hl && !hr && !vu && !vd)
2095                     *p++ = ' ';
2096                 else if (hl && hr && !vu && !vd)
2097                     *p++ = '-';
2098                 else if (!hl && !hr && vu && vd)
2099                     *p++ = '|';
2100                 else
2101                     *p++ = '+';
2102             }
2103         }
2104         *p++ = '\n';
2105     }
2106
2107     assert(p - ret == maxlen);
2108     *p = '\0';
2109     return ret;
2110 }
2111
2112 struct game_ui {
2113     /*
2114      * These coordinates are 2 times the obvious grid coordinates.
2115      * Hence, the top left of the grid is (0,0), the grid point to
2116      * the right of that is (2,0), the one _below that_ is (2,2)
2117      * and so on. This is so that we can specify a drag start point
2118      * on an edge (one odd coordinate) or in the middle of a square
2119      * (two odd coordinates) rather than always at a corner.
2120      *
2121      * -1,-1 means no drag is in progress.
2122      */
2123     int drag_start_x;
2124     int drag_start_y;
2125     int drag_end_x;
2126     int drag_end_y;
2127     /*
2128      * This flag is set as soon as a dragging action moves the
2129      * mouse pointer away from its starting point, so that even if
2130      * the pointer _returns_ to its starting point the action is
2131      * treated as a small drag rather than a click.
2132      */
2133     int dragged;
2134     /*
2135      * These are the co-ordinates of the top-left and bottom-right squares
2136      * in the drag box, respectively, or -1 otherwise.
2137      */
2138     int x1;
2139     int y1;
2140     int x2;
2141     int y2;
2142 };
2143
2144 static game_ui *new_ui(game_state *state)
2145 {
2146     game_ui *ui = snew(game_ui);
2147     ui->drag_start_x = -1;
2148     ui->drag_start_y = -1;
2149     ui->drag_end_x = -1;
2150     ui->drag_end_y = -1;
2151     ui->dragged = FALSE;
2152     ui->x1 = -1;
2153     ui->y1 = -1;
2154     ui->x2 = -1;
2155     ui->y2 = -1;
2156     return ui;
2157 }
2158
2159 static void free_ui(game_ui *ui)
2160 {
2161     sfree(ui);
2162 }
2163
2164 static char *encode_ui(game_ui *ui)
2165 {
2166     return NULL;
2167 }
2168
2169 static void decode_ui(game_ui *ui, char *encoding)
2170 {
2171 }
2172
2173 static void coord_round(float x, float y, int *xr, int *yr)
2174 {
2175     float xs, ys, xv, yv, dx, dy, dist;
2176
2177     /*
2178      * Find the nearest square-centre.
2179      */
2180     xs = (float)floor(x) + 0.5F;
2181     ys = (float)floor(y) + 0.5F;
2182
2183     /*
2184      * And find the nearest grid vertex.
2185      */
2186     xv = (float)floor(x + 0.5F);
2187     yv = (float)floor(y + 0.5F);
2188
2189     /*
2190      * We allocate clicks in parts of the grid square to either
2191      * corners, edges or square centres, as follows:
2192      *
2193      *   +--+--------+--+
2194      *   |  |        |  |
2195      *   +--+        +--+
2196      *   |   `.    ,'   |
2197      *   |     +--+     |
2198      *   |     |  |     |
2199      *   |     +--+     |
2200      *   |   ,'    `.   |
2201      *   +--+        +--+
2202      *   |  |        |  |
2203      *   +--+--------+--+
2204      *
2205      * (Not to scale!)
2206      *
2207      * In other words: we measure the square distance (i.e.
2208      * max(dx,dy)) from the click to the nearest corner, and if
2209      * it's within CORNER_TOLERANCE then we return a corner click.
2210      * We measure the square distance from the click to the nearest
2211      * centre, and if that's within CENTRE_TOLERANCE we return a
2212      * centre click. Failing that, we find which of the two edge
2213      * centres is nearer to the click and return that edge.
2214      */
2215
2216     /*
2217      * Check for corner click.
2218      */
2219     dx = (float)fabs(x - xv);
2220     dy = (float)fabs(y - yv);
2221     dist = (dx > dy ? dx : dy);
2222     if (dist < CORNER_TOLERANCE) {
2223         *xr = 2 * (int)xv;
2224         *yr = 2 * (int)yv;
2225     } else {
2226         /*
2227          * Check for centre click.
2228          */
2229         dx = (float)fabs(x - xs);
2230         dy = (float)fabs(y - ys);
2231         dist = (dx > dy ? dx : dy);
2232         if (dist < CENTRE_TOLERANCE) {
2233             *xr = 1 + 2 * (int)xs;
2234             *yr = 1 + 2 * (int)ys;
2235         } else {
2236             /*
2237              * Failing both of those, see which edge we're closer to.
2238              * Conveniently, this is simply done by testing the relative
2239              * magnitude of dx and dy (which are currently distances from
2240              * the square centre).
2241              */
2242             if (dx > dy) {
2243                 /* Vertical edge: x-coord of corner,
2244                  * y-coord of square centre. */
2245                 *xr = 2 * (int)xv;
2246                 *yr = 1 + 2 * (int)floor(ys);
2247             } else {
2248                 /* Horizontal edge: x-coord of square centre,
2249                  * y-coord of corner. */
2250                 *xr = 1 + 2 * (int)floor(xs);
2251                 *yr = 2 * (int)yv;
2252             }
2253         }
2254     }
2255 }
2256
2257 /*
2258  * Returns TRUE if it has made any change to the grid.
2259  */
2260 static int grid_draw_rect(game_state *state,
2261                           unsigned char *hedge, unsigned char *vedge,
2262                           int c, int really,
2263                           int x1, int y1, int x2, int y2)
2264 {
2265     int x, y;
2266     int changed = FALSE;
2267
2268     /*
2269      * Draw horizontal edges of rectangles.
2270      */
2271     for (x = x1; x < x2; x++)
2272         for (y = y1; y <= y2; y++)
2273             if (HRANGE(state,x,y)) {
2274                 int val = index(state,hedge,x,y);
2275                 if (y == y1 || y == y2)
2276                     val = c;
2277                 else if (c == 1)
2278                     val = 0;
2279                 changed = changed || (index(state,hedge,x,y) != val);
2280                 if (really)
2281                     index(state,hedge,x,y) = val;
2282             }
2283
2284     /*
2285      * Draw vertical edges of rectangles.
2286      */
2287     for (y = y1; y < y2; y++)
2288         for (x = x1; x <= x2; x++)
2289             if (VRANGE(state,x,y)) {
2290                 int val = index(state,vedge,x,y);
2291                 if (x == x1 || x == x2)
2292                     val = c;
2293                 else if (c == 1)
2294                     val = 0;
2295                 changed = changed || (index(state,vedge,x,y) != val);
2296                 if (really)
2297                     index(state,vedge,x,y) = val;
2298             }
2299
2300     return changed;
2301 }
2302
2303 static int ui_draw_rect(game_state *state, game_ui *ui,
2304                         unsigned char *hedge, unsigned char *vedge, int c,
2305                         int really)
2306 {
2307     return grid_draw_rect(state, hedge, vedge, c, really,
2308                           ui->x1, ui->y1, ui->x2, ui->y2);
2309 }
2310
2311 static void game_changed_state(game_ui *ui, game_state *oldstate,
2312                                game_state *newstate)
2313 {
2314 }
2315
2316 struct game_drawstate {
2317     int started;
2318     int w, h, tilesize;
2319     unsigned long *visible;
2320 };
2321
2322 static char *interpret_move(game_state *from, game_ui *ui, game_drawstate *ds,
2323                             int x, int y, int button)
2324 {
2325     int xc, yc;
2326     int startdrag = FALSE, enddrag = FALSE, active = FALSE;
2327     char buf[80], *ret;
2328
2329     button &= ~MOD_MASK;
2330
2331     if (button == LEFT_BUTTON) {
2332         startdrag = TRUE;
2333     } else if (button == LEFT_RELEASE) {
2334         enddrag = TRUE;
2335     } else if (button != LEFT_DRAG) {
2336         return NULL;
2337     }
2338
2339     coord_round(FROMCOORD((float)x), FROMCOORD((float)y), &xc, &yc);
2340
2341     if (startdrag &&
2342         xc >= 0 && xc <= 2*from->w &&
2343         yc >= 0 && yc <= 2*from->h) {
2344
2345         ui->drag_start_x = xc;
2346         ui->drag_start_y = yc;
2347         ui->drag_end_x = xc;
2348         ui->drag_end_y = yc;
2349         ui->dragged = FALSE;
2350         active = TRUE;
2351     }
2352
2353     if (ui->drag_start_x >= 0 &&
2354         (xc != ui->drag_end_x || yc != ui->drag_end_y)) {
2355         int t;
2356
2357         ui->drag_end_x = xc;
2358         ui->drag_end_y = yc;
2359         ui->dragged = TRUE;
2360         active = TRUE;
2361
2362         if (xc >= 0 && xc <= 2*from->w &&
2363             yc >= 0 && yc <= 2*from->h) {
2364             ui->x1 = ui->drag_start_x;
2365             ui->x2 = ui->drag_end_x;
2366             if (ui->x2 < ui->x1) { t = ui->x1; ui->x1 = ui->x2; ui->x2 = t; }
2367
2368             ui->y1 = ui->drag_start_y;
2369             ui->y2 = ui->drag_end_y;
2370             if (ui->y2 < ui->y1) { t = ui->y1; ui->y1 = ui->y2; ui->y2 = t; }
2371
2372             ui->x1 = ui->x1 / 2;               /* rounds down */
2373             ui->x2 = (ui->x2+1) / 2;           /* rounds up */
2374             ui->y1 = ui->y1 / 2;               /* rounds down */
2375             ui->y2 = (ui->y2+1) / 2;           /* rounds up */
2376         } else {
2377             ui->x1 = -1;
2378             ui->y1 = -1;
2379             ui->x2 = -1;
2380             ui->y2 = -1;
2381         }
2382     }
2383
2384     ret = NULL;
2385
2386     if (enddrag && (ui->drag_start_x >= 0)) {
2387         if (xc >= 0 && xc <= 2*from->w &&
2388             yc >= 0 && yc <= 2*from->h) {
2389
2390             if (ui->dragged) {
2391                 if (ui_draw_rect(from, ui, from->hedge,
2392                                  from->vedge, 1, FALSE)) {
2393                     sprintf(buf, "R%d,%d,%d,%d",
2394                             ui->x1, ui->y1, ui->x2 - ui->x1, ui->y2 - ui->y1);
2395                     ret = dupstr(buf);
2396                 }
2397             } else {
2398                 if ((xc & 1) && !(yc & 1) && HRANGE(from,xc/2,yc/2)) {
2399                     sprintf(buf, "H%d,%d", xc/2, yc/2);
2400                     ret = dupstr(buf);
2401                 }
2402                 if ((yc & 1) && !(xc & 1) && VRANGE(from,xc/2,yc/2)) {
2403                     sprintf(buf, "V%d,%d", xc/2, yc/2);
2404                     ret = dupstr(buf);
2405                 }
2406             }
2407         }
2408
2409         ui->drag_start_x = -1;
2410         ui->drag_start_y = -1;
2411         ui->drag_end_x = -1;
2412         ui->drag_end_y = -1;
2413         ui->x1 = -1;
2414         ui->y1 = -1;
2415         ui->x2 = -1;
2416         ui->y2 = -1;
2417         ui->dragged = FALSE;
2418         active = TRUE;
2419     }
2420
2421     if (ret)
2422         return ret;                    /* a move has been made */
2423     else if (active)
2424         return "";                     /* UI activity has occurred */
2425     else
2426         return NULL;
2427 }
2428
2429 static game_state *execute_move(game_state *from, char *move)
2430 {
2431     game_state *ret;
2432     int x1, y1, x2, y2, mode;
2433
2434     if (move[0] == 'S') {
2435         char *p = move+1;
2436         int x, y;
2437
2438         ret = dup_game(from);
2439         ret->cheated = TRUE;
2440
2441         for (y = 0; y < ret->h; y++)
2442             for (x = 1; x < ret->w; x++) {
2443                 vedge(ret, x, y) = (*p == '1');
2444                 if (*p) p++;
2445             }
2446         for (y = 1; y < ret->h; y++)
2447             for (x = 0; x < ret->w; x++) {
2448                 hedge(ret, x, y) = (*p == '1');
2449                 if (*p) p++;
2450             }
2451
2452         sfree(ret->correct);
2453         ret->correct = get_correct(ret);
2454
2455         return ret;
2456
2457     } else if (move[0] == 'R' &&
2458         sscanf(move+1, "%d,%d,%d,%d", &x1, &y1, &x2, &y2) == 4 &&
2459         x1 >= 0 && x2 >= 0 && x1+x2 <= from->w &&
2460         y1 >= 0 && y2 >= 0 && y1+y2 <= from->h) {
2461         x2 += x1;
2462         y2 += y1;
2463         mode = move[0];
2464     } else if ((move[0] == 'H' || move[0] == 'V') &&
2465                sscanf(move+1, "%d,%d", &x1, &y1) == 2 &&
2466                (move[0] == 'H' ? HRANGE(from, x1, y1) :
2467                 VRANGE(from, x1, y1))) {
2468         mode = move[0];
2469     } else
2470         return NULL;                   /* can't parse move string */
2471
2472     ret = dup_game(from);
2473
2474     if (mode == 'R') {
2475         grid_draw_rect(ret, ret->hedge, ret->vedge, 1, TRUE, x1, y1, x2, y2);
2476     } else if (mode == 'H') {
2477         hedge(ret,x1,y1) = !hedge(ret,x1,y1);
2478     } else if (mode == 'V') {
2479         vedge(ret,x1,y1) = !vedge(ret,x1,y1);
2480     }
2481
2482     sfree(ret->correct);
2483     ret->correct = get_correct(ret);
2484
2485     /*
2486      * We've made a real change to the grid. Check to see
2487      * if the game has been completed.
2488      */
2489     if (!ret->completed) {
2490         int x, y, ok;
2491
2492         ok = TRUE;
2493         for (x = 0; x < ret->w; x++)
2494             for (y = 0; y < ret->h; y++)
2495                 if (!index(ret, ret->correct, x, y))
2496                     ok = FALSE;
2497
2498         if (ok)
2499             ret->completed = TRUE;
2500     }
2501
2502     return ret;
2503 }
2504
2505 /* ----------------------------------------------------------------------
2506  * Drawing routines.
2507  */
2508
2509 #define CORRECT (1L<<16)
2510
2511 #define COLOUR(k) ( (k)==1 ? COL_LINE : COL_DRAG )
2512 #define MAX4(x,y,z,w) ( max(max(x,y),max(z,w)) )
2513
2514 static void game_compute_size(game_params *params, int tilesize,
2515                               int *x, int *y)
2516 {
2517     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2518     struct { int tilesize; } ads, *ds = &ads;
2519     ads.tilesize = tilesize;
2520
2521     *x = params->w * TILE_SIZE + 2*BORDER + 1;
2522     *y = params->h * TILE_SIZE + 2*BORDER + 1;
2523 }
2524
2525 static void game_set_size(game_drawstate *ds, game_params *params,
2526                           int tilesize)
2527 {
2528     ds->tilesize = tilesize;
2529 }
2530
2531 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
2532 {
2533     float *ret = snewn(3 * NCOLOURS, float);
2534
2535     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2536
2537     ret[COL_GRID * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
2538     ret[COL_GRID * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
2539     ret[COL_GRID * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
2540
2541     ret[COL_DRAG * 3 + 0] = 1.0F;
2542     ret[COL_DRAG * 3 + 1] = 0.0F;
2543     ret[COL_DRAG * 3 + 2] = 0.0F;
2544
2545     ret[COL_CORRECT * 3 + 0] = 0.75F * ret[COL_BACKGROUND * 3 + 0];
2546     ret[COL_CORRECT * 3 + 1] = 0.75F * ret[COL_BACKGROUND * 3 + 1];
2547     ret[COL_CORRECT * 3 + 2] = 0.75F * ret[COL_BACKGROUND * 3 + 2];
2548
2549     ret[COL_LINE * 3 + 0] = 0.0F;
2550     ret[COL_LINE * 3 + 1] = 0.0F;
2551     ret[COL_LINE * 3 + 2] = 0.0F;
2552
2553     ret[COL_TEXT * 3 + 0] = 0.0F;
2554     ret[COL_TEXT * 3 + 1] = 0.0F;
2555     ret[COL_TEXT * 3 + 2] = 0.0F;
2556
2557     *ncolours = NCOLOURS;
2558     return ret;
2559 }
2560
2561 static game_drawstate *game_new_drawstate(game_state *state)
2562 {
2563     struct game_drawstate *ds = snew(struct game_drawstate);
2564     int i;
2565
2566     ds->started = FALSE;
2567     ds->w = state->w;
2568     ds->h = state->h;
2569     ds->visible = snewn(ds->w * ds->h, unsigned long);
2570     ds->tilesize = 0;                  /* not decided yet */
2571     for (i = 0; i < ds->w * ds->h; i++)
2572         ds->visible[i] = 0xFFFF;
2573
2574     return ds;
2575 }
2576
2577 static void game_free_drawstate(game_drawstate *ds)
2578 {
2579     sfree(ds->visible);
2580     sfree(ds);
2581 }
2582
2583 static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state,
2584                       int x, int y, unsigned char *hedge, unsigned char *vedge,
2585                       unsigned char *corners, int correct)
2586 {
2587     int cx = COORD(x), cy = COORD(y);
2588     char str[80];
2589
2590     draw_rect(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1, COL_GRID);
2591     draw_rect(fe, cx+1, cy+1, TILE_SIZE-1, TILE_SIZE-1,
2592               correct ? COL_CORRECT : COL_BACKGROUND);
2593
2594     if (grid(state,x,y)) {
2595         sprintf(str, "%d", grid(state,x,y));
2596         draw_text(fe, cx+TILE_SIZE/2, cy+TILE_SIZE/2, FONT_VARIABLE,
2597                   TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, COL_TEXT, str);
2598     }
2599
2600     /*
2601      * Draw edges.
2602      */
2603     if (!HRANGE(state,x,y) || index(state,hedge,x,y))
2604         draw_rect(fe, cx, cy, TILE_SIZE+1, 2,
2605                   HRANGE(state,x,y) ? COLOUR(index(state,hedge,x,y)) :
2606                   COL_LINE);
2607     if (!HRANGE(state,x,y+1) || index(state,hedge,x,y+1))
2608         draw_rect(fe, cx, cy+TILE_SIZE-1, TILE_SIZE+1, 2,
2609                   HRANGE(state,x,y+1) ? COLOUR(index(state,hedge,x,y+1)) :
2610                   COL_LINE);
2611     if (!VRANGE(state,x,y) || index(state,vedge,x,y))
2612         draw_rect(fe, cx, cy, 2, TILE_SIZE+1,
2613                   VRANGE(state,x,y) ? COLOUR(index(state,vedge,x,y)) :
2614                   COL_LINE);
2615     if (!VRANGE(state,x+1,y) || index(state,vedge,x+1,y))
2616         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, TILE_SIZE+1,
2617                   VRANGE(state,x+1,y) ? COLOUR(index(state,vedge,x+1,y)) :
2618                   COL_LINE);
2619
2620     /*
2621      * Draw corners.
2622      */
2623     if (index(state,corners,x,y))
2624         draw_rect(fe, cx, cy, 2, 2,
2625                   COLOUR(index(state,corners,x,y)));
2626     if (x+1 < state->w && index(state,corners,x+1,y))
2627         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, 2,
2628                   COLOUR(index(state,corners,x+1,y)));
2629     if (y+1 < state->h && index(state,corners,x,y+1))
2630         draw_rect(fe, cx, cy+TILE_SIZE-1, 2, 2,
2631                   COLOUR(index(state,corners,x,y+1)));
2632     if (x+1 < state->w && y+1 < state->h && index(state,corners,x+1,y+1))
2633         draw_rect(fe, cx+TILE_SIZE-1, cy+TILE_SIZE-1, 2, 2,
2634                   COLOUR(index(state,corners,x+1,y+1)));
2635
2636     draw_update(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1);
2637 }
2638
2639 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
2640                  game_state *state, int dir, game_ui *ui,
2641                  float animtime, float flashtime)
2642 {
2643     int x, y;
2644     unsigned char *hedge, *vedge, *corners;
2645
2646     if (ui->dragged) {
2647         hedge = snewn(state->w*state->h, unsigned char);
2648         vedge = snewn(state->w*state->h, unsigned char);
2649         memcpy(hedge, state->hedge, state->w*state->h);
2650         memcpy(vedge, state->vedge, state->w*state->h);
2651         ui_draw_rect(state, ui, hedge, vedge, 2, TRUE);
2652     } else {
2653         hedge = state->hedge;
2654         vedge = state->vedge;
2655     }
2656
2657     corners = snewn(state->w * state->h, unsigned char);
2658     memset(corners, 0, state->w * state->h);
2659     for (x = 0; x < state->w; x++)
2660         for (y = 0; y < state->h; y++) {
2661             if (x > 0) {
2662                 int e = index(state, vedge, x, y);
2663                 if (index(state,corners,x,y) < e)
2664                     index(state,corners,x,y) = e;
2665                 if (y+1 < state->h &&
2666                     index(state,corners,x,y+1) < e)
2667                     index(state,corners,x,y+1) = e;
2668             }
2669             if (y > 0) {
2670                 int e = index(state, hedge, x, y);
2671                 if (index(state,corners,x,y) < e)
2672                     index(state,corners,x,y) = e;
2673                 if (x+1 < state->w &&
2674                     index(state,corners,x+1,y) < e)
2675                     index(state,corners,x+1,y) = e;
2676             }
2677         }
2678
2679     if (!ds->started) {
2680         draw_rect(fe, 0, 0,
2681                   state->w * TILE_SIZE + 2*BORDER + 1,
2682                   state->h * TILE_SIZE + 2*BORDER + 1, COL_BACKGROUND);
2683         draw_rect(fe, COORD(0)-1, COORD(0)-1,
2684                   ds->w*TILE_SIZE+3, ds->h*TILE_SIZE+3, COL_LINE);
2685         ds->started = TRUE;
2686         draw_update(fe, 0, 0,
2687                     state->w * TILE_SIZE + 2*BORDER + 1,
2688                     state->h * TILE_SIZE + 2*BORDER + 1);
2689     }
2690
2691     for (x = 0; x < state->w; x++)
2692         for (y = 0; y < state->h; y++) {
2693             unsigned long c = 0;
2694
2695             if (HRANGE(state,x,y))
2696                 c |= index(state,hedge,x,y);
2697             if (HRANGE(state,x,y+1))
2698                 c |= index(state,hedge,x,y+1) << 2;
2699             if (VRANGE(state,x,y))
2700                 c |= index(state,vedge,x,y) << 4;
2701             if (VRANGE(state,x+1,y))
2702                 c |= index(state,vedge,x+1,y) << 6;
2703             c |= index(state,corners,x,y) << 8;
2704             if (x+1 < state->w)
2705                 c |= index(state,corners,x+1,y) << 10;
2706             if (y+1 < state->h)
2707                 c |= index(state,corners,x,y+1) << 12;
2708             if (x+1 < state->w && y+1 < state->h)
2709                 /* cast to prevent 2<<14 sign-extending on promotion to long */
2710                 c |= (unsigned long)index(state,corners,x+1,y+1) << 14;
2711             if (index(state, state->correct, x, y) && !flashtime)
2712                 c |= CORRECT;
2713
2714             if (index(ds,ds->visible,x,y) != c) {
2715                 draw_tile(fe, ds, state, x, y, hedge, vedge, corners,
2716                           (c & CORRECT) ? 1 : 0);
2717                 index(ds,ds->visible,x,y) = c;
2718             }
2719         }
2720
2721     {
2722         char buf[256];
2723
2724         if (ui->x1 >= 0 && ui->y1 >= 0 &&
2725             ui->x2 >= 0 && ui->y2 >= 0) {
2726             sprintf(buf, "%dx%d ",
2727                     ui->x2-ui->x1,
2728                     ui->y2-ui->y1);
2729         } else {
2730             buf[0] = '\0';
2731         }
2732
2733         if (state->cheated)
2734             strcat(buf, "Auto-solved.");
2735         else if (state->completed)
2736             strcat(buf, "COMPLETED!");
2737
2738         status_bar(fe, buf);
2739     }
2740
2741     if (hedge != state->hedge) {
2742         sfree(hedge);
2743         sfree(vedge);
2744     }
2745
2746     sfree(corners);
2747 }
2748
2749 static float game_anim_length(game_state *oldstate,
2750                               game_state *newstate, int dir, game_ui *ui)
2751 {
2752     return 0.0F;
2753 }
2754
2755 static float game_flash_length(game_state *oldstate,
2756                                game_state *newstate, int dir, game_ui *ui)
2757 {
2758     if (!oldstate->completed && newstate->completed &&
2759         !oldstate->cheated && !newstate->cheated)
2760         return FLASH_TIME;
2761     return 0.0F;
2762 }
2763
2764 static int game_wants_statusbar(void)
2765 {
2766     return TRUE;
2767 }
2768
2769 static int game_timing_state(game_state *state, game_ui *ui)
2770 {
2771     return TRUE;
2772 }
2773
2774 #ifdef COMBINED
2775 #define thegame rect
2776 #endif
2777
2778 const struct game thegame = {
2779     "Rectangles", "games.rectangles",
2780     default_params,
2781     game_fetch_preset,
2782     decode_params,
2783     encode_params,
2784     free_params,
2785     dup_params,
2786     TRUE, game_configure, custom_params,
2787     validate_params,
2788     new_game_desc,
2789     validate_desc,
2790     new_game,
2791     dup_game,
2792     free_game,
2793     TRUE, solve_game,
2794     TRUE, game_text_format,
2795     new_ui,
2796     free_ui,
2797     encode_ui,
2798     decode_ui,
2799     game_changed_state,
2800     interpret_move,
2801     execute_move,
2802     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2803     game_colours,
2804     game_new_drawstate,
2805     game_free_drawstate,
2806     game_redraw,
2807     game_anim_length,
2808     game_flash_length,
2809     game_wants_statusbar,
2810     FALSE, game_timing_state,
2811     0,                                 /* mouse_priorities */
2812 };