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