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