range.c

   1 /*
   2  * range.c: implementation of the Nikoli game 'Kurodoko' / 'Kuromasu'.
   3  */
   4
   5 /*
   6  * Puzzle rules: the player is given a WxH grid of white squares, some
   7  * of which contain numbers. The goal is to paint some of the squares
   8  * black, such that:
   9  *
  10  *  - no cell (err, cell = square) with a number is painted black
  11  *  - no black cells have an adjacent (horz/vert) black cell
  12  *  - the white cells are all connected (through other white cells)
  13  *  - if a cell contains a number n, let h and v be the lengths of the
  14  *    maximal horizontal and vertical white sequences containing that
  15  *    cell.  Then n must equal h + v - 1.
  16  */
  17
  18 /* example instance with its encoding:
  19  *
  20  * +--+--+--+--+--+--+--+
  21  * |  |  |  |  | 7|  |  |
  22  * +--+--+--+--+--+--+--+
  23  * | 3|  |  |  |  |  | 8|
  24  * +--+--+--+--+--+--+--+
  25  * |  |  |  |  |  | 5|  |
  26  * +--+--+--+--+--+--+--+
  27  * |  |  | 7|  | 7|  |  |
  28  * +--+--+--+--+--+--+--+
  29  * |  |13|  |  |  |  |  |
  30  * +--+--+--+--+--+--+--+
  31  * | 4|  |  |  |  |  | 8|
  32  * +--+--+--+--+--+--+--+
  33  * |  |  | 4|  |  |  |  |
  34  * +--+--+--+--+--+--+--+
  35  *
  36  * 7x7:d7b3e8e5c7a7c13e4d8b4d
  37  */
  38
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <string.h>
  42 #include <assert.h>
  43 #include <ctype.h>
  44 #include <math.h>
  45
  46 #include "puzzles.h"
  47
  48 #include <stdarg.h>
  49
  50 #define setmember(obj, field) ( (obj) . field = field )
  51
  52 char *nfmtstr(int n, char *fmt, ...) {
  53     va_list va;
  54     char *ret = snewn(n+1, char);
  55     va_start(va, fmt);
  56     vsprintf(ret, fmt, va);
  57     va_end(va);
  58     return ret;
  59 }
  60
  61 #define SWAP(type, lvar1, lvar2) do { \
  62     type tmp = (lvar1); \
  63     (lvar1) = (lvar2); \
  64     (lvar2) = tmp; \
  65 } while (0)
  66
  67 /* ----------------------------------------------------------------------
  68  * Game parameters, presets, states
  69  */
  70
  71 typedef signed char puzzle_size;
  72
  73 struct game_params {
  74     puzzle_size w;
  75     puzzle_size h;
  76 };
  77
  78 struct game_state {
  79     struct game_params params;
  80     unsigned int has_cheated: 1;
  81     unsigned int was_solved: 1;
  82     puzzle_size *grid;
  83 };
  84
  85 #define DEFAULT_PRESET 0
  86 static struct game_params presets[] = {{9, 6}, {12, 8}, {13, 9}, {16, 11}};
  87 /* rationale: I want all four combinations of {odd/even, odd/even}, as
  88  * they play out differently with respect to two-way symmetry.  I also
  89  * want them to be generated relatively fast yet still be large enough
  90  * to be entertaining for a decent amount of time, and I want them to
  91  * make good use of monitor real estate (the typical screen resolution
  92  * is why I do 13x9 and not 9x13).
  93  */
  94
  95 static game_params *default_params(void)
  96 {
  97     game_params *ret = snew(game_params);
  98     *ret = presets[DEFAULT_PRESET]; /* structure copy */
  99     return ret;
 100 }
 101
 102 static game_params *dup_params(game_params *params)
 103 {
 104     game_params *ret = snew(game_params);
 105     *ret = *params; /* structure copy */
 106     return ret;
 107 }
 108
 109 static int game_fetch_preset(int i, char **name, game_params **params)
 110 {
 111     if (i < 0 || i >= lenof(presets)) return FALSE;
 112
 113     *name = nfmtstr(40, "%d x %d", presets[i].w, presets[i].h);
 114     *params = dup_params(&presets[i]);
 115
 116     return TRUE;
 117 }
 118
 119 static void free_params(game_params *params)
 120 {
 121     sfree(params);
 122 }
 123
 124 static void decode_params(game_params *params, char const *string)
 125 {
 126     /* FIXME check for puzzle_size overflow and decoding issues */
 127     params->w = params->h = atoi(string);
 128     while (*string && isdigit((unsigned char) *string)) ++string;
 129     if (*string == 'x') {
 130         string++;
 131         params->h = atoi(string);
 132         while (*string && isdigit((unsigned char)*string)) string++;
 133     }
 134 }
 135
 136 static char *encode_params(game_params *params, int full)
 137 {
 138     char str[80];
 139     sprintf(str, "%dx%d", params->w, params->h);
 140     return dupstr(str);
 141 }
 142
 143 static config_item *game_configure(game_params *params)
 144 {
 145     config_item *ret;
 146
 147     ret = snewn(3, config_item);
 148
 149     ret[0].name = "Width";
 150     ret[0].type = C_STRING;
 151     ret[0].sval = nfmtstr(10, "%d", params->w);
 152     ret[0].ival = 0;
 153
 154     ret[1].name = "Height";
 155     ret[1].type = C_STRING;
 156     ret[1].sval = nfmtstr(10, "%d", params->h);
 157     ret[1].ival = 0;
 158
 159     ret[2].name = NULL;
 160     ret[2].type = C_END;
 161     ret[2].sval = NULL;
 162     ret[2].ival = 0;
 163
 164     return ret;
 165 }
 166
 167 static game_params *custom_params(config_item *configuration)
 168 {
 169     game_params *ret = snew(game_params);
 170     ret->w = atoi(configuration[0].sval);
 171     ret->h = atoi(configuration[1].sval);
 172     return ret;
 173 }
 174
 175 #define memdup(dst, src, n, type) do { \
 176     dst = snewn(n, type); \
 177     memcpy(dst, src, n * sizeof (type)); \
 178 } while (0)
 179
 180 static game_state *dup_game(game_state *state)
 181 {
 182     game_state *ret = snew(game_state);
 183     int const n = state->params.w * state->params.h;
 184
 185     *ret = *state; /* structure copy */
 186
 187     /* copy the poin_tee_, set a new value of the poin_ter_ */
 188     memdup(ret->grid, state->grid, n, puzzle_size);
 189
 190     return ret;
 191 }
 192
 193 static void free_game(game_state *state)
 194 {
 195     sfree(state->grid);
 196     sfree(state);
 197 }
 198
 199
 200 /* ----------------------------------------------------------------------
 201  * The solver subsystem.
 202  *
 203  * The solver is used for two purposes:
 204  *  - To solve puzzles when the user selects `Solve'.
 205  *  - To test solubility of a grid as clues are being removed from it
 206  *    during the puzzle generation.
 207  *
 208  * It supports the following ways of reasoning:
 209  *
 210  *  - A cell adjacent to a black cell must be white.
 211  *
 212  *  - If painting a square black would bisect the white regions, that
 213  *    square is white (by finding biconnected components' cut points)
 214  *
 215  *  - A cell with number n, covering at most k white squares in three
 216  *    directions must white-cover n-k squares in the last direction.
 217  *
 218  *  - A cell with number n known to cover k squares, if extending the
 219  *    cover by one square in a given direction causes the cell to
 220  *    cover _more_ than n squares, that extension cell must be black.
 221  *
 222  *    (either if the square already covers n, or if it extends into a
 223  *    chunk of size > n - k)
 224  *
 225  *  - Recursion.  Pick any cell and see if this leads to either a
 226  *    contradiction or a solution (and then act appropriately).
 227  *
 228  *
 229  * TODO:
 230  *
 231  * (propagation upper limit)
 232  *  - If one has two numbers on the same line, the smaller limits the
 233  *    larger.  Example: in |b|_|_|8|4|_|_|b|, only two _'s can be both
 234  *    white and connected to the "8" cell; so that cell will propagate
 235  *    at least four cells orthogonally to the displayed line (which is
 236  *    better than the current "at least 2").
 237  *
 238  * (propagation upper limit)
 239  *  - cells can't propagate into other cells if doing so exceeds that
 240  *    number.  Example: in |b|4|.|.|2|b|, at most one _ can be white;
 241  *    otherwise, the |2| would have too many reaching white cells.
 242  *
 243  * (propagation lower and upper limit)
 244  *  - `Full Combo': in each four directions d_1 ... d_4, find a set of
 245  *    possible propagation distances S_1 ... S_4.  For each i=1..4,
 246  *    for each x in S_i: if not exists (y, z, w) in the other sets
 247  *    such that (x+y+z+w+1 == clue value): then remove x from S_i.
 248  *    Repeat until this stabilizes.  If any cell would contradict
 249  */
 250
 251 #define idx(i, j, w) ((i)*(w) + (j))
 252 #define out_of_bounds(r, c, w, h) \
 253    ((r) < 0 || (r) >= h || (c) < 0 || (c) >= w)
 254
 255 typedef struct square {
 256     puzzle_size r, c;
 257 } square;
 258
 259 enum {BLACK = -2, WHITE, EMPTY};
 260 /* white is for pencil marks, empty is undecided */
 261
 262 static int const dr[4] = {+1,  0, -1,  0};
 263 static int const dc[4] = { 0, +1,  0, -1};
 264 static int const cursors[4] = /* must match dr and dc */
 265 {CURSOR_DOWN, CURSOR_RIGHT, CURSOR_UP, CURSOR_LEFT};
 266
 267 typedef struct move {
 268     square square;
 269     unsigned int colour: 1;
 270 } move;
 271 enum {M_BLACK = 0, M_WHITE = 1};
 272
 273 typedef move *(reasoning)(game_state *state,
 274                           int nclues,
 275                           const square *clues,
 276                           move *buf);
 277
 278 static reasoning solver_reasoning_not_too_big;
 279 static reasoning solver_reasoning_adjacency;
 280 static reasoning solver_reasoning_connectedness;
 281 static reasoning solver_reasoning_recursion;
 282
 283 enum {
 284     DIFF_NOT_TOO_BIG,
 285     DIFF_ADJACENCY,
 286     DIFF_CONNECTEDNESS,
 287     DIFF_RECURSION
 288 };
 289
 290 static move *solve_internal(game_state *state, move *base, int diff);
 291
 292 static char *solve_game(game_state *orig, game_state *curpos,
 293                         char *aux, char **error)
 294 {
 295     int const n = orig->params.w * orig->params.h;
 296     move *const base = snewn(n, move);
 297     move *moves = solve_internal(orig, base, DIFF_RECURSION);
 298
 299     char *ret = NULL;
 300
 301     if (moves != NULL) {
 302         int const k = moves - base;
 303         char *str = ret = snewn(15*k + 2, char);
 304         char colour[2] = "BW";
 305         move *it;
 306         *str++ = 'S';
 307         *str = '\0';
 308         for (it = base; it < moves; ++it)
 309             str += sprintf(str, "%c,%d,%d", colour[it->colour],
 310                            it->square.r, it->square.c);
 311     } else *error = "This puzzle instance contains a contradiction";
 312
 313     sfree(base);
 314     return ret;
 315 }
 316
 317 static square *find_clues(game_state *state, int *ret_nclues);
 318 static move *do_solve(game_state *state,
 319                       int nclues,
 320                       const square *clues,
 321                       move *move_buffer,
 322                       int difficulty);
 323
 324 /* new_game_desc entry point in the solver subsystem */
 325 static move *solve_internal(game_state *state, move *base, int diff)
 326 {
 327     int nclues;
 328     square *const clues = find_clues(state, &nclues);
 329     game_state *dup = dup_game(state);
 330     move *const moves = do_solve(dup, nclues, clues, base, diff);
 331     free_game(dup);
 332     sfree(clues);
 333     return moves;
 334 }
 335
 336 static move *do_solve(game_state *state,
 337                       int nclues,
 338                       const square *clues,
 339                       move *move_buffer,
 340                       int difficulty)
 341 {
 342     reasoning *reasonings[] = {
 343         solver_reasoning_not_too_big,
 344         solver_reasoning_adjacency,
 345         solver_reasoning_connectedness,
 346         solver_reasoning_recursion
 347     };
 348
 349     struct move *buf = move_buffer, *oldbuf;
 350     int i;
 351
 352     do {
 353         oldbuf = buf;
 354         for (i = 0; i < lenof(reasonings) && i <= difficulty; ++i) {
 355             /* only recurse if all else fails */
 356             if (i == DIFF_RECURSION && buf > oldbuf) continue;
 357             buf = (*reasonings[i])(state, nclues, clues, buf);
 358             if (buf == NULL) return NULL;
 359         }
 360     } while (buf > oldbuf);
 361
 362     return buf;
 363 }
 364
 365 #define MASK(n) (1 << ((n) + 2))
 366
 367 static int runlength(puzzle_size r, puzzle_size c,
 368                      puzzle_size dr, puzzle_size dc,
 369                      game_state *state, int colourmask)
 370 {
 371     int const w = state->params.w, h = state->params.h;
 372     int sz = 0;
 373     while (TRUE) {
 374         int cell = idx(r, c, w);
 375         if (out_of_bounds(r, c, w, h)) break;
 376         if (state->grid[cell] > 0) {
 377             if (!(colourmask & ~(MASK(BLACK) | MASK(WHITE) | MASK(EMPTY))))
 378                 break;
 379         } else if (!(MASK(state->grid[cell]) & colourmask)) break;
 380         ++sz;
 381         r += dr;
 382         c += dc;
 383     }
 384     return sz;
 385 }
 386
 387 static void solver_makemove(puzzle_size r, puzzle_size c, int colour,
 388                             game_state *state, move **buffer_ptr)
 389 {
 390     int const cell = idx(r, c, state->params.w);
 391     if (out_of_bounds(r, c, state->params.w, state->params.h)) return;
 392     if (state->grid[cell] != EMPTY) return;
 393     setmember((*buffer_ptr)->square, r);
 394     setmember((*buffer_ptr)->square, c);
 395     setmember(**buffer_ptr, colour);
 396     ++*buffer_ptr;
 397     state->grid[cell] = (colour == M_BLACK ? BLACK : WHITE);
 398 }
 399
 400 static move *solver_reasoning_adjacency(game_state *state,
 401                                         int nclues,
 402                                         const square *clues,
 403                                         move *buf)
 404 {
 405     int r, c, i;
 406     for (r = 0; r < state->params.h; ++r)
 407         for (c = 0; c < state->params.w; ++c) {
 408             int const cell = idx(r, c, state->params.w);
 409             if (state->grid[cell] != BLACK) continue;
 410             for (i = 0; i < 4; ++i)
 411                 solver_makemove(r + dr[i], c + dc[i], M_WHITE, state, &buf);
 412         }
 413     return buf;
 414 }
 415
 416 enum {NOT_VISITED = -1};
 417
 418 static int dfs_biconnect_visit(puzzle_size r, puzzle_size c,
 419                                game_state *state,
 420                                square *dfs_parent, int *dfs_depth,
 421                                move **buf);
 422
 423 static move *solver_reasoning_connectedness(game_state *state,
 424                                             int nclues,
 425                                             const square *clues,
 426                                             move *buf)
 427 {
 428     int const w = state->params.w, h = state->params.h, n = w * h;
 429
 430     square *const dfs_parent = snewn(n, square);
 431     int *const dfs_depth = snewn(n, int);
 432
 433     int i;
 434     for (i = 0; i < n; ++i) {
 435         dfs_parent[i].r = NOT_VISITED;
 436         dfs_depth[i] = -n;
 437     }
 438
 439     for (i = 0; i < n && state->grid[i] == BLACK; ++i);
 440
 441     dfs_parent[i].r = i / w;
 442     dfs_parent[i].c = i % w; /* `dfs root`.parent == `dfs root` */
 443     dfs_depth[i] = 0;
 444
 445     dfs_biconnect_visit(i / w, i % w, state, dfs_parent, dfs_depth, &buf);
 446
 447     sfree(dfs_parent);
 448     sfree(dfs_depth);
 449
 450     return buf;
 451 }
 452
 453 /* returns the `lowpoint` of (r, c) */
 454 static int dfs_biconnect_visit(puzzle_size r, puzzle_size c,
 455                                game_state *state,
 456                                square *dfs_parent, int *dfs_depth,
 457                                move **buf)
 458 {
 459     const puzzle_size w = state->params.w, h = state->params.h;
 460     int const i = idx(r, c, w), mydepth = dfs_depth[i];
 461     int lowpoint = mydepth, j, nchildren = 0;
 462
 463     for (j = 0; j < 4; ++j) {
 464         const puzzle_size rr = r + dr[j], cc = c + dc[j];
 465         int const cell = idx(rr, cc, w);
 466
 467         if (out_of_bounds(rr, cc, w, h)) continue;
 468         if (state->grid[cell] == BLACK) continue;
 469
 470         if (dfs_parent[cell].r == NOT_VISITED) {
 471             int child_lowpoint;
 472             dfs_parent[cell].r = r;
 473             dfs_parent[cell].c = c;
 474             dfs_depth[cell] = mydepth + 1;
 475             child_lowpoint = dfs_biconnect_visit(rr, cc, state, dfs_parent,
 476                                                  dfs_depth, buf);
 477
 478             if (child_lowpoint >= mydepth && mydepth > 0)
 479                 solver_makemove(r, c, M_WHITE, state, buf);
 480
 481             lowpoint = min(lowpoint, child_lowpoint);
 482             ++nchildren;
 483         } else if (rr != dfs_parent[i].r || cc != dfs_parent[i].c) {
 484             lowpoint = min(lowpoint, dfs_depth[cell]);
 485         }
 486     }
 487
 488     if (mydepth == 0 && nchildren >= 2)
 489         solver_makemove(r, c, M_WHITE, state, buf);
 490
 491     return lowpoint;
 492 }
 493
 494 static move *solver_reasoning_not_too_big(game_state *state,
 495                                           int nclues,
 496                                           const square *clues,
 497                                           move *buf)
 498 {
 499     int const w = state->params.w, runmasks[4] = {
 500         ~(MASK(BLACK) | MASK(EMPTY)),
 501         MASK(EMPTY),
 502         ~(MASK(BLACK) | MASK(EMPTY)),
 503         ~(MASK(BLACK))
 504     };
 505     enum {RUN_WHITE, RUN_EMPTY, RUN_BEYOND, RUN_SPACE};
 506
 507     int i, runlengths[4][4];
 508
 509     for (i = 0; i < nclues; ++i) {
 510         int j, k, whites, space;
 511
 512         const puzzle_size row = clues[i].r, col = clues[i].c;
 513         int const clue = state->grid[idx(row, col, w)];
 514
 515         for (j = 0; j < 4; ++j) {
 516             puzzle_size r = row + dr[j], c = col + dc[j];
 517             runlengths[RUN_SPACE][j] = 0;
 518             for (k = 0; k <= RUN_SPACE; ++k) {
 519                 int l = runlength(r, c, dr[j], dc[j], state, runmasks[k]);
 520                 if (k < RUN_SPACE) {
 521                     runlengths[k][j] = l;
 522                     r += dr[j] * l;
 523                     c += dc[j] * l;
 524                 }
 525                 runlengths[RUN_SPACE][j] += l;
 526             }
 527         }
 528
 529         whites = 1;
 530         for (j = 0; j < 4; ++j) whites += runlengths[RUN_WHITE][j];
 531
 532         for (j = 0; j < 4; ++j) {
 533             int const delta = 1 + runlengths[RUN_WHITE][j];
 534             const puzzle_size r = row + delta * dr[j];
 535             const puzzle_size c = col + delta * dc[j];
 536
 537             if (whites == clue) {
 538                 solver_makemove(r, c, M_BLACK, state, &buf);
 539                 continue;
 540             }
 541
 542             if (runlengths[RUN_EMPTY][j] == 1 &&
 543                 whites
 544                 + runlengths[RUN_EMPTY][j]
 545                 + runlengths[RUN_BEYOND][j]
 546                 > clue) {
 547                 solver_makemove(r, c, M_BLACK, state, &buf);
 548                 continue;
 549             }
 550
 551             if (whites
 552                 + runlengths[RUN_EMPTY][j]
 553                 + runlengths[RUN_BEYOND][j]
 554                 > clue) {
 555                 runlengths[RUN_SPACE][j] =
 556                     runlengths[RUN_WHITE][j] +
 557                     runlengths[RUN_EMPTY][j] - 1;
 558
 559                 if (runlengths[RUN_EMPTY][j] == 1)
 560                     solver_makemove(r, c, M_BLACK, state, &buf);
 561             }
 562         }
 563
 564         space = 1;
 565         for (j = 0; j < 4; ++j) space += runlengths[RUN_SPACE][j];
 566         for (j = 0; j < 4; ++j) {
 567             puzzle_size r = row + dr[j], c = col + dc[j];
 568
 569             int k = space - runlengths[RUN_SPACE][j];
 570             if (k >= clue) continue;
 571
 572             for (; k < clue; ++k, r += dr[j], c += dc[j])
 573                 solver_makemove(r, c, M_WHITE, state, &buf);
 574         }
 575     }
 576     return buf;
 577 }
 578
 579 static move *solver_reasoning_recursion(game_state *state,
 580                                         int nclues,
 581                                         const square *clues,
 582                                         move *buf)
 583 {
 584     int const w = state->params.w, n = w * state->params.h;
 585     int cell, colour;
 586
 587     for (cell = 0; cell < n; ++cell) {
 588         int const r = cell / w, c = cell % w;
 589         int i;
 590         game_state *newstate;
 591         move *recursive_result;
 592
 593         if (state->grid[cell] != EMPTY) continue;
 594
 595         /* FIXME: add enum alias for smallest and largest (or N) */
 596         for (colour = M_BLACK; colour <= M_WHITE; ++colour) {
 597             newstate = dup_game(state);
 598             newstate->grid[cell] = colour;
 599             recursive_result = do_solve(newstate, nclues, clues, buf,
 600                                         DIFF_RECURSION);
 601             free_game(newstate);
 602             if (recursive_result == NULL) {
 603                 solver_makemove(r, c, M_BLACK + M_WHITE - colour, state, &buf);
 604                 return buf;
 605             }
 606             for (i = 0; i < n && newstate->grid[i] != EMPTY; ++i);
 607             if (i == n) return buf;
 608         }
 609     }
 610     return buf;
 611 }
 612
 613 static square *find_clues(game_state *state, int *ret_nclues)
 614 {
 615     int r, c, i, nclues = 0;
 616     square *ret = snewn(state->params.w * state->params.h, struct square);
 617
 618     for (i = r = 0; r < state->params.h; ++r)
 619         for (c = 0; c < state->params.w; ++c, ++i)
 620             if (state->grid[i] > 0) {
 621                 ret[nclues].r = r;
 622                 ret[nclues].c = c;
 623                 ++nclues;
 624             }
 625
 626     *ret_nclues = nclues;
 627     return sresize(ret, nclues + (nclues == 0), square);
 628 }
 629
 630 /* ----------------------------------------------------------------------
 631  * Puzzle generation
 632  *
 633  * Generating kurodoko instances is rather straightforward:
 634  *
 635  *  - Start with a white grid and add black squares at randomly chosen
 636  *    locations, unless colouring that square black would violate
 637  *    either the adjacency or connectedness constraints.
 638  *
 639  *  - For each white square, compute the number it would contain if it
 640  *    were given as a clue.
 641  *
 642  *  - From a starting point of "give _every_ white square as a clue",
 643  *    for each white square (in a random order), see if the board is
 644  *    solvable when that square is not given as a clue.  If not, don't
 645  *    give it as a clue, otherwise do.
 646  *
 647  * This never fails, but it's only _almost_ what I do.  The real final
 648  * step is this:
 649  *
 650  *  - From a starting point of "give _every_ white square as a clue",
 651  *    first remove all clues that are two-way rotationally symmetric
 652  *    to a black square.  If this leaves the puzzle unsolvable, throw
 653  *    it out and try again.  Otherwise, remove all _pairs_ of clues
 654  *    (that are rotationally symmetric) which can be removed without
 655  *    rendering the puzzle unsolvable.
 656  *
 657  * This can fail even if one only removes the black and symmetric
 658  * clues; indeed it happens often (avg. once or twice per puzzle) when
 659  * generating 1xN instances.  (If you add black cells they must be in
 660  * the end, and if you only add one, it's ambiguous where).
 661  */
 662
 663 /* forward declarations of internal calls */
 664 static void newdesc_choose_black_squares(game_state *state,
 665                                          const int *shuffle_1toN);
 666 static void newdesc_compute_clues(game_state *state);
 667 static int newdesc_strip_clues(game_state *state, int *shuffle_1toN);
 668 static char *newdesc_encode_game_description(int n, puzzle_size *grid);
 669
 670 static char *new_game_desc(game_params *params, random_state *rs,
 671                            char **aux, int interactive)
 672 {
 673     int const w = params->w, h = params->h, n = w * h;
 674
 675     puzzle_size *const grid = snewn(n, puzzle_size);
 676     int *const shuffle_1toN = snewn(n, int);
 677
 678     int i, clues_removed;
 679
 680     char *encoding;
 681
 682     game_state state;
 683     state.params = *params;
 684     state.grid = grid;
 685
 686     interactive = 0; /* I don't need it, I shouldn't use it*/
 687
 688     for (i = 0; i < n; ++i) shuffle_1toN[i] = i;
 689
 690     while (TRUE) {
 691         shuffle(shuffle_1toN, n, sizeof (int), rs);
 692         newdesc_choose_black_squares(&state, shuffle_1toN);
 693
 694         newdesc_compute_clues(&state);
 695
 696         shuffle(shuffle_1toN, n, sizeof (int), rs);
 697         clues_removed = newdesc_strip_clues(&state, shuffle_1toN);
 698
 699         if (clues_removed < 0) continue; else break;
 700     }
 701
 702     encoding = newdesc_encode_game_description(n, grid);
 703
 704     sfree(grid);
 705     sfree(shuffle_1toN);
 706
 707     return encoding;
 708 }
 709
 710 static int dfs_count_white(game_state *state, int cell);
 711
 712 static void newdesc_choose_black_squares(game_state *state,
 713                                          const int *shuffle_1toN)
 714 {
 715     int const w = state->params.w, h = state->params.h, n = w * h;
 716
 717     int k, any_white_cell, n_black_cells;
 718
 719     for (k = 0; k < n; ++k) state->grid[k] = WHITE;
 720
 721     any_white_cell = shuffle_1toN[n - 1];
 722     n_black_cells = 0;
 723
 724     /* I like the puzzles that result from n / 3, but maybe this
 725      * could be made a (generation, i.e. non-full) parameter? */
 726     for (k = 0; k < n / 3; ++k) {
 727         int const i = shuffle_1toN[k], c = i % w, r = i / w;
 728
 729         int j;
 730         for (j = 0; j < 4; ++j) {
 731             int const rr = r + dr[j], cc = c + dc[j], cell = idx(rr, cc, w);
 732             /* if you're out of bounds, we skip you */
 733             if (out_of_bounds(rr, cc, w, h)) continue;
 734             if (state->grid[cell] == BLACK) break; /* I can't be black */
 735         } if (j < 4) continue; /* I have black neighbour: I'm white */
 736
 737         state->grid[i] = BLACK;
 738         ++n_black_cells;
 739
 740         j = dfs_count_white(state, any_white_cell);
 741         if (j + n_black_cells < n) {
 742             state->grid[i] = WHITE;
 743             --n_black_cells;
 744         }
 745     }
 746 }
 747
 748 static void newdesc_compute_clues(game_state *state)
 749 {
 750     int const w = state->params.w, h = state->params.h;
 751     int r, c;
 752
 753     for (r = 0; r < h; ++r) {
 754         int run_size = 0, c, cc;
 755         for (c = 0; c <= w; ++c) {
 756             if (c == w || state->grid[idx(r, c, w)] == BLACK) {
 757                 for (cc = c - run_size; cc < c; ++cc)
 758                     state->grid[idx(r, cc, w)] += run_size;
 759                 run_size = 0;
 760             } else ++run_size;
 761         }
 762     }
 763
 764     for (c = 0; c < w; ++c) {
 765         int run_size = 0, r, rr;
 766         for (r = 0; r <= h; ++r) {
 767             if (r == h || state->grid[idx(r, c, w)] == BLACK) {
 768                 for (rr = r - run_size; rr < r; ++rr)
 769                     state->grid[idx(rr, c, w)] += run_size;
 770                 run_size = 0;
 771             } else ++run_size;
 772         }
 773     }
 774 }
 775
 776 #define rotate(x) (n - 1 - (x))
 777
 778 static int newdesc_strip_clues(game_state *state, int *shuffle_1toN)
 779 {
 780     int const w = state->params.w, n = w * state->params.h;
 781
 782     move *const move_buffer = snewn(n, move);
 783     move *buf;
 784     game_state *dupstate;
 785
 786     /*
 787      * do a partition/pivot of shuffle_1toN into three groups:
 788      * (1) squares rotationally-symmetric to (3)
 789      * (2) squares not in (1) or (3)
 790      * (3) black squares
 791      *
 792      * They go from [0, left), [left, right) and [right, n) in
 793      * shuffle_1toN (and from there into state->grid[ ])
 794      *
 795      * Then, remove clues from the grid one by one in shuffle_1toN
 796      * order, until the solver becomes unhappy.  If we didn't remove
 797      * all of (1), return (-1).  Else, we're happy.
 798      */
 799
 800     /* do the partition */
 801     int clues_removed, k = 0, left = 0, right = n;
 802
 803     for (;; ++k) {
 804         while (k < right && state->grid[shuffle_1toN[k]] == BLACK) {
 805             --right;
 806             SWAP(int, shuffle_1toN[right], shuffle_1toN[k]);
 807             assert(state->grid[shuffle_1toN[right]] == BLACK);
 808         }
 809         if (k >= right) break;
 810         assert (k >= left);
 811         if (state->grid[rotate(shuffle_1toN[k])] == BLACK) {
 812             SWAP(int, shuffle_1toN[k], shuffle_1toN[left]);
 813             ++left;
 814         }
 815         assert (state->grid[rotate(shuffle_1toN[k])] != BLACK
 816                 || k == left - 1);
 817     }
 818
 819     for (k = 0; k < left; ++k) {
 820         assert (state->grid[rotate(shuffle_1toN[k])] == BLACK);
 821         state->grid[shuffle_1toN[k]] = EMPTY;
 822     }
 823     for (k = left; k < right; ++k) {
 824         assert (state->grid[rotate(shuffle_1toN[k])] != BLACK);
 825         assert (state->grid[shuffle_1toN[k]] != BLACK);
 826     }
 827     for (k = right; k < n; ++k) {
 828         assert (state->grid[shuffle_1toN[k]] == BLACK);
 829         state->grid[shuffle_1toN[k]] = EMPTY;
 830     }
 831
 832     clues_removed = (left - 0) + (n - right);
 833
 834     dupstate = dup_game(state);
 835     buf = solve_internal(dupstate, move_buffer, DIFF_RECURSION - 1);
 836     free_game(dupstate);
 837     if (buf - move_buffer < clues_removed) {
 838         /* branch prediction: I don't think I'll go here */
 839         clues_removed = -1;
 840         goto ret;
 841     }
 842
 843     for (k = left; k < right; ++k) {
 844         const int i = shuffle_1toN[k], j = rotate(i);
 845         int const clue = state->grid[i], clue_rot = state->grid[j];
 846         if (clue == BLACK) continue;
 847         state->grid[i] = state->grid[j] = EMPTY;
 848         dupstate = dup_game(state);
 849         buf = solve_internal(dupstate, move_buffer, DIFF_RECURSION - 1);
 850         free_game(dupstate);
 851         clues_removed += 2 - (i == j);
 852         /* if i is the center square, then i == (j = rotate(i))
 853          * when i and j are one, removing i and j removes only one */
 854         if (buf - move_buffer == clues_removed) continue;
 855         /* if the solver is sound, refilling all removed clues means
 856          * we have filled all squares, i.e. solved the puzzle. */
 857         state->grid[i] = clue;
 858         state->grid[j] = clue_rot;
 859         clues_removed -= 2 - (i == j);
 860     }
 861
 862 ret:
 863     sfree(move_buffer);
 864     return clues_removed;
 865 }
 866
 867 static int dfs_count_rec(puzzle_size *grid, int r, int c, int w, int h)
 868 {
 869     int const cell = idx(r, c, w);
 870     if (out_of_bounds(r, c, w, h)) return 0;
 871     if (grid[cell] != WHITE) return 0;
 872     grid[cell] = EMPTY;
 873     return 1 +
 874         dfs_count_rec(grid, r + 0, c + 1, w, h) +
 875         dfs_count_rec(grid, r + 0, c - 1, w, h) +
 876         dfs_count_rec(grid, r + 1, c + 0, w, h) +
 877         dfs_count_rec(grid, r - 1, c + 0, w, h);
 878 }
 879
 880 static int dfs_count_white(game_state *state, int cell)
 881 {
 882     int const w = state->params.w, h = state->params.h, n = w * h;
 883     int const r = cell / w, c = cell % w;
 884     int i, k = dfs_count_rec(state->grid, r, c, w, h);
 885     for (i = 0; i < n; ++i)
 886         if (state->grid[i] == EMPTY)
 887             state->grid[i] = WHITE;
 888     return k;
 889 }
 890
 891 static char *validate_params(game_params *params, int full)
 892 {
 893     int const w = params->w, h = params->h;
 894     if (w < 1) return "Error: width is less than 1";
 895     if (h < 1) return "Error: height is less than 1";
 896     if (w * h < 1) return "Error: size is less than 1";
 897     if (w + h - 1 > SCHAR_MAX) return "Error: w + h is too big";
 898     /* I might be unable to store clues in my puzzle_size *grid; */
 899     if (full) {
 900         if (w == 2 && h == 2) return "Error: can't create 2x2 puzzles";
 901         if (w == 1 && h == 2) return "Error: can't create 1x2 puzzles";
 902         if (w == 2 && h == 1) return "Error: can't create 2x1 puzzles";
 903         if (w == 1 && h == 1) return "Error: can't create 1x1 puzzles";
 904     }
 905     return NULL;
 906 }
 907
 908 /* Definition: a puzzle instance is _good_ if:
 909  *  - it has a unique solution
 910  *  - the solver can find this solution without using recursion
 911  *  - the solution contains at least one black square
 912  *  - the clues are 2-way rotationally symmetric
 913  *
 914  * (the idea being: the generator can not output any _bad_ puzzles)
 915  *
 916  * Theorem: validate_params, when full != 0, discards exactly the set
 917  * of parameters for which there are _no_ good puzzle instances.
 918  *
 919  * Proof: it's an immediate consequence of the five lemmas below.
 920  *
 921  * Observation: not only do puzzles on non-tiny grids exist, the
 922  * generator is pretty fast about coming up with them.  On my pre-2004
 923  * desktop box, it generates 100 puzzles on the highest preset (16x11)
 924  * in 8.383 seconds, or <= 0.1 second per puzzle.
 925  *
 926  * ----------------------------------------------------------------------
 927  *
 928  * Lemma: On a 1x1 grid, there are no good puzzles.
 929  *
 930  * Proof: the one square can't be a clue because at least one square
 931  * is black.  But both a white square and a black square satisfy the
 932  * solution criteria, so the puzzle is ambiguous (and hence bad).
 933  *
 934  * Lemma: On a 1x2 grid, there are no good puzzles.
 935  *
 936  * Proof: let's name the squares l and r.  Note that there can be at
 937  * most one black square, or adjacency is violated.  By assumption at
 938  * least one square is black, so let's call that one l.  By clue
 939  * symmetry, neither l nor r can be given as a clue, so the puzzle
 940  * instance is blank and thus ambiguous.
 941  *
 942  * Corollary: On a 2x1 grid, there are no good puzzles.
 943  * Proof: rotate the above proof 90 degrees ;-)
 944  *
 945  * ----------------------------------------------------------------------
 946  *
 947  * Lemma: On a 2x2 grid, there are no soluble puzzles with 2-way
 948  * rotational symmetric clues and at least one black square.
 949  *
 950  * Proof: Let's name the squares a, b, c, and d, with a and b on the
 951  * top row, a and c in the left column.  Let's consider the case where
 952  * a is black.  Then no other square can be black: b and c would both
 953  * violate the adjacency constraint; d would disconnect b from c.
 954  *
 955  * So exactly one square is black (and by 4-way rotation symmetry of
 956  * the 2x2 square, it doesn't matter which one, so let's stick to a).
 957  * By 2-way rotational symmetry of the clues and the rule about not
 958  * painting numbers black, neither a nor d can be clues.  A blank
 959  * puzzle would be ambiguous, so one of {b, c} is a clue; by symmetry,
 960  * so is the other one.
 961  *
 962  * It is readily seen that their clue value is 2.  But "a is black"
 963  * and "d is black" are both valid solutions in this case, so the
 964  * puzzle is ambiguous (and hence bad).
 965  *
 966  * ----------------------------------------------------------------------
 967  *
 968  * Lemma: On a wxh grid with w, h >= 1 and (w > 2 or h > 2), there is
 969  * at least one good puzzle.
 970  *
 971  * Proof: assume that w > h (otherwise rotate the proof again).  Paint
 972  * the top left and bottom right corners black, and fill a clue into
 973  * all the other squares.  Present this board to the solver code (or
 974  * player, hypothetically), except with the two black squares as blank
 975  * squares.
 976  *
 977  * For an Nx1 puzzle, observe that every clue is N - 2, and there are
 978  * N - 2 of them in one connected sequence, so the remaining two
 979  * squares can be deduced to be black, which solves the puzzle.
 980  *
 981  * For any other puzzle, let j be a cell in the same row as a black
 982  * cell, but not in the same column (such a cell doesn't exist in 2x3
 983  * puzzles, but we assume w > h and such cells exist in 3x2 puzzles).
 984  *
 985  * Note that the number of cells in axis parallel `rays' going out
 986  * from j exceeds j's clue value by one.  Only one such cell is a
 987  * non-clue, so it must be black.  Similarly for the other corner (let
 988  * j' be a cell in the same row as the _other_ black cell, but not in
 989  * the same column as _any_ black cell; repeat this argument at j').
 990  *
 991  * This fills the grid and satisfies all clues and the adjacency
 992  * constraint and doesn't paint on top of any clues.  All that is left
 993  * to see is connectedness.
 994  *
 995  * Observe that the white cells in each column form a single connected
 996  * `run', and each column contains a white cell adjacent to a white
 997  * cell in the column to the right, if that column exists.
 998  *
 999  * Thus, any cell in the left-most column can reach any other cell:
1000  * first go to the target column (by repeatedly going to the cell in
1001  * your current column that lets you go right, then going right), then
1002  * go up or down to the desired cell.
1003  *
1004  * As reachability is symmetric (in undirected graphs) and transitive,
1005  * any cell can reach any left-column cell, and from there any other
1006  * cell.
1007  */
1008
1009 /* ----------------------------------------------------------------------
1010  * Game encoding and decoding
1011  */
1012
1013 #define NDIGITS_BASE '!'
1014
1015 static char *newdesc_encode_game_description(int area, puzzle_size *grid)
1016 {
1017     char *desc = NULL;
1018     int desclen = 0, descsize = 0;
1019     int run, i;
1020
1021     run = 0;
1022     for (i = 0; i <= area; i++) {
1023         int n = (i < area ? grid[i] : -1);
1024
1025         if (!n)
1026             run++;
1027         else {
1028             if (descsize < desclen + 40) {
1029                 descsize = desclen * 3 / 2 + 40;
1030                 desc = sresize(desc, descsize, char);
1031             }
1032             if (run) {
1033                 while (run > 0) {
1034                     int c = 'a' - 1 + run;
1035                     if (run > 26)
1036                         c = 'z';
1037                     desc[desclen++] = c;
1038                     run -= c - ('a' - 1);
1039                 }
1040             } else {
1041                 /*
1042                  * If there's a number in the very top left or
1043                  * bottom right, there's no point putting an
1044                  * unnecessary _ before or after it.
1045                  */
1046                 if (desclen > 0 && n > 0)
1047                     desc[desclen++] = '_';
1048             }
1049             if (n > 0)
1050                 desclen += sprintf(desc+desclen, "%d", n);
1051             run = 0;
1052         }
1053     }
1054     desc[desclen] = '\0';
1055     return desc;
1056 }
1057
1058 static char *validate_desc(game_params *params, char *desc)
1059 {
1060     int const n = params->w * params->h;
1061     int squares = 0;
1062     int range = params->w + params->h - 1;   /* maximum cell value */
1063
1064     while (*desc && *desc != ',') {
1065         int c = *desc++;
1066         if (c >= 'a' && c <= 'z') {
1067             squares += c - 'a' + 1;
1068         } else if (c == '_') {
1069             /* do nothing */;
1070         } else if (c > '0' && c <= '9') {
1071             int val = atoi(desc-1);
1072             if (val < 1 || val > range)
1073                 return "Out-of-range number in game description";
1074             squares++;
1075             while (*desc >= '0' && *desc <= '9')
1076                 desc++;
1077         } else
1078             return "Invalid character in game description";
1079     }
1080
1081     if (squares < n)
1082         return "Not enough data to fill grid";
1083
1084     if (squares > n)
1085         return "Too much data to fit in grid";
1086
1087     return NULL;
1088 }
1089
1090 static game_state *new_game(midend *me, game_params *params, char *desc)
1091 {
1092     int i;
1093     char *p;
1094
1095     int const n = params->w * params->h;
1096     game_state *state = snew(game_state);
1097
1098     me = NULL; /* I don't need it, I shouldn't use it */
1099
1100     state->params = *params; /* structure copy */
1101     state->grid = snewn(n, puzzle_size);
1102
1103     p = desc;
1104     i = 0;
1105     while (i < n && *p) {
1106         int c = *p++;
1107         if (c >= 'a' && c <= 'z') {
1108             int squares = c - 'a' + 1;
1109             while (squares--)
1110                 state->grid[i++] = 0;
1111         } else if (c == '_') {
1112             /* do nothing */;
1113         } else if (c > '0' && c <= '9') {
1114             int val = atoi(p-1);
1115             assert(val >= 1 && val <= params->w+params->h-1);
1116             state->grid[i++] = val;
1117             while (*p >= '0' && *p <= '9')
1118                 p++;
1119         }
1120     }
1121     assert(i == n);
1122     state->has_cheated = FALSE;
1123     state->was_solved = FALSE;
1124
1125     return state;
1126 }
1127
1128 /* ----------------------------------------------------------------------
1129  * User interface: ascii
1130  */
1131
1132 static int game_can_format_as_text_now(game_params *params)
1133 {
1134     return TRUE;
1135 }
1136
1137 static char *game_text_format(game_state *state)
1138 {
1139     int cellsize, r, c, i, w_string, h_string, n_string;
1140     char *ret, *buf, *gridline;
1141
1142     int const w = state->params.w, h = state->params.h;
1143
1144     cellsize = 0; /* or may be used uninitialized */
1145
1146     for (c = 0; c < w; ++c) {
1147         for (r = 1; r < h; ++r) {
1148             puzzle_size k = state->grid[idx(r, c, w)];
1149             int d;
1150             for (d = 0; k; k /= 10, ++d);
1151             cellsize = max(cellsize, d);
1152         }
1153     }
1154
1155     ++cellsize;
1156
1157     w_string = w * cellsize + 2; /* "|%d|%d|...|\n" */
1158     h_string = 2 * h + 1; /* "+--+--+...+\n%s\n+--+--+...+\n" */
1159     n_string = w_string * h_string;
1160
1161     gridline = snewn(w_string + 1, char); /* +1: NUL terminator */
1162     memset(gridline, '-', w_string);
1163     for (c = 0; c <= w; ++c) gridline[c * cellsize] = '+';
1164     gridline[w_string - 1] = '\n';
1165     gridline[w_string - 0] = '\0';
1166
1167     buf = ret = snewn(n_string + 1, char); /* +1: NUL terminator */
1168     for (i = r = 0; r < h; ++r) {
1169         memcpy(buf, gridline, w_string);
1170         buf += w_string;
1171         for (c = 0; c < w; ++c, ++i) {
1172             char ch;
1173             switch (state->grid[i]) {
1174               case BLACK: ch = '#'; break;
1175               case WHITE: ch = '.'; break;
1176               case EMPTY: ch = ' '; break;
1177               default:
1178                 buf += sprintf(buf, "|%*d", cellsize - 1, state->grid[i]);
1179                 continue;
1180             }
1181             *buf++ = '|';
1182             memset(buf, ch, cellsize - 1);
1183             buf += cellsize - 1;
1184         }
1185         buf += sprintf(buf, "|\n");
1186     }
1187     memcpy(buf, gridline, w_string);
1188     buf += w_string;
1189     assert (buf - ret == n_string);
1190     *buf = '\0';
1191
1192     sfree(gridline);
1193
1194     return ret;
1195 }
1196
1197 /* ----------------------------------------------------------------------
1198  * User interfaces: interactive
1199  */
1200
1201 struct game_ui {
1202     puzzle_size r, c; /* cursor position */
1203     unsigned int cursor_show: 1;
1204     unsigned int cheated: 1;
1205 };
1206
1207 static game_ui *new_ui(game_state *state)
1208 {
1209     struct game_ui *ui = snew(game_ui);
1210     ui->r = ui->c = 0;
1211     ui->cursor_show = ui->cheated = FALSE;
1212     return ui;
1213 }
1214
1215 static void free_ui(game_ui *ui)
1216 {
1217     sfree(ui);
1218 }
1219
1220 static char *encode_ui(game_ui *ui)
1221 {
1222     return dupstr(ui->cheated ? "1" : "0");
1223 }
1224
1225 static void decode_ui(game_ui *ui, char *encoding)
1226 {
1227     ui->cheated = (*encoding == '1');
1228 }
1229
1230 typedef struct drawcell {
1231     puzzle_size value;
1232     unsigned int error: 1;
1233     unsigned int cursor: 1;
1234     unsigned int flash: 1;
1235 } drawcell;
1236
1237 struct game_drawstate {
1238     int tilesize;
1239     drawcell *grid;
1240     unsigned int started: 1;
1241 };
1242
1243 #define TILESIZE (ds->tilesize)
1244 #define BORDER (TILESIZE / 2)
1245 #define COORD(x) ((x) * TILESIZE + BORDER)
1246 #define FROMCOORD(x) (((x) - BORDER) / TILESIZE)
1247
1248 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1249                             int x, int y, int button)
1250 {
1251     enum {none, forwards, backwards, hint};
1252     int const w = state->params.w, h = state->params.h;
1253     int r = ui->r, c = ui->c, action = none, cell;
1254
1255     if (IS_CURSOR_SELECT(button) && !ui->cursor_show) return NULL;
1256
1257     if (IS_MOUSE_DOWN(button)) {
1258         r = FROMCOORD(y + TILESIZE) - 1; /* or (x, y) < TILESIZE) */
1259         c = FROMCOORD(x + TILESIZE) - 1; /* are considered inside */
1260         if (out_of_bounds(r, c, w, h)) return NULL;
1261         ui->r = r;
1262         ui->c = c;
1263         ui->cursor_show = FALSE;
1264     }
1265
1266     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1267         /*
1268          * Utterly awful hack, exactly analogous to the one in Slant,
1269          * to configure the left and right mouse buttons the opposite
1270          * way round.
1271          *
1272          * The original puzzle submitter thought it would be more
1273          * useful to have the left button turn an empty square into a
1274          * dotted one, on the grounds that that was what you did most
1275          * often; I (SGT) felt instinctively that the left button
1276          * ought to place black squares and the right button place
1277          * dots, on the grounds that that was consistent with many
1278          * other puzzles in which the left button fills in the data
1279          * used by the solution checker while the right button places
1280          * pencil marks for the user's convenience.
1281          *
1282          * My first beta-player wasn't sure either, so I thought I'd
1283          * pre-emptively put in a 'configuration' mechanism just in
1284          * case.
1285          */
1286         {
1287             static int swap_buttons = -1;
1288             if (swap_buttons < 0) {
1289                 char *env = getenv("RANGE_SWAP_BUTTONS");
1290                 swap_buttons = (env && (env[0] == 'y' || env[0] == 'Y'));
1291             }
1292             if (swap_buttons) {
1293                 if (button == LEFT_BUTTON)
1294                     button = RIGHT_BUTTON;
1295                 else
1296                     button = LEFT_BUTTON;
1297             }
1298         }
1299     }
1300
1301     switch (button) {
1302       case CURSOR_SELECT : case   LEFT_BUTTON: action = backwards; break;
1303       case CURSOR_SELECT2: case  RIGHT_BUTTON: action =  forwards; break;
1304       case 'h': case 'H' :                     action =      hint; break;
1305       case CURSOR_UP: case CURSOR_DOWN:
1306       case CURSOR_LEFT: case CURSOR_RIGHT:
1307         if (ui->cursor_show) {
1308             int i;
1309             for (i = 0; i < 4 && cursors[i] != button; ++i);
1310             assert (i < 4);
1311             if (!out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
1312                 ui->r += dr[i];
1313                 ui->c += dc[i];
1314             }
1315         } else ui->cursor_show = TRUE;
1316         return "";
1317     }
1318
1319     if (action == hint) {
1320         move *end, *buf = snewn(state->params.w * state->params.h,
1321                                 struct move);
1322         char *ret = NULL;
1323         end = solve_internal(state, buf, DIFF_RECURSION);
1324         if (end != NULL && end > buf) {
1325             ret = nfmtstr(40, "%c,%d,%d",
1326                           buf->colour == M_BLACK ? 'B' : 'W',
1327                           buf->square.r, buf->square.c);
1328             ui->cheated = TRUE; /* you are being naughty ;-) */
1329         }
1330         sfree(buf);
1331         return ret;
1332     }
1333
1334     cell = state->grid[idx(r, c, state->params.w)];
1335     if (cell > 0) return NULL;
1336
1337     if (action == forwards) switch (cell) {
1338       case EMPTY: return nfmtstr(40, "W,%d,%d", r, c);
1339       case WHITE: return nfmtstr(40, "B,%d,%d", r, c);
1340       case BLACK: return nfmtstr(40, "E,%d,%d", r, c);
1341     }
1342
1343     else if (action == backwards) switch (cell) {
1344       case BLACK: return nfmtstr(40, "W,%d,%d", r, c);
1345       case WHITE: return nfmtstr(40, "E,%d,%d", r, c);
1346       case EMPTY: return nfmtstr(40, "B,%d,%d", r, c);
1347     }
1348
1349     return NULL;
1350 }
1351
1352 static int find_errors(game_state *state, int *report)
1353 {
1354     int const w = state->params.w, h = state->params.h, n = w * h;
1355
1356     int r, c, i;
1357
1358     int nblack = 0, any_white_cell = -1;
1359     game_state *dup = dup_game(state);
1360
1361     for (i = r = 0; r < h; ++r)
1362         for (c = 0; c < w; ++c, ++i) {
1363             switch (state->grid[i]) {
1364
1365               case BLACK:
1366                 {
1367                     int j;
1368                     ++nblack;
1369                     for (j = 0; j < 4; ++j) {
1370                         int const rr = r + dr[j], cc = c + dc[j];
1371                         if (out_of_bounds(rr, cc, w, h)) continue;
1372                         if (state->grid[idx(rr, cc, w)] != BLACK) continue;
1373                         if (!report) goto found_error;
1374                         report[i] = TRUE;
1375                         break;
1376                     }
1377                 }
1378                 break;
1379               default:
1380                 {
1381                     int j, runs;
1382                     for (runs = 1, j = 0; j < 4; ++j) {
1383                         int const rr = r + dr[j], cc = c + dc[j];
1384                         runs += runlength(rr, cc, dr[j], dc[j], state,
1385                                           ~MASK(BLACK));
1386                     }
1387                     if (!report) {
1388                         if (runs != state->grid[i]) goto found_error;
1389                     } else if (runs < state->grid[i]) report[i] = TRUE;
1390                     else {
1391                         for (runs = 1, j = 0; j < 4; ++j) {
1392                             int const rr = r + dr[j], cc = c + dc[j];
1393                             runs += runlength(rr, cc, dr[j], dc[j], state,
1394                                               ~(MASK(BLACK) | MASK(EMPTY)));
1395                         }
1396                         if (runs > state->grid[i]) report[i] = TRUE;
1397                     }
1398                 }
1399
1400                 /* note: fallthrough _into_ these cases */
1401               case EMPTY:
1402               case WHITE: any_white_cell = i;
1403             }
1404         }
1405
1406     for (i = 0; i < n; ++i) if (dup->grid[i] != BLACK) dup->grid[i] = WHITE;
1407     if (nblack + dfs_count_white(dup, any_white_cell) < n) {
1408         if (!report) {
1409             printf("dfs fail at %d\n", any_white_cell);
1410             goto found_error;
1411         }
1412         for (i = 0; i < n; ++i) if (state->grid[i] != BLACK) report[i] = TRUE;
1413     }
1414
1415     free_game(dup);
1416     return FALSE; /* if report != NULL, this is ignored */
1417
1418 found_error:
1419     free_game(dup);
1420     return TRUE;
1421 }
1422
1423 static game_state *execute_move(game_state *state, char *move)
1424 {
1425     signed int r, c, value, nchars, ntok;
1426     signed char what_to_do;
1427     game_state *ret;
1428
1429     assert (move);
1430
1431     ret = dup_game(state);
1432
1433     if (*move == 'S') {
1434         ++move;
1435         ret->has_cheated = ret->was_solved = TRUE;
1436     }
1437
1438     for (; *move; move += nchars) {
1439         ntok = sscanf(move, "%c,%d,%d%n", &what_to_do, &r, &c, &nchars);
1440         if (ntok < 3) goto failure;
1441         switch (what_to_do) {
1442           case 'W': value = WHITE; break;
1443           case 'E': value = EMPTY; break;
1444           case 'B': value = BLACK; break;
1445           default: goto failure;
1446         }
1447         if (out_of_bounds(r, c, ret->params.w, ret->params.h)) goto failure;
1448         ret->grid[idx(r, c, ret->params.w)] = value;
1449     }
1450
1451     if (ret->was_solved == FALSE)
1452         ret->was_solved = !find_errors(ret, NULL);
1453
1454     return ret;
1455
1456 failure:
1457     free_game(ret);
1458     return NULL;
1459 }
1460
1461 static void game_changed_state(game_ui *ui, game_state *oldstate,
1462                                game_state *newstate)
1463 {
1464     if (newstate->has_cheated) ui->cheated = TRUE;
1465 }
1466
1467 static float game_anim_length(game_state *oldstate, game_state *newstate,
1468                               int dir, game_ui *ui)
1469 {
1470     return 0.0F;
1471 }
1472
1473 #define FLASH_TIME 0.7F
1474
1475 static float game_flash_length(game_state *from, game_state *to,
1476                                int dir, game_ui *ui)
1477 {
1478     if (!from->was_solved && to->was_solved && !ui->cheated)
1479         return FLASH_TIME;
1480     return 0.0F;
1481 }
1482
1483 static int game_is_solved(game_state *state)
1484 {
1485     return state->was_solved;
1486 }
1487
1488 /* ----------------------------------------------------------------------
1489  * Drawing routines.
1490  */
1491
1492 #define PREFERRED_TILE_SIZE 32
1493
1494 enum {
1495     COL_BACKGROUND = 0,
1496     COL_GRID,
1497     COL_BLACK = COL_GRID,
1498     COL_TEXT = COL_GRID,
1499     COL_USER = COL_GRID,
1500     COL_ERROR,
1501     COL_LOWLIGHT,
1502     COL_HIGHLIGHT = COL_ERROR, /* mkhighlight needs it, I don't */
1503     COL_CURSOR = COL_LOWLIGHT,
1504     NCOLOURS
1505 };
1506
1507 static void game_compute_size(game_params *params, int tilesize,
1508                               int *x, int *y)
1509 {
1510     *x = (1 + params->w) * tilesize;
1511     *y = (1 + params->h) * tilesize;
1512 }
1513
1514 static void game_set_size(drawing *dr, game_drawstate *ds,
1515                           game_params *params, int tilesize)
1516 {
1517     ds->tilesize = tilesize;
1518 }
1519
1520 #define COLOUR(ret, i, r, g, b) \
1521    ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1522
1523 static float *game_colours(frontend *fe, int *ncolours)
1524 {
1525     float *ret = snewn(3 * NCOLOURS, float);
1526
1527     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1528     COLOUR(ret, COL_GRID,  0.0F, 0.0F, 0.0F);
1529     COLOUR(ret, COL_ERROR, 1.0F, 0.0F, 0.0F);
1530
1531     *ncolours = NCOLOURS;
1532     return ret;
1533 }
1534
1535 static drawcell makecell(puzzle_size value, int error, int cursor, int flash)
1536 {
1537     drawcell ret;
1538     setmember(ret, value);
1539     setmember(ret, error);
1540     setmember(ret, cursor);
1541     setmember(ret, flash);
1542     return ret;
1543 }
1544
1545 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1546 {
1547     int const w = state->params.w, h = state->params.h, n = w * h;
1548     struct game_drawstate *ds = snew(struct game_drawstate);
1549     int i;
1550
1551     ds->tilesize = 0;
1552     ds->started = FALSE;
1553
1554     ds->grid = snewn(n, drawcell);
1555     for (i = 0; i < n; ++i)
1556         ds->grid[i] = makecell(w + h, FALSE, FALSE, FALSE);
1557
1558     return ds;
1559 }
1560
1561 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1562 {
1563     sfree(ds->grid);
1564     sfree(ds);
1565 }
1566
1567 #define cmpmember(a, b, field) ((a) . field == (b) . field)
1568
1569 static int cell_eq(drawcell a, drawcell b)
1570 {
1571     return
1572         cmpmember(a, b, value) &&
1573         cmpmember(a, b, error) &&
1574         cmpmember(a, b, cursor) &&
1575         cmpmember(a, b, flash);
1576 }
1577
1578 static void draw_cell(drawing *dr, game_drawstate *ds, int r, int c,
1579                       drawcell cell);
1580
1581 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1582                         game_state *state, int dir, game_ui *ui,
1583                         float animtime, float flashtime)
1584 {
1585     int const w = state->params.w, h = state->params.h, n = w * h;
1586     int const wpx = (w+1) * ds->tilesize, hpx = (h+1) * ds->tilesize;
1587     int const flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2;
1588
1589     int r, c, i;
1590
1591     int *errors = snewn(n, int);
1592     memset(errors, FALSE, n * sizeof (int));
1593     find_errors(state, errors);
1594
1595     assert (oldstate == NULL); /* only happens if animating moves */
1596
1597     if (!ds->started) {
1598         ds->started = TRUE;
1599         draw_rect(dr, 0, 0, wpx, hpx, COL_BACKGROUND);
1600         draw_rect(dr, BORDER-1, BORDER-1,
1601                   ds->tilesize*w+2, ds->tilesize*h+2, COL_GRID);
1602         draw_update(dr, 0, 0, wpx, hpx);
1603     }
1604
1605     for (i = r = 0; r < h; ++r) {
1606         for (c = 0; c < w; ++c, ++i) {
1607             drawcell cell = makecell(state->grid[i], errors[i], FALSE, flash);
1608             if (r == ui->r && c == ui->c && ui->cursor_show)
1609                 cell.cursor = TRUE;
1610             if (!cell_eq(cell, ds->grid[i])) {
1611                 draw_cell(dr, ds, r, c, cell);
1612                 ds->grid[i] = cell;
1613             }
1614         }
1615     }
1616
1617     sfree(errors);
1618 }
1619
1620 static void draw_cell(drawing *draw, game_drawstate *ds, int r, int c,
1621                       drawcell cell)
1622 {
1623     int const ts = ds->tilesize;
1624     int const y = BORDER + ts * r, x = BORDER + ts * c;
1625     int const tx = x + (ts / 2), ty = y + (ts / 2);
1626     int const dotsz = (ds->tilesize + 9) / 10;
1627
1628     int const colour = (cell.value == BLACK ?
1629                         cell.error ? COL_ERROR : COL_BLACK :
1630                         cell.flash || cell.cursor ?
1631                         COL_LOWLIGHT : COL_BACKGROUND);
1632
1633     draw_rect        (draw, x, y, ts, ts, colour);
1634     draw_rect_outline(draw, x, y, ts, ts, COL_GRID);
1635
1636     switch (cell.value) {
1637       case WHITE: draw_rect(draw, tx - dotsz / 2, ty - dotsz / 2, dotsz, dotsz,
1638                             cell.error ? COL_ERROR : COL_USER);
1639       case BLACK: break;
1640       case EMPTY:
1641         if (cell.error)
1642             draw_circle(draw, tx, ty, dotsz / 2, COL_ERROR, COL_GRID);
1643         break;
1644       default:
1645         {
1646             int const colour = (cell.error ? COL_ERROR : COL_GRID);
1647             char *msg = nfmtstr(10, "%d", cell.value);
1648             draw_text(draw, tx, ty, FONT_VARIABLE, ts * 3 / 5,
1649                       ALIGN_VCENTRE | ALIGN_HCENTRE, colour, msg);
1650             sfree(msg);
1651         }
1652     }
1653
1654     draw_update(draw, x, y, ts, ts);
1655 }
1656
1657 static int game_timing_state(game_state *state, game_ui *ui)
1658 {
1659     puts("warning: game_timing_state was called (this shouldn't happen)");
1660     return FALSE; /* the (non-existing) timer should not be running */
1661 }
1662
1663 /* ----------------------------------------------------------------------
1664  * User interface: print
1665  */
1666
1667 static void game_print_size(game_params *params, float *x, float *y)
1668 {
1669     int print_width, print_height;
1670     game_compute_size(params, 800, &print_width, &print_height);
1671     *x = print_width  / 100.0F;
1672     *y = print_height / 100.0F;
1673 }
1674
1675 static void game_print(drawing *dr, game_state *state, int tilesize)
1676 {
1677     int const w = state->params.w, h = state->params.h;
1678     game_drawstate ds_obj, *ds = &ds_obj;
1679     int r, c, i, colour;
1680
1681     ds->tilesize = tilesize;
1682
1683     colour = print_mono_colour(dr, 1); assert(colour == COL_BACKGROUND);
1684     colour = print_mono_colour(dr, 0); assert(colour == COL_GRID);
1685     colour = print_mono_colour(dr, 1); assert(colour == COL_ERROR);
1686     colour = print_mono_colour(dr, 0); assert(colour == COL_LOWLIGHT);
1687     colour = print_mono_colour(dr, 0); assert(colour == NCOLOURS);
1688
1689     for (i = r = 0; r < h; ++r)
1690         for (c = 0; c < w; ++c, ++i)
1691             draw_cell(dr, ds, r, c,
1692                       makecell(state->grid[i], FALSE, FALSE, FALSE));
1693
1694     print_line_width(dr, 3 * tilesize / 40);
1695     draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, h*TILESIZE, COL_GRID);
1696 }
1697
1698 /* And that's about it ;-) **************************************************/
1699
1700 #ifdef COMBINED
1701 #define thegame range
1702 #endif
1703
1704 struct game const thegame = {
1705     "Range", "games.range", "range",
1706     default_params,
1707     game_fetch_preset,
1708     decode_params,
1709     encode_params,
1710     free_params,
1711     dup_params,
1712     TRUE, game_configure, custom_params,
1713     validate_params,
1714     new_game_desc,
1715     validate_desc,
1716     new_game,
1717     dup_game,
1718     free_game,
1719     TRUE, solve_game,
1720     TRUE, game_can_format_as_text_now, game_text_format,
1721     new_ui,
1722     free_ui,
1723     encode_ui,
1724     decode_ui,
1725     game_changed_state,
1726     interpret_move,
1727     execute_move,
1728     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1729     game_colours,
1730     game_new_drawstate,
1731     game_free_drawstate,
1732     game_redraw,
1733     game_anim_length,
1734     game_flash_length,
1735     game_is_solved,
1736     TRUE, FALSE, game_print_size, game_print,
1737     FALSE, /* wants_statusbar */
1738     FALSE, game_timing_state,
1739     0, /* flags */
1740 };