filling.c

   1 /* -*- tab-width: 8; indent-tabs-mode: t -*-
   2  * filling.c: An implementation of the Nikoli game fillomino.
   3  * Copyright (C) 2007 Jonas Kölker.  See LICENSE for the license.
   4  */
   5
   6 /* TODO:
   7  *
   8  *  - use a typedef instead of int for numbers on the board
   9  *     + replace int with something else (signed char?)
  10  *        - the type should be signed (I use -board[i] temporarily)
  11  *        - problems are small (<= 9?): type can be char?
  12  *
  13  *  - make a somewhat more clever solver
  14  *
  15  *  - make the solver do recursion/backtracking.
  16  *     + This is for user-submitted puzzles, not for puzzle
  17  *       generation (on the other hand, never say never).
  18  *
  19  *  - prove that only w=h=2 needs a special case
  20  *
  21  *  - solo-like pencil marks?
  22  *
  23  *  - speed up generation of puzzles of size >= 11x11
  24  *
  25  *  - Allow square contents > 9?
  26  *     + I could use letters for digits (solo does this), but
  27  *       letters don't have numeric significance (normal people hate
  28  *       base36), which is relevant here (much more than in solo).
  29  *     + How much information is needed to solve?  Does one need to
  30  *       know the algorithm by which the largest number is set?
  31  *
  32  *  - eliminate puzzle instances with done chunks (1's in particular)?
  33  *     + that's what the qsort call is all about.
  34  *     + the 1's don't bother me that much.
  35  *     + but this takes a LONG time (not always possible)?
  36  *        - this may be affected by solver (lack of) quality.
  37  *        - weed them out by construction instead of post-cons check
  38  *           + but that interleaves make_board and new_game_desc: you
  39  *             have to alternate between changing the board and
  40  *             changing the hint set (instead of just creating the
  41  *             board once, then changing the hint set once -> done).
  42  *
  43  *  - use binary search when discovering the minimal sovable point
  44  *     + profile to show a need (but when the solver gets slower...)
  45  *     + avg 0.1s per 9x9, which _is_ human-patience noticable.
  46  */
  47
  48 #include <assert.h>
  49 #include <ctype.h>
  50 #include <math.h>
  51 #include <stdio.h>
  52 #include <stdlib.h>
  53 #include <string.h>
  54
  55 #include "puzzles.h"
  56
  57 struct game_params {
  58     int w, h;
  59 };
  60
  61 struct shared_state {
  62     struct game_params params;
  63     int *clues;
  64     int refcnt;
  65 };
  66
  67 struct game_state {
  68     int *board;
  69     struct shared_state *shared;
  70     int completed, cheated;
  71 };
  72
  73 static const struct game_params defaults[3] = {{5, 5}, {7, 7}, {9, 9}};
  74
  75 static game_params *default_params(void)
  76 {
  77     game_params *ret = snew(game_params);
  78
  79     *ret = defaults[1]; /* struct copy */
  80
  81     return ret;
  82 }
  83
  84 static int game_fetch_preset(int i, char **name, game_params **params)
  85 {
  86     char buf[64];
  87
  88     if (i < 0 || i >= lenof(defaults)) return FALSE;
  89     *params = snew(game_params);
  90     **params = defaults[i]; /* struct copy */
  91     sprintf(buf, "%dx%d", defaults[i].w, defaults[i].h);
  92     *name = dupstr(buf);
  93
  94     return TRUE;
  95 }
  96
  97 static void free_params(game_params *params)
  98 {
  99     sfree(params);
 100 }
 101
 102 static game_params *dup_params(game_params *params)
 103 {
 104     game_params *ret = snew(game_params);
 105     *ret = *params; /* struct copy */
 106     return ret;
 107 }
 108
 109 static void decode_params(game_params *ret, char const *string)
 110 {
 111     ret->w = ret->h = atoi(string);
 112     while (*string && isdigit((unsigned char) *string)) ++string;
 113     if (*string == 'x') ret->h = atoi(++string);
 114 }
 115
 116 static char *encode_params(game_params *params, int full)
 117 {
 118     char buf[64];
 119     sprintf(buf, "%dx%d", params->w, params->h);
 120     return dupstr(buf);
 121 }
 122
 123 static config_item *game_configure(game_params *params)
 124 {
 125     config_item *ret;
 126     char buf[64];
 127
 128     ret = snewn(3, config_item);
 129
 130     ret[0].name = "Width";
 131     ret[0].type = C_STRING;
 132     sprintf(buf, "%d", params->w);
 133     ret[0].sval = dupstr(buf);
 134     ret[0].ival = 0;
 135
 136     ret[1].name = "Height";
 137     ret[1].type = C_STRING;
 138     sprintf(buf, "%d", params->h);
 139     ret[1].sval = dupstr(buf);
 140     ret[1].ival = 0;
 141
 142     ret[2].name = NULL;
 143     ret[2].type = C_END;
 144     ret[2].sval = NULL;
 145     ret[2].ival = 0;
 146
 147     return ret;
 148 }
 149
 150 static game_params *custom_params(config_item *cfg)
 151 {
 152     game_params *ret = snew(game_params);
 153
 154     ret->w = atoi(cfg[0].sval);
 155     ret->h = atoi(cfg[1].sval);
 156
 157     return ret;
 158 }
 159
 160 static char *validate_params(game_params *params, int full)
 161 {
 162     if (params->w < 1) return "Width must be at least one";
 163     if (params->h < 1) return "Height must be at least one";
 164
 165     return NULL;
 166 }
 167
 168 /*****************************************************************************
 169  * STRINGIFICATION OF GAME STATE                                             *
 170  *****************************************************************************/
 171
 172 #define EMPTY 0
 173
 174 /* Example of plaintext rendering:
 175  *  +---+---+---+---+---+---+---+
 176  *  | 6 |   |   | 2 |   |   | 2 |
 177  *  +---+---+---+---+---+---+---+
 178  *  |   | 3 |   | 6 |   | 3 |   |
 179  *  +---+---+---+---+---+---+---+
 180  *  | 3 |   |   |   |   |   | 1 |
 181  *  +---+---+---+---+---+---+---+
 182  *  |   | 2 | 3 |   | 4 | 2 |   |
 183  *  +---+---+---+---+---+---+---+
 184  *  | 2 |   |   |   |   |   | 3 |
 185  *  +---+---+---+---+---+---+---+
 186  *  |   | 5 |   | 1 |   | 4 |   |
 187  *  +---+---+---+---+---+---+---+
 188  *  | 4 |   |   | 3 |   |   | 3 |
 189  *  +---+---+---+---+---+---+---+
 190  *
 191  * This puzzle instance is taken from the nikoli website
 192  * Encoded (unsolved and solved), the strings are these:
 193  * 7x7:6002002030603030000010230420200000305010404003003
 194  * 7x7:6662232336663232331311235422255544325413434443313
 195  */
 196 static char *board_to_string(int *board, int w, int h) {
 197     const int sz = w * h;
 198     const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */
 199     const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */
 200     const int chlen = chw * chh;
 201     char *repr = snewn(chlen + 1, char);
 202     int i;
 203
 204     assert(board);
 205
 206     /* build the first line ("^(\+---){n}\+$") */
 207     for (i = 0; i < w; ++i) {
 208         repr[4*i + 0] = '+';
 209         repr[4*i + 1] = '-';
 210         repr[4*i + 2] = '-';
 211         repr[4*i + 3] = '-';
 212     }
 213     repr[4*i + 0] = '+';
 214     repr[4*i + 1] = '\n';
 215
 216     /* ... and copy it onto the odd-numbered lines */
 217     for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw);
 218
 219     /* build the second line ("^(\|\t){n}\|$") */
 220     for (i = 0; i < w; ++i) {
 221         repr[chw + 4*i + 0] = '|';
 222         repr[chw + 4*i + 1] = ' ';
 223         repr[chw + 4*i + 2] = ' ';
 224         repr[chw + 4*i + 3] = ' ';
 225     }
 226     repr[chw + 4*i + 0] = '|';
 227     repr[chw + 4*i + 1] = '\n';
 228
 229     /* ... and copy it onto the even-numbered lines */
 230     for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw);
 231
 232     /* fill in the numbers */
 233     for (i = 0; i < sz; ++i) {
 234         const int x = i % w;
 235         const int y = i / w;
 236         if (board[i] == EMPTY) continue;
 237         repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0';
 238     }
 239
 240     repr[chlen] = '\0';
 241     return repr;
 242 }
 243
 244 static char *game_text_format(game_state *state)
 245 {
 246     const int w = state->shared->params.w;
 247     const int h = state->shared->params.h;
 248     return board_to_string(state->board, w, h);
 249 }
 250
 251 /*****************************************************************************
 252  * GAME GENERATION AND SOLVER                                                *
 253  *****************************************************************************/
 254
 255 static const int dx[4] = {-1, 1, 0, 0};
 256 static const int dy[4] = {0, 0, -1, 1};
 257
 258 /*
 259 static void print_board(int *board, int w, int h) {
 260     char *repr = board_to_string(board, w, h);
 261     fputs(repr, stdout);
 262     free(repr);
 263 }
 264 */
 265
 266 #define SENTINEL sz
 267
 268 /* determines whether a board (in dsf form) is valid.  If possible,
 269  * return a conflicting pair in *a and *b and a non-*b neighbour of *a
 270  * in *c.  If not possible, leave them unmodified. */
 271 static void
 272 validate_board(int *dsf, int w, int h, int *sq, int *a, int *b, int *c) {
 273     const int sz = w * h;
 274     int i;
 275     assert(*a == SENTINEL);
 276     assert(*b == SENTINEL);
 277     assert(*c == SENTINEL);
 278     for (i = 0; i < sz && *a == sz; ++i) {
 279         const int aa = dsf_canonify(dsf, sq[i]);
 280         int cc = sz;
 281         int j;
 282         for (j = 0; j < 4; ++j) {
 283             const int x = (sq[i] % w) + dx[j];
 284             const int y = (sq[i] / w) + dy[j];
 285             int bb;
 286             if (x < 0 || x >= w || y < 0 || y >= h) continue;
 287             bb = dsf_canonify(dsf, w*y + x);
 288             if (aa == bb) continue;
 289             else if (dsf_size(dsf, aa) == dsf_size(dsf, bb)) {
 290                 *a = aa;
 291                 *b = bb;
 292                 *c = cc;
 293             } else if (cc == sz) *c = cc = bb;
 294         }
 295     }
 296 }
 297
 298 static game_state *new_game(midend *, game_params *, char *);
 299 static void free_game(game_state *);
 300
 301 /* generate a random valid board; uses validate_board.  */
 302 void make_board(int *board, int w, int h, random_state *rs) {
 303     int *dsf;
 304
 305     const unsigned int sz = w * h;
 306
 307     /* w=h=2 is a special case which requires a number > max(w, h) */
 308     /* TODO prove that this is the case ONLY for w=h=2. */
 309     const int maxsize = min(max(max(w, h), 3), 9);
 310
 311     /* Note that if 1 in {w, h} then it's impossible to have a region
 312      * of size > w*h, so the special case only affects w=h=2. */
 313
 314     int nboards = 0;
 315
 316     int i;
 317
 318     assert(w >= 1);
 319     assert(h >= 1);
 320
 321     assert(board);
 322
 323     dsf = snew_dsf(sz); /* implicit dsf_init */
 324
 325     /* I abuse the board variable: when generating the puzzle, it
 326      * contains a shuffled list of numbers {0, ..., nsq-1}. */
 327     for (i = 0; i < sz; ++i) board[i] = i;
 328
 329     while (1) {
 330         ++nboards;
 331         shuffle(board, sz, sizeof (int), rs);
 332         /* while the board can in principle be fixed */
 333         while (1) {
 334             int a = SENTINEL;
 335             int b = SENTINEL;
 336             int c = SENTINEL;
 337             validate_board(dsf, w, h, board, &a, &b, &c);
 338             if (a == SENTINEL /* meaning the board is valid */) {
 339                 int i;
 340                 for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i);
 341                 sfree(dsf);
 342                 /* printf("returning board number %d\n", nboards); */
 343                 return;
 344             } else {
 345                 /* try to repair the invalid board */
 346                 a = dsf_canonify(dsf, a);
 347                 assert(a != dsf_canonify(dsf, b));
 348                 if (c != sz) assert(a != dsf_canonify(dsf, c));
 349                 dsf_merge(dsf, a, c == sz? b: c);
 350                 /* if repair impossible; make a new board */
 351                 if (dsf_size(dsf, a) > maxsize) break;
 352             }
 353         }
 354         dsf_init(dsf, sz); /* re-init the dsf */
 355     }
 356     assert(FALSE); /* unreachable */
 357 }
 358
 359 static int rhofree(int *hop, int start) {
 360     int turtle = start, rabbit = hop[start];
 361     while (rabbit != turtle) { /* find a cycle */
 362         turtle = hop[turtle];
 363         rabbit = hop[hop[rabbit]];
 364     }
 365     do { /* check that start is in the cycle */
 366         rabbit = hop[rabbit];
 367         if (start == rabbit) return 1;
 368     } while (rabbit != turtle);
 369     return 0;
 370 }
 371
 372 static void merge(int *dsf, int *connected, int a, int b) {
 373     int c;
 374     assert(dsf);
 375     assert(connected);
 376     assert(rhofree(connected, a));
 377     assert(rhofree(connected, b));
 378     a = dsf_canonify(dsf, a);
 379     b = dsf_canonify(dsf, b);
 380     if (a == b) return;
 381     dsf_merge(dsf, a, b);
 382     c = connected[a];
 383     connected[a] = connected[b];
 384     connected[b] = c;
 385     assert(rhofree(connected, a));
 386     assert(rhofree(connected, b));
 387 }
 388
 389 static void *memdup(const void *ptr, size_t len, size_t esz) {
 390     void *dup = smalloc(len * esz);
 391     assert(ptr);
 392     memcpy(dup, ptr, len * esz);
 393     return dup;
 394 }
 395
 396 static void expand(int *board, int *connected, int *dsf, int w, int h,
 397                    int dst, int src, int *empty, int *learn) {
 398     int j;
 399     assert(board);
 400     assert(connected);
 401     assert(dsf);
 402     assert(empty);
 403     assert(learn);
 404     assert(board[dst] == EMPTY);
 405     assert(board[src] != EMPTY);
 406     board[dst] = board[src];
 407     for (j = 0; j < 4; ++j) {
 408         const int x = (dst % w) + dx[j];
 409         const int y = (dst / w) + dy[j];
 410         const int idx = w*y + x;
 411         if (x < 0 || x >= w || y < 0 || y >= h) continue;
 412         if (board[idx] != board[dst]) continue;
 413         merge(dsf, connected, dst, idx);
 414     }
 415 /*  printf("set board[%d] = board[%d], which is %d; size(%d) = %d\n", dst, src, board[src], src, dsf[dsf_canonify(dsf, src)] >> 2); */
 416     --*empty;
 417     *learn = TRUE;
 418 }
 419
 420 static void flood(int *board, int w, int h, int i, int n) {
 421     const int sz = w * h;
 422     int k;
 423
 424     if (board[i] == EMPTY) board[i] = -SENTINEL;
 425     else if (board[i] == n) board[i] = -board[i];
 426     else return;
 427
 428     for (k = 0; k < 4; ++k) {
 429         const int x = (i % w) + dx[k];
 430         const int y = (i / w) + dy[k];
 431         const int idx = w*y + x;
 432         if (x < 0 || x >= w || y < 0 || y >= h) continue;
 433         flood(board, w, h, idx, n);
 434     }
 435 }
 436
 437 static int count_and_clear(int *board, int sz) {
 438     int count = -1;
 439     int i;
 440     for (i = 0; i < sz; ++i) {
 441         if (board[i] >= 0) continue;
 442         ++count;
 443         if (board[i] == -SENTINEL) board[i] = EMPTY;
 444         else board[i] = -board[i];
 445     }
 446     return count;
 447 }
 448
 449 static int count(int *board, int w, int h, int i) {
 450     flood(board, w, h, i, board[i]);
 451     return count_and_clear(board, w * h);
 452 }
 453
 454 static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) {
 455     int j;
 456     int nhits = 0;
 457     int hits[4];
 458     int size = 1;
 459     for (j = 0; j < 4; ++j) {
 460         const int x = (i % w) + dx[j];
 461         const int y = (i / w) + dy[j];
 462         const int idx = w*y + x;
 463         int root;
 464         int m;
 465         if (x < 0 || x >= w || y < 0 || y >= h) continue;
 466         if (board[idx] != n) continue;
 467         root = dsf_canonify(dsf, idx);
 468         for (m = 0; m < nhits && root != hits[m]; ++m);
 469         if (m < nhits) continue;
 470         /* printf("\t  (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2); */
 471         size += dsf_size(dsf, root);
 472         assert(dsf_size(dsf, root) >= 1);
 473         hits[nhits++] = root;
 474     }
 475     return size;
 476 }
 477
 478 /*
 479  *  +---+---+---+---+---+---+---+
 480  *  | 6 |   |   | 2 |   |   | 2 |
 481  *  +---+---+---+---+---+---+---+
 482  *  |   | 3 |   | 6 |   | 3 |   |
 483  *  +---+---+---+---+---+---+---+
 484  *  | 3 |   |   |   |   |   | 1 |
 485  *  +---+---+---+---+---+---+---+
 486  *  |   | 2 | 3 |   | 4 | 2 |   |
 487  *  +---+---+---+---+---+---+---+
 488  *  | 2 |   |   |   |   |   | 3 |
 489  *  +---+---+---+---+---+---+---+
 490  *  |   | 5 |   | 1 |   | 4 |   |
 491  *  +---+---+---+---+---+---+---+
 492  *  | 4 |   |   | 3 |   |   | 3 |
 493  *  +---+---+---+---+---+---+---+
 494  */
 495
 496 /* Solving techniques:
 497  *
 498  * CONNECTED COMPONENT FORCED EXPANSION (too big):
 499  * When a CC can only be expanded in one direction, because all the
 500  * other ones would make the CC too big.
 501  *  +---+---+---+---+---+
 502  *  | 2 | 2 |   | 2 | _ |
 503  *  +---+---+---+---+---+
 504  *
 505  * CONNECTED COMPONENT FORCED EXPANSION (too small):
 506  * When a CC must include a particular square, because otherwise there
 507  * would not be enough room to complete it.
 508  *  +---+---+
 509  *  | 2 | _ |
 510  *  +---+---+
 511  *
 512  * DROPPING IN A ONE:
 513  * When an empty square has no neighbouring empty squares and only a 1
 514  * will go into the square (or other CCs would be too big).
 515  *  +---+---+---+
 516  *  | 2 | 2 | _ |
 517  *  +---+---+---+
 518  *
 519  * TODO: generalise DROPPING IN A ONE: find the size of the CC of
 520  * empty squares and a list of all adjacent numbers.  See if only one
 521  * number in {1, ..., size} u {all adjacent numbers} is possible.
 522  * Probably this is only effective for a CC size < n for some n (4?)
 523  *
 524  * TODO: backtracking.
 525  */
 526 #define EXPAND(a, b)\
 527 expand(board, connected, dsf, w, h, a, b, &nempty, &learn)
 528
 529 static int solver(const int *orig, int w, int h, char **solution) {
 530     const int sz = w * h;
 531
 532     int *board = memdup(orig, sz, sizeof (int));
 533     int *dsf = snew_dsf(sz); /* eqv classes: connected components */
 534     int *connected = snewn(sz, int); /* connected[n] := n.next; */
 535     /* cyclic disjoint singly linked lists, same partitioning as dsf.
 536      * The lists lets you iterate over a partition given any member */
 537
 538     int nempty = 0;
 539
 540     int learn;
 541
 542     int i;
 543     for (i = 0; i < sz; i++) connected[i] = i;
 544
 545     for (i = 0; i < sz; ++i) {
 546         int j;
 547         if (board[i] == EMPTY) ++nempty;
 548         else for (j = 0; j < 4; ++j) {
 549             const int x = (i % w) + dx[j];
 550             const int y = (i / w) + dy[j];
 551             const int idx = w*y + x;
 552             if (x < 0 || x >= w || y < 0 || y >= h) continue;
 553             if (board[i] == board[idx]) merge(dsf, connected, i, idx);
 554         }
 555     }
 556
 557 /*  puts("trying to solve this:");
 558     print_board(board, w, h); */
 559
 560     /* TODO: refactor this code, it's too long */
 561     do {
 562         int i;
 563         learn = FALSE;
 564
 565         /* for every connected component */
 566         for (i = 0; i < sz; ++i) {
 567             int exp = SENTINEL;
 568             int j;
 569
 570             /* If the component consists of empty squares */
 571             if (board[i] == EMPTY) {
 572                 int k;
 573                 int one = TRUE;
 574                 for (k = 0; k < 4; ++k) {
 575                     const int x = (i % w) + dx[k];
 576                     const int y = (i / w) + dy[k];
 577                     const int idx = w*y + x;
 578                     int n;
 579                     if (x < 0 || x >= w || y < 0 || y >= h) continue;
 580                     if (board[idx] == EMPTY) {
 581                         one = FALSE;
 582                         continue;
 583                     }
 584                     if (one &&
 585                         (board[idx] == 1 ||
 586                          (board[idx] >= expandsize(board, dsf, w, h,
 587                                                    i, board[idx]))))
 588                         one = FALSE;
 589                     assert(board[i] == EMPTY);
 590                     board[i] = -SENTINEL;
 591                     n = count(board, w, h, idx);
 592                     assert(board[i] == EMPTY);
 593                     if (n >= board[idx]) continue;
 594                     EXPAND(i, idx);
 595                     break;
 596                 }
 597                 if (k == 4 && one) {
 598                     assert(board[i] == EMPTY);
 599                     board[i] = 1;
 600                     assert(nempty);
 601                     --nempty;
 602                     learn = TRUE;
 603                 }
 604                 continue;
 605             }
 606             /* printf("expanding blob of (%d, %d)\n", i % w, i / w); */
 607
 608             j = dsf_canonify(dsf, i);
 609
 610             /* (but only for each connected component) */
 611             if (i != j) continue;
 612
 613             /* (and not if it's already complete) */
 614             if (dsf_size(dsf, j) == board[j]) continue;
 615
 616             /* for each square j _in_ the connected component */
 617             do {
 618                 int k;
 619                 /* printf("  looking at (%d, %d)\n", j % w, j / w); */
 620
 621                 /* for each neighbouring square (idx) */
 622                 for (k = 0; k < 4; ++k) {
 623                     const int x = (j % w) + dx[k];
 624                     const int y = (j / w) + dy[k];
 625                     const int idx = w*y + x;
 626                     int size;
 627                     /* int l;
 628                        int nhits = 0;
 629                        int hits[4]; */
 630                     if (x < 0 || x >= w || y < 0 || y >= h) continue;
 631                     if (board[idx] != EMPTY) continue;
 632                     if (exp == idx) continue;
 633                     /* printf("\ttrying to expand onto (%d, %d)\n", x, y); */
 634
 635                     /* find out the would-be size of the new connected
 636                      * component if we actually expanded into idx */
 637                     /*
 638                     size = 1;
 639                     for (l = 0; l < 4; ++l) {
 640                         const int lx = x + dx[l];
 641                         const int ly = y + dy[l];
 642                         const int idxl = w*ly + lx;
 643                         int root;
 644                         int m;
 645                         if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
 646                         if (board[idxl] != board[j]) continue;
 647                         root = dsf_canonify(dsf, idxl);
 648                         for (m = 0; m < nhits && root != hits[m]; ++m);
 649                         if (m != nhits) continue;
 650                         // printf("\t  (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);
 651                         size += dsf_size(dsf, root);
 652                         assert(dsf_size(dsf, root) >= 1);
 653                         hits[nhits++] = root;
 654                     }
 655                     */
 656
 657                     size = expandsize(board, dsf, w, h, idx, board[j]);
 658
 659                     /* ... and see if that size is too big, or if we
 660                      * have other expansion candidates.  Otherwise
 661                      * remember the (so far) only candidate. */
 662
 663                     /* printf("\tthat would give a size of %d\n", size); */
 664                     if (size > board[j]) continue;
 665                     /* printf("\tnow knowing %d expansions\n", nexpand + 1); */
 666                     if (exp != SENTINEL) goto next_i;
 667                     assert(exp != idx);
 668                     exp = idx;
 669                 }
 670
 671                 j = connected[j]; /* next square in the same CC */
 672                 assert(board[i] == board[j]);
 673             } while (j != i);
 674             /* end: for each square j _in_ the connected component */
 675
 676             if (exp == SENTINEL) continue;
 677             /* printf("expand b: %d -> %d\n", i, exp); */
 678             EXPAND(exp, i);
 679
 680             next_i:
 681             ;
 682         }
 683         /* end: for each connected component */
 684     } while (learn && nempty);
 685
 686     /* puts("best guess:");
 687        print_board(board, w, h); */
 688
 689     if (solution) {
 690         int i;
 691         assert(*solution == NULL);
 692         *solution = snewn(sz + 2, char);
 693         **solution = 's';
 694         for (i = 0; i < sz; ++i) (*solution)[i + 1] = board[i] + '0';
 695         (*solution)[sz + 1] = '\0';
 696         /* We don't need the \0 for execute_move (the only user)
 697          * I'm just being printf-friendly in case I wanna print */
 698     }
 699
 700     sfree(dsf);
 701     sfree(board);
 702     sfree(connected);
 703
 704     return !nempty;
 705 }
 706
 707 static int *make_dsf(int *dsf, int *board, const int w, const int h) {
 708     const int sz = w * h;
 709     int i;
 710
 711     if (!dsf)
 712         dsf = snew_dsf(w * h);
 713     else
 714         dsf_init(dsf, w * h);
 715
 716     for (i = 0; i < sz; ++i) {
 717         int j;
 718         for (j = 0; j < 4; ++j) {
 719             const int x = (i % w) + dx[j];
 720             const int y = (i / w) + dy[j];
 721             const int k = w*y + x;
 722             if (x < 0 || x >= w || y < 0 || y >= h) continue;
 723             if (board[i] == board[k]) dsf_merge(dsf, i, k);
 724         }
 725     }
 726     return dsf;
 727 }
 728
 729 /*
 730 static int filled(int *board, int *randomize, int k, int n) {
 731     int i;
 732     if (board == NULL) return FALSE;
 733     if (randomize == NULL) return FALSE;
 734     if (k > n) return FALSE;
 735     for (i = 0; i < k; ++i) if (board[randomize[i]] == 0) return FALSE;
 736     for (; i < n; ++i) if (board[randomize[i]] != 0) return FALSE;
 737     return TRUE;
 738 }
 739 */
 740
 741 static int *g_board;
 742 static int compare(const void *pa, const void *pb) {
 743     if (!g_board) return 0;
 744     return g_board[*(const int *)pb] - g_board[*(const int *)pa];
 745 }
 746
 747 static char *new_game_desc(game_params *params, random_state *rs,
 748                            char **aux, int interactive)
 749 {
 750     const int w = params->w;
 751     const int h = params->h;
 752     const int sz = w * h;
 753     int *board = snewn(sz, int);
 754     int *randomize = snewn(sz, int);
 755     int *solver_board = snewn(sz, int);
 756     char *game_description = snewn(sz + 1, char);
 757     int i;
 758
 759     for (i = 0; i < sz; ++i) {
 760         board[i] = EMPTY;
 761         randomize[i] = i;
 762     }
 763
 764     make_board(board, w, h, rs);
 765     memcpy(solver_board, board, sz * sizeof (int));
 766
 767     g_board = board;
 768     qsort(randomize, sz, sizeof (int), compare);
 769
 770     /* since more clues only helps and never hurts, one pass will do
 771      * just fine: if we can remove clue n with k clues of index > n,
 772      * we could have removed clue n with >= k clues of index > n.
 773      * So an additional pass wouldn't do anything [use induction]. */
 774     for (i = 0; i < sz; ++i) {
 775         solver_board[randomize[i]] = EMPTY;
 776         if (!solver(solver_board, w, h, NULL))
 777             solver_board[randomize[i]] = board[randomize[i]];
 778     }
 779
 780     for (i = 0; i < sz; ++i) {
 781         assert(solver_board[i] >= 0);
 782         assert(solver_board[i] < 10);
 783         game_description[i] = solver_board[i] + '0';
 784     }
 785     game_description[sz] = '\0';
 786
 787 /*
 788   solver(solver_board, w, h, aux);
 789   print_board(solver_board, w, h);
 790 */
 791
 792     sfree(randomize);
 793     sfree(solver_board);
 794     sfree(board);
 795
 796     return game_description;
 797 }
 798
 799 static char *validate_desc(game_params *params, char *desc)
 800 {
 801     int i;
 802     const int sz = params->w * params->h;
 803     const char m = '0' + max(max(params->w, params->h), 3);
 804
 805     /* printf("desc = '%s'; sz = %d\n", desc, sz); */
 806
 807     for (i = 0; desc[i] && i < sz; ++i)
 808         if (!isdigit((unsigned char) *desc))
 809             return "non-digit in string";
 810         else if (desc[i] > m)
 811             return "too large digit in string";
 812     if (desc[i]) return "string too long";
 813     else if (i < sz) return "string too short";
 814     return NULL;
 815 }
 816
 817 static game_state *new_game(midend *me, game_params *params, char *desc)
 818 {
 819     game_state *state = snew(game_state);
 820     int sz = params->w * params->h;
 821     int i;
 822
 823     state->cheated = state->completed = FALSE;
 824     state->shared = snew(struct shared_state);
 825     state->shared->refcnt = 1;
 826     state->shared->params = *params; /* struct copy */
 827     state->shared->clues = snewn(sz, int);
 828     for (i = 0; i < sz; ++i) state->shared->clues[i] = desc[i] - '0';
 829     state->board = memdup(state->shared->clues, sz, sizeof (int));
 830
 831     return state;
 832 }
 833
 834 static game_state *dup_game(game_state *state)
 835 {
 836     const int sz = state->shared->params.w * state->shared->params.h;
 837     game_state *ret = snew(game_state);
 838
 839     ret->board = memdup(state->board, sz, sizeof (int));
 840     ret->shared = state->shared;
 841     ret->cheated = state->cheated;
 842     ret->completed = state->completed;
 843     ++ret->shared->refcnt;
 844
 845     return ret;
 846 }
 847
 848 static void free_game(game_state *state)
 849 {
 850     assert(state);
 851     sfree(state->board);
 852     if (--state->shared->refcnt == 0) {
 853         sfree(state->shared->clues);
 854         sfree(state->shared);
 855     }
 856     sfree(state);
 857 }
 858
 859 static char *solve_game(game_state *state, game_state *currstate,
 860                         char *aux, char **error)
 861 {
 862     if (aux == NULL) {
 863         const int w = state->shared->params.w;
 864         const int h = state->shared->params.h;
 865         if (!solver(state->board, w, h, &aux))
 866             *error = "Sorry, I couldn't find a solution";
 867     }
 868     return aux;
 869 }
 870
 871 /*****************************************************************************
 872  * USER INTERFACE STATE AND ACTION                                           *
 873  *****************************************************************************/
 874
 875 struct game_ui {
 876     int x, y; /* highlighted square, or (-1, -1) if none */
 877 };
 878
 879 static game_ui *new_ui(game_state *state)
 880 {
 881     game_ui *ui = snew(game_ui);
 882
 883     ui->x = ui->y = -1;
 884
 885     return ui;
 886 }
 887
 888 static void free_ui(game_ui *ui)
 889 {
 890     sfree(ui);
 891 }
 892
 893 static char *encode_ui(game_ui *ui)
 894 {
 895     return NULL;
 896 }
 897
 898 static void decode_ui(game_ui *ui, char *encoding)
 899 {
 900 }
 901
 902 static void game_changed_state(game_ui *ui, game_state *oldstate,
 903                                game_state *newstate)
 904 {
 905 }
 906
 907 #define PREFERRED_TILE_SIZE 32
 908 #define TILE_SIZE (ds->tilesize)
 909 #define BORDER (TILE_SIZE / 2)
 910 #define BORDER_WIDTH (TILE_SIZE / 32)
 911
 912 struct game_drawstate {
 913     struct game_params params;
 914     int tilesize;
 915     int started;
 916     int *v, *flags;
 917     int *dsf_scratch, *border_scratch;
 918 };
 919
 920 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
 921                             int x, int y, int button)
 922 {
 923     const int w = state->shared->params.w;
 924     const int h = state->shared->params.h;
 925
 926     const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
 927     const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
 928
 929     assert(ui);
 930     assert(ds);
 931
 932     button &= ~MOD_MASK;
 933
 934     if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
 935         if (button == LEFT_BUTTON) {
 936             if ((tx == ui->x && ty == ui->y) || state->shared->clues[w*ty+tx])
 937                 ui->x = ui->y = -1;
 938             else ui->x = tx, ui->y = ty;
 939             return ""; /* redraw */
 940         }
 941     }
 942
 943     assert((ui->x == -1) == (ui->y == -1));
 944     if (ui->x == -1) return NULL;
 945     assert(state->shared->clues[w*ui->y + ui->x] == 0);
 946
 947     switch (button) {
 948       case ' ':
 949       case '\r':
 950       case '\n':
 951       case '\b':
 952       case '\177':
 953         button = 0;
 954         break;
 955       default:
 956         if (!isdigit(button)) return NULL;
 957         button -= '0';
 958         if (button > (w == 2 && h == 2? 3: max(w, h))) return NULL;
 959     }
 960
 961     {
 962         const int i = w*ui->y + ui->x;
 963         char buf[64];
 964         ui->x = ui->y = -1;
 965         if (state->board[i] == button) {
 966             return "";                 /* no change - just update ui */
 967         } else {
 968             sprintf(buf, "%d_%d", i, button);
 969             return dupstr(buf);
 970         }
 971     }
 972 }
 973
 974 static game_state *execute_move(game_state *state, char *move)
 975 {
 976     game_state *new_state;
 977
 978     if (*move == 's') {
 979         const int sz = state->shared->params.w * state->shared->params.h;
 980         int i = 0;
 981         new_state = dup_game(state);
 982         for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0';
 983         new_state->cheated = TRUE;
 984     } else {
 985         char *endptr;
 986         const int i = strtol(move, &endptr, 0);
 987         int value;
 988         if (endptr == move) return NULL;
 989         if (*endptr != '_') return NULL;
 990         move = endptr + 1;
 991         value = strtol(move, &endptr, 0);
 992         if (endptr == move) return NULL;
 993         if (*endptr != '\0') return NULL;
 994         new_state = dup_game(state);
 995         new_state->board[i] = value;
 996     }
 997
 998     /*
 999      * Check for completion.
1000      */
1001     if (!new_state->completed) {
1002         const int w = new_state->shared->params.w;
1003         const int h = new_state->shared->params.h;
1004         const int sz = w * h;
1005         int *dsf = make_dsf(NULL, new_state->board, w, h);
1006         int i;
1007         for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i);
1008         sfree(dsf);
1009         if (i == sz)
1010             new_state->completed = TRUE;
1011     }
1012
1013     return new_state;
1014 }
1015
1016 /* ----------------------------------------------------------------------
1017  * Drawing routines.
1018  */
1019
1020 #define FLASH_TIME 0.4F
1021
1022 #define COL_CLUE COL_GRID
1023 enum {
1024     COL_BACKGROUND,
1025     COL_GRID,
1026     COL_HIGHLIGHT,
1027     COL_CORRECT,
1028     COL_ERROR,
1029     COL_USER,
1030     NCOLOURS
1031 };
1032
1033 static void game_compute_size(game_params *params, int tilesize,
1034                               int *x, int *y)
1035 {
1036     *x = (params->w + 1) * tilesize;
1037     *y = (params->h + 1) * tilesize;
1038 }
1039
1040 static void game_set_size(drawing *dr, game_drawstate *ds,
1041                           game_params *params, int tilesize)
1042 {
1043     ds->tilesize = tilesize;
1044 }
1045
1046 static float *game_colours(frontend *fe, int *ncolours)
1047 {
1048     float *ret = snewn(3 * NCOLOURS, float);
1049
1050     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1051
1052     ret[COL_GRID * 3 + 0] = 0.0F;
1053     ret[COL_GRID * 3 + 1] = 0.0F;
1054     ret[COL_GRID * 3 + 2] = 0.0F;
1055
1056     ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
1057     ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1058     ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1059
1060     ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0];
1061     ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1];
1062     ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2];
1063
1064     ret[COL_ERROR * 3 + 0] = 1.0F;
1065     ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1066     ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1067
1068     ret[COL_USER * 3 + 0] = 0.0F;
1069     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1070     ret[COL_USER * 3 + 2] = 0.0F;
1071
1072     *ncolours = NCOLOURS;
1073     return ret;
1074 }
1075
1076 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1077 {
1078     struct game_drawstate *ds = snew(struct game_drawstate);
1079     int i;
1080
1081     ds->tilesize = PREFERRED_TILE_SIZE;
1082     ds->started = 0;
1083     ds->params = state->shared->params;
1084     ds->v = snewn(ds->params.w * ds->params.h, int);
1085     ds->flags = snewn(ds->params.w * ds->params.h, int);
1086     for (i = 0; i < ds->params.w * ds->params.h; i++)
1087         ds->v[i] = ds->flags[i] = -1;
1088     ds->border_scratch = snewn(ds->params.w * ds->params.h, int);
1089     ds->dsf_scratch = NULL;
1090
1091     return ds;
1092 }
1093
1094 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1095 {
1096     sfree(ds->v);
1097     sfree(ds->flags);
1098     sfree(ds->border_scratch);
1099     sfree(ds->dsf_scratch);
1100     sfree(ds);
1101 }
1102
1103 #define BORDER_U   0x001
1104 #define BORDER_D   0x002
1105 #define BORDER_L   0x004
1106 #define BORDER_R   0x008
1107 #define BORDER_UR  0x010
1108 #define BORDER_DR  0x020
1109 #define BORDER_UL  0x040
1110 #define BORDER_DL  0x080
1111 #define CURSOR_BG  0x100
1112 #define CORRECT_BG 0x200
1113 #define ERROR_BG   0x400
1114 #define USER_COL   0x800
1115
1116 static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
1117                         int n, int flags)
1118 {
1119     assert(dr);
1120     assert(ds);
1121
1122     /*
1123      * Clip to the grid square.
1124      */
1125     clip(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1126          TILE_SIZE, TILE_SIZE);
1127
1128     /*
1129      * Clear the square.
1130      */
1131     draw_rect(dr,
1132               BORDER + x*TILE_SIZE,
1133               BORDER + y*TILE_SIZE,
1134               TILE_SIZE,
1135               TILE_SIZE,
1136               (flags & CURSOR_BG ? COL_HIGHLIGHT :
1137                flags & ERROR_BG ? COL_ERROR :
1138                flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
1139
1140     /*
1141      * Draw the grid lines.
1142      */
1143     draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1144               BORDER + (x+1)*TILE_SIZE, BORDER + y*TILE_SIZE, COL_GRID);
1145     draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1146               BORDER + x*TILE_SIZE, BORDER + (y+1)*TILE_SIZE, COL_GRID);
1147
1148     /*
1149      * Draw the number.
1150      */
1151     if (n) {
1152         char buf[2];
1153         buf[0] = n + '0';
1154         buf[1] = '\0';
1155         draw_text(dr,
1156                   (x + 1) * TILE_SIZE,
1157                   (y + 1) * TILE_SIZE,
1158                   FONT_VARIABLE,
1159                   TILE_SIZE / 2,
1160                   ALIGN_VCENTRE | ALIGN_HCENTRE,
1161                   flags & USER_COL ? COL_USER : COL_CLUE,
1162                   buf);
1163     }
1164
1165     /*
1166      * Draw bold lines around the borders.
1167      */
1168     if (flags & BORDER_L)
1169         draw_rect(dr,
1170                   BORDER + x*TILE_SIZE + 1,
1171                   BORDER + y*TILE_SIZE + 1,
1172                   BORDER_WIDTH,
1173                   TILE_SIZE - 1,
1174                   COL_GRID);
1175     if (flags & BORDER_U)
1176         draw_rect(dr,
1177                   BORDER + x*TILE_SIZE + 1,
1178                   BORDER + y*TILE_SIZE + 1,
1179                   TILE_SIZE - 1,
1180                   BORDER_WIDTH,
1181                   COL_GRID);
1182     if (flags & BORDER_R)
1183         draw_rect(dr,
1184                   BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1185                   BORDER + y*TILE_SIZE + 1,
1186                   BORDER_WIDTH,
1187                   TILE_SIZE - 1,
1188                   COL_GRID);
1189     if (flags & BORDER_D)
1190         draw_rect(dr,
1191                   BORDER + x*TILE_SIZE + 1,
1192                   BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1193                   TILE_SIZE - 1,
1194                   BORDER_WIDTH,
1195                   COL_GRID);
1196     if (flags & BORDER_UL)
1197         draw_rect(dr,
1198                   BORDER + x*TILE_SIZE + 1,
1199                   BORDER + y*TILE_SIZE + 1,
1200                   BORDER_WIDTH,
1201                   BORDER_WIDTH,
1202                   COL_GRID);
1203     if (flags & BORDER_UR)
1204         draw_rect(dr,
1205                   BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1206                   BORDER + y*TILE_SIZE + 1,
1207                   BORDER_WIDTH,
1208                   BORDER_WIDTH,
1209                   COL_GRID);
1210     if (flags & BORDER_DL)
1211         draw_rect(dr,
1212                   BORDER + x*TILE_SIZE + 1,
1213                   BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1214                   BORDER_WIDTH,
1215                   BORDER_WIDTH,
1216                   COL_GRID);
1217     if (flags & BORDER_DR)
1218         draw_rect(dr,
1219                   BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1220                   BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1221                   BORDER_WIDTH,
1222                   BORDER_WIDTH,
1223                   COL_GRID);
1224
1225     unclip(dr);
1226
1227     draw_update(dr,
1228                 BORDER + x*TILE_SIZE,
1229                 BORDER + y*TILE_SIZE,
1230                 TILE_SIZE,
1231                 TILE_SIZE);
1232 }
1233
1234 static void draw_grid(drawing *dr, game_drawstate *ds, game_state *state,
1235                       game_ui *ui, int flashy, int borders, int shading)
1236 {
1237     const int w = state->shared->params.w;
1238     const int h = state->shared->params.h;
1239     int x;
1240     int y;
1241
1242     /*
1243      * Build a dsf for the board in its current state, to use for
1244      * highlights and hints.
1245      */
1246     ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h);
1247
1248     /*
1249      * Work out where we're putting borders between the cells.
1250      */
1251     for (y = 0; y < w*h; y++)
1252         ds->border_scratch[y] = 0;
1253
1254     for (y = 0; y < h; y++)
1255         for (x = 0; x < w; x++) {
1256             int dx, dy;
1257             int v1, s1, v2, s2;
1258
1259             for (dx = 0; dx <= 1; dx++) {
1260                 int border = FALSE;
1261
1262                 dy = 1 - dx;
1263
1264                 if (x+dx >= w || y+dy >= h)
1265                     continue;
1266
1267                 v1 = state->board[y*w+x];
1268                 v2 = state->board[(y+dy)*w+(x+dx)];
1269                 s1 = dsf_size(ds->dsf_scratch, y*w+x);
1270                 s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx));
1271
1272                 /*
1273                  * We only ever draw a border between two cells if
1274                  * they don't have the same contents.
1275                  */
1276                 if (v1 != v2) {
1277                     /*
1278                      * But in that situation, we don't always draw
1279                      * a border. We do if the two cells both
1280                      * contain actual numbers...
1281                      */
1282                     if (v1 && v2)
1283                         border = TRUE;
1284
1285                     /*
1286                      * ... or if at least one of them is a
1287                      * completed or overfull omino.
1288                      */
1289                     if (v1 && s1 >= v1)
1290                         border = TRUE;
1291                     if (v2 && s2 >= v2)
1292                         border = TRUE;
1293                 }
1294
1295                 if (border)
1296                     ds->border_scratch[y*w+x] |= (dx ? 1 : 2);
1297             }
1298         }
1299
1300     /*
1301      * Actually do the drawing.
1302      */
1303     for (y = 0; y < h; ++y)
1304         for (x = 0; x < w; ++x) {
1305             /*
1306              * Determine what we need to draw in this square.
1307              */
1308             int v = state->board[y*w+x];
1309             int flags = 0;
1310
1311             if (flashy || !shading) {
1312                 /* clear all background flags */
1313             } else if (x == ui->x && y == ui->y) {
1314                 flags |= CURSOR_BG;
1315             } else if (v) {
1316                 int size = dsf_size(ds->dsf_scratch, y*w+x);
1317                 if (size == v)
1318                     flags |= CORRECT_BG;
1319                 else if (size > v)
1320                     flags |= ERROR_BG;
1321             }
1322
1323             /*
1324              * Borders at the very edges of the grid are
1325              * independent of the `borders' flag.
1326              */
1327             if (x == 0)
1328                 flags |= BORDER_L;
1329             if (y == 0)
1330                 flags |= BORDER_U;
1331             if (x == w-1)
1332                 flags |= BORDER_R;
1333             if (y == h-1)
1334                 flags |= BORDER_D;
1335
1336             if (borders) {
1337                 if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1))
1338                     flags |= BORDER_L;
1339                 if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2))
1340                     flags |= BORDER_U;
1341                 if (x == w-1 || (ds->border_scratch[y*w+x] & 1))
1342                     flags |= BORDER_R;
1343                 if (y == h-1 || (ds->border_scratch[y*w+x] & 2))
1344                     flags |= BORDER_D;
1345
1346                 if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)]))
1347                     flags |= BORDER_UL;
1348                 if (y > 0 && x < w-1 &&
1349                     ((ds->border_scratch[(y-1)*w+x] & 1) ||
1350                      (ds->border_scratch[(y-1)*w+(x+1)] & 2)))
1351                     flags |= BORDER_UR;
1352                 if (y < h-1 && x > 0 &&
1353                     ((ds->border_scratch[y*w+(x-1)] & 2) ||
1354                      (ds->border_scratch[(y+1)*w+(x-1)] & 1)))
1355                     flags |= BORDER_DL;
1356                 if (y < h-1 && x < w-1 &&
1357                     ((ds->border_scratch[y*w+(x+1)] & 2) ||
1358                      (ds->border_scratch[(y+1)*w+x] & 1)))
1359                     flags |= BORDER_DR;
1360             }
1361
1362             if (!state->shared->clues[y*w+x])
1363                 flags |= USER_COL;
1364
1365             if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) {
1366                 draw_square(dr, ds, x, y, v, flags);
1367                 ds->v[y*w+x] = v;
1368                 ds->flags[y*w+x] = flags;
1369             }
1370         }
1371 }
1372
1373 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1374                         game_state *state, int dir, game_ui *ui,
1375                         float animtime, float flashtime)
1376 {
1377     const int w = state->shared->params.w;
1378     const int h = state->shared->params.h;
1379
1380     const int flashy =
1381         flashtime > 0 &&
1382         (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3);
1383
1384     if (!ds->started) {
1385         /*
1386          * The initial contents of the window are not guaranteed and
1387          * can vary with front ends. To be on the safe side, all games
1388          * should start by drawing a big background-colour rectangle
1389          * covering the whole window.
1390          */
1391         draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
1392
1393         /*
1394          * Smaller black rectangle which is the main grid.
1395          */
1396         draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1397                   w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1398                   h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1399                   COL_GRID);
1400
1401         ds->started = TRUE;
1402     }
1403
1404     draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE);
1405 }
1406
1407 static float game_anim_length(game_state *oldstate, game_state *newstate,
1408                               int dir, game_ui *ui)
1409 {
1410     return 0.0F;
1411 }
1412
1413 static float game_flash_length(game_state *oldstate, game_state *newstate,
1414                                int dir, game_ui *ui)
1415 {
1416     assert(oldstate);
1417     assert(newstate);
1418     assert(newstate->shared);
1419     assert(oldstate->shared == newstate->shared);
1420     if (!oldstate->completed && newstate->completed &&
1421         !oldstate->cheated && !newstate->cheated)
1422         return FLASH_TIME;
1423     return 0.0F;
1424 }
1425
1426 static int game_timing_state(game_state *state, game_ui *ui)
1427 {
1428     return TRUE;
1429 }
1430
1431 static void game_print_size(game_params *params, float *x, float *y)
1432 {
1433     int pw, ph;
1434
1435     /*
1436      * I'll use 6mm squares by default.
1437      */
1438     game_compute_size(params, 600, &pw, &ph);
1439     *x = pw / 100.0;
1440     *y = ph / 100.0;
1441 }
1442
1443 static void game_print(drawing *dr, game_state *state, int tilesize)
1444 {
1445     const int w = state->shared->params.w;
1446     const int h = state->shared->params.h;
1447     int c, i, borders;
1448
1449     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1450     game_drawstate *ds = game_new_drawstate(dr, state);
1451     game_set_size(dr, ds, NULL, tilesize);
1452
1453     c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1454     c = print_mono_colour(dr, 0); assert(c == COL_GRID);
1455     c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT);
1456     c = print_mono_colour(dr, 1); assert(c == COL_CORRECT);
1457     c = print_mono_colour(dr, 1); assert(c == COL_ERROR);
1458     c = print_mono_colour(dr, 0); assert(c == COL_USER);
1459
1460     /*
1461      * Border.
1462      */
1463     draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1464               w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1465               h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1466               COL_GRID);
1467
1468     /*
1469      * We'll draw borders between the ominoes iff the grid is not
1470      * pristine. So scan it to see if it is.
1471      */
1472     borders = FALSE;
1473     for (i = 0; i < w*h; i++)
1474         if (state->board[i] && !state->shared->clues[i])
1475             borders = TRUE;
1476
1477     /*
1478      * Draw grid.
1479      */
1480     print_line_width(dr, TILE_SIZE / 64);
1481     draw_grid(dr, ds, state, NULL, FALSE, borders, FALSE);
1482
1483     /*
1484      * Clean up.
1485      */
1486     game_free_drawstate(dr, ds);
1487 }
1488
1489 #ifdef COMBINED
1490 #define thegame filling
1491 #endif
1492
1493 const struct game thegame = {
1494     "Filling", "games.filling", "filling",
1495     default_params,
1496     game_fetch_preset,
1497     decode_params,
1498     encode_params,
1499     free_params,
1500     dup_params,
1501     TRUE, game_configure, custom_params,
1502     validate_params,
1503     new_game_desc,
1504     validate_desc,
1505     new_game,
1506     dup_game,
1507     free_game,
1508     TRUE, solve_game,
1509     TRUE, game_text_format,
1510     new_ui,
1511     free_ui,
1512     encode_ui,
1513     decode_ui,
1514     game_changed_state,
1515     interpret_move,
1516     execute_move,
1517     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1518     game_colours,
1519     game_new_drawstate,
1520     game_free_drawstate,
1521     game_redraw,
1522     game_anim_length,
1523     game_flash_length,
1524     TRUE, FALSE, game_print_size, game_print,
1525     FALSE,                                 /* wants_statusbar */
1526     FALSE, game_timing_state,
1527     0,                                     /* flags */
1528 };
1529
1530 #ifdef STANDALONE_SOLVER /* solver? hah! */
1531
1532 int main(int argc, char **argv) {
1533     while (*++argv) {
1534         game_params *params;
1535         game_state *state;
1536         char *par;
1537         char *desc;
1538
1539         for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc);
1540         if (*desc == '\0') {
1541             fprintf(stderr, "bad puzzle id: %s", par);
1542             continue;
1543         }
1544
1545         *desc++ = '\0';
1546
1547         params = snew(game_params);
1548         decode_params(params, par);
1549         state = new_game(NULL, params, desc);
1550         if (solver(state->board, params->w, params->h, NULL))
1551             printf("%s:%s: solvable\n", par, desc);
1552         else
1553             printf("%s:%s: not solvable\n", par, desc);
1554     }
1555     return 0;
1556 }
1557
1558 #endif