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