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 on singleton removal by making an aesthetic choice
  13  *    about which of the options to take.
  14  *
  15  *  - When doing the 3x3 trick in singleton removal, limit the size
  16  *    of the generated rectangles in accordance with the max
  17  *    rectangle size.
  18  *
  19  *  - It might be interesting to deliberately try to place
  20  *    numbers so as to reduce alternative solution patterns. I
  21  *    doubt we can do a perfect job of this, but we can make a
  22  *    start by, for example, noticing pairs of 2-rects
  23  *    alongside one another and _not_ putting their numbers at
  24  *    opposite ends.
  25  *
  26  *  - If we start by sorting the rectlist in descending order
  27  *    of area, we might be able to bias our random number
  28  *    selection to produce a few large rectangles more often
  29  *    than oodles of small ones? Unsure, but might be worth a
  30  *    try.
  31  */
  32
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36 #include <assert.h>
  37 #include <ctype.h>
  38 #include <math.h>
  39
  40 #include "puzzles.h"
  41
  42 const char *const game_name = "Rectangles";
  43 const char *const game_winhelp_topic = "games.rectangles";
  44 const int game_can_configure = TRUE;
  45
  46 enum {
  47     COL_BACKGROUND,
  48     COL_CORRECT,
  49     COL_LINE,
  50     COL_TEXT,
  51     COL_GRID,
  52     COL_DRAG,
  53     NCOLOURS
  54 };
  55
  56 struct game_params {
  57     int w, h;
  58     float expandfactor;
  59 };
  60
  61 #define INDEX(state, x, y)    (((y) * (state)->w) + (x))
  62 #define index(state, a, x, y) ((a) [ INDEX(state,x,y) ])
  63 #define grid(state,x,y)       index(state, (state)->grid, x, y)
  64 #define vedge(state,x,y)      index(state, (state)->vedge, x, y)
  65 #define hedge(state,x,y)      index(state, (state)->hedge, x, y)
  66
  67 #define CRANGE(state,x,y,dx,dy) ( (x) >= dx && (x) < (state)->w && \
  68                                 (y) >= dy && (y) < (state)->h )
  69 #define RANGE(state,x,y)  CRANGE(state,x,y,0,0)
  70 #define HRANGE(state,x,y) CRANGE(state,x,y,0,1)
  71 #define VRANGE(state,x,y) CRANGE(state,x,y,1,0)
  72
  73 #define TILE_SIZE 24
  74 #define BORDER 18
  75
  76 #define CORNER_TOLERANCE 0.15F
  77 #define CENTRE_TOLERANCE 0.15F
  78
  79 #define FLASH_TIME 0.13F
  80
  81 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
  82 #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE )
  83
  84 struct game_state {
  85     int w, h;
  86     int *grid;                         /* contains the numbers */
  87     unsigned char *vedge;              /* (w+1) x h */
  88     unsigned char *hedge;              /* w x (h+1) */
  89     int completed;
  90 };
  91
  92 game_params *default_params(void)
  93 {
  94     game_params *ret = snew(game_params);
  95
  96     ret->w = ret->h = 7;
  97     ret->expandfactor = 0.0F;
  98
  99     return ret;
 100 }
 101
 102 int game_fetch_preset(int i, char **name, game_params **params)
 103 {
 104     game_params *ret;
 105     int w, h;
 106     char buf[80];
 107
 108     switch (i) {
 109       case 0: w = 7, h = 7; break;
 110       case 1: w = 11, h = 11; break;
 111       case 2: w = 15, h = 15; break;
 112       case 3: w = 19, h = 19; break;
 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     return TRUE;
 123 }
 124
 125 void free_params(game_params *params)
 126 {
 127     sfree(params);
 128 }
 129
 130 game_params *dup_params(game_params *params)
 131 {
 132     game_params *ret = snew(game_params);
 133     *ret = *params;                    /* structure copy */
 134     return ret;
 135 }
 136
 137 game_params *decode_params(char const *string)
 138 {
 139     game_params *ret = default_params();
 140
 141     ret->w = ret->h = atoi(string);
 142     ret->expandfactor = 0.0F;
 143     while (*string && isdigit((unsigned char)*string)) string++;
 144     if (*string == 'x') {
 145         string++;
 146         ret->h = atoi(string);
 147         while (*string && isdigit((unsigned char)*string)) string++;
 148     }
 149     if (*string == 'e') {
 150         string++;
 151         ret->expandfactor = atof(string);
 152     }
 153
 154     return ret;
 155 }
 156
 157 char *encode_params(game_params *params)
 158 {
 159     char data[256];
 160
 161     sprintf(data, "%dx%d", params->w, params->h);
 162
 163     return dupstr(data);
 164 }
 165
 166 config_item *game_configure(game_params *params)
 167 {
 168     config_item *ret;
 169     char buf[80];
 170
 171     ret = snewn(5, config_item);
 172
 173     ret[0].name = "Width";
 174     ret[0].type = C_STRING;
 175     sprintf(buf, "%d", params->w);
 176     ret[0].sval = dupstr(buf);
 177     ret[0].ival = 0;
 178
 179     ret[1].name = "Height";
 180     ret[1].type = C_STRING;
 181     sprintf(buf, "%d", params->h);
 182     ret[1].sval = dupstr(buf);
 183     ret[1].ival = 0;
 184
 185     ret[2].name = "Expansion factor";
 186     ret[2].type = C_STRING;
 187     sprintf(buf, "%g", params->expandfactor);
 188     ret[2].sval = dupstr(buf);
 189     ret[2].ival = 0;
 190
 191     ret[3].name = NULL;
 192     ret[3].type = C_END;
 193     ret[3].sval = NULL;
 194     ret[3].ival = 0;
 195
 196     return ret;
 197 }
 198
 199 game_params *custom_params(config_item *cfg)
 200 {
 201     game_params *ret = snew(game_params);
 202
 203     ret->w = atoi(cfg[0].sval);
 204     ret->h = atoi(cfg[1].sval);
 205     ret->expandfactor = atof(cfg[2].sval);
 206
 207     return ret;
 208 }
 209
 210 char *validate_params(game_params *params)
 211 {
 212     if (params->w <= 0 && params->h <= 0)
 213         return "Width and height must both be greater than zero";
 214     if (params->w < 2 && params->h < 2)
 215         return "Grid area must be greater than one";
 216     if (params->expandfactor < 0.0F)
 217         return "Expansion factor may not be negative";
 218     return NULL;
 219 }
 220
 221 struct rect {
 222     int x, y;
 223     int w, h;
 224 };
 225
 226 struct rectlist {
 227     struct rect *rects;
 228     int n;
 229 };
 230
 231 static struct rectlist *get_rectlist(game_params *params, int *grid)
 232 {
 233     int rw, rh;
 234     int x, y;
 235     int maxarea;
 236     struct rect *rects = NULL;
 237     int nrects = 0, rectsize = 0;
 238
 239     /*
 240      * Maximum rectangle area is 1/6 of total grid size, unless
 241      * this means we can't place any rectangles at all in which
 242      * case we set it to 2 at minimum.
 243      */
 244     maxarea = params->w * params->h / 6;
 245     if (maxarea < 2)
 246         maxarea = 2;
 247
 248     for (rw = 1; rw <= params->w; rw++)
 249         for (rh = 1; rh <= params->h; rh++) {
 250             if (rw * rh > maxarea)
 251                 continue;
 252             if (rw * rh == 1)
 253                 continue;
 254             for (x = 0; x <= params->w - rw; x++)
 255                 for (y = 0; y <= params->h - rh; y++) {
 256                     if (nrects >= rectsize) {
 257                         rectsize = nrects + 256;
 258                         rects = sresize(rects, rectsize, struct rect);
 259                     }
 260
 261                     rects[nrects].x = x;
 262                     rects[nrects].y = y;
 263                     rects[nrects].w = rw;
 264                     rects[nrects].h = rh;
 265                     nrects++;
 266                 }
 267         }
 268
 269     if (nrects > 0) {
 270         struct rectlist *ret;
 271         ret = snew(struct rectlist);
 272         ret->rects = rects;
 273         ret->n = nrects;
 274         return ret;
 275     } else {
 276         assert(rects == NULL);         /* hence no need to free */
 277         return NULL;
 278     }
 279 }
 280
 281 static void free_rectlist(struct rectlist *list)
 282 {
 283     sfree(list->rects);
 284     sfree(list);
 285 }
 286
 287 static void place_rect(game_params *params, int *grid, struct rect r)
 288 {
 289     int idx = INDEX(params, r.x, r.y);
 290     int x, y;
 291
 292     for (x = r.x; x < r.x+r.w; x++)
 293         for (y = r.y; y < r.y+r.h; y++) {
 294             index(params, grid, x, y) = idx;
 295         }
 296 #ifdef GENERATION_DIAGNOSTICS
 297     printf("    placing rectangle at (%d,%d) size %d x %d\n",
 298            r.x, r.y, r.w, r.h);
 299 #endif
 300 }
 301
 302 static struct rect find_rect(game_params *params, int *grid, int x, int y)
 303 {
 304     int idx, w, h;
 305     struct rect r;
 306
 307     /*
 308      * Find the top left of the rectangle.
 309      */
 310     idx = index(params, grid, x, y);
 311
 312     if (idx < 0) {
 313         r.x = x;
 314         r.y = y;
 315         r.w = r.h = 1;
 316         return r;                      /* 1x1 singleton here */
 317     }
 318
 319     y = idx / params->w;
 320     x = idx % params->w;
 321
 322     /*
 323      * Find the width and height of the rectangle.
 324      */
 325     for (w = 1;
 326          (x+w < params->w && index(params,grid,x+w,y)==idx);
 327          w++);
 328     for (h = 1;
 329          (y+h < params->h && index(params,grid,x,y+h)==idx);
 330          h++);
 331
 332     r.x = x;
 333     r.y = y;
 334     r.w = w;
 335     r.h = h;
 336
 337     return r;
 338 }
 339
 340 #ifdef GENERATION_DIAGNOSTICS
 341 static void display_grid(game_params *params, int *grid, int *numbers, int all)
 342 {
 343     unsigned char *egrid = snewn((params->w*2+3) * (params->h*2+3),
 344                                  unsigned char);
 345     int x, y;
 346     int r = (params->w*2+3);
 347
 348     memset(egrid, 0, (params->w*2+3) * (params->h*2+3));
 349
 350     for (x = 0; x < params->w; x++)
 351         for (y = 0; y < params->h; y++) {
 352             int i = index(params, grid, x, y);
 353             if (x == 0 || index(params, grid, x-1, y) != i)
 354                 egrid[(2*y+2) * r + (2*x+1)] = 1;
 355             if (x == params->w-1 || index(params, grid, x+1, y) != i)
 356                 egrid[(2*y+2) * r + (2*x+3)] = 1;
 357             if (y == 0 || index(params, grid, x, y-1) != i)
 358                 egrid[(2*y+1) * r + (2*x+2)] = 1;
 359             if (y == params->h-1 || index(params, grid, x, y+1) != i)
 360                 egrid[(2*y+3) * r + (2*x+2)] = 1;
 361         }
 362
 363     for (y = 1; y < 2*params->h+2; y++) {
 364         for (x = 1; x < 2*params->w+2; x++) {
 365             if (!((y|x)&1)) {
 366                 int k = numbers ? index(params, numbers, x/2-1, y/2-1) : 0;
 367                 if (k || (all && numbers)) printf("%2d", k); else printf("  ");
 368             } else if (!((y&x)&1)) {
 369                 int v = egrid[y*r+x];
 370                 if ((y&1) && v) v = '-';
 371                 if ((x&1) && v) v = '|';
 372                 if (!v) v = ' ';
 373                 putchar(v);
 374                 if (!(x&1)) putchar(v);
 375             } else {
 376                 int c, d = 0;
 377                 if (egrid[y*r+(x+1)]) d |= 1;
 378                 if (egrid[(y-1)*r+x]) d |= 2;
 379                 if (egrid[y*r+(x-1)]) d |= 4;
 380                 if (egrid[(y+1)*r+x]) d |= 8;
 381                 c = " ??+?-++?+|+++++"[d];
 382                 putchar(c);
 383                 if (!(x&1)) putchar(c);
 384             }
 385         }
 386         putchar('\n');
 387     }
 388
 389     sfree(egrid);
 390 }
 391 #endif
 392
 393 char *new_game_seed(game_params *params, random_state *rs)
 394 {
 395     int *grid, *numbers;
 396     struct rectlist *list;
 397     int x, y, y2, y2last, yx, run, i;
 398     char *seed, *p;
 399     game_params params2real, *params2 = &params2real;
 400
 401     /*
 402      * Set up the smaller width and height which we will use to
 403      * generate the base grid.
 404      */
 405     params2->w = params->w / (1.0F + params->expandfactor);
 406     if (params2->w < 2 && params->w >= 2) params2->w = 2;
 407     params2->h = params->h / (1.0F + params->expandfactor);
 408     if (params2->h < 2 && params->h >= 2) params2->h = 2;
 409
 410     grid = snewn(params2->w * params2->h, int);
 411
 412     for (y = 0; y < params2->h; y++)
 413         for (x = 0; x < params2->w; x++) {
 414             index(params2, grid, x, y) = -1;
 415         }
 416
 417     list = get_rectlist(params2, grid);
 418     assert(list != NULL);
 419
 420     /*
 421      * Place rectangles until we can't any more.
 422      */
 423     while (list->n > 0) {
 424         int i, m;
 425         struct rect r;
 426
 427         /*
 428          * Pick a random rectangle.
 429          */
 430         i = random_upto(rs, list->n);
 431         r = list->rects[i];
 432
 433         /*
 434          * Place it.
 435          */
 436         place_rect(params2, grid, r);
 437
 438         /*
 439          * Winnow the list by removing any rectangles which
 440          * overlap this one.
 441          */
 442         m = 0;
 443         for (i = 0; i < list->n; i++) {
 444             struct rect s = list->rects[i];
 445             if (s.x+s.w <= r.x || r.x+r.w <= s.x ||
 446                 s.y+s.h <= r.y || r.y+r.h <= s.y)
 447                 list->rects[m++] = s;
 448         }
 449         list->n = m;
 450     }
 451
 452     free_rectlist(list);
 453
 454     /*
 455      * Deal with singleton spaces remaining in the grid, one by
 456      * one.
 457      *
 458      * We do this by making a local change to the layout. There are
 459      * several possibilities:
 460      *
 461      *     +-----+-----+    Here, we can remove the singleton by
 462      *     |     |     |    extending the 1x2 rectangle below it
 463      *     +--+--+-----+    into a 1x3.
 464      *     |  |  |     |
 465      *     |  +--+     |
 466      *     |  |  |     |
 467      *     |  |  |     |
 468      *     |  |  |     |
 469      *     +--+--+-----+
 470      *
 471      *     +--+--+--+       Here, that trick doesn't work: there's no
 472      *     |     |  |       1 x n rectangle with the singleton at one
 473      *     |     |  |       end. Instead, we extend a 1 x n rectangle
 474      *     |     |  |       _out_ from the singleton, shaving a layer
 475      *     +--+--+  |       off the end of another rectangle. So if we
 476      *     |  |  |  |       extended up, we'd make our singleton part
 477      *     |  +--+--+       of a 1x3 and generate a 1x2 where the 2x2
 478      *     |  |     |       used to be; or we could extend right into
 479      *     +--+-----+       a 2x1, turning the 1x3 into a 1x2.
 480      *
 481      *     +-----+--+       Here, we can't even do _that_, since any
 482      *     |     |  |       direction we choose to extend the singleton
 483      *     +--+--+  |       will produce a new singleton as a result of
 484      *     |  |  |  |       truncating one of the size-2 rectangles.
 485      *     |  +--+--+       Fortunately, this case can _only_ occur when
 486      *     |  |     |       a singleton is surrounded by four size-2s
 487      *     +--+-----+       in this fashion; so instead we can simply
 488      *                      replace the whole section with a single 3x3.
 489      */
 490     for (x = 0; x < params2->w; x++) {
 491         for (y = 0; y < params2->h; y++) {
 492             if (index(params2, grid, x, y) < 0) {
 493                 int dirs[4], ndirs;
 494
 495 #ifdef GENERATION_DIAGNOSTICS
 496                 display_grid(params2, grid, NULL, FALSE);
 497                 printf("singleton at %d,%d\n", x, y);
 498 #endif
 499
 500                 /*
 501                  * Check in which directions we can feasibly extend
 502                  * the singleton. We can extend in a particular
 503                  * direction iff either:
 504                  *
 505                  *  - the rectangle on that side of the singleton
 506                  *    is not 2x1, and we are at one end of the edge
 507                  *    of it we are touching
 508                  *
 509                  *  - it is 2x1 but we are on its short side.
 510                  *
 511                  * FIXME: we could plausibly choose between these
 512                  * based on the sizes of the rectangles they would
 513                  * create?
 514                  */
 515                 ndirs = 0;
 516                 if (x < params2->w-1) {
 517                     struct rect r = find_rect(params2, grid, x+1, y);
 518                     if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
 519                         dirs[ndirs++] = 1;   /* right */
 520                 }
 521                 if (y > 0) {
 522                     struct rect r = find_rect(params2, grid, x, y-1);
 523                     if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
 524                         dirs[ndirs++] = 2;   /* up */
 525                 }
 526                 if (x > 0) {
 527                     struct rect r = find_rect(params2, grid, x-1, y);
 528                     if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
 529                         dirs[ndirs++] = 4;   /* left */
 530                 }
 531                 if (y < params2->h-1) {
 532                     struct rect r = find_rect(params2, grid, x, y+1);
 533                     if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
 534                         dirs[ndirs++] = 8;   /* down */
 535                 }
 536
 537                 if (ndirs > 0) {
 538                     int which, dir;
 539                     struct rect r1, r2;
 540
 541                     which = random_upto(rs, ndirs);
 542                     dir = dirs[which];
 543
 544                     switch (dir) {
 545                       case 1:          /* right */
 546                         assert(x < params2->w+1);
 547 #ifdef GENERATION_DIAGNOSTICS
 548                         printf("extending right\n");
 549 #endif
 550                         r1 = find_rect(params2, grid, x+1, y);
 551                         r2.x = x;
 552                         r2.y = y;
 553                         r2.w = 1 + r1.w;
 554                         r2.h = 1;
 555                         if (r1.y == y)
 556                             r1.y++;
 557                         r1.h--;
 558                         break;
 559                       case 2:          /* up */
 560                         assert(y > 0);
 561 #ifdef GENERATION_DIAGNOSTICS
 562                         printf("extending up\n");
 563 #endif
 564                         r1 = find_rect(params2, grid, x, y-1);
 565                         r2.x = x;
 566                         r2.y = r1.y;
 567                         r2.w = 1;
 568                         r2.h = 1 + r1.h;
 569                         if (r1.x == x)
 570                             r1.x++;
 571                         r1.w--;
 572                         break;
 573                       case 4:          /* left */
 574                         assert(x > 0);
 575 #ifdef GENERATION_DIAGNOSTICS
 576                         printf("extending left\n");
 577 #endif
 578                         r1 = find_rect(params2, grid, x-1, y);
 579                         r2.x = r1.x;
 580                         r2.y = y;
 581                         r2.w = 1 + r1.w;
 582                         r2.h = 1;
 583                         if (r1.y == y)
 584                             r1.y++;
 585                         r1.h--;
 586                         break;
 587                       case 8:          /* down */
 588                         assert(y < params2->h+1);
 589 #ifdef GENERATION_DIAGNOSTICS
 590                         printf("extending down\n");
 591 #endif
 592                         r1 = find_rect(params2, grid, x, y+1);
 593                         r2.x = x;
 594                         r2.y = y;
 595                         r2.w = 1;
 596                         r2.h = 1 + r1.h;
 597                         if (r1.x == x)
 598                             r1.x++;
 599                         r1.w--;
 600                         break;
 601                     }
 602                     if (r1.h > 0 && r1.w > 0)
 603                         place_rect(params2, grid, r1);
 604                     place_rect(params2, grid, r2);
 605                 } else {
 606 #ifndef NDEBUG
 607                     /*
 608                      * Sanity-check that there really is a 3x3
 609                      * rectangle surrounding this singleton and it
 610                      * contains absolutely everything we could
 611                      * possibly need.
 612                      */
 613                     {
 614                         int xx, yy;
 615                         assert(x > 0 && x < params2->w-1);
 616                         assert(y > 0 && y < params2->h-1);
 617
 618                         for (xx = x-1; xx <= x+1; xx++)
 619                             for (yy = y-1; yy <= y+1; yy++) {
 620                                 struct rect r = find_rect(params2,grid,xx,yy);
 621                                 assert(r.x >= x-1);
 622                                 assert(r.y >= y-1);
 623                                 assert(r.x+r.w-1 <= x+1);
 624                                 assert(r.y+r.h-1 <= y+1);
 625                             }
 626                     }
 627 #endif
 628
 629 #ifdef GENERATION_DIAGNOSTICS
 630                     printf("need the 3x3 trick\n");
 631 #endif
 632
 633                     /*
 634                      * FIXME: If the maximum rectangle area for
 635                      * this grid is less than 9, we ought to
 636                      * subdivide the 3x3 in some fashion. There are
 637                      * five other possibilities:
 638                      *
 639                      *  - a 6 and a 3
 640                      *  - a 4, a 3 and a 2
 641                      *  - three 3s
 642                      *  - a 3 and three 2s (two different arrangements).
 643                      */
 644
 645                     {
 646                         struct rect r;
 647                         r.x = x-1;
 648                         r.y = y-1;
 649                         r.w = r.h = 3;
 650                         place_rect(params2, grid, r);
 651                     }
 652                 }
 653             }
 654         }
 655     }
 656
 657     /*
 658      * We have now constructed a grid of the size specified in
 659      * params2. Now we extend it into a grid of the size specified
 660      * in params. We do this in two passes: we extend it vertically
 661      * until it's the right height, then we transpose it, then
 662      * extend it vertically again (getting it effectively the right
 663      * width), then finally transpose again.
 664      */
 665     for (i = 0; i < 2; i++) {
 666         int *grid2, *expand, *where;
 667         game_params params3real, *params3 = &params3real;
 668
 669 #ifdef GENERATION_DIAGNOSTICS
 670         printf("before expansion:\n");
 671         display_grid(params2, grid, NULL, TRUE);
 672 #endif
 673
 674         /*
 675          * Set up the new grid.
 676          */
 677         grid2 = snewn(params2->w * params->h, int);
 678         expand = snewn(params2->h-1, int);
 679         where = snewn(params2->w, int);
 680         params3->w = params2->w;
 681         params3->h = params->h;
 682
 683         /*
 684          * Decide which horizontal edges are going to get expanded,
 685          * and by how much.
 686          */
 687         for (y = 0; y < params2->h-1; y++)
 688             expand[y] = 0;
 689         for (y = params2->h; y < params->h; y++) {
 690             x = random_upto(rs, params2->h-1);
 691             expand[x]++;
 692         }
 693
 694 #ifdef GENERATION_DIAGNOSTICS
 695         printf("expand[] = {");
 696         for (y = 0; y < params2->h-1; y++)
 697             printf(" %d", expand[y]);
 698         printf(" }\n");
 699 #endif
 700
 701         /*
 702          * Perform the expansion. The way this works is that we
 703          * alternately:
 704          *
 705          *  - copy a row from grid into grid2
 706          *
 707          *  - invent some number of additional rows in grid2 where
 708          *    there was previously only a horizontal line between
 709          *    rows in grid, and make random decisions about where
 710          *    among these to place each rectangle edge that ran
 711          *    along this line.
 712          */
 713         for (y = y2 = y2last = 0; y < params2->h; y++) {
 714             /*
 715              * Copy a single line from row y of grid into row y2 of
 716              * grid2.
 717              */
 718             for (x = 0; x < params2->w; x++) {
 719                 int val = index(params2, grid, x, y);
 720                 if (val / params2->w == y &&   /* rect starts on this line */
 721                     (y2 == 0 ||        /* we're at the very top, or... */
 722                      index(params3, grid2, x, y2-1) / params3->w < y2last
 723                                        /* this rect isn't already started */))
 724                     index(params3, grid2, x, y2) =
 725                     INDEX(params3, val % params2->w, y2);
 726                 else
 727                     index(params3, grid2, x, y2) =
 728                     index(params3, grid2, x, y2-1);
 729             }
 730
 731             /*
 732              * If that was the last line, terminate the loop early.
 733              */
 734             if (++y2 == params3->h)
 735                 break;
 736
 737             y2last = y2;
 738
 739             /*
 740              * Invent some number of additional lines. First walk
 741              * along this line working out where to put all the
 742              * edges that coincide with it.
 743              */
 744             yx = -1;
 745             for (x = 0; x < params2->w; x++) {
 746                 if (index(params2, grid, x, y) !=
 747                     index(params2, grid, x, y+1)) {
 748                     /*
 749                      * This is a horizontal edge, so it needs
 750                      * placing.
 751                      */
 752                     if (x == 0 ||
 753                         (index(params2, grid, x-1, y) !=
 754                          index(params2, grid, x, y) &&
 755                          index(params2, grid, x-1, y+1) !=
 756                          index(params2, grid, x, y+1))) {
 757                         /*
 758                          * Here we have the chance to make a new
 759                          * decision.
 760                          */
 761                         yx = random_upto(rs, expand[y]+1);
 762                     } else {
 763                         /*
 764                          * Here we just reuse the previous value of
 765                          * yx.
 766                          */
 767                     }
 768                 } else
 769                     yx = -1;
 770                 where[x] = yx;
 771             }
 772
 773             for (yx = 0; yx < expand[y]; yx++) {
 774                 /*
 775                  * Invent a single row. For each square in the row,
 776                  * we copy the grid entry from the square above it,
 777                  * unless we're starting the new rectangle here.
 778                  */
 779                 for (x = 0; x < params2->w; x++) {
 780                     if (yx == where[x]) {
 781                         int val = index(params2, grid, x, y+1);
 782                         val %= params2->w;
 783                         val = INDEX(params3, val, y2);
 784                         index(params3, grid2, x, y2) = val;
 785                     } else
 786                         index(params3, grid2, x, y2) =
 787                         index(params3, grid2, x, y2-1);
 788                 }
 789
 790                 y2++;
 791             }
 792         }
 793
 794         sfree(expand);
 795         sfree(where);
 796
 797 #ifdef GENERATION_DIAGNOSTICS
 798         printf("after expansion:\n");
 799         display_grid(params3, grid2, NULL, TRUE);
 800 #endif
 801         /*
 802          * Transpose.
 803          */
 804         params2->w = params3->h;
 805         params2->h = params3->w;
 806         sfree(grid);
 807         grid = snewn(params2->w * params2->h, int);
 808         for (x = 0; x < params2->w; x++)
 809             for (y = 0; y < params2->h; y++) {
 810                 int idx1 = INDEX(params2, x, y);
 811                 int idx2 = INDEX(params3, y, x);
 812                 int tmp;
 813
 814                 tmp = grid2[idx2];
 815                 tmp = (tmp % params3->w) * params2->w + (tmp / params3->w);
 816                 grid[idx1] = tmp;
 817             }
 818
 819         sfree(grid2);
 820
 821         {
 822             int tmp;
 823             tmp = params->w;
 824             params->w = params->h;
 825             params->h = tmp;
 826         }
 827
 828 #ifdef GENERATION_DIAGNOSTICS
 829         printf("after transposition:\n");
 830         display_grid(params2, grid, NULL, TRUE);
 831 #endif
 832     }
 833
 834     /*
 835      * Place numbers.
 836      */
 837     numbers = snewn(params->w * params->h, int);
 838
 839     for (y = 0; y < params->h; y++)
 840         for (x = 0; x < params->w; x++) {
 841             index(params, numbers, x, y) = 0;
 842         }
 843
 844     for (x = 0; x < params->w; x++) {
 845         for (y = 0; y < params->h; y++) {
 846             int idx = INDEX(params, x, y);
 847             if (index(params, grid, x, y) == idx) {
 848                 struct rect r = find_rect(params, grid, x, y);
 849                 int n, xx, yy;
 850
 851                 /*
 852                  * Decide where to put the number.
 853                  */
 854                 n = random_upto(rs, r.w*r.h);
 855                 yy = n / r.w;
 856                 xx = n % r.w;
 857                 index(params,numbers,x+xx,y+yy) = r.w*r.h;
 858             }
 859         }
 860     }
 861
 862 #ifdef GENERATION_DIAGNOSTICS
 863     display_grid(params, grid, numbers, FALSE);
 864 #endif
 865
 866     seed = snewn(11 * params->w * params->h, char);
 867     p = seed;
 868     run = 0;
 869     for (i = 0; i <= params->w * params->h; i++) {
 870         int n = (i < params->w * params->h ? numbers[i] : -1);
 871
 872         if (!n)
 873             run++;
 874         else {
 875             if (run) {
 876                 while (run > 0) {
 877                     int c = 'a' - 1 + run;
 878                     if (run > 26)
 879                         c = 'z';
 880                     *p++ = c;
 881                     run -= c - ('a' - 1);
 882                 }
 883             } else {
 884                 /*
 885                  * If there's a number in the very top left or
 886                  * bottom right, there's no point putting an
 887                  * unnecessary _ before or after it.
 888                  */
 889                 if (p > seed && n > 0)
 890                     *p++ = '_';
 891             }
 892             if (n > 0)
 893                 p += sprintf(p, "%d", n);
 894             run = 0;
 895         }
 896     }
 897     *p = '\0';
 898
 899     sfree(grid);
 900     sfree(numbers);
 901
 902     return seed;
 903 }
 904
 905 char *validate_seed(game_params *params, char *seed)
 906 {
 907     int area = params->w * params->h;
 908     int squares = 0;
 909
 910     while (*seed) {
 911         int n = *seed++;
 912         if (n >= 'a' && n <= 'z') {
 913             squares += n - 'a' + 1;
 914         } else if (n == '_') {
 915             /* do nothing */;
 916         } else if (n > '0' && n <= '9') {
 917             squares++;
 918             while (*seed >= '0' && *seed <= '9')
 919                 seed++;
 920         } else
 921             return "Invalid character in game specification";
 922     }
 923
 924     if (squares < area)
 925         return "Not enough data to fill grid";
 926
 927     if (squares > area)
 928         return "Too much data to fit in grid";
 929
 930     return NULL;
 931 }
 932
 933 game_state *new_game(game_params *params, char *seed)
 934 {
 935     game_state *state = snew(game_state);
 936     int x, y, i, area;
 937
 938     state->w = params->w;
 939     state->h = params->h;
 940
 941     area = state->w * state->h;
 942
 943     state->grid = snewn(area, int);
 944     state->vedge = snewn(area, unsigned char);
 945     state->hedge = snewn(area, unsigned char);
 946     state->completed = FALSE;
 947
 948     i = 0;
 949     while (*seed) {
 950         int n = *seed++;
 951         if (n >= 'a' && n <= 'z') {
 952             int run = n - 'a' + 1;
 953             assert(i + run <= area);
 954             while (run-- > 0)
 955                 state->grid[i++] = 0;
 956         } else if (n == '_') {
 957             /* do nothing */;
 958         } else if (n > '0' && n <= '9') {
 959             assert(i < area);
 960             state->grid[i++] = atoi(seed-1);
 961             while (*seed >= '0' && *seed <= '9')
 962                 seed++;
 963         } else {
 964             assert(!"We can't get here");
 965         }
 966     }
 967     assert(i == area);
 968
 969     for (y = 0; y < state->h; y++)
 970         for (x = 0; x < state->w; x++)
 971             vedge(state,x,y) = hedge(state,x,y) = 0;
 972
 973     return state;
 974 }
 975
 976 game_state *dup_game(game_state *state)
 977 {
 978     game_state *ret = snew(game_state);
 979
 980     ret->w = state->w;
 981     ret->h = state->h;
 982
 983     ret->vedge = snewn(state->w * state->h, unsigned char);
 984     ret->hedge = snewn(state->w * state->h, unsigned char);
 985     ret->grid = snewn(state->w * state->h, int);
 986
 987     ret->completed = state->completed;
 988
 989     memcpy(ret->grid, state->grid, state->w * state->h * sizeof(int));
 990     memcpy(ret->vedge, state->vedge, state->w*state->h*sizeof(unsigned char));
 991     memcpy(ret->hedge, state->hedge, state->w*state->h*sizeof(unsigned char));
 992
 993     return ret;
 994 }
 995
 996 void free_game(game_state *state)
 997 {
 998     sfree(state->grid);
 999     sfree(state->vedge);
1000     sfree(state->hedge);
1001     sfree(state);
1002 }
1003
1004 static unsigned char *get_correct(game_state *state)
1005 {
1006     unsigned char *ret;
1007     int x, y;
1008
1009     ret = snewn(state->w * state->h, unsigned char);
1010     memset(ret, 0xFF, state->w * state->h);
1011
1012     for (x = 0; x < state->w; x++)
1013         for (y = 0; y < state->h; y++)
1014             if (index(state,ret,x,y) == 0xFF) {
1015                 int rw, rh;
1016                 int xx, yy;
1017                 int num, area, valid;
1018
1019                 /*
1020                  * Find a rectangle starting at this point.
1021                  */
1022                 rw = 1;
1023                 while (x+rw < state->w && !vedge(state,x+rw,y))
1024                     rw++;
1025                 rh = 1;
1026                 while (y+rh < state->h && !hedge(state,x,y+rh))
1027                     rh++;
1028
1029                 /*
1030                  * We know what the dimensions of the rectangle
1031                  * should be if it's there at all. Find out if we
1032                  * really have a valid rectangle.
1033                  */
1034                 valid = TRUE;
1035                 /* Check the horizontal edges. */
1036                 for (xx = x; xx < x+rw; xx++) {
1037                     for (yy = y; yy <= y+rh; yy++) {
1038                         int e = !HRANGE(state,xx,yy) || hedge(state,xx,yy);
1039                         int ec = (yy == y || yy == y+rh);
1040                         if (e != ec)
1041                             valid = FALSE;
1042                     }
1043                 }
1044                 /* Check the vertical edges. */
1045                 for (yy = y; yy < y+rh; yy++) {
1046                     for (xx = x; xx <= x+rw; xx++) {
1047                         int e = !VRANGE(state,xx,yy) || vedge(state,xx,yy);
1048                         int ec = (xx == x || xx == x+rw);
1049                         if (e != ec)
1050                             valid = FALSE;
1051                     }
1052                 }
1053
1054                 /*
1055                  * If this is not a valid rectangle with no other
1056                  * edges inside it, we just mark this square as not
1057                  * complete and proceed to the next square.
1058                  */
1059                 if (!valid) {
1060                     index(state, ret, x, y) = 0;
1061                     continue;
1062                 }
1063
1064                 /*
1065                  * We have a rectangle. Now see what its area is,
1066                  * and how many numbers are in it.
1067                  */
1068                 num = 0;
1069                 area = 0;
1070                 for (xx = x; xx < x+rw; xx++) {
1071                     for (yy = y; yy < y+rh; yy++) {
1072                         area++;
1073                         if (grid(state,xx,yy)) {
1074                             if (num > 0)
1075                                 valid = FALSE;   /* two numbers */
1076                             num = grid(state,xx,yy);
1077                         }
1078                     }
1079                 }
1080                 if (num != area)
1081                     valid = FALSE;
1082
1083                 /*
1084                  * Now fill in the whole rectangle based on the
1085                  * value of `valid'.
1086                  */
1087                 for (xx = x; xx < x+rw; xx++) {
1088                     for (yy = y; yy < y+rh; yy++) {
1089                         index(state, ret, xx, yy) = valid;
1090                     }
1091                 }
1092             }
1093
1094     return ret;
1095 }
1096
1097 struct game_ui {
1098     /*
1099      * These coordinates are 2 times the obvious grid coordinates.
1100      * Hence, the top left of the grid is (0,0), the grid point to
1101      * the right of that is (2,0), the one _below that_ is (2,2)
1102      * and so on. This is so that we can specify a drag start point
1103      * on an edge (one odd coordinate) or in the middle of a square
1104      * (two odd coordinates) rather than always at a corner.
1105      *
1106      * -1,-1 means no drag is in progress.
1107      */
1108     int drag_start_x;
1109     int drag_start_y;
1110     int drag_end_x;
1111     int drag_end_y;
1112     /*
1113      * This flag is set as soon as a dragging action moves the
1114      * mouse pointer away from its starting point, so that even if
1115      * the pointer _returns_ to its starting point the action is
1116      * treated as a small drag rather than a click.
1117      */
1118     int dragged;
1119 };
1120
1121 game_ui *new_ui(game_state *state)
1122 {
1123     game_ui *ui = snew(game_ui);
1124     ui->drag_start_x = -1;
1125     ui->drag_start_y = -1;
1126     ui->drag_end_x = -1;
1127     ui->drag_end_y = -1;
1128     ui->dragged = FALSE;
1129     return ui;
1130 }
1131
1132 void free_ui(game_ui *ui)
1133 {
1134     sfree(ui);
1135 }
1136
1137 void coord_round(float x, float y, int *xr, int *yr)
1138 {
1139     float xs, ys, xv, yv, dx, dy, dist;
1140
1141     /*
1142      * Find the nearest square-centre.
1143      */
1144     xs = (float)floor(x) + 0.5F;
1145     ys = (float)floor(y) + 0.5F;
1146
1147     /*
1148      * And find the nearest grid vertex.
1149      */
1150     xv = (float)floor(x + 0.5F);
1151     yv = (float)floor(y + 0.5F);
1152
1153     /*
1154      * We allocate clicks in parts of the grid square to either
1155      * corners, edges or square centres, as follows:
1156      *
1157      *   +--+--------+--+
1158      *   |  |        |  |
1159      *   +--+        +--+
1160      *   |   `.    ,'   |
1161      *   |     +--+     |
1162      *   |     |  |     |
1163      *   |     +--+     |
1164      *   |   ,'    `.   |
1165      *   +--+        +--+
1166      *   |  |        |  |
1167      *   +--+--------+--+
1168      *
1169      * (Not to scale!)
1170      *
1171      * In other words: we measure the square distance (i.e.
1172      * max(dx,dy)) from the click to the nearest corner, and if
1173      * it's within CORNER_TOLERANCE then we return a corner click.
1174      * We measure the square distance from the click to the nearest
1175      * centre, and if that's within CENTRE_TOLERANCE we return a
1176      * centre click. Failing that, we find which of the two edge
1177      * centres is nearer to the click and return that edge.
1178      */
1179
1180     /*
1181      * Check for corner click.
1182      */
1183     dx = (float)fabs(x - xv);
1184     dy = (float)fabs(y - yv);
1185     dist = (dx > dy ? dx : dy);
1186     if (dist < CORNER_TOLERANCE) {
1187         *xr = 2 * (int)xv;
1188         *yr = 2 * (int)yv;
1189     } else {
1190         /*
1191          * Check for centre click.
1192          */
1193         dx = (float)fabs(x - xs);
1194         dy = (float)fabs(y - ys);
1195         dist = (dx > dy ? dx : dy);
1196         if (dist < CENTRE_TOLERANCE) {
1197             *xr = 1 + 2 * (int)xs;
1198             *yr = 1 + 2 * (int)ys;
1199         } else {
1200             /*
1201              * Failing both of those, see which edge we're closer to.
1202              * Conveniently, this is simply done by testing the relative
1203              * magnitude of dx and dy (which are currently distances from
1204              * the square centre).
1205              */
1206             if (dx > dy) {
1207                 /* Vertical edge: x-coord of corner,
1208                  * y-coord of square centre. */
1209                 *xr = 2 * (int)xv;
1210                 *yr = 1 + 2 * (int)ys;
1211             } else {
1212                 /* Horizontal edge: x-coord of square centre,
1213                  * y-coord of corner. */
1214                 *xr = 1 + 2 * (int)xs;
1215                 *yr = 2 * (int)yv;
1216             }
1217         }
1218     }
1219 }
1220
1221 static void ui_draw_rect(game_state *state, game_ui *ui,
1222                          unsigned char *hedge, unsigned char *vedge, int c)
1223 {
1224     int x1, x2, y1, y2, x, y, t;
1225
1226     x1 = ui->drag_start_x;
1227     x2 = ui->drag_end_x;
1228     if (x2 < x1) { t = x1; x1 = x2; x2 = t; }
1229
1230     y1 = ui->drag_start_y;
1231     y2 = ui->drag_end_y;
1232     if (y2 < y1) { t = y1; y1 = y2; y2 = t; }
1233
1234     x1 = x1 / 2;               /* rounds down */
1235     x2 = (x2+1) / 2;           /* rounds up */
1236     y1 = y1 / 2;               /* rounds down */
1237     y2 = (y2+1) / 2;           /* rounds up */
1238
1239     /*
1240      * Draw horizontal edges of rectangles.
1241      */
1242     for (x = x1; x < x2; x++)
1243         for (y = y1; y <= y2; y++)
1244             if (HRANGE(state,x,y)) {
1245                 int val = index(state,hedge,x,y);
1246                 if (y == y1 || y == y2)
1247                     val = c;
1248                 else if (c == 1)
1249                     val = 0;
1250                 index(state,hedge,x,y) = val;
1251             }
1252
1253     /*
1254      * Draw vertical edges of rectangles.
1255      */
1256     for (y = y1; y < y2; y++)
1257         for (x = x1; x <= x2; x++)
1258             if (VRANGE(state,x,y)) {
1259                 int val = index(state,vedge,x,y);
1260                 if (x == x1 || x == x2)
1261                     val = c;
1262                 else if (c == 1)
1263                     val = 0;
1264                 index(state,vedge,x,y) = val;
1265             }
1266 }
1267
1268 game_state *make_move(game_state *from, game_ui *ui, int x, int y, int button)
1269 {
1270     int xc, yc;
1271     int startdrag = FALSE, enddrag = FALSE, active = FALSE;
1272     game_state *ret;
1273
1274     if (button == LEFT_BUTTON) {
1275         startdrag = TRUE;
1276     } else if (button == LEFT_RELEASE) {
1277         enddrag = TRUE;
1278     } else if (button != LEFT_DRAG) {
1279         return NULL;
1280     }
1281
1282     coord_round(FROMCOORD((float)x), FROMCOORD((float)y), &xc, &yc);
1283
1284     if (startdrag) {
1285         ui->drag_start_x = xc;
1286         ui->drag_start_y = yc;
1287         ui->drag_end_x = xc;
1288         ui->drag_end_y = yc;
1289         ui->dragged = FALSE;
1290         active = TRUE;
1291     }
1292
1293     if (xc != ui->drag_end_x || yc != ui->drag_end_y) {
1294         ui->drag_end_x = xc;
1295         ui->drag_end_y = yc;
1296         ui->dragged = TRUE;
1297         active = TRUE;
1298     }
1299
1300     ret = NULL;
1301
1302     if (enddrag) {
1303         if (xc >= 0 && xc <= 2*from->w &&
1304             yc >= 0 && yc <= 2*from->h) {
1305             ret = dup_game(from);
1306
1307             if (ui->dragged) {
1308                 ui_draw_rect(ret, ui, ret->hedge, ret->vedge, 1);
1309             } else {
1310                 if ((xc & 1) && !(yc & 1) && HRANGE(from,xc/2,yc/2)) {
1311                     hedge(ret,xc/2,yc/2) = !hedge(ret,xc/2,yc/2);
1312                 }
1313                 if ((yc & 1) && !(xc & 1) && VRANGE(from,xc/2,yc/2)) {
1314                     vedge(ret,xc/2,yc/2) = !vedge(ret,xc/2,yc/2);
1315                 }
1316             }
1317
1318             if (!memcmp(ret->hedge, from->hedge, from->w*from->h) &&
1319                 !memcmp(ret->vedge, from->vedge, from->w*from->h)) {
1320                 free_game(ret);
1321                 ret = NULL;
1322             }
1323
1324             /*
1325              * We've made a real change to the grid. Check to see
1326              * if the game has been completed.
1327              */
1328             if (ret && !ret->completed) {
1329                 int x, y, ok;
1330                 unsigned char *correct = get_correct(ret);
1331
1332                 ok = TRUE;
1333                 for (x = 0; x < ret->w; x++)
1334                     for (y = 0; y < ret->h; y++)
1335                         if (!index(ret, correct, x, y))
1336                             ok = FALSE;
1337
1338                 sfree(correct);
1339
1340                 if (ok)
1341                     ret->completed = TRUE;
1342             }
1343         }
1344
1345         ui->drag_start_x = -1;
1346         ui->drag_start_y = -1;
1347         ui->drag_end_x = -1;
1348         ui->drag_end_y = -1;
1349         ui->dragged = FALSE;
1350         active = TRUE;
1351     }
1352
1353     if (ret)
1354         return ret;                    /* a move has been made */
1355     else if (active)
1356         return from;                   /* UI activity has occurred */
1357     else
1358         return NULL;
1359 }
1360
1361 /* ----------------------------------------------------------------------
1362  * Drawing routines.
1363  */
1364
1365 #define CORRECT 65536
1366
1367 #define COLOUR(k) ( (k)==1 ? COL_LINE : COL_DRAG )
1368 #define MAX(x,y) ( (x)>(y) ? (x) : (y) )
1369 #define MAX4(x,y,z,w) ( MAX(MAX(x,y),MAX(z,w)) )
1370
1371 struct game_drawstate {
1372     int started;
1373     int w, h;
1374     unsigned int *visible;
1375 };
1376
1377 void game_size(game_params *params, int *x, int *y)
1378 {
1379     *x = params->w * TILE_SIZE + 2*BORDER + 1;
1380     *y = params->h * TILE_SIZE + 2*BORDER + 1;
1381 }
1382
1383 float *game_colours(frontend *fe, game_state *state, int *ncolours)
1384 {
1385     float *ret = snewn(3 * NCOLOURS, float);
1386
1387     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1388
1389     ret[COL_GRID * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1390     ret[COL_GRID * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1391     ret[COL_GRID * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
1392
1393     ret[COL_DRAG * 3 + 0] = 1.0F;
1394     ret[COL_DRAG * 3 + 1] = 0.0F;
1395     ret[COL_DRAG * 3 + 2] = 0.0F;
1396
1397     ret[COL_CORRECT * 3 + 0] = 0.75F * ret[COL_BACKGROUND * 3 + 0];
1398     ret[COL_CORRECT * 3 + 1] = 0.75F * ret[COL_BACKGROUND * 3 + 1];
1399     ret[COL_CORRECT * 3 + 2] = 0.75F * ret[COL_BACKGROUND * 3 + 2];
1400
1401     ret[COL_LINE * 3 + 0] = 0.0F;
1402     ret[COL_LINE * 3 + 1] = 0.0F;
1403     ret[COL_LINE * 3 + 2] = 0.0F;
1404
1405     ret[COL_TEXT * 3 + 0] = 0.0F;
1406     ret[COL_TEXT * 3 + 1] = 0.0F;
1407     ret[COL_TEXT * 3 + 2] = 0.0F;
1408
1409     *ncolours = NCOLOURS;
1410     return ret;
1411 }
1412
1413 game_drawstate *game_new_drawstate(game_state *state)
1414 {
1415     struct game_drawstate *ds = snew(struct game_drawstate);
1416     int i;
1417
1418     ds->started = FALSE;
1419     ds->w = state->w;
1420     ds->h = state->h;
1421     ds->visible = snewn(ds->w * ds->h, unsigned int);
1422     for (i = 0; i < ds->w * ds->h; i++)
1423         ds->visible[i] = 0xFFFF;
1424
1425     return ds;
1426 }
1427
1428 void game_free_drawstate(game_drawstate *ds)
1429 {
1430     sfree(ds->visible);
1431     sfree(ds);
1432 }
1433
1434 void draw_tile(frontend *fe, game_state *state, int x, int y,
1435                unsigned char *hedge, unsigned char *vedge,
1436                unsigned char *corners, int correct)
1437 {
1438     int cx = COORD(x), cy = COORD(y);
1439     char str[80];
1440
1441     draw_rect(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1, COL_GRID);
1442     draw_rect(fe, cx+1, cy+1, TILE_SIZE-1, TILE_SIZE-1,
1443               correct ? COL_CORRECT : COL_BACKGROUND);
1444
1445     if (grid(state,x,y)) {
1446         sprintf(str, "%d", grid(state,x,y));
1447         draw_text(fe, cx+TILE_SIZE/2, cy+TILE_SIZE/2, FONT_VARIABLE,
1448                   TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, COL_TEXT, str);
1449     }
1450
1451     /*
1452      * Draw edges.
1453      */
1454     if (!HRANGE(state,x,y) || index(state,hedge,x,y))
1455         draw_rect(fe, cx, cy, TILE_SIZE+1, 2,
1456                   HRANGE(state,x,y) ? COLOUR(index(state,hedge,x,y)) :
1457                   COL_LINE);
1458     if (!HRANGE(state,x,y+1) || index(state,hedge,x,y+1))
1459         draw_rect(fe, cx, cy+TILE_SIZE-1, TILE_SIZE+1, 2,
1460                   HRANGE(state,x,y+1) ? COLOUR(index(state,hedge,x,y+1)) :
1461                   COL_LINE);
1462     if (!VRANGE(state,x,y) || index(state,vedge,x,y))
1463         draw_rect(fe, cx, cy, 2, TILE_SIZE+1,
1464                   VRANGE(state,x,y) ? COLOUR(index(state,vedge,x,y)) :
1465                   COL_LINE);
1466     if (!VRANGE(state,x+1,y) || index(state,vedge,x+1,y))
1467         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, TILE_SIZE+1,
1468                   VRANGE(state,x+1,y) ? COLOUR(index(state,vedge,x+1,y)) :
1469                   COL_LINE);
1470
1471     /*
1472      * Draw corners.
1473      */
1474     if (index(state,corners,x,y))
1475         draw_rect(fe, cx, cy, 2, 2,
1476                   COLOUR(index(state,corners,x,y)));
1477     if (x+1 < state->w && index(state,corners,x+1,y))
1478         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, 2,
1479                   COLOUR(index(state,corners,x+1,y)));
1480     if (y+1 < state->h && index(state,corners,x,y+1))
1481         draw_rect(fe, cx, cy+TILE_SIZE-1, 2, 2,
1482                   COLOUR(index(state,corners,x,y+1)));
1483     if (x+1 < state->w && y+1 < state->h && index(state,corners,x+1,y+1))
1484         draw_rect(fe, cx+TILE_SIZE-1, cy+TILE_SIZE-1, 2, 2,
1485                   COLOUR(index(state,corners,x+1,y+1)));
1486
1487     draw_update(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1);
1488 }
1489
1490 void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1491                  game_state *state, int dir, game_ui *ui,
1492                  float animtime, float flashtime)
1493 {
1494     int x, y;
1495     unsigned char *correct;
1496     unsigned char *hedge, *vedge, *corners;
1497
1498     correct = get_correct(state);
1499
1500     if (ui->dragged) {
1501         hedge = snewn(state->w*state->h, unsigned char);
1502         vedge = snewn(state->w*state->h, unsigned char);
1503         memcpy(hedge, state->hedge, state->w*state->h);
1504         memcpy(vedge, state->vedge, state->w*state->h);
1505         ui_draw_rect(state, ui, hedge, vedge, 2);
1506     } else {
1507         hedge = state->hedge;
1508         vedge = state->vedge;
1509     }
1510
1511     corners = snewn(state->w * state->h, unsigned char);
1512     memset(corners, 0, state->w * state->h);
1513     for (x = 0; x < state->w; x++)
1514         for (y = 0; y < state->h; y++) {
1515             if (x > 0) {
1516                 int e = index(state, vedge, x, y);
1517                 if (index(state,corners,x,y) < e)
1518                     index(state,corners,x,y) = e;
1519                 if (y+1 < state->h &&
1520                     index(state,corners,x,y+1) < e)
1521                     index(state,corners,x,y+1) = e;
1522             }
1523             if (y > 0) {
1524                 int e = index(state, hedge, x, y);
1525                 if (index(state,corners,x,y) < e)
1526                     index(state,corners,x,y) = e;
1527                 if (x+1 < state->w &&
1528                     index(state,corners,x+1,y) < e)
1529                     index(state,corners,x+1,y) = e;
1530             }
1531         }
1532
1533     if (!ds->started) {
1534         draw_rect(fe, 0, 0,
1535                   state->w * TILE_SIZE + 2*BORDER + 1,
1536                   state->h * TILE_SIZE + 2*BORDER + 1, COL_BACKGROUND);
1537         draw_rect(fe, COORD(0)-1, COORD(0)-1,
1538                   ds->w*TILE_SIZE+3, ds->h*TILE_SIZE+3, COL_LINE);
1539         ds->started = TRUE;
1540         draw_update(fe, 0, 0,
1541                     state->w * TILE_SIZE + 2*BORDER + 1,
1542                     state->h * TILE_SIZE + 2*BORDER + 1);
1543     }
1544
1545     for (x = 0; x < state->w; x++)
1546         for (y = 0; y < state->h; y++) {
1547             unsigned int c = 0;
1548
1549             if (HRANGE(state,x,y))
1550                 c |= index(state,hedge,x,y);
1551             if (HRANGE(state,x,y+1))
1552                 c |= index(state,hedge,x,y+1) << 2;
1553             if (VRANGE(state,x,y))
1554                 c |= index(state,vedge,x,y) << 4;
1555             if (VRANGE(state,x+1,y))
1556                 c |= index(state,vedge,x+1,y) << 6;
1557             c |= index(state,corners,x,y) << 8;
1558             if (x+1 < state->w)
1559                 c |= index(state,corners,x+1,y) << 10;
1560             if (y+1 < state->h)
1561                 c |= index(state,corners,x,y+1) << 12;
1562             if (x+1 < state->w && y+1 < state->h)
1563                 c |= index(state,corners,x+1,y+1) << 14;
1564             if (index(state, correct, x, y) && !flashtime)
1565                 c |= CORRECT;
1566
1567             if (index(ds,ds->visible,x,y) != c) {
1568                 draw_tile(fe, state, x, y, hedge, vedge, corners, c & CORRECT);
1569                 index(ds,ds->visible,x,y) = c;
1570             }
1571         }
1572
1573     if (hedge != state->hedge) {
1574         sfree(hedge);
1575         sfree(vedge);
1576    }
1577
1578     sfree(corners);
1579     sfree(correct);
1580 }
1581
1582 float game_anim_length(game_state *oldstate, game_state *newstate, int dir)
1583 {
1584     return 0.0F;
1585 }
1586
1587 float game_flash_length(game_state *oldstate, game_state *newstate, int dir)
1588 {
1589     if (!oldstate->completed && newstate->completed)
1590         return FLASH_TIME;
1591     return 0.0F;
1592 }
1593
1594 int game_wants_statusbar(void)
1595 {
1596     return FALSE;
1597 }