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  *  - During redraw, do corner analysis centrally in game_redraw()
  33  *    itself so that we can take it into account when computing the
  34  *    `visible' array. If we can do this, we can actually _turn on_
  35  *    the `visible' processing and keep redraws to the minimum
  36  *    required.
  37  */
  38
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <string.h>
  42 #include <assert.h>
  43 #include <math.h>
  44
  45 #include "puzzles.h"
  46
  47 const char *const game_name = "Rectangles";
  48 const int game_can_configure = TRUE;
  49
  50 enum {
  51     COL_BACKGROUND,
  52     COL_CORRECT,
  53     COL_LINE,
  54     COL_TEXT,
  55     COL_GRID,
  56     COL_DRAG,
  57     NCOLOURS
  58 };
  59
  60 struct game_params {
  61     int w, h;
  62 };
  63
  64 #define INDEX(state, x, y)    (((y) * (state)->w) + (x))
  65 #define index(state, a, x, y) ((a) [ INDEX(state,x,y) ])
  66 #define grid(state,x,y)       index(state, (state)->grid, x, y)
  67 #define vedge(state,x,y)      index(state, (state)->vedge, x, y)
  68 #define hedge(state,x,y)      index(state, (state)->hedge, x, y)
  69
  70 #define CRANGE(state,x,y,dx,dy) ( (x) >= dx && (x) < (state)->w && \
  71                                 (y) >= dy && (y) < (state)->h )
  72 #define RANGE(state,x,y)  CRANGE(state,x,y,0,0)
  73 #define HRANGE(state,x,y) CRANGE(state,x,y,0,1)
  74 #define VRANGE(state,x,y) CRANGE(state,x,y,1,0)
  75
  76 #define TILE_SIZE 24
  77 #define BORDER 18
  78
  79 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
  80 #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE )
  81
  82 struct game_state {
  83     int w, h;
  84     int *grid;                         /* contains the numbers */
  85     unsigned char *vedge;              /* (w+1) x h */
  86     unsigned char *hedge;              /* w x (h+1) */
  87 };
  88
  89 game_params *default_params(void)
  90 {
  91     game_params *ret = snew(game_params);
  92
  93     ret->w = ret->h = 7;
  94
  95     return ret;
  96 }
  97
  98 int game_fetch_preset(int i, char **name, game_params **params)
  99 {
 100     game_params *ret;
 101     int w, h;
 102     char buf[80];
 103
 104     switch (i) {
 105       case 0: w = 7, h = 7; break;
 106       case 1: w = 11, h = 11; break;
 107       case 2: w = 15, h = 15; break;
 108       case 3: w = 19, h = 19; break;
 109       default: return FALSE;
 110     }
 111
 112     sprintf(buf, "%dx%d", w, h);
 113     *name = dupstr(buf);
 114     *params = ret = snew(game_params);
 115     ret->w = w;
 116     ret->h = h;
 117     return TRUE;
 118 }
 119
 120 void free_params(game_params *params)
 121 {
 122     sfree(params);
 123 }
 124
 125 game_params *dup_params(game_params *params)
 126 {
 127     game_params *ret = snew(game_params);
 128     *ret = *params;                    /* structure copy */
 129     return ret;
 130 }
 131
 132 config_item *game_configure(game_params *params)
 133 {
 134     config_item *ret;
 135     char buf[80];
 136
 137     ret = snewn(5, config_item);
 138
 139     ret[0].name = "Width";
 140     ret[0].type = C_STRING;
 141     sprintf(buf, "%d", params->w);
 142     ret[0].sval = dupstr(buf);
 143     ret[0].ival = 0;
 144
 145     ret[1].name = "Height";
 146     ret[1].type = C_STRING;
 147     sprintf(buf, "%d", params->h);
 148     ret[1].sval = dupstr(buf);
 149     ret[1].ival = 0;
 150
 151     ret[2].name = NULL;
 152     ret[2].type = C_END;
 153     ret[2].sval = NULL;
 154     ret[2].ival = 0;
 155
 156     return ret;
 157 }
 158
 159 game_params *custom_params(config_item *cfg)
 160 {
 161     game_params *ret = snew(game_params);
 162
 163     ret->w = atoi(cfg[0].sval);
 164     ret->h = atoi(cfg[1].sval);
 165
 166     return ret;
 167 }
 168
 169 char *validate_params(game_params *params)
 170 {
 171     if (params->w <= 0 && params->h <= 0)
 172         return "Width and height must both be greater than zero";
 173     if (params->w * params->h < 4)
 174         return "Total area must be at least 4";
 175     return NULL;
 176 }
 177
 178 struct rect {
 179     int x, y;
 180     int w, h;
 181 };
 182
 183 struct rectlist {
 184     struct rect *rects;
 185     int n;
 186 };
 187
 188 static struct rectlist *get_rectlist(game_params *params, int *grid)
 189 {
 190     int rw, rh;
 191     int x, y;
 192     int maxarea;
 193     struct rect *rects = NULL;
 194     int nrects = 0, rectsize = 0;
 195
 196     /*
 197      * Maximum rectangle area is 1/6 of total grid size.
 198      */
 199     maxarea = params->w * params->h / 6;
 200
 201     for (rw = 1; rw <= params->w; rw++)
 202         for (rh = 1; rh <= params->h; rh++) {
 203             if (rw * rh > maxarea)
 204                 continue;
 205             if (rw * rh == 1)
 206                 continue;
 207             for (x = 0; x <= params->w - rw; x++)
 208                 for (y = 0; y <= params->h - rh; y++) {
 209                     /*
 210                      * We have a candidate rectangle placement. See
 211                      * if it's unobstructed.
 212                      */
 213                     int xx, yy;
 214                     int ok;
 215
 216                     ok = TRUE;
 217                     for (xx = x; xx < x+rw; xx++)
 218                         for (yy = y; yy < y+rh; yy++)
 219                             if (index(params, grid, xx, yy) >= 0) {
 220                                 ok = FALSE;
 221                                 goto break1;   /* break both loops at once */
 222                             }
 223                     break1:
 224
 225                     if (!ok)
 226                         continue;
 227
 228                     if (nrects >= rectsize) {
 229                         rectsize = nrects + 256;
 230                         rects = sresize(rects, rectsize, struct rect);
 231                     }
 232
 233                     rects[nrects].x = x;
 234                     rects[nrects].y = y;
 235                     rects[nrects].w = rw;
 236                     rects[nrects].h = rh;
 237                     nrects++;
 238                 }
 239         }
 240
 241     if (nrects > 0) {
 242         struct rectlist *ret;
 243         ret = snew(struct rectlist);
 244         ret->rects = rects;
 245         ret->n = nrects;
 246         return ret;
 247     } else {
 248         assert(rects == NULL);         /* hence no need to free */
 249         return NULL;
 250     }
 251 }
 252
 253 static void free_rectlist(struct rectlist *list)
 254 {
 255     sfree(list->rects);
 256     sfree(list);
 257 }
 258
 259 static void place_rect(game_params *params, int *grid, struct rect r)
 260 {
 261     int idx = INDEX(params, r.x, r.y);
 262     int x, y;
 263
 264     for (x = r.x; x < r.x+r.w; x++)
 265         for (y = r.y; y < r.y+r.h; y++) {
 266             index(params, grid, x, y) = idx;
 267         }
 268 #ifdef GENERATION_DIAGNOSTICS
 269     printf("    placing rectangle at (%d,%d) size %d x %d\n",
 270            r.x, r.y, r.w, r.h);
 271 #endif
 272 }
 273
 274 static struct rect find_rect(game_params *params, int *grid, int x, int y)
 275 {
 276     int idx, w, h;
 277     struct rect r;
 278
 279     /*
 280      * Find the top left of the rectangle.
 281      */
 282     idx = index(params, grid, x, y);
 283
 284     if (idx < 0) {
 285         r.x = x;
 286         r.y = y;
 287         r.w = r.h = 1;
 288         return r;                      /* 1x1 singleton here */
 289     }
 290
 291     y = idx / params->w;
 292     x = idx % params->w;
 293
 294     /*
 295      * Find the width and height of the rectangle.
 296      */
 297     for (w = 1;
 298          (x+w < params->w && index(params,grid,x+w,y)==idx);
 299          w++);
 300     for (h = 1;
 301          (y+h < params->h && index(params,grid,x,y+h)==idx);
 302          h++);
 303
 304     r.x = x;
 305     r.y = y;
 306     r.w = w;
 307     r.h = h;
 308
 309     return r;
 310 }
 311
 312 #ifdef GENERATION_DIAGNOSTICS
 313 static void display_grid(game_params *params, int *grid, int *numbers)
 314 {
 315     unsigned char *egrid = snewn((params->w*2+3) * (params->h*2+3),
 316                                  unsigned char);
 317     memset(egrid, 0, (params->w*2+3) * (params->h*2+3));
 318     int x, y;
 319     int r = (params->w*2+3);
 320
 321     for (x = 0; x < params->w; x++)
 322         for (y = 0; y < params->h; y++) {
 323             int i = index(params, grid, x, y);
 324             if (x == 0 || index(params, grid, x-1, y) != i)
 325                 egrid[(2*y+2) * r + (2*x+1)] = 1;
 326             if (x == params->w-1 || index(params, grid, x+1, y) != i)
 327                 egrid[(2*y+2) * r + (2*x+3)] = 1;
 328             if (y == 0 || index(params, grid, x, y-1) != i)
 329                 egrid[(2*y+1) * r + (2*x+2)] = 1;
 330             if (y == params->h-1 || index(params, grid, x, y+1) != i)
 331                 egrid[(2*y+3) * r + (2*x+2)] = 1;
 332         }
 333
 334     for (y = 1; y < 2*params->h+2; y++) {
 335         for (x = 1; x < 2*params->w+2; x++) {
 336             if (!((y|x)&1)) {
 337                 int k = index(params, numbers, x/2-1, y/2-1);
 338                 if (k) printf("%2d", k); else printf("  ");
 339             } else if (!((y&x)&1)) {
 340                 int v = egrid[y*r+x];
 341                 if ((y&1) && v) v = '-';
 342                 if ((x&1) && v) v = '|';
 343                 if (!v) v = ' ';
 344                 putchar(v);
 345                 if (!(x&1)) putchar(v);
 346             } else {
 347                 int c, d = 0;
 348                 if (egrid[y*r+(x+1)]) d |= 1;
 349                 if (egrid[(y-1)*r+x]) d |= 2;
 350                 if (egrid[y*r+(x-1)]) d |= 4;
 351                 if (egrid[(y+1)*r+x]) d |= 8;
 352                 c = " ??+?-++?+|+++++"[d];
 353                 putchar(c);
 354                 if (!(x&1)) putchar(c);
 355             }
 356         }
 357         putchar('\n');
 358     }
 359
 360     sfree(egrid);
 361 }
 362 #endif
 363
 364 char *new_game_seed(game_params *params, random_state *rs)
 365 {
 366     int *grid, *numbers;
 367     struct rectlist *list;
 368     int x, y, run, i;
 369     char *seed, *p;
 370
 371     grid = snewn(params->w * params->h, int);
 372     numbers = snewn(params->w * params->h, int);
 373
 374     for (y = 0; y < params->h; y++)
 375         for (x = 0; x < params->w; x++) {
 376             index(params, grid, x, y) = -1;
 377             index(params, numbers, x, y) = 0;
 378         }
 379
 380     list = get_rectlist(params, grid);
 381     assert(list != NULL);
 382
 383     /*
 384      * Place rectangles until we can't any more.
 385      */
 386     while (list->n > 0) {
 387         int i, m;
 388         struct rect r;
 389
 390         /*
 391          * Pick a random rectangle.
 392          */
 393         i = random_upto(rs, list->n);
 394         r = list->rects[i];
 395
 396         /*
 397          * Place it.
 398          */
 399         place_rect(params, grid, r);
 400
 401         /*
 402          * Winnow the list by removing any rectangles which
 403          * overlap this one.
 404          */
 405         m = 0;
 406         for (i = 0; i < list->n; i++) {
 407             struct rect s = list->rects[i];
 408             if (s.x+s.w <= r.x || r.x+r.w <= s.x ||
 409                 s.y+s.h <= r.y || r.y+r.h <= s.y)
 410                 list->rects[m++] = s;
 411         }
 412         list->n = m;
 413     }
 414
 415     free_rectlist(list);
 416
 417     /*
 418      * Deal with singleton spaces remaining in the grid, one by
 419      * one.
 420      *
 421      * We do this by making a local change to the layout. There are
 422      * several possibilities:
 423      *
 424      *     +-----+-----+    Here, we can remove the singleton by
 425      *     |     |     |    extending the 1x2 rectangle below it
 426      *     +--+--+-----+    into a 1x3.
 427      *     |  |  |     |
 428      *     |  +--+     |
 429      *     |  |  |     |
 430      *     |  |  |     |
 431      *     |  |  |     |
 432      *     +--+--+-----+
 433      *
 434      *     +--+--+--+       Here, that trick doesn't work: there's no
 435      *     |     |  |       1 x n rectangle with the singleton at one
 436      *     |     |  |       end. Instead, we extend a 1 x n rectangle
 437      *     |     |  |       _out_ from the singleton, shaving a layer
 438      *     +--+--+  |       off the end of another rectangle. So if we
 439      *     |  |  |  |       extended up, we'd make our singleton part
 440      *     |  +--+--+       of a 1x3 and generate a 1x2 where the 2x2
 441      *     |  |     |       used to be; or we could extend right into
 442      *     +--+-----+       a 2x1, turning the 1x3 into a 1x2.
 443      *
 444      *     +-----+--+       Here, we can't even do _that_, since any
 445      *     |     |  |       direction we choose to extend the singleton
 446      *     +--+--+  |       will produce a new singleton as a result of
 447      *     |  |  |  |       truncating one of the size-2 rectangles.
 448      *     |  +--+--+       Fortunately, this case can _only_ occur when
 449      *     |  |     |       a singleton is surrounded by four size-2s
 450      *     +--+-----+       in this fashion; so instead we can simply
 451      *                      replace the whole section with a single 3x3.
 452      */
 453     for (x = 0; x < params->w; x++) {
 454         for (y = 0; y < params->h; y++) {
 455             if (index(params, grid, x, y) < 0) {
 456                 int dirs[4], ndirs;
 457
 458 #ifdef GENERATION_DIAGNOSTICS
 459                 display_grid(params, grid, numbers);
 460                 printf("singleton at %d,%d\n", x, y);
 461 #endif
 462
 463                 /*
 464                  * Check in which directions we can feasibly extend
 465                  * the singleton. We can extend in a particular
 466                  * direction iff either:
 467                  *
 468                  *  - the rectangle on that side of the singleton
 469                  *    is not 2x1, and we are at one end of the edge
 470                  *    of it we are touching
 471                  *
 472                  *  - it is 2x1 but we are on its short side.
 473                  *
 474                  * FIXME: we could plausibly choose between these
 475                  * based on the sizes of the rectangles they would
 476                  * create?
 477                  */
 478                 ndirs = 0;
 479                 if (x < params->w-1) {
 480                     struct rect r = find_rect(params, grid, x+1, y);
 481                     if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
 482                         dirs[ndirs++] = 1;   /* right */
 483                 }
 484                 if (y > 0) {
 485                     struct rect r = find_rect(params, grid, x, y-1);
 486                     if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
 487                         dirs[ndirs++] = 2;   /* up */
 488                 }
 489                 if (x > 0) {
 490                     struct rect r = find_rect(params, grid, x-1, y);
 491                     if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
 492                         dirs[ndirs++] = 4;   /* left */
 493                 }
 494                 if (y < params->h-1) {
 495                     struct rect r = find_rect(params, grid, x, y+1);
 496                     if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
 497                         dirs[ndirs++] = 8;   /* down */
 498                 }
 499
 500                 if (ndirs > 0) {
 501                     int which, dir;
 502                     struct rect r1, r2;
 503
 504                     which = random_upto(rs, ndirs);
 505                     dir = dirs[which];
 506
 507                     switch (dir) {
 508                       case 1:          /* right */
 509                         assert(x < params->w+1);
 510 #ifdef GENERATION_DIAGNOSTICS
 511                         printf("extending right\n");
 512 #endif
 513                         r1 = find_rect(params, grid, x+1, y);
 514                         r2.x = x;
 515                         r2.y = y;
 516                         r2.w = 1 + r1.w;
 517                         r2.h = 1;
 518                         if (r1.y == y)
 519                             r1.y++;
 520                         r1.h--;
 521                         break;
 522                       case 2:          /* up */
 523                         assert(y > 0);
 524 #ifdef GENERATION_DIAGNOSTICS
 525                         printf("extending up\n");
 526 #endif
 527                         r1 = find_rect(params, grid, x, y-1);
 528                         r2.x = x;
 529                         r2.y = r1.y;
 530                         r2.w = 1;
 531                         r2.h = 1 + r1.h;
 532                         if (r1.x == x)
 533                             r1.x++;
 534                         r1.w--;
 535                         break;
 536                       case 4:          /* left */
 537                         assert(x > 0);
 538 #ifdef GENERATION_DIAGNOSTICS
 539                         printf("extending left\n");
 540 #endif
 541                         r1 = find_rect(params, grid, x-1, y);
 542                         r2.x = r1.x;
 543                         r2.y = y;
 544                         r2.w = 1 + r1.w;
 545                         r2.h = 1;
 546                         if (r1.y == y)
 547                             r1.y++;
 548                         r1.h--;
 549                         break;
 550                       case 8:          /* down */
 551                         assert(y < params->h+1);
 552 #ifdef GENERATION_DIAGNOSTICS
 553                         printf("extending down\n");
 554 #endif
 555                         r1 = find_rect(params, grid, x, y+1);
 556                         r2.x = x;
 557                         r2.y = y;
 558                         r2.w = 1;
 559                         r2.h = 1 + r1.h;
 560                         if (r1.x == x)
 561                             r1.x++;
 562                         r1.w--;
 563                         break;
 564                     }
 565                     if (r1.h > 0 && r1.w > 0)
 566                         place_rect(params, grid, r1);
 567                     place_rect(params, grid, r2);
 568                 } else {
 569 #ifndef NDEBUG
 570                     /*
 571                      * Sanity-check that there really is a 3x3
 572                      * rectangle surrounding this singleton and it
 573                      * contains absolutely everything we could
 574                      * possibly need.
 575                      */
 576                     {
 577                         int xx, yy;
 578                         assert(x > 0 && x < params->w-1);
 579                         assert(y > 0 && y < params->h-1);
 580
 581                         for (xx = x-1; xx <= x+1; xx++)
 582                             for (yy = y-1; yy <= y+1; yy++) {
 583                                 struct rect r = find_rect(params,grid,xx,yy);
 584                                 assert(r.x >= x-1);
 585                                 assert(r.y >= y-1);
 586                                 assert(r.x+r.w-1 <= x+1);
 587                                 assert(r.y+r.h-1 <= y+1);
 588                             }
 589                     }
 590 #endif
 591
 592 #ifdef GENERATION_DIAGNOSTICS
 593                     printf("need the 3x3 trick\n");
 594 #endif
 595
 596                     /*
 597                      * FIXME: If the maximum rectangle area for
 598                      * this grid is less than 9, we ought to
 599                      * subdivide the 3x3 in some fashion. There are
 600                      * five other possibilities:
 601                      *
 602                      *  - a 6 and a 3
 603                      *  - a 4, a 3 and a 2
 604                      *  - three 3s
 605                      *  - a 3 and three 2s (two different arrangements).
 606                      */
 607
 608                     {
 609                         struct rect r;
 610                         r.x = x-1;
 611                         r.y = y-1;
 612                         r.w = r.h = 3;
 613                         place_rect(params, grid, r);
 614                     }
 615                 }
 616             }
 617         }
 618     }
 619
 620     /*
 621      * Place numbers.
 622      */
 623     for (x = 0; x < params->w; x++) {
 624         for (y = 0; y < params->h; y++) {
 625             int idx = INDEX(params, x, y);
 626             if (index(params, grid, x, y) == idx) {
 627                 struct rect r = find_rect(params, grid, x, y);
 628                 int n, xx, yy;
 629
 630                 /*
 631                  * Decide where to put the number.
 632                  */
 633                 n = random_upto(rs, r.w*r.h);
 634                 yy = n / r.w;
 635                 xx = n % r.w;
 636                 index(params,numbers,x+xx,y+yy) = r.w*r.h;
 637             }
 638         }
 639     }
 640
 641 #ifdef GENERATION_DIAGNOSTICS
 642     display_grid(params, grid, numbers);
 643 #endif
 644
 645     seed = snewn(11 * params->w * params->h, char);
 646     p = seed;
 647     run = 0;
 648     for (i = 0; i <= params->w * params->h; i++) {
 649         int n = (i < params->w * params->h ? numbers[i] : -1);
 650
 651         if (!n)
 652             run++;
 653         else {
 654             if (run) {
 655                 while (run > 0) {
 656                     int c = 'a' - 1 + run;
 657                     if (run > 26)
 658                         c = 'z';
 659                     *p++ = c;
 660                     run -= c - ('a' - 1);
 661                 }
 662             } else {
 663                 *p++ = '_';
 664             }
 665             if (n > 0)
 666                 p += sprintf(p, "%d", n);
 667             run = 0;
 668         }
 669     }
 670     *p = '\0';
 671
 672     sfree(grid);
 673     sfree(numbers);
 674
 675     return seed;
 676 }
 677
 678 char *validate_seed(game_params *params, char *seed)
 679 {
 680     int area = params->w * params->h;
 681     int squares = 0;
 682
 683     while (*seed) {
 684         int n = *seed++;
 685         if (n >= 'a' && n <= 'z') {
 686             squares += n - 'a' + 1;
 687         } else if (n == '_') {
 688             /* do nothing */;
 689         } else if (n > '0' && n <= '9') {
 690             squares += atoi(seed-1);
 691             while (*seed >= '0' && *seed <= '9')
 692                 seed++;
 693         } else
 694             return "Invalid character in game specification";
 695     }
 696
 697     if (squares < area)
 698         return "Not enough data to fill grid";
 699
 700     if (squares > area)
 701         return "Too much data to fit in grid";
 702
 703     return NULL;
 704 }
 705
 706 game_state *new_game(game_params *params, char *seed)
 707 {
 708     game_state *state = snew(game_state);
 709     int x, y, i, area;
 710
 711     state->w = params->w;
 712     state->h = params->h;
 713
 714     area = state->w * state->h;
 715
 716     state->grid = snewn(area, int);
 717     state->vedge = snewn(area, unsigned char);
 718     state->hedge = snewn(area, unsigned char);
 719
 720     i = 0;
 721     while (*seed) {
 722         int n = *seed++;
 723         if (n >= 'a' && n <= 'z') {
 724             int run = n - 'a' + 1;
 725             assert(i + run <= area);
 726             while (run-- > 0)
 727                 state->grid[i++] = 0;
 728         } else if (n == '_') {
 729             /* do nothing */;
 730         } else if (n > '0' && n <= '9') {
 731             assert(i < area);
 732             state->grid[i++] = atoi(seed-1);
 733             while (*seed >= '0' && *seed <= '9')
 734                 seed++;
 735         } else {
 736             assert(!"We can't get here");
 737         }
 738     }
 739     assert(i == area);
 740
 741     for (y = 0; y < state->h; y++)
 742         for (x = 0; x < state->w; x++)
 743             vedge(state,x,y) = hedge(state,x,y) = 0;
 744
 745     return state;
 746 }
 747
 748 game_state *dup_game(game_state *state)
 749 {
 750     game_state *ret = snew(game_state);
 751
 752     ret->w = state->w;
 753     ret->h = state->h;
 754
 755     ret->vedge = snewn(state->w * state->h, unsigned char);
 756     ret->hedge = snewn(state->w * state->h, unsigned char);
 757     ret->grid = snewn(state->w * state->h, int);
 758
 759     memcpy(ret->grid, state->grid, state->w * state->h * sizeof(int));
 760     memcpy(ret->vedge, state->vedge, state->w*state->h*sizeof(unsigned char));
 761     memcpy(ret->hedge, state->hedge, state->w*state->h*sizeof(unsigned char));
 762
 763     return ret;
 764 }
 765
 766 void free_game(game_state *state)
 767 {
 768     sfree(state->grid);
 769     sfree(state->vedge);
 770     sfree(state->hedge);
 771     sfree(state);
 772 }
 773
 774 static unsigned char *get_correct(game_state *state)
 775 {
 776     unsigned char *ret;
 777     int x, y;
 778
 779     ret = snewn(state->w * state->h, unsigned char);
 780     memset(ret, 0xFF, state->w * state->h);
 781
 782     for (x = 0; x < state->w; x++)
 783         for (y = 0; y < state->h; y++)
 784             if (index(state,ret,x,y) == 0xFF) {
 785                 int rw, rh;
 786                 int xx, yy;
 787                 int num, area, valid;
 788
 789                 /*
 790                  * Find a rectangle starting at this point.
 791                  */
 792                 rw = 1;
 793                 while (x+rw < state->w && !vedge(state,x+rw,y))
 794                     rw++;
 795                 rh = 1;
 796                 while (y+rh < state->h && !hedge(state,x,y+rh))
 797                     rh++;
 798
 799                 /*
 800                  * We know what the dimensions of the rectangle
 801                  * should be if it's there at all. Find out if we
 802                  * really have a valid rectangle.
 803                  */
 804                 valid = TRUE;
 805                 /* Check the horizontal edges. */
 806                 for (xx = x; xx < x+rw; xx++) {
 807                     for (yy = y; yy <= y+rh; yy++) {
 808                         int e = !HRANGE(state,xx,yy) || hedge(state,xx,yy);
 809                         int ec = (yy == y || yy == y+rh);
 810                         if (e != ec)
 811                             valid = FALSE;
 812                     }
 813                 }
 814                 /* Check the vertical edges. */
 815                 for (yy = y; yy < y+rh; yy++) {
 816                     for (xx = x; xx <= x+rw; xx++) {
 817                         int e = !VRANGE(state,xx,yy) || vedge(state,xx,yy);
 818                         int ec = (xx == x || xx == x+rw);
 819                         if (e != ec)
 820                             valid = FALSE;
 821                     }
 822                 }
 823
 824                 /*
 825                  * If this is not a valid rectangle with no other
 826                  * edges inside it, we just mark this square as not
 827                  * complete and proceed to the next square.
 828                  */
 829                 if (!valid) {
 830                     index(state, ret, x, y) = 0;
 831                     continue;
 832                 }
 833
 834                 /*
 835                  * We have a rectangle. Now see what its area is,
 836                  * and how many numbers are in it.
 837                  */
 838                 num = 0;
 839                 area = 0;
 840                 for (xx = x; xx < x+rw; xx++) {
 841                     for (yy = y; yy < y+rh; yy++) {
 842                         area++;
 843                         if (grid(state,xx,yy)) {
 844                             if (num > 0)
 845                                 valid = FALSE;   /* two numbers */
 846                             num = grid(state,xx,yy);
 847                         }
 848                     }
 849                 }
 850                 if (num != area)
 851                     valid = FALSE;
 852
 853                 /*
 854                  * Now fill in the whole rectangle based on the
 855                  * value of `valid'.
 856                  */
 857                 for (xx = x; xx < x+rw; xx++) {
 858                     for (yy = y; yy < y+rh; yy++) {
 859                         index(state, ret, xx, yy) = valid;
 860                     }
 861                 }
 862             }
 863
 864     return ret;
 865 }
 866
 867 struct game_ui {
 868     /*
 869      * These coordinates are 2 times the obvious grid coordinates.
 870      * Hence, the top left of the grid is (0,0), the grid point to
 871      * the right of that is (2,0), the one _below that_ is (2,2)
 872      * and so on. This is so that we can specify a drag start point
 873      * on an edge (one odd coordinate) or in the middle of a square
 874      * (two odd coordinates) rather than always at a corner.
 875      *
 876      * -1,-1 means no drag is in progress.
 877      */
 878     int drag_start_x;
 879     int drag_start_y;
 880     int drag_end_x;
 881     int drag_end_y;
 882     /*
 883      * This flag is set as soon as a dragging action moves the
 884      * mouse pointer away from its starting point, so that even if
 885      * the pointer _returns_ to its starting point the action is
 886      * treated as a small drag rather than a click.
 887      */
 888     int dragged;
 889 };
 890
 891 game_ui *new_ui(game_state *state)
 892 {
 893     game_ui *ui = snew(game_ui);
 894     ui->drag_start_x = -1;
 895     ui->drag_start_y = -1;
 896     ui->drag_end_x = -1;
 897     ui->drag_end_y = -1;
 898     ui->dragged = FALSE;
 899     return ui;
 900 }
 901
 902 void free_ui(game_ui *ui)
 903 {
 904     sfree(ui);
 905 }
 906
 907 int coord_round(float coord)
 908 {
 909     int i;
 910     float dist;
 911
 912     /*
 913      * Find the nearest integer.
 914      */
 915     i = (int)(coord + 0.5F);
 916
 917     /*
 918      * Find the distance from us to that integer.
 919      */
 920     dist = (float)fabs(coord - (float)i);
 921
 922     /*
 923      * If we're within the tolerance limit, return the edge
 924      * coordinate. Otherwise, return the centre coordinate.
 925      */
 926     if (dist < 0.3F)
 927         return i * 2;
 928     else
 929         return 1 + 2 * (int)coord;
 930 }
 931
 932 static void ui_draw_rect(game_state *state, game_ui *ui,
 933                          unsigned char *hedge, unsigned char *vedge, int c)
 934 {
 935     int x1, x2, y1, y2, x, y, t;
 936
 937     x1 = ui->drag_start_x;
 938     x2 = ui->drag_end_x;
 939     if (x2 < x1) { t = x1; x1 = x2; x2 = t; }
 940
 941     y1 = ui->drag_start_y;
 942     y2 = ui->drag_end_y;
 943     if (y2 < y1) { t = y1; y1 = y2; y2 = t; }
 944
 945     x1 = x1 / 2;               /* rounds down */
 946     x2 = (x2+1) / 2;           /* rounds up */
 947     y1 = y1 / 2;               /* rounds down */
 948     y2 = (y2+1) / 2;           /* rounds up */
 949
 950     /*
 951      * Draw horizontal edges of rectangles.
 952      */
 953     for (x = x1; x < x2; x++)
 954         for (y = y1; y <= y2; y++)
 955             if (HRANGE(state,x,y)) {
 956                 int val = index(state,hedge,x,y);
 957                 if (y == y1 || y == y2)
 958                     val = c;
 959                 else if (c == 1)
 960                     val = 0;
 961                 index(state,hedge,x,y) = val;
 962             }
 963
 964     /*
 965      * Draw vertical edges of rectangles.
 966      */
 967     for (y = y1; y < y2; y++)
 968         for (x = x1; x <= x2; x++)
 969             if (VRANGE(state,x,y)) {
 970                 int val = index(state,vedge,x,y);
 971                 if (x == x1 || x == x2)
 972                     val = c;
 973                 else if (c == 1)
 974                     val = 0;
 975                 index(state,vedge,x,y) = val;
 976             }
 977 }
 978
 979 game_state *make_move(game_state *from, game_ui *ui, int x, int y, int button)
 980 {
 981     int xc, yc;
 982     int startdrag = FALSE, enddrag = FALSE, active = FALSE;
 983     game_state *ret;
 984
 985     if (button == LEFT_BUTTON) {
 986         startdrag = TRUE;
 987     } else if (button == LEFT_RELEASE) {
 988         enddrag = TRUE;
 989     } else if (button != LEFT_DRAG) {
 990         return NULL;
 991     }
 992
 993     xc = coord_round(FROMCOORD((float)x));
 994     yc = coord_round(FROMCOORD((float)y));
 995
 996     if (startdrag) {
 997         ui->drag_start_x = xc;
 998         ui->drag_start_y = yc;
 999         ui->drag_end_x = xc;
1000         ui->drag_end_y = yc;
1001         ui->dragged = FALSE;
1002         active = TRUE;
1003     }
1004
1005     if (xc != ui->drag_end_x || yc != ui->drag_end_y) {
1006         ui->drag_end_x = xc;
1007         ui->drag_end_y = yc;
1008         ui->dragged = TRUE;
1009         active = TRUE;
1010     }
1011
1012     ret = NULL;
1013
1014     if (enddrag) {
1015         if (xc >= 0 && xc <= 2*from->w &&
1016             yc >= 0 && yc <= 2*from->h) {
1017             ret = dup_game(from);
1018
1019             if (ui->dragged) {
1020                 ui_draw_rect(ret, ui, ret->hedge, ret->vedge, 1);
1021             } else {
1022                 if ((xc & 1) && !(yc & 1) && HRANGE(from,xc/2,yc/2)) {
1023                     hedge(ret,xc/2,yc/2) = !hedge(ret,xc/2,yc/2);
1024                 }
1025                 if ((yc & 1) && !(xc & 1) && VRANGE(from,xc/2,yc/2)) {
1026                     vedge(ret,xc/2,yc/2) = !vedge(ret,xc/2,yc/2);
1027                 }
1028             }
1029
1030             if (!memcmp(ret->hedge, from->hedge, from->w*from->h) &&
1031                 !memcmp(ret->vedge, from->vedge, from->w*from->h)) {
1032                 free_game(ret);
1033                 ret = NULL;
1034             }
1035         }
1036
1037         ui->drag_start_x = -1;
1038         ui->drag_start_y = -1;
1039         ui->drag_end_x = -1;
1040         ui->drag_end_y = -1;
1041         ui->dragged = FALSE;
1042         active = TRUE;
1043     }
1044
1045     if (ret)
1046         return ret;                    /* a move has been made */
1047     else if (active)
1048         return from;                   /* UI activity has occurred */
1049     else
1050         return NULL;
1051 }
1052
1053 /* ----------------------------------------------------------------------
1054  * Drawing routines.
1055  */
1056
1057 #define CORRECT 256
1058
1059 #define COLOUR(k) ( (k)==1 ? COL_LINE : COL_DRAG )
1060 #define MAX(x,y) ( (x)>(y) ? (x) : (y) )
1061 #define MAX4(x,y,z,w) ( MAX(MAX(x,y),MAX(z,w)) )
1062
1063 struct game_drawstate {
1064     int started;
1065     int w, h;
1066     unsigned short *visible;
1067 };
1068
1069 void game_size(game_params *params, int *x, int *y)
1070 {
1071     *x = params->w * TILE_SIZE + 2*BORDER + 1;
1072     *y = params->h * TILE_SIZE + 2*BORDER + 1;
1073 }
1074
1075 float *game_colours(frontend *fe, game_state *state, int *ncolours)
1076 {
1077     float *ret = snewn(3 * NCOLOURS, float);
1078
1079     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1080
1081     ret[COL_GRID * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1082     ret[COL_GRID * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1083     ret[COL_GRID * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
1084
1085     ret[COL_DRAG * 3 + 0] = 1.0F;
1086     ret[COL_DRAG * 3 + 1] = 0.0F;
1087     ret[COL_DRAG * 3 + 2] = 0.0F;
1088
1089     ret[COL_CORRECT * 3 + 0] = 0.75F * ret[COL_BACKGROUND * 3 + 0];
1090     ret[COL_CORRECT * 3 + 1] = 0.75F * ret[COL_BACKGROUND * 3 + 1];
1091     ret[COL_CORRECT * 3 + 2] = 0.75F * ret[COL_BACKGROUND * 3 + 2];
1092
1093     ret[COL_LINE * 3 + 0] = 0.0F;
1094     ret[COL_LINE * 3 + 1] = 0.0F;
1095     ret[COL_LINE * 3 + 2] = 0.0F;
1096
1097     ret[COL_TEXT * 3 + 0] = 0.0F;
1098     ret[COL_TEXT * 3 + 1] = 0.0F;
1099     ret[COL_TEXT * 3 + 2] = 0.0F;
1100
1101     *ncolours = NCOLOURS;
1102     return ret;
1103 }
1104
1105 game_drawstate *game_new_drawstate(game_state *state)
1106 {
1107     struct game_drawstate *ds = snew(struct game_drawstate);
1108     int i;
1109
1110     ds->started = FALSE;
1111     ds->w = state->w;
1112     ds->h = state->h;
1113     ds->visible = snewn(ds->w * ds->h, unsigned short);
1114     for (i = 0; i < ds->w * ds->h; i++)
1115         ds->visible[i] = 0xFFFF;
1116
1117     return ds;
1118 }
1119
1120 void game_free_drawstate(game_drawstate *ds)
1121 {
1122     sfree(ds->visible);
1123     sfree(ds);
1124 }
1125
1126 void draw_tile(frontend *fe, game_state *state, int x, int y,
1127                unsigned char *hedge, unsigned char *vedge, int correct)
1128 {
1129     int cx = COORD(x), cy = COORD(y);
1130     char str[80];
1131
1132     draw_rect(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1, COL_GRID);
1133     draw_rect(fe, cx+1, cy+1, TILE_SIZE-1, TILE_SIZE-1,
1134               correct ? COL_CORRECT : COL_BACKGROUND);
1135
1136     if (grid(state,x,y)) {
1137         sprintf(str, "%d", grid(state,x,y));
1138         draw_text(fe, cx+TILE_SIZE/2, cy+TILE_SIZE/2, FONT_VARIABLE,
1139                   TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, COL_TEXT, str);
1140     }
1141
1142     /*
1143      * Draw edges.
1144      */
1145     if (!HRANGE(state,x,y) || index(state,hedge,x,y))
1146         draw_rect(fe, cx, cy, TILE_SIZE+1, 2,
1147                   HRANGE(state,x,y) ? COLOUR(index(state,hedge,x,y)) :
1148                   COL_LINE);
1149     if (!HRANGE(state,x,y+1) || index(state,hedge,x,y+1))
1150         draw_rect(fe, cx, cy+TILE_SIZE-1, TILE_SIZE+1, 2,
1151                   HRANGE(state,x,y+1) ? COLOUR(index(state,hedge,x,y+1)) :
1152                   COL_LINE);
1153     if (!VRANGE(state,x,y) || index(state,vedge,x,y))
1154         draw_rect(fe, cx, cy, 2, TILE_SIZE+1,
1155                   VRANGE(state,x,y) ? COLOUR(index(state,vedge,x,y)) :
1156                   COL_LINE);
1157     if (!VRANGE(state,x+1,y) || index(state,vedge,x+1,y))
1158         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, TILE_SIZE+1,
1159                   VRANGE(state,x+1,y) ? COLOUR(index(state,vedge,x+1,y)) :
1160                   COL_LINE);
1161
1162     /*
1163      * Draw corners.
1164      */
1165     if ((HRANGE(state,x-1,y) && index(state,hedge,x-1,y)) ||
1166         (VRANGE(state,x,y-1) && index(state,vedge,x,y-1)))
1167         draw_rect(fe, cx, cy, 2, 2,
1168                   COLOUR(MAX4(index(state,hedge,x-1,y),
1169                               index(state,vedge,x,y-1),
1170                               index(state,hedge,x,y),
1171                               index(state,vedge,x,y))));
1172     if ((HRANGE(state,x+1,y) && index(state,hedge,x+1,y)) ||
1173         (VRANGE(state,x+1,y-1) && index(state,vedge,x+1,y-1)))
1174         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, 2,
1175                   COLOUR(MAX4(index(state,hedge,x+1,y),
1176                               index(state,vedge,x+1,y-1),
1177                               index(state,hedge,x,y),
1178                               index(state,vedge,x+1,y))));
1179     if ((HRANGE(state,x-1,y+1) && index(state,hedge,x-1,y+1)) ||
1180         (VRANGE(state,x,y+1) && index(state,vedge,x,y+1)))
1181         draw_rect(fe, cx, cy+TILE_SIZE-1, 2, 2,
1182                   COLOUR(MAX4(index(state,hedge,x-1,y+1),
1183                               index(state,vedge,x,y+1),
1184                               index(state,hedge,x,y+1),
1185                               index(state,vedge,x,y))));
1186     if ((HRANGE(state,x+1,y+1) && index(state,hedge,x+1,y+1)) ||
1187         (VRANGE(state,x+1,y+1) && index(state,vedge,x+1,y+1)))
1188         draw_rect(fe, cx+TILE_SIZE-1, cy+TILE_SIZE-1, 2, 2,
1189                   COLOUR(MAX4(index(state,hedge,x+1,y+1),
1190                               index(state,vedge,x+1,y+1),
1191                               index(state,hedge,x,y+1),
1192                               index(state,vedge,x+1,y))));
1193
1194     draw_update(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1);
1195 }
1196
1197 void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1198                  game_state *state, game_ui *ui,
1199                  float animtime, float flashtime)
1200 {
1201     int x, y;
1202     unsigned char *correct;
1203     unsigned char *hedge, *vedge;
1204
1205     correct = get_correct(state);
1206
1207     if (ui->dragged) {
1208         hedge = snewn(state->w*state->h, unsigned char);
1209         vedge = snewn(state->w*state->h, unsigned char);
1210         memcpy(hedge, state->hedge, state->w*state->h);
1211         memcpy(vedge, state->vedge, state->w*state->h);
1212         ui_draw_rect(state, ui, hedge, vedge, 2);
1213     } else {
1214         hedge = state->hedge;
1215         vedge = state->vedge;
1216     }
1217
1218     if (!ds->started) {
1219         draw_rect(fe, 0, 0,
1220                   state->w * TILE_SIZE + 2*BORDER + 1,
1221                   state->h * TILE_SIZE + 2*BORDER + 1, COL_BACKGROUND);
1222         draw_rect(fe, COORD(0)-1, COORD(0)-1,
1223                   ds->w*TILE_SIZE+3, ds->h*TILE_SIZE+3, COL_LINE);
1224         ds->started = TRUE;
1225     }
1226
1227     for (x = 0; x < state->w; x++)
1228         for (y = 0; y < state->h; y++) {
1229             unsigned short c = 0;
1230
1231             if (HRANGE(state,x,y))
1232                 c |= index(state,hedge,x,y);
1233             if (HRANGE(state,x+1,y))
1234                 c |= index(state,hedge,x+1,y) << 2;
1235             if (VRANGE(state,x,y))
1236                 c |= index(state,vedge,x,y) << 4;
1237             if (VRANGE(state,x,y+1))
1238                 c |= index(state,vedge,x,y+1) << 6;
1239             if (index(state, correct, x, y))
1240                 c |= CORRECT;
1241
1242             if (index(ds,ds->visible,x,y) != c) {
1243                 draw_tile(fe, state, x, y, hedge, vedge, c & CORRECT);
1244                 /* index(ds,ds->visible,x,y) = c; */
1245             }
1246         }
1247
1248     if (hedge != state->hedge) {
1249         sfree(hedge);
1250         sfree(vedge);
1251    }
1252
1253     sfree(correct);
1254 }
1255
1256 float game_anim_length(game_state *oldstate, game_state *newstate)
1257 {
1258     return 0.0F;
1259 }
1260
1261 float game_flash_length(game_state *oldstate, game_state *newstate)
1262 {
1263     return 0.0F;
1264 }
1265
1266 int game_wants_statusbar(void)
1267 {
1268     return FALSE;
1269 }