2 * range.c: implementation of the Nikoli game 'Kurodoko' / 'Kuromasu'.
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
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.
18 /* example instance with its encoding and textual representation, both
19 * solved and unsolved (made by thegame.solve and thegame.text_format)
21 * +--+--+--+--+--+--+--+
23 * +--+--+--+--+--+--+--+
25 * +--+--+--+--+--+--+--+
27 * +--+--+--+--+--+--+--+
29 * +--+--+--+--+--+--+--+
31 * +--+--+--+--+--+--+--+
33 * +--+--+--+--+--+--+--+
35 * +--+--+--+--+--+--+--+
37 * 7x7:d7b3e8e5c7a7c13e4d8b4d
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 * +--+--+--+--+--+--+--+
67 #define setmember(obj, field) ( (obj) . field = field )
69 static char *nfmtstr(int n, const char *fmt, ...) {
71 char *ret = snewn(n+1, char);
73 vsprintf(ret, fmt, va);
78 #define SWAP(type, lvar1, lvar2) do { \
84 /* ----------------------------------------------------------------------
85 * Game parameters, presets, states
88 typedef signed char puzzle_size;
96 struct game_params params;
97 unsigned int has_cheated: 1;
98 unsigned int was_solved: 1;
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).
112 static game_params *default_params(void)
114 game_params *ret = snew(game_params);
115 *ret = range_presets[DEFAULT_PRESET]; /* structure copy */
119 static game_params *dup_params(const game_params *params)
121 game_params *ret = snew(game_params);
122 *ret = *params; /* structure copy */
126 static int game_fetch_preset(int i, char **name, game_params **params)
130 if (i < 0 || i >= lenof(range_presets)) return FALSE;
132 ret = default_params();
133 *ret = range_presets[i]; /* struct copy */
136 *name = nfmtstr(40, "%d x %d", range_presets[i].w, range_presets[i].h);
141 static void free_params(game_params *params)
146 static void decode_params(game_params *params, char const *string)
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') {
153 params->h = atoi(string);
154 while (*string && isdigit((unsigned char)*string)) string++;
158 static char *encode_params(const game_params *params, int full)
161 sprintf(str, "%dx%d", params->w, params->h);
165 static config_item *game_configure(const game_params *params)
169 ret = snewn(3, config_item);
171 ret[0].name = "Width";
172 ret[0].type = C_STRING;
173 ret[0].u.string.sval = nfmtstr(10, "%d", params->w);
175 ret[1].name = "Height";
176 ret[1].type = C_STRING;
177 ret[1].u.string.sval = nfmtstr(10, "%d", params->h);
185 static game_params *custom_params(const config_item *configuration)
187 game_params *ret = snew(game_params);
188 ret->w = atoi(configuration[0].u.string.sval);
189 ret->h = atoi(configuration[1].u.string.sval);
193 #define memdup(dst, src, n, type) do { \
194 dst = snewn(n, type); \
195 memcpy(dst, src, n * sizeof (type)); \
198 static game_state *dup_game(const game_state *state)
200 game_state *ret = snew(game_state);
201 int const n = state->params.w * state->params.h;
203 *ret = *state; /* structure copy */
205 /* copy the poin_tee_, set a new value of the poin_ter_ */
206 memdup(ret->grid, state->grid, n, puzzle_size);
211 static void free_game(game_state *state)
218 /* ----------------------------------------------------------------------
219 * The solver subsystem.
221 * The solver is used for two purposes:
222 * - To solve puzzles when the user selects `Solve'.
223 * - To test solubility of a grid as clues are being removed from it
224 * during the puzzle generation.
226 * It supports the following ways of reasoning:
228 * - A cell adjacent to a black cell must be white.
230 * - If painting a square black would bisect the white regions, that
231 * square is white (by finding biconnected components' cut points)
233 * - A cell with number n, covering at most k white squares in three
234 * directions must white-cover n-k squares in the last direction.
236 * - A cell with number n known to cover k squares, if extending the
237 * cover by one square in a given direction causes the cell to
238 * cover _more_ than n squares, that extension cell must be black.
240 * (either if the square already covers n, or if it extends into a
241 * chunk of size > n - k)
243 * - Recursion. Pick any cell and see if this leads to either a
244 * contradiction or a solution (and then act appropriately).
249 * (propagation upper limit)
250 * - If one has two numbers on the same line, the smaller limits the
251 * larger. Example: in |b|_|_|8|4|_|_|b|, only two _'s can be both
252 * white and connected to the "8" cell; so that cell will propagate
253 * at least four cells orthogonally to the displayed line (which is
254 * better than the current "at least 2").
256 * (propagation upper limit)
257 * - cells can't propagate into other cells if doing so exceeds that
258 * number. Example: in |b|4|.|.|2|b|, at most one _ can be white;
259 * otherwise, the |2| would have too many reaching white cells.
261 * (propagation lower and upper limit)
262 * - `Full Combo': in each four directions d_1 ... d_4, find a set of
263 * possible propagation distances S_1 ... S_4. For each i=1..4,
264 * for each x in S_i: if not exists (y, z, w) in the other sets
265 * such that (x+y+z+w+1 == clue value): then remove x from S_i.
266 * Repeat until this stabilizes. If any cell would contradict
269 #define idx(i, j, w) ((i)*(w) + (j))
270 #define out_of_bounds(r, c, w, h) \
271 ((r) < 0 || (r) >= h || (c) < 0 || (c) >= w)
273 typedef struct square {
277 enum {BLACK = -2, WHITE, EMPTY};
278 /* white is for pencil marks, empty is undecided */
280 static int const dr[4] = {+1, 0, -1, 0};
281 static int const dc[4] = { 0, +1, 0, -1};
282 static int const cursors[4] = /* must match dr and dc */
283 {CURSOR_DOWN, CURSOR_RIGHT, CURSOR_UP, CURSOR_LEFT};
285 typedef struct move {
287 unsigned int colour: 1;
289 enum {M_BLACK = 0, M_WHITE = 1};
291 typedef move *(reasoning)(game_state *state,
296 static reasoning solver_reasoning_not_too_big;
297 static reasoning solver_reasoning_adjacency;
298 static reasoning solver_reasoning_connectedness;
299 static reasoning solver_reasoning_recursion;
308 static move *solve_internal(const game_state *state, move *base, int diff);
310 static char *solve_game(const game_state *orig, const game_state *curpos,
311 const char *aux, const char **error)
313 int const n = orig->params.w * orig->params.h;
314 move *const base = snewn(n, move);
315 move *moves = solve_internal(orig, base, DIFF_RECURSION);
320 int const k = moves - base;
321 char *str = ret = snewn(15*k + 2, char);
322 char colour[2] = "BW";
326 for (it = base; it < moves; ++it)
327 str += sprintf(str, "%c,%d,%d", colour[it->colour],
328 it->square.r, it->square.c);
329 } else *error = "This puzzle instance contains a contradiction";
335 static square *find_clues(const game_state *state, int *ret_nclues);
336 static move *do_solve(game_state *state,
342 /* new_game_desc entry point in the solver subsystem */
343 static move *solve_internal(const game_state *state, move *base, int diff)
346 square *const clues = find_clues(state, &nclues);
347 game_state *dup = dup_game(state);
348 move *const moves = do_solve(dup, nclues, clues, base, diff);
354 static reasoning *const reasonings[] = {
355 solver_reasoning_not_too_big,
356 solver_reasoning_adjacency,
357 solver_reasoning_connectedness,
358 solver_reasoning_recursion
361 static move *do_solve(game_state *state,
367 struct move *buf = move_buffer, *oldbuf;
372 for (i = 0; i < lenof(reasonings) && i <= difficulty; ++i) {
373 /* only recurse if all else fails */
374 if (i == DIFF_RECURSION && buf > oldbuf) continue;
375 buf = (*reasonings[i])(state, nclues, clues, buf);
376 if (buf == NULL) return NULL;
378 } while (buf > oldbuf);
383 #define MASK(n) (1 << ((n) + 2))
385 static int runlength(puzzle_size r, puzzle_size c,
386 puzzle_size dr, puzzle_size dc,
387 const game_state *state, int colourmask)
389 int const w = state->params.w, h = state->params.h;
392 int cell = idx(r, c, w);
393 if (out_of_bounds(r, c, w, h)) break;
394 if (state->grid[cell] > 0) {
395 if (!(colourmask & ~(MASK(BLACK) | MASK(WHITE) | MASK(EMPTY))))
397 } else if (!(MASK(state->grid[cell]) & colourmask)) break;
405 static void solver_makemove(puzzle_size r, puzzle_size c, int colour,
406 game_state *state, move **buffer_ptr)
408 int const cell = idx(r, c, state->params.w);
409 if (out_of_bounds(r, c, state->params.w, state->params.h)) return;
410 if (state->grid[cell] != EMPTY) return;
411 setmember((*buffer_ptr)->square, r);
412 setmember((*buffer_ptr)->square, c);
413 setmember(**buffer_ptr, colour);
415 state->grid[cell] = (colour == M_BLACK ? BLACK : WHITE);
418 static move *solver_reasoning_adjacency(game_state *state,
424 for (r = 0; r < state->params.h; ++r)
425 for (c = 0; c < state->params.w; ++c) {
426 int const cell = idx(r, c, state->params.w);
427 if (state->grid[cell] != BLACK) continue;
428 for (i = 0; i < 4; ++i)
429 solver_makemove(r + dr[i], c + dc[i], M_WHITE, state, &buf);
434 enum {NOT_VISITED = -1};
436 static int dfs_biconnect_visit(puzzle_size r, puzzle_size c,
438 square *dfs_parent, int *dfs_depth,
441 static move *solver_reasoning_connectedness(game_state *state,
446 int const w = state->params.w, h = state->params.h, n = w * h;
448 square *const dfs_parent = snewn(n, square);
449 int *const dfs_depth = snewn(n, int);
452 for (i = 0; i < n; ++i) {
453 dfs_parent[i].r = NOT_VISITED;
457 for (i = 0; i < n && state->grid[i] == BLACK; ++i);
459 dfs_parent[i].r = i / w;
460 dfs_parent[i].c = i % w; /* `dfs root`.parent == `dfs root` */
463 dfs_biconnect_visit(i / w, i % w, state, dfs_parent, dfs_depth, &buf);
471 /* returns the `lowpoint` of (r, c) */
472 static int dfs_biconnect_visit(puzzle_size r, puzzle_size c,
474 square *dfs_parent, int *dfs_depth,
477 const puzzle_size w = state->params.w, h = state->params.h;
478 int const i = idx(r, c, w), mydepth = dfs_depth[i];
479 int lowpoint = mydepth, j, nchildren = 0;
481 for (j = 0; j < 4; ++j) {
482 const puzzle_size rr = r + dr[j], cc = c + dc[j];
483 int const cell = idx(rr, cc, w);
485 if (out_of_bounds(rr, cc, w, h)) continue;
486 if (state->grid[cell] == BLACK) continue;
488 if (dfs_parent[cell].r == NOT_VISITED) {
490 dfs_parent[cell].r = r;
491 dfs_parent[cell].c = c;
492 dfs_depth[cell] = mydepth + 1;
493 child_lowpoint = dfs_biconnect_visit(rr, cc, state, dfs_parent,
496 if (child_lowpoint >= mydepth && mydepth > 0)
497 solver_makemove(r, c, M_WHITE, state, buf);
499 lowpoint = min(lowpoint, child_lowpoint);
501 } else if (rr != dfs_parent[i].r || cc != dfs_parent[i].c) {
502 lowpoint = min(lowpoint, dfs_depth[cell]);
506 if (mydepth == 0 && nchildren >= 2)
507 solver_makemove(r, c, M_WHITE, state, buf);
512 static move *solver_reasoning_not_too_big(game_state *state,
517 int const w = state->params.w, runmasks[4] = {
518 ~(MASK(BLACK) | MASK(EMPTY)),
520 ~(MASK(BLACK) | MASK(EMPTY)),
523 enum {RUN_WHITE, RUN_EMPTY, RUN_BEYOND, RUN_SPACE};
525 int i, runlengths[4][4];
527 for (i = 0; i < nclues; ++i) {
528 int j, k, whites, space;
530 const puzzle_size row = clues[i].r, col = clues[i].c;
531 int const clue = state->grid[idx(row, col, w)];
533 for (j = 0; j < 4; ++j) {
534 puzzle_size r = row + dr[j], c = col + dc[j];
535 runlengths[RUN_SPACE][j] = 0;
536 for (k = 0; k <= RUN_SPACE; ++k) {
537 int l = runlength(r, c, dr[j], dc[j], state, runmasks[k]);
539 runlengths[k][j] = l;
543 runlengths[RUN_SPACE][j] += l;
548 for (j = 0; j < 4; ++j) whites += runlengths[RUN_WHITE][j];
550 for (j = 0; j < 4; ++j) {
551 int const delta = 1 + runlengths[RUN_WHITE][j];
552 const puzzle_size r = row + delta * dr[j];
553 const puzzle_size c = col + delta * dc[j];
555 if (whites == clue) {
556 solver_makemove(r, c, M_BLACK, state, &buf);
560 if (runlengths[RUN_EMPTY][j] == 1 &&
562 + runlengths[RUN_EMPTY][j]
563 + runlengths[RUN_BEYOND][j]
565 solver_makemove(r, c, M_BLACK, state, &buf);
570 + runlengths[RUN_EMPTY][j]
571 + runlengths[RUN_BEYOND][j]
573 runlengths[RUN_SPACE][j] =
574 runlengths[RUN_WHITE][j] +
575 runlengths[RUN_EMPTY][j] - 1;
577 if (runlengths[RUN_EMPTY][j] == 1)
578 solver_makemove(r, c, M_BLACK, state, &buf);
583 for (j = 0; j < 4; ++j) space += runlengths[RUN_SPACE][j];
584 for (j = 0; j < 4; ++j) {
585 puzzle_size r = row + dr[j], c = col + dc[j];
587 int k = space - runlengths[RUN_SPACE][j];
588 if (k >= clue) continue;
590 for (; k < clue; ++k, r += dr[j], c += dc[j])
591 solver_makemove(r, c, M_WHITE, state, &buf);
597 static move *solver_reasoning_recursion(game_state *state,
602 int const w = state->params.w, n = w * state->params.h;
605 for (cell = 0; cell < n; ++cell) {
606 int const r = cell / w, c = cell % w;
608 game_state *newstate;
609 move *recursive_result;
611 if (state->grid[cell] != EMPTY) continue;
613 /* FIXME: add enum alias for smallest and largest (or N) */
614 for (colour = M_BLACK; colour <= M_WHITE; ++colour) {
615 newstate = dup_game(state);
616 newstate->grid[cell] = colour;
617 recursive_result = do_solve(newstate, nclues, clues, buf,
620 if (recursive_result == NULL) {
621 solver_makemove(r, c, M_BLACK + M_WHITE - colour, state, &buf);
624 for (i = 0; i < n && newstate->grid[i] != EMPTY; ++i);
625 if (i == n) return buf;
631 static square *find_clues(const game_state *state, int *ret_nclues)
633 int r, c, i, nclues = 0;
634 square *ret = snewn(state->params.w * state->params.h, struct square);
636 for (i = r = 0; r < state->params.h; ++r)
637 for (c = 0; c < state->params.w; ++c, ++i)
638 if (state->grid[i] > 0) {
644 *ret_nclues = nclues;
645 return sresize(ret, nclues + (nclues == 0), square);
648 /* ----------------------------------------------------------------------
651 * Generating kurodoko instances is rather straightforward:
653 * - Start with a white grid and add black squares at randomly chosen
654 * locations, unless colouring that square black would violate
655 * either the adjacency or connectedness constraints.
657 * - For each white square, compute the number it would contain if it
658 * were given as a clue.
660 * - From a starting point of "give _every_ white square as a clue",
661 * for each white square (in a random order), see if the board is
662 * solvable when that square is not given as a clue. If not, don't
663 * give it as a clue, otherwise do.
665 * This never fails, but it's only _almost_ what I do. The real final
668 * - From a starting point of "give _every_ white square as a clue",
669 * first remove all clues that are two-way rotationally symmetric
670 * to a black square. If this leaves the puzzle unsolvable, throw
671 * it out and try again. Otherwise, remove all _pairs_ of clues
672 * (that are rotationally symmetric) which can be removed without
673 * rendering the puzzle unsolvable.
675 * This can fail even if one only removes the black and symmetric
676 * clues; indeed it happens often (avg. once or twice per puzzle) when
677 * generating 1xN instances. (If you add black cells they must be in
678 * the end, and if you only add one, it's ambiguous where).
681 /* forward declarations of internal calls */
682 static void newdesc_choose_black_squares(game_state *state,
683 const int *shuffle_1toN);
684 static void newdesc_compute_clues(game_state *state);
685 static int newdesc_strip_clues(game_state *state, int *shuffle_1toN);
686 static char *newdesc_encode_game_description(int n, puzzle_size *grid);
688 static char *new_game_desc(const game_params *params, random_state *rs,
689 char **aux, int interactive)
691 int const w = params->w, h = params->h, n = w * h;
693 puzzle_size *const grid = snewn(n, puzzle_size);
694 int *const shuffle_1toN = snewn(n, int);
696 int i, clues_removed;
701 state.params = *params;
704 interactive = 0; /* I don't need it, I shouldn't use it*/
706 for (i = 0; i < n; ++i) shuffle_1toN[i] = i;
709 shuffle(shuffle_1toN, n, sizeof (int), rs);
710 newdesc_choose_black_squares(&state, shuffle_1toN);
712 newdesc_compute_clues(&state);
714 shuffle(shuffle_1toN, n, sizeof (int), rs);
715 clues_removed = newdesc_strip_clues(&state, shuffle_1toN);
717 if (clues_removed < 0) continue; else break;
720 encoding = newdesc_encode_game_description(n, grid);
728 static int dfs_count_white(game_state *state, int cell);
730 static void newdesc_choose_black_squares(game_state *state,
731 const int *shuffle_1toN)
733 int const w = state->params.w, h = state->params.h, n = w * h;
735 int k, any_white_cell, n_black_cells;
737 for (k = 0; k < n; ++k) state->grid[k] = WHITE;
739 any_white_cell = shuffle_1toN[n - 1];
742 /* I like the puzzles that result from n / 3, but maybe this
743 * could be made a (generation, i.e. non-full) parameter? */
744 for (k = 0; k < n / 3; ++k) {
745 int const i = shuffle_1toN[k], c = i % w, r = i / w;
748 for (j = 0; j < 4; ++j) {
749 int const rr = r + dr[j], cc = c + dc[j], cell = idx(rr, cc, w);
750 /* if you're out of bounds, we skip you */
751 if (out_of_bounds(rr, cc, w, h)) continue;
752 if (state->grid[cell] == BLACK) break; /* I can't be black */
753 } if (j < 4) continue; /* I have black neighbour: I'm white */
755 state->grid[i] = BLACK;
758 j = dfs_count_white(state, any_white_cell);
759 if (j + n_black_cells < n) {
760 state->grid[i] = WHITE;
766 static void newdesc_compute_clues(game_state *state)
768 int const w = state->params.w, h = state->params.h;
771 for (r = 0; r < h; ++r) {
772 int run_size = 0, c, cc;
773 for (c = 0; c <= w; ++c) {
774 if (c == w || state->grid[idx(r, c, w)] == BLACK) {
775 for (cc = c - run_size; cc < c; ++cc)
776 state->grid[idx(r, cc, w)] += run_size;
782 for (c = 0; c < w; ++c) {
783 int run_size = 0, r, rr;
784 for (r = 0; r <= h; ++r) {
785 if (r == h || state->grid[idx(r, c, w)] == BLACK) {
786 for (rr = r - run_size; rr < r; ++rr)
787 state->grid[idx(rr, c, w)] += run_size;
794 #define rotate(x) (n - 1 - (x))
796 static int newdesc_strip_clues(game_state *state, int *shuffle_1toN)
798 int const w = state->params.w, n = w * state->params.h;
800 move *const move_buffer = snewn(n, move);
802 game_state *dupstate;
805 * do a partition/pivot of shuffle_1toN into three groups:
806 * (1) squares rotationally-symmetric to (3)
807 * (2) squares not in (1) or (3)
810 * They go from [0, left), [left, right) and [right, n) in
811 * shuffle_1toN (and from there into state->grid[ ])
813 * Then, remove clues from the grid one by one in shuffle_1toN
814 * order, until the solver becomes unhappy. If we didn't remove
815 * all of (1), return (-1). Else, we're happy.
818 /* do the partition */
819 int clues_removed, k = 0, left = 0, right = n;
822 while (k < right && state->grid[shuffle_1toN[k]] == BLACK) {
824 SWAP(int, shuffle_1toN[right], shuffle_1toN[k]);
825 assert(state->grid[shuffle_1toN[right]] == BLACK);
827 if (k >= right) break;
829 if (state->grid[rotate(shuffle_1toN[k])] == BLACK) {
830 SWAP(int, shuffle_1toN[k], shuffle_1toN[left]);
833 assert (state->grid[rotate(shuffle_1toN[k])] != BLACK
837 for (k = 0; k < left; ++k) {
838 assert (state->grid[rotate(shuffle_1toN[k])] == BLACK);
839 state->grid[shuffle_1toN[k]] = EMPTY;
841 for (k = left; k < right; ++k) {
842 assert (state->grid[rotate(shuffle_1toN[k])] != BLACK);
843 assert (state->grid[shuffle_1toN[k]] != BLACK);
845 for (k = right; k < n; ++k) {
846 assert (state->grid[shuffle_1toN[k]] == BLACK);
847 state->grid[shuffle_1toN[k]] = EMPTY;
850 clues_removed = (left - 0) + (n - right);
852 dupstate = dup_game(state);
853 buf = solve_internal(dupstate, move_buffer, DIFF_RECURSION - 1);
855 if (buf - move_buffer < clues_removed) {
856 /* branch prediction: I don't think I'll go here */
861 for (k = left; k < right; ++k) {
862 const int i = shuffle_1toN[k], j = rotate(i);
863 int const clue = state->grid[i], clue_rot = state->grid[j];
864 if (clue == BLACK) continue;
865 state->grid[i] = state->grid[j] = EMPTY;
866 dupstate = dup_game(state);
867 buf = solve_internal(dupstate, move_buffer, DIFF_RECURSION - 1);
869 clues_removed += 2 - (i == j);
870 /* if i is the center square, then i == (j = rotate(i))
871 * when i and j are one, removing i and j removes only one */
872 if (buf - move_buffer == clues_removed) continue;
873 /* if the solver is sound, refilling all removed clues means
874 * we have filled all squares, i.e. solved the puzzle. */
875 state->grid[i] = clue;
876 state->grid[j] = clue_rot;
877 clues_removed -= 2 - (i == j);
882 return clues_removed;
885 static int dfs_count_rec(puzzle_size *grid, int r, int c, int w, int h)
887 int const cell = idx(r, c, w);
888 if (out_of_bounds(r, c, w, h)) return 0;
889 if (grid[cell] != WHITE) return 0;
892 dfs_count_rec(grid, r + 0, c + 1, w, h) +
893 dfs_count_rec(grid, r + 0, c - 1, w, h) +
894 dfs_count_rec(grid, r + 1, c + 0, w, h) +
895 dfs_count_rec(grid, r - 1, c + 0, w, h);
898 static int dfs_count_white(game_state *state, int cell)
900 int const w = state->params.w, h = state->params.h, n = w * h;
901 int const r = cell / w, c = cell % w;
902 int i, k = dfs_count_rec(state->grid, r, c, w, h);
903 for (i = 0; i < n; ++i)
904 if (state->grid[i] == EMPTY)
905 state->grid[i] = WHITE;
909 static const char *validate_params(const game_params *params, int full)
911 int const w = params->w, h = params->h;
912 if (w < 1) return "Error: width is less than 1";
913 if (h < 1) return "Error: height is less than 1";
914 if (w * h < 1) return "Error: size is less than 1";
915 if (w + h - 1 > SCHAR_MAX) return "Error: w + h is too big";
916 /* I might be unable to store clues in my puzzle_size *grid; */
918 if (w == 2 && h == 2) return "Error: can't create 2x2 puzzles";
919 if (w == 1 && h == 2) return "Error: can't create 1x2 puzzles";
920 if (w == 2 && h == 1) return "Error: can't create 2x1 puzzles";
921 if (w == 1 && h == 1) return "Error: can't create 1x1 puzzles";
926 /* Definition: a puzzle instance is _good_ if:
927 * - it has a unique solution
928 * - the solver can find this solution without using recursion
929 * - the solution contains at least one black square
930 * - the clues are 2-way rotationally symmetric
932 * (the idea being: the generator can not output any _bad_ puzzles)
934 * Theorem: validate_params, when full != 0, discards exactly the set
935 * of parameters for which there are _no_ good puzzle instances.
937 * Proof: it's an immediate consequence of the five lemmas below.
939 * Observation: not only do puzzles on non-tiny grids exist, the
940 * generator is pretty fast about coming up with them. On my pre-2004
941 * desktop box, it generates 100 puzzles on the highest preset (16x11)
942 * in 8.383 seconds, or <= 0.1 second per puzzle.
944 * ----------------------------------------------------------------------
946 * Lemma: On a 1x1 grid, there are no good puzzles.
948 * Proof: the one square can't be a clue because at least one square
949 * is black. But both a white square and a black square satisfy the
950 * solution criteria, so the puzzle is ambiguous (and hence bad).
952 * Lemma: On a 1x2 grid, there are no good puzzles.
954 * Proof: let's name the squares l and r. Note that there can be at
955 * most one black square, or adjacency is violated. By assumption at
956 * least one square is black, so let's call that one l. By clue
957 * symmetry, neither l nor r can be given as a clue, so the puzzle
958 * instance is blank and thus ambiguous.
960 * Corollary: On a 2x1 grid, there are no good puzzles.
961 * Proof: rotate the above proof 90 degrees ;-)
963 * ----------------------------------------------------------------------
965 * Lemma: On a 2x2 grid, there are no soluble puzzles with 2-way
966 * rotational symmetric clues and at least one black square.
968 * Proof: Let's name the squares a, b, c, and d, with a and b on the
969 * top row, a and c in the left column. Let's consider the case where
970 * a is black. Then no other square can be black: b and c would both
971 * violate the adjacency constraint; d would disconnect b from c.
973 * So exactly one square is black (and by 4-way rotation symmetry of
974 * the 2x2 square, it doesn't matter which one, so let's stick to a).
975 * By 2-way rotational symmetry of the clues and the rule about not
976 * painting numbers black, neither a nor d can be clues. A blank
977 * puzzle would be ambiguous, so one of {b, c} is a clue; by symmetry,
978 * so is the other one.
980 * It is readily seen that their clue value is 2. But "a is black"
981 * and "d is black" are both valid solutions in this case, so the
982 * puzzle is ambiguous (and hence bad).
984 * ----------------------------------------------------------------------
986 * Lemma: On a wxh grid with w, h >= 1 and (w > 2 or h > 2), there is
987 * at least one good puzzle.
989 * Proof: assume that w > h (otherwise rotate the proof again). Paint
990 * the top left and bottom right corners black, and fill a clue into
991 * all the other squares. Present this board to the solver code (or
992 * player, hypothetically), except with the two black squares as blank
995 * For an Nx1 puzzle, observe that every clue is N - 2, and there are
996 * N - 2 of them in one connected sequence, so the remaining two
997 * squares can be deduced to be black, which solves the puzzle.
999 * For any other puzzle, let j be a cell in the same row as a black
1000 * cell, but not in the same column (such a cell doesn't exist in 2x3
1001 * puzzles, but we assume w > h and such cells exist in 3x2 puzzles).
1003 * Note that the number of cells in axis parallel `rays' going out
1004 * from j exceeds j's clue value by one. Only one such cell is a
1005 * non-clue, so it must be black. Similarly for the other corner (let
1006 * j' be a cell in the same row as the _other_ black cell, but not in
1007 * the same column as _any_ black cell; repeat this argument at j').
1009 * This fills the grid and satisfies all clues and the adjacency
1010 * constraint and doesn't paint on top of any clues. All that is left
1011 * to see is connectedness.
1013 * Observe that the white cells in each column form a single connected
1014 * `run', and each column contains a white cell adjacent to a white
1015 * cell in the column to the right, if that column exists.
1017 * Thus, any cell in the left-most column can reach any other cell:
1018 * first go to the target column (by repeatedly going to the cell in
1019 * your current column that lets you go right, then going right), then
1020 * go up or down to the desired cell.
1022 * As reachability is symmetric (in undirected graphs) and transitive,
1023 * any cell can reach any left-column cell, and from there any other
1027 /* ----------------------------------------------------------------------
1028 * Game encoding and decoding
1031 #define NDIGITS_BASE '!'
1033 static char *newdesc_encode_game_description(int area, puzzle_size *grid)
1036 int desclen = 0, descsize = 0;
1040 for (i = 0; i <= area; i++) {
1041 int n = (i < area ? grid[i] : -1);
1046 if (descsize < desclen + 40) {
1047 descsize = desclen * 3 / 2 + 40;
1048 desc = sresize(desc, descsize, char);
1052 int c = 'a' - 1 + run;
1055 desc[desclen++] = c;
1056 run -= c - ('a' - 1);
1060 * If there's a number in the very top left or
1061 * bottom right, there's no point putting an
1062 * unnecessary _ before or after it.
1064 if (desclen > 0 && n > 0)
1065 desc[desclen++] = '_';
1068 desclen += sprintf(desc+desclen, "%d", n);
1072 desc[desclen] = '\0';
1076 static const char *validate_desc(const game_params *params, const char *desc)
1078 int const n = params->w * params->h;
1080 int range = params->w + params->h - 1; /* maximum cell value */
1082 while (*desc && *desc != ',') {
1084 if (c >= 'a' && c <= 'z') {
1085 squares += c - 'a' + 1;
1086 } else if (c == '_') {
1088 } else if (c > '0' && c <= '9') {
1089 int val = atoi(desc-1);
1090 if (val < 1 || val > range)
1091 return "Out-of-range number in game description";
1093 while (*desc >= '0' && *desc <= '9')
1096 return "Invalid character in game description";
1100 return "Not enough data to fill grid";
1103 return "Too much data to fit in grid";
1108 static game_state *new_game(midend *me, const game_params *params,
1114 int const n = params->w * params->h;
1115 game_state *state = snew(game_state);
1117 me = NULL; /* I don't need it, I shouldn't use it */
1119 state->params = *params; /* structure copy */
1120 state->grid = snewn(n, puzzle_size);
1124 while (i < n && *p) {
1126 if (c >= 'a' && c <= 'z') {
1127 int squares = c - 'a' + 1;
1129 state->grid[i++] = 0;
1130 } else if (c == '_') {
1132 } else if (c > '0' && c <= '9') {
1133 int val = atoi(p-1);
1134 assert(val >= 1 && val <= params->w+params->h-1);
1135 state->grid[i++] = val;
1136 while (*p >= '0' && *p <= '9')
1141 state->has_cheated = FALSE;
1142 state->was_solved = FALSE;
1147 /* ----------------------------------------------------------------------
1148 * User interface: ascii
1151 static int game_can_format_as_text_now(const game_params *params)
1156 static char *game_text_format(const game_state *state)
1158 int r, c, i, w_string, h_string, n_string;
1160 char *ret, *buf, *gridline;
1162 int const w = state->params.w, h = state->params.h;
1164 cellsize = 0; /* or may be used uninitialized */
1166 for (c = 0; c < w; ++c) {
1167 for (r = 0; r < h; ++r) {
1168 puzzle_size k = state->grid[idx(r, c, w)];
1170 for (d = 0; k; k /= 10, ++d);
1171 cellsize = max(cellsize, d);
1177 w_string = w * cellsize + 2; /* "|%d|%d|...|\n" */
1178 h_string = 2 * h + 1; /* "+--+--+...+\n%s\n+--+--+...+\n" */
1179 n_string = w_string * h_string;
1181 gridline = snewn(w_string + 1, char); /* +1: NUL terminator */
1182 memset(gridline, '-', w_string);
1183 for (c = 0; c <= w; ++c) gridline[c * cellsize] = '+';
1184 gridline[w_string - 1] = '\n';
1185 gridline[w_string - 0] = '\0';
1187 buf = ret = snewn(n_string + 1, char); /* +1: NUL terminator */
1188 for (i = r = 0; r < h; ++r) {
1189 memcpy(buf, gridline, w_string);
1191 for (c = 0; c < w; ++c, ++i) {
1193 switch (state->grid[i]) {
1194 case BLACK: ch = '#'; break;
1195 case WHITE: ch = '.'; break;
1196 case EMPTY: ch = ' '; break;
1198 buf += sprintf(buf, "|%*d", cellsize - 1, state->grid[i]);
1202 memset(buf, ch, cellsize - 1);
1203 buf += cellsize - 1;
1205 buf += sprintf(buf, "|\n");
1207 memcpy(buf, gridline, w_string);
1209 assert (buf - ret == n_string);
1217 /* ----------------------------------------------------------------------
1218 * User interfaces: interactive
1222 puzzle_size r, c; /* cursor position */
1223 unsigned int cursor_show: 1;
1226 static game_ui *new_ui(const game_state *state)
1228 struct game_ui *ui = snew(game_ui);
1230 ui->cursor_show = FALSE;
1234 static void free_ui(game_ui *ui)
1239 static char *encode_ui(const game_ui *ui)
1244 static void decode_ui(game_ui *ui, const char *encoding)
1248 typedef struct drawcell {
1250 unsigned int error: 1;
1251 unsigned int cursor: 1;
1252 unsigned int flash: 1;
1255 struct game_drawstate {
1258 unsigned int started: 1;
1261 #define TILESIZE (ds->tilesize)
1262 #define BORDER (TILESIZE / 2)
1263 #define COORD(x) ((x) * TILESIZE + BORDER)
1264 #define FROMCOORD(x) (((x) - BORDER) / TILESIZE)
1266 static char *interpret_move(const game_state *state, game_ui *ui,
1267 const game_drawstate *ds,
1268 int x, int y, int button)
1270 enum {none, forwards, backwards, hint};
1271 int const w = state->params.w, h = state->params.h;
1272 int r = ui->r, c = ui->c, action = none, cell;
1273 int shift = button & MOD_SHFT;
1276 if (IS_CURSOR_SELECT(button) && !ui->cursor_show) return NULL;
1278 if (IS_MOUSE_DOWN(button)) {
1279 r = FROMCOORD(y + TILESIZE) - 1; /* or (x, y) < TILESIZE) */
1280 c = FROMCOORD(x + TILESIZE) - 1; /* are considered inside */
1281 if (out_of_bounds(r, c, w, h)) return NULL;
1284 ui->cursor_show = FALSE;
1287 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1289 * Utterly awful hack, exactly analogous to the one in Slant,
1290 * to configure the left and right mouse buttons the opposite
1293 * The original puzzle submitter thought it would be more
1294 * useful to have the left button turn an empty square into a
1295 * dotted one, on the grounds that that was what you did most
1296 * often; I (SGT) felt instinctively that the left button
1297 * ought to place black squares and the right button place
1298 * dots, on the grounds that that was consistent with many
1299 * other puzzles in which the left button fills in the data
1300 * used by the solution checker while the right button places
1301 * pencil marks for the user's convenience.
1303 * My first beta-player wasn't sure either, so I thought I'd
1304 * pre-emptively put in a 'configuration' mechanism just in
1308 static int swap_buttons = -1;
1309 if (swap_buttons < 0) {
1310 char *env = getenv("RANGE_SWAP_BUTTONS");
1311 swap_buttons = (env && (env[0] == 'y' || env[0] == 'Y'));
1314 if (button == LEFT_BUTTON)
1315 button = RIGHT_BUTTON;
1317 button = LEFT_BUTTON;
1323 case CURSOR_SELECT : case LEFT_BUTTON: action = backwards; break;
1324 case CURSOR_SELECT2: case RIGHT_BUTTON: action = forwards; break;
1325 case 'h': case 'H' : action = hint; break;
1326 case CURSOR_UP: case CURSOR_DOWN:
1327 case CURSOR_LEFT: case CURSOR_RIGHT:
1328 if (ui->cursor_show) {
1330 for (i = 0; i < 4 && cursors[i] != button; ++i);
1333 int pre_r = r, pre_c = c, do_pre, do_post;
1334 cell = state->grid[idx(r, c, state->params.w)];
1335 do_pre = (cell == EMPTY);
1337 if (out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
1339 return nfmtstr(40, "W,%d,%d", pre_r, pre_c);
1347 cell = state->grid[idx(ui->r, ui->c, state->params.w)];
1348 do_post = (cell == EMPTY);
1350 /* (do_pre ? "..." : "") concat (do_post ? "..." : "") */
1351 if (do_pre && do_post)
1352 return nfmtstr(80, "W,%d,%dW,%d,%d",
1353 pre_r, pre_c, ui->r, ui->c);
1355 return nfmtstr(40, "W,%d,%d", pre_r, pre_c);
1357 return nfmtstr(40, "W,%d,%d", ui->r, ui->c);
1361 } else if (!out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
1365 } else ui->cursor_show = TRUE;
1369 if (action == hint) {
1370 move *end, *buf = snewn(state->params.w * state->params.h,
1373 end = solve_internal(state, buf, DIFF_RECURSION);
1374 if (end != NULL && end > buf) {
1375 ret = nfmtstr(40, "%c,%d,%d",
1376 buf->colour == M_BLACK ? 'B' : 'W',
1377 buf->square.r, buf->square.c);
1378 /* We used to set a flag here in the game_ui indicating
1379 * that the player had used the hint function. I (SGT)
1380 * retired it, on grounds of consistency with other games
1381 * (most of these games will still flash to indicate
1382 * completion if you solved and undid it, so why not if
1383 * you got a hint?) and because the flash is as much about
1384 * checking you got it all right than about congratulating
1385 * you on a job well done. */
1391 cell = state->grid[idx(r, c, state->params.w)];
1392 if (cell > 0) return NULL;
1394 if (action == forwards) switch (cell) {
1395 case EMPTY: return nfmtstr(40, "W,%d,%d", r, c);
1396 case WHITE: return nfmtstr(40, "B,%d,%d", r, c);
1397 case BLACK: return nfmtstr(40, "E,%d,%d", r, c);
1400 else if (action == backwards) switch (cell) {
1401 case BLACK: return nfmtstr(40, "W,%d,%d", r, c);
1402 case WHITE: return nfmtstr(40, "E,%d,%d", r, c);
1403 case EMPTY: return nfmtstr(40, "B,%d,%d", r, c);
1409 static int find_errors(const game_state *state, int *report)
1411 int const w = state->params.w, h = state->params.h, n = w * h;
1416 int nblack = 0, any_white_cell = -1;
1417 game_state *dup = dup_game(state);
1419 for (i = r = 0; r < h; ++r)
1420 for (c = 0; c < w; ++c, ++i) {
1421 switch (state->grid[i]) {
1427 for (j = 0; j < 4; ++j) {
1428 int const rr = r + dr[j], cc = c + dc[j];
1429 if (out_of_bounds(rr, cc, w, h)) continue;
1430 if (state->grid[idx(rr, cc, w)] != BLACK) continue;
1431 if (!report) goto found_error;
1440 for (runs = 1, j = 0; j < 4; ++j) {
1441 int const rr = r + dr[j], cc = c + dc[j];
1442 runs += runlength(rr, cc, dr[j], dc[j], state,
1446 if (runs != state->grid[i]) goto found_error;
1447 } else if (runs < state->grid[i]) report[i] = TRUE;
1449 for (runs = 1, j = 0; j < 4; ++j) {
1450 int const rr = r + dr[j], cc = c + dc[j];
1451 runs += runlength(rr, cc, dr[j], dc[j], state,
1452 ~(MASK(BLACK) | MASK(EMPTY)));
1454 if (runs > state->grid[i]) report[i] = TRUE;
1458 /* note: fallthrough _into_ these cases */
1460 case WHITE: any_white_cell = i;
1465 * Check that all the white cells form a single connected component.
1468 for (r = 0; r < h-1; ++r)
1469 for (c = 0; c < w; ++c)
1470 if (state->grid[r*w+c] != BLACK &&
1471 state->grid[(r+1)*w+c] != BLACK)
1472 dsf_merge(dsf, r*w+c, (r+1)*w+c);
1473 for (r = 0; r < h; ++r)
1474 for (c = 0; c < w-1; ++c)
1475 if (state->grid[r*w+c] != BLACK &&
1476 state->grid[r*w+(c+1)] != BLACK)
1477 dsf_merge(dsf, r*w+c, r*w+(c+1));
1478 if (nblack + dsf_size(dsf, any_white_cell) < n) {
1479 int biggest, canonical;
1487 * Report this error by choosing one component to be the
1488 * canonical one (we pick the largest, arbitrarily
1489 * tie-breaking towards lower array indices) and highlighting
1490 * as an error any square in a different component.
1494 for (i = 0; i < n; ++i)
1495 if (state->grid[i] != BLACK) {
1496 int size = dsf_size(dsf, i);
1497 if (size > biggest) {
1499 canonical = dsf_canonify(dsf, i);
1503 for (i = 0; i < n; ++i)
1504 if (state->grid[i] != BLACK && dsf_canonify(dsf, i) != canonical)
1510 return FALSE; /* if report != NULL, this is ignored */
1517 static game_state *execute_move(const game_state *state, const char *move)
1519 signed int r, c, value, nchars, ntok;
1520 signed char what_to_do;
1525 ret = dup_game(state);
1529 ret->has_cheated = ret->was_solved = TRUE;
1532 for (; *move; move += nchars) {
1533 ntok = sscanf(move, "%c,%d,%d%n", &what_to_do, &r, &c, &nchars);
1534 if (ntok < 3) goto failure;
1535 switch (what_to_do) {
1536 case 'W': value = WHITE; break;
1537 case 'E': value = EMPTY; break;
1538 case 'B': value = BLACK; break;
1539 default: goto failure;
1541 if (out_of_bounds(r, c, ret->params.w, ret->params.h)) goto failure;
1542 ret->grid[idx(r, c, ret->params.w)] = value;
1545 if (ret->was_solved == FALSE)
1546 ret->was_solved = !find_errors(ret, NULL);
1555 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1556 const game_state *newstate)
1560 static float game_anim_length(const game_state *oldstate,
1561 const game_state *newstate, int dir, game_ui *ui)
1566 #define FLASH_TIME 0.7F
1568 static float game_flash_length(const game_state *from,
1569 const game_state *to, int dir, game_ui *ui)
1571 if (!from->was_solved && to->was_solved && !to->has_cheated)
1576 static int game_status(const game_state *state)
1578 return state->was_solved ? +1 : 0;
1581 /* ----------------------------------------------------------------------
1585 #define PREFERRED_TILE_SIZE 32
1590 COL_BLACK = COL_GRID,
1591 COL_TEXT = COL_GRID,
1592 COL_USER = COL_GRID,
1595 COL_HIGHLIGHT = COL_ERROR, /* mkhighlight needs it, I don't */
1596 COL_CURSOR = COL_LOWLIGHT,
1600 static void game_compute_size(const game_params *params, int tilesize,
1603 *x = (1 + params->w) * tilesize;
1604 *y = (1 + params->h) * tilesize;
1607 static void game_set_size(drawing *dr, game_drawstate *ds,
1608 const game_params *params, int tilesize)
1610 ds->tilesize = tilesize;
1613 #define COLOUR(ret, i, r, g, b) \
1614 ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1616 static float *game_colours(frontend *fe, int *ncolours)
1618 float *ret = snewn(3 * NCOLOURS, float);
1620 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1621 COLOUR(ret, COL_GRID, 0.0F, 0.0F, 0.0F);
1622 COLOUR(ret, COL_ERROR, 1.0F, 0.0F, 0.0F);
1624 *ncolours = NCOLOURS;
1628 static drawcell makecell(puzzle_size value, int error, int cursor, int flash)
1631 setmember(ret, value);
1632 setmember(ret, error);
1633 setmember(ret, cursor);
1634 setmember(ret, flash);
1638 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1640 int const w = state->params.w, h = state->params.h, n = w * h;
1641 struct game_drawstate *ds = snew(struct game_drawstate);
1645 ds->started = FALSE;
1647 ds->grid = snewn(n, drawcell);
1648 for (i = 0; i < n; ++i)
1649 ds->grid[i] = makecell(w + h, FALSE, FALSE, FALSE);
1654 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1660 #define cmpmember(a, b, field) ((a) . field == (b) . field)
1662 static int cell_eq(drawcell a, drawcell b)
1665 cmpmember(a, b, value) &&
1666 cmpmember(a, b, error) &&
1667 cmpmember(a, b, cursor) &&
1668 cmpmember(a, b, flash);
1671 static void draw_cell(drawing *dr, game_drawstate *ds, int r, int c,
1674 static void game_redraw(drawing *dr, game_drawstate *ds,
1675 const game_state *oldstate, const game_state *state,
1676 int dir, const game_ui *ui,
1677 float animtime, float flashtime)
1679 int const w = state->params.w, h = state->params.h, n = w * h;
1680 int const wpx = (w+1) * ds->tilesize, hpx = (h+1) * ds->tilesize;
1681 int const flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2;
1685 int *errors = snewn(n, int);
1686 memset(errors, FALSE, n * sizeof (int));
1687 find_errors(state, errors);
1689 assert (oldstate == NULL); /* only happens if animating moves */
1693 draw_rect(dr, 0, 0, wpx, hpx, COL_BACKGROUND);
1694 draw_update(dr, 0, 0, wpx, hpx);
1697 for (i = r = 0; r < h; ++r) {
1698 for (c = 0; c < w; ++c, ++i) {
1699 drawcell cell = makecell(state->grid[i], errors[i], FALSE, flash);
1700 if (r == ui->r && c == ui->c && ui->cursor_show)
1702 if (!cell_eq(cell, ds->grid[i])) {
1703 draw_cell(dr, ds, r, c, cell);
1712 static void draw_cell(drawing *draw, game_drawstate *ds, int r, int c,
1715 int const ts = ds->tilesize;
1716 int const y = BORDER + ts * r, x = BORDER + ts * c;
1717 int const tx = x + (ts / 2), ty = y + (ts / 2);
1718 int const dotsz = (ds->tilesize + 9) / 10;
1720 int const colour = (cell.value == BLACK ?
1721 cell.error ? COL_ERROR : COL_BLACK :
1722 cell.flash || cell.cursor ?
1723 COL_LOWLIGHT : COL_BACKGROUND);
1725 draw_rect_outline(draw, x, y, ts + 1, ts + 1, COL_GRID);
1726 draw_rect (draw, x + 1, y + 1, ts - 1, ts - 1, colour);
1728 draw_rect_outline(draw, x + 1, y + 1, ts - 1, ts - 1, COL_ERROR);
1730 switch (cell.value) {
1731 case WHITE: draw_rect(draw, tx - dotsz / 2, ty - dotsz / 2, dotsz, dotsz,
1732 cell.error ? COL_ERROR : COL_USER);
1733 case BLACK: case EMPTY: break;
1736 int const colour = (cell.error ? COL_ERROR : COL_GRID);
1737 char *msg = nfmtstr(10, "%d", cell.value);
1738 draw_text(draw, tx, ty, FONT_VARIABLE, ts * 3 / 5,
1739 ALIGN_VCENTRE | ALIGN_HCENTRE, colour, msg);
1744 draw_update(draw, x, y, ts + 1, ts + 1);
1747 static int game_timing_state(const game_state *state, game_ui *ui)
1749 puts("warning: game_timing_state was called (this shouldn't happen)");
1750 return FALSE; /* the (non-existing) timer should not be running */
1753 /* ----------------------------------------------------------------------
1754 * User interface: print
1757 static void game_print_size(const game_params *params, float *x, float *y)
1759 int print_width, print_height;
1760 game_compute_size(params, 800, &print_width, &print_height);
1761 *x = print_width / 100.0F;
1762 *y = print_height / 100.0F;
1765 static void game_print(drawing *dr, const game_state *state, int tilesize)
1767 int const w = state->params.w, h = state->params.h;
1768 game_drawstate ds_obj, *ds = &ds_obj;
1769 int r, c, i, colour;
1771 ds->tilesize = tilesize;
1773 colour = print_mono_colour(dr, 1); assert(colour == COL_BACKGROUND);
1774 colour = print_mono_colour(dr, 0); assert(colour == COL_GRID);
1775 colour = print_mono_colour(dr, 1); assert(colour == COL_ERROR);
1776 colour = print_mono_colour(dr, 0); assert(colour == COL_LOWLIGHT);
1777 colour = print_mono_colour(dr, 0); assert(colour == NCOLOURS);
1779 for (i = r = 0; r < h; ++r)
1780 for (c = 0; c < w; ++c, ++i)
1781 draw_cell(dr, ds, r, c,
1782 makecell(state->grid[i], FALSE, FALSE, FALSE));
1784 print_line_width(dr, 3 * tilesize / 40);
1785 draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, h*TILESIZE, COL_GRID);
1788 /* And that's about it ;-) **************************************************/
1791 #define thegame range
1794 struct game const thegame = {
1795 "Range", "games.range", "range",
1797 game_fetch_preset, NULL,
1802 TRUE, game_configure, custom_params,
1810 TRUE, game_can_format_as_text_now, game_text_format,
1818 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1821 game_free_drawstate,
1826 TRUE, FALSE, game_print_size, game_print,
1827 FALSE, /* wants_statusbar */
1828 FALSE, game_timing_state,