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