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