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