From e7414d31ae04ed38c1e3c6dd820c932b825af416 Mon Sep 17 00:00:00 2001 From: simon Date: Tue, 14 Sep 2010 09:31:52 +0000 Subject: [PATCH] New puzzle from Jonas Koelker: 'Range', an implementation of the puzzle variously known (depending on which website you look at) as Kurodoko, Kuromasu or 'Where is Black Cells'. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@8996 cda61777-01e9-0310-a592-d414129be87e --- icons/Makefile | 5 +- icons/range.sav | 36 ++ puzzles.but | 56 ++ range.R | 19 + range.c | 1734 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 1848 insertions(+), 2 deletions(-) create mode 100644 icons/range.sav create mode 100644 range.R create mode 100644 range.c diff --git a/icons/Makefile b/icons/Makefile index 3e79c76..95e0e2e 100644 --- a/icons/Makefile +++ b/icons/Makefile @@ -2,8 +2,8 @@ PUZZLES = blackbox bridges cube dominosa fifteen filling flip galaxies guess \ inertia keen lightup loopy magnets map mines net netslide pattern \ - pegs rect samegame signpost singles sixteen slant solo tents towers \ - twiddle unequal untangle + pegs range rect samegame signpost singles sixteen slant solo tents \ + towers twiddle unequal untangle BASE = $(patsubst %,%-base.png,$(PUZZLES)) WEB = $(patsubst %,%-web.png,$(PUZZLES)) @@ -70,6 +70,7 @@ net-ibase.png : override CROP=193x193 113x113+0+80 netslide-ibase.png : override CROP=289x289 144x144+0+0 pattern-ibase.png : override CROP=384x384 223x223+0+0 pegs-ibase.png : override CROP=263x263 147x147+116+0 +range-ibase.png : override CROP=256x256 98x98+111+15 rect-ibase.png : override CROP=205x205 115x115+90+0 signpost-ibase.png : override CROP=240x240 98x98+23+23 singles-ibase.png : override CROP=224x224 98x98+15+15 diff --git a/icons/range.sav b/icons/range.sav new file mode 100644 index 0000000..708e7db --- /dev/null +++ b/icons/range.sav @@ -0,0 +1,36 @@ +SAVEFILE:41:Simon Tatham's Portable Puzzle Collection +VERSION :1:1 +GAME :5:Range +PARAMS :3:7x7 +CPARAMS :3:7x7 +SEED :15:989032078841515 +DESC :22:d7b3e8e5c7a7c13e4e8b4d +UI :1:0 +NSTATES :2:27 +STATEPOS:2:27 +MOVE :5:W,4,2 +MOVE :5:W,4,3 +MOVE :5:W,4,4 +MOVE :5:W,4,5 +MOVE :5:W,4,6 +MOVE :5:W,4,0 +MOVE :5:W,3,1 +MOVE :5:W,2,1 +MOVE :5:W,1,1 +MOVE :5:W,0,1 +MOVE :5:W,6,1 +MOVE :5:W,5,1 +MOVE :5:W,5,5 +MOVE :5:W,1,5 +MOVE :5:B,5,2 +MOVE :5:W,5,3 +MOVE :5:W,6,3 +MOVE :5:W,3,6 +MOVE :5:W,2,6 +MOVE :5:B,3,5 +MOVE :5:W,2,4 +MOVE :5:W,2,2 +MOVE :5:B,2,3 +MOVE :5:W,1,3 +MOVE :5:W,3,3 +MOVE :5:W,0,5 diff --git a/puzzles.but b/puzzles.but index 1db8b71..a5dff8f 100644 --- a/puzzles.but +++ b/puzzles.but @@ -2851,6 +2851,62 @@ These parameters are available from the \q{Custom...} option on the (the start at the top left, and the end at the bottom right). If false the start and end squares are placed randomly (although always both shown). +\C{range} \i{Range} + +\cfg{winhelp-topic}{games.range} + +You have a grid of squares; some squares contain numbers. Your job is +to colour some of the squares black, such that several criteria are +satisfied: + +\b no square with a number is coloured black. + +\b no two black squares are adjacent (horizontally or vertically). + +\b for any two white squares, there is a path between them using only +white squares. + +\b for each square with a number, that number denotes the number of +squares reachable from that square going in each direction until +hitting a wall or a black square. + +For instance, a square containing the number one must have four black +squares as its neighbours by the last criterion; but then it's +impossible for it to be connected to any outside white square, which +violates the second to last criterion. So no square will contain the +number one. + +Credit for this puzzle goes to \i{Nikoli}, who have variously called +it \q{Kurodoko}, \q{Kuromasu} or \q{Where is Black Cells}. +\k{nikoli-range}. + +Range was contributed to this collection by Jonas K\u00F6{oe}lker. + +\B{nikoli-range} +\W{http://www.nikoli.co.jp/en/puzzles/where_is_black_cells/}\cw{http://www.nikoli.co.jp/en/puzzles/where_is_black_cells/} + +\H{range-controls} \I{controls, for Range}Range controls + +Click with the left button to paint a square black, or with the right +button to mark a square with a dot to indicate that you are sure it +should \e{not} be painted black. Repeated clicking with either button +will cycle the square through the three possible states (filled, +dotted or empty) in opposite directions. + +You can also use the cursor keys to move around the grid squares. +Pressing Return does the same as clicking with the left button, while +pressing Space does the same as a right button click. + +(All the actions described in \k{common-actions} are also available.) + +\H{range-parameters} \I{parameters, for Range}Range parameters + +These parameters are available from the \q{Custom...} option on the +\q{Type} menu. + +\dt \e{Width}, \e{Height} + +\dd Size of grid in squares. \A{licence} \I{MIT licence}\ii{Licence} diff --git a/range.R b/range.R new file mode 100644 index 0000000..257b270 --- /dev/null +++ b/range.R @@ -0,0 +1,19 @@ +# -*- makefile -*- + +range : [X] GTK COMMON range range-icon|no-icon + +range : [G] WINDOWS COMMON range range.res|noicon.res + +ALL += range[COMBINED] + +!begin gtk +GAMES += range +!end + +!begin >list.c + A(range) \ +!end + +!begin >wingames.lst +range.exe:Range +!end diff --git a/range.c b/range.c new file mode 100644 index 0000000..a82acb3 --- /dev/null +++ b/range.c @@ -0,0 +1,1734 @@ +/* + * range.c: implementation of the Nikoli game 'Kurodoko' / 'Kuromasu'. + */ + +/* + * Puzzle rules: the player is given a WxH grid of white squares, some + * of which contain numbers. The goal is to paint some of the squares + * black, such that: + * + * - no cell (err, cell = square) with a number is painted black + * - no black cells have an adjacent (horz/vert) black cell + * - the white cells are all connected (through other white cells) + * - if a cell contains a number n, let h and v be the lengths of the + * maximal horizontal and vertical white sequences containing that + * cell. Then n must equal h + v - 1. + */ + +/* example instance with its encoding: + * + * +--+--+--+--+--+--+--+ + * | | | | | 7| | | + * +--+--+--+--+--+--+--+ + * | 3| | | | | | 8| + * +--+--+--+--+--+--+--+ + * | | | | | | 5| | + * +--+--+--+--+--+--+--+ + * | | | 7| | 7| | | + * +--+--+--+--+--+--+--+ + * | |13| | | | | | + * +--+--+--+--+--+--+--+ + * | 4| | | | | | 8| + * +--+--+--+--+--+--+--+ + * | | | 4| | | | | + * +--+--+--+--+--+--+--+ + * + * 7x7:d7b3e8e5c7a7c13e4d8b4d + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" + +#include + +#define setmember(obj, field) ( (obj) . field = field ) + +char *nfmtstr(int n, char *fmt, ...) { + va_list va; + char *ret = snewn(n+1, char); + va_start(va, fmt); + vsprintf(ret, fmt, va); + va_end(va); + return ret; +} + +#define SWAP(type, lvar1, lvar2) do { \ + type tmp = (lvar1); \ + (lvar1) = (lvar2); \ + (lvar2) = tmp; \ +} while (0) + +/* ---------------------------------------------------------------------- + * Game parameters, presets, states + */ + +typedef signed char puzzle_size; + +struct game_params { + puzzle_size w; + puzzle_size h; +}; + +struct game_state { + struct game_params params; + unsigned int has_cheated: 1; + unsigned int was_solved: 1; + puzzle_size *grid; +}; + +#define DEFAULT_PRESET 0 +static struct game_params presets[] = {{9, 6}, {12, 8}, {13, 9}, {16, 11}}; +/* rationale: I want all four combinations of {odd/even, odd/even}, as + * they play out differently with respect to two-way symmetry. I also + * want them to be generated relatively fast yet still be large enough + * to be entertaining for a decent amount of time, and I want them to + * make good use of monitor real estate (the typical screen resolution + * is why I do 13x9 and not 9x13). + */ + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + *ret = presets[DEFAULT_PRESET]; /* structure copy */ + return ret; +} + +static game_params *dup_params(game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + if (i < 0 || i >= lenof(presets)) return FALSE; + + *name = nfmtstr(40, "%d x %d", presets[i].w, presets[i].h); + *params = dup_params(&presets[i]); + + return TRUE; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static void decode_params(game_params *params, char const *string) +{ + /* FIXME check for puzzle_size overflow and decoding issues */ + params->w = params->h = atoi(string); + while (*string && isdigit((unsigned char) *string)) ++string; + if (*string == 'x') { + string++; + params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } +} + +static char *encode_params(game_params *params, int full) +{ + char str[80]; + sprintf(str, "%dx%d", params->w, params->h); + return dupstr(str); +} + +static config_item *game_configure(game_params *params) +{ + config_item *ret; + + ret = snewn(3, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + ret[0].sval = nfmtstr(10, "%d", params->w); + ret[0].ival = 0; + + ret[1].name = "Height"; + ret[1].type = C_STRING; + ret[1].sval = nfmtstr(10, "%d", params->h); + ret[1].ival = 0; + + ret[2].name = NULL; + ret[2].type = C_END; + ret[2].sval = NULL; + ret[2].ival = 0; + + return ret; +} + +static game_params *custom_params(config_item *configuration) +{ + game_params *ret = snew(game_params); + ret->w = atoi(configuration[0].sval); + ret->h = atoi(configuration[1].sval); + return ret; +} + +#define memdup(dst, src, n, type) do { \ + dst = snewn(n, type); \ + memcpy(dst, src, n * sizeof (type)); \ +} while (0) + +static game_state *dup_game(game_state *state) +{ + game_state *ret = snew(game_state); + int const n = state->params.w * state->params.h; + + *ret = *state; /* structure copy */ + + /* copy the poin_tee_, set a new value of the poin_ter_ */ + memdup(ret->grid, state->grid, n, puzzle_size); + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state->grid); + sfree(state); +} + + +/* ---------------------------------------------------------------------- + * The solver subsystem. + * + * The solver is used for two purposes: + * - To solve puzzles when the user selects `Solve'. + * - To test solubility of a grid as clues are being removed from it + * during the puzzle generation. + * + * It supports the following ways of reasoning: + * + * - A cell adjacent to a black cell must be white. + * + * - If painting a square black would bisect the white regions, that + * square is white (by finding biconnected components' cut points) + * + * - A cell with number n, covering at most k white squares in three + * directions must white-cover n-k squares in the last direction. + * + * - A cell with number n known to cover k squares, if extending the + * cover by one square in a given direction causes the cell to + * cover _more_ than n squares, that extension cell must be black. + * + * (either if the square already covers n, or if it extends into a + * chunk of size > n - k) + * + * - Recursion. Pick any cell and see if this leads to either a + * contradiction or a solution (and then act appropriately). + * + * + * TODO: + * + * (propagation upper limit) + * - If one has two numbers on the same line, the smaller limits the + * larger. Example: in |b|_|_|8|4|_|_|b|, only two _'s can be both + * white and connected to the "8" cell; so that cell will propagate + * at least four cells orthogonally to the displayed line (which is + * better than the current "at least 2"). + * + * (propagation upper limit) + * - cells can't propagate into other cells if doing so exceeds that + * number. Example: in |b|4|.|.|2|b|, at most one _ can be white; + * otherwise, the |2| would have too many reaching white cells. + * + * (propagation lower and upper limit) + * - `Full Combo': in each four directions d_1 ... d_4, find a set of + * possible propagation distances S_1 ... S_4. For each i=1..4, + * for each x in S_i: if not exists (y, z, w) in the other sets + * such that (x+y+z+w+1 == clue value): then remove x from S_i. + * Repeat until this stabilizes. If any cell would contradict + */ + +#define idx(i, j, w) ((i)*(w) + (j)) +#define out_of_bounds(r, c, w, h) \ + ((r) < 0 || (r) >= h || (c) < 0 || (c) >= w) + +typedef struct square { + puzzle_size r, c; +} square; + +enum {BLACK = -2, WHITE, EMPTY}; +/* white is for pencil marks, empty is undecided */ + +static int const dr[4] = {+1, 0, -1, 0}; +static int const dc[4] = { 0, +1, 0, -1}; +static int const cursors[4] = /* must match dr and dc */ +{CURSOR_DOWN, CURSOR_RIGHT, CURSOR_UP, CURSOR_LEFT}; + +typedef struct move { + square square; + unsigned int colour: 1; +} move; +enum {M_BLACK = 0, M_WHITE = 1}; + +typedef move *(reasoning)(game_state *state, + int nclues, + const square *clues, + move *buf); + +static reasoning solver_reasoning_not_too_big; +static reasoning solver_reasoning_adjacency; +static reasoning solver_reasoning_connectedness; +static reasoning solver_reasoning_recursion; + +enum { + DIFF_NOT_TOO_BIG, + DIFF_ADJACENCY, + DIFF_CONNECTEDNESS, + DIFF_RECURSION +}; + +static move *solve_internal(game_state *state, move *base, int diff); + +static char *solve_game(game_state *orig, game_state *curpos, + char *aux, char **error) +{ + int const n = orig->params.w * orig->params.h; + move *const base = snewn(n, move); + move *moves = solve_internal(orig, base, DIFF_RECURSION); + + char *ret = NULL; + + if (moves != NULL) { + int const k = moves - base; + char *str = ret = snewn(15*k + 2, char); + char colour[2] = "BW"; + move *it; + *str++ = 'S'; + *str = '\0'; + for (it = base; it < moves; ++it) + str += sprintf(str, "%c,%d,%d", colour[it->colour], + it->square.r, it->square.c); + } else *error = "This puzzle instance contains a contradiction"; + + sfree(base); + return ret; +} + +static square *find_clues(game_state *state, int *ret_nclues); +static move *do_solve(game_state *state, + int nclues, + const square *clues, + move *move_buffer, + int difficulty); + +/* new_game_desc entry point in the solver subsystem */ +static move *solve_internal(game_state *state, move *base, int diff) +{ + int nclues; + square *const clues = find_clues(state, &nclues); + game_state *dup = dup_game(state); + move *const moves = do_solve(dup, nclues, clues, base, diff); + free_game(dup); + sfree(clues); + return moves; +} + +static move *do_solve(game_state *state, + int nclues, + const square *clues, + move *move_buffer, + int difficulty) +{ + reasoning *reasonings[] = { + solver_reasoning_not_too_big, + solver_reasoning_adjacency, + solver_reasoning_connectedness, + solver_reasoning_recursion + }; + + struct move *buf = move_buffer, *oldbuf; + int i; + + do { + oldbuf = buf; + for (i = 0; i < lenof(reasonings) && i <= difficulty; ++i) { + /* only recurse if all else fails */ + if (i == DIFF_RECURSION && buf > oldbuf) continue; + buf = (*reasonings[i])(state, nclues, clues, buf); + if (buf == NULL) return NULL; + } + } while (buf > oldbuf); + + return buf; +} + +#define MASK(n) (1 << ((n) + 2)) + +static int runlength(puzzle_size r, puzzle_size c, + puzzle_size dr, puzzle_size dc, + game_state *state, int colourmask) +{ + int const w = state->params.w, h = state->params.h; + int sz = 0; + while (TRUE) { + int cell = idx(r, c, w); + if (out_of_bounds(r, c, w, h)) break; + if (state->grid[cell] > 0) { + if (!(colourmask & ~(MASK(BLACK) | MASK(WHITE) | MASK(EMPTY)))) + break; + } else if (!(MASK(state->grid[cell]) & colourmask)) break; + ++sz; + r += dr; + c += dc; + } + return sz; +} + +static void solver_makemove(puzzle_size r, puzzle_size c, int colour, + game_state *state, move **buffer_ptr) +{ + int const cell = idx(r, c, state->params.w); + if (out_of_bounds(r, c, state->params.w, state->params.h)) return; + if (state->grid[cell] != EMPTY) return; + setmember((*buffer_ptr)->square, r); + setmember((*buffer_ptr)->square, c); + setmember(**buffer_ptr, colour); + ++*buffer_ptr; + state->grid[cell] = (colour == M_BLACK ? BLACK : WHITE); +} + +static move *solver_reasoning_adjacency(game_state *state, + int nclues, + const square *clues, + move *buf) +{ + int r, c, i; + for (r = 0; r < state->params.h; ++r) + for (c = 0; c < state->params.w; ++c) { + int const cell = idx(r, c, state->params.w); + if (state->grid[cell] != BLACK) continue; + for (i = 0; i < 4; ++i) + solver_makemove(r + dr[i], c + dc[i], M_WHITE, state, &buf); + } + return buf; +} + +enum {NOT_VISITED = -1}; + +static int dfs_biconnect_visit(puzzle_size r, puzzle_size c, + game_state *state, + square *dfs_parent, int *dfs_depth, + move **buf); + +static move *solver_reasoning_connectedness(game_state *state, + int nclues, + const square *clues, + move *buf) +{ + int const w = state->params.w, h = state->params.h, n = w * h; + + square *const dfs_parent = snewn(n, square); + int *const dfs_depth = snewn(n, int); + + int i; + for (i = 0; i < n; ++i) { + dfs_parent[i].r = NOT_VISITED; + dfs_depth[i] = -n; + } + + for (i = 0; i < n && state->grid[i] == BLACK; ++i); + + dfs_parent[i].r = i / w; + dfs_parent[i].c = i % w; /* `dfs root`.parent == `dfs root` */ + dfs_depth[i] = 0; + + dfs_biconnect_visit(i / w, i % w, state, dfs_parent, dfs_depth, &buf); + + sfree(dfs_parent); + sfree(dfs_depth); + + return buf; +} + +/* returns the `lowpoint` of (r, c) */ +static int dfs_biconnect_visit(puzzle_size r, puzzle_size c, + game_state *state, + square *dfs_parent, int *dfs_depth, + move **buf) +{ + const puzzle_size w = state->params.w, h = state->params.h; + int const i = idx(r, c, w), mydepth = dfs_depth[i]; + int lowpoint = mydepth, j, nchildren = 0; + + for (j = 0; j < 4; ++j) { + const puzzle_size rr = r + dr[j], cc = c + dc[j]; + int const cell = idx(rr, cc, w); + + if (out_of_bounds(rr, cc, w, h)) continue; + if (state->grid[cell] == BLACK) continue; + + if (dfs_parent[cell].r == NOT_VISITED) { + int child_lowpoint; + dfs_parent[cell].r = r; + dfs_parent[cell].c = c; + dfs_depth[cell] = mydepth + 1; + child_lowpoint = dfs_biconnect_visit(rr, cc, state, dfs_parent, + dfs_depth, buf); + + if (child_lowpoint >= mydepth && mydepth > 0) + solver_makemove(r, c, M_WHITE, state, buf); + + lowpoint = min(lowpoint, child_lowpoint); + ++nchildren; + } else if (rr != dfs_parent[i].r || cc != dfs_parent[i].c) { + lowpoint = min(lowpoint, dfs_depth[cell]); + } + } + + if (mydepth == 0 && nchildren >= 2) + solver_makemove(r, c, M_WHITE, state, buf); + + return lowpoint; +} + +static move *solver_reasoning_not_too_big(game_state *state, + int nclues, + const square *clues, + move *buf) +{ + int const w = state->params.w, runmasks[4] = { + ~(MASK(BLACK) | MASK(EMPTY)), + MASK(EMPTY), + ~(MASK(BLACK) | MASK(EMPTY)), + ~(MASK(BLACK)) + }; + enum {RUN_WHITE, RUN_EMPTY, RUN_BEYOND, RUN_SPACE}; + + int i, runlengths[4][4]; + + for (i = 0; i < nclues; ++i) { + int j, k, whites, space; + + const puzzle_size row = clues[i].r, col = clues[i].c; + int const clue = state->grid[idx(row, col, w)]; + + for (j = 0; j < 4; ++j) { + puzzle_size r = row + dr[j], c = col + dc[j]; + runlengths[RUN_SPACE][j] = 0; + for (k = 0; k <= RUN_SPACE; ++k) { + int l = runlength(r, c, dr[j], dc[j], state, runmasks[k]); + if (k < RUN_SPACE) { + runlengths[k][j] = l; + r += dr[j] * l; + c += dc[j] * l; + } + runlengths[RUN_SPACE][j] += l; + } + } + + whites = 1; + for (j = 0; j < 4; ++j) whites += runlengths[RUN_WHITE][j]; + + for (j = 0; j < 4; ++j) { + int const delta = 1 + runlengths[RUN_WHITE][j]; + const puzzle_size r = row + delta * dr[j]; + const puzzle_size c = col + delta * dc[j]; + + if (whites == clue) { + solver_makemove(r, c, M_BLACK, state, &buf); + continue; + } + + if (runlengths[RUN_EMPTY][j] == 1 && + whites + + runlengths[RUN_EMPTY][j] + + runlengths[RUN_BEYOND][j] + > clue) { + solver_makemove(r, c, M_BLACK, state, &buf); + continue; + } + + if (whites + + runlengths[RUN_EMPTY][j] + + runlengths[RUN_BEYOND][j] + > clue) { + runlengths[RUN_SPACE][j] = + runlengths[RUN_WHITE][j] + + runlengths[RUN_EMPTY][j] - 1; + + if (runlengths[RUN_EMPTY][j] == 1) + solver_makemove(r, c, M_BLACK, state, &buf); + } + } + + space = 1; + for (j = 0; j < 4; ++j) space += runlengths[RUN_SPACE][j]; + for (j = 0; j < 4; ++j) { + puzzle_size r = row + dr[j], c = col + dc[j]; + + int k = space - runlengths[RUN_SPACE][j]; + if (k >= clue) continue; + + for (; k < clue; ++k, r += dr[j], c += dc[j]) + solver_makemove(r, c, M_WHITE, state, &buf); + } + } + return buf; +} + +static move *solver_reasoning_recursion(game_state *state, + int nclues, + const square *clues, + move *buf) +{ + int const w = state->params.w, n = w * state->params.h; + int cell, colour; + + for (cell = 0; cell < n; ++cell) { + int const r = cell / w, c = cell % w; + int i; + game_state *newstate; + move *recursive_result; + + if (state->grid[cell] != EMPTY) continue; + + /* FIXME: add enum alias for smallest and largest (or N) */ + for (colour = M_BLACK; colour <= M_WHITE; ++colour) { + newstate = dup_game(state); + newstate->grid[cell] = colour; + recursive_result = do_solve(newstate, nclues, clues, buf, + DIFF_RECURSION); + free_game(newstate); + if (recursive_result == NULL) { + solver_makemove(r, c, M_BLACK + M_WHITE - colour, state, &buf); + return buf; + } + for (i = 0; i < n && newstate->grid[i] != EMPTY; ++i); + if (i == n) return buf; + } + } + return buf; +} + +static square *find_clues(game_state *state, int *ret_nclues) +{ + int r, c, i, nclues = 0; + square *ret = snewn(state->params.w * state->params.h, struct square); + + for (i = r = 0; r < state->params.h; ++r) + for (c = 0; c < state->params.w; ++c, ++i) + if (state->grid[i] > 0) { + ret[nclues].r = r; + ret[nclues].c = c; + ++nclues; + } + + *ret_nclues = nclues; + return sresize(ret, nclues + (nclues == 0), square); +} + +/* ---------------------------------------------------------------------- + * Puzzle generation + * + * Generating kurodoko instances is rather straightforward: + * + * - Start with a white grid and add black squares at randomly chosen + * locations, unless colouring that square black would violate + * either the adjacency or connectedness constraints. + * + * - For each white square, compute the number it would contain if it + * were given as a clue. + * + * - From a starting point of "give _every_ white square as a clue", + * for each white square (in a random order), see if the board is + * solvable when that square is not given as a clue. If not, don't + * give it as a clue, otherwise do. + * + * This never fails, but it's only _almost_ what I do. The real final + * step is this: + * + * - From a starting point of "give _every_ white square as a clue", + * first remove all clues that are two-way rotationally symmetric + * to a black square. If this leaves the puzzle unsolvable, throw + * it out and try again. Otherwise, remove all _pairs_ of clues + * (that are rotationally symmetric) which can be removed without + * rendering the puzzle unsolvable. + * + * This can fail even if one only removes the black and symmetric + * clues; indeed it happens often (avg. once or twice per puzzle) when + * generating 1xN instances. (If you add black cells they must be in + * the end, and if you only add one, it's ambiguous where). + */ + +/* forward declarations of internal calls */ +static void newdesc_choose_black_squares(game_state *state, + const int *shuffle_1toN); +static void newdesc_compute_clues(game_state *state); +static int newdesc_strip_clues(game_state *state, int *shuffle_1toN); +static char *newdesc_encode_game_description(int n, puzzle_size *grid); + +static char *new_game_desc(game_params *params, random_state *rs, + char **aux, int interactive) +{ + int const w = params->w, h = params->h, n = w * h; + + puzzle_size *const grid = snewn(n, puzzle_size); + int *const shuffle_1toN = snewn(n, int); + + int i, clues_removed; + + char *encoding; + + game_state state; + state.params = *params; + state.grid = grid; + + interactive = 0; /* I don't need it, I shouldn't use it*/ + + for (i = 0; i < n; ++i) shuffle_1toN[i] = i; + + while (TRUE) { + shuffle(shuffle_1toN, n, sizeof (int), rs); + newdesc_choose_black_squares(&state, shuffle_1toN); + + newdesc_compute_clues(&state); + + shuffle(shuffle_1toN, n, sizeof (int), rs); + clues_removed = newdesc_strip_clues(&state, shuffle_1toN); + + if (clues_removed < 0) continue; else break; + } + + encoding = newdesc_encode_game_description(n, grid); + + sfree(grid); + sfree(shuffle_1toN); + + return encoding; +} + +static int dfs_count_white(game_state *state, int cell); + +static void newdesc_choose_black_squares(game_state *state, + const int *shuffle_1toN) +{ + int const w = state->params.w, h = state->params.h, n = w * h; + + int k, any_white_cell, n_black_cells; + + for (k = 0; k < n; ++k) state->grid[k] = WHITE; + + any_white_cell = shuffle_1toN[n - 1]; + n_black_cells = 0; + + /* I like the puzzles that result from n / 3, but maybe this + * could be made a (generation, i.e. non-full) parameter? */ + for (k = 0; k < n / 3; ++k) { + int const i = shuffle_1toN[k], c = i % w, r = i / w; + + int j; + for (j = 0; j < 4; ++j) { + int const rr = r + dr[j], cc = c + dc[j], cell = idx(rr, cc, w); + /* if you're out of bounds, we skip you */ + if (out_of_bounds(rr, cc, w, h)) continue; + if (state->grid[cell] == BLACK) break; /* I can't be black */ + } if (j < 4) continue; /* I have black neighbour: I'm white */ + + state->grid[i] = BLACK; + ++n_black_cells; + + j = dfs_count_white(state, any_white_cell); + if (j + n_black_cells < n) { + state->grid[i] = WHITE; + --n_black_cells; + } + } +} + +static void newdesc_compute_clues(game_state *state) +{ + int const w = state->params.w, h = state->params.h; + int r, c; + + for (r = 0; r < h; ++r) { + int run_size = 0, c, cc; + for (c = 0; c <= w; ++c) { + if (c == w || state->grid[idx(r, c, w)] == BLACK) { + for (cc = c - run_size; cc < c; ++cc) + state->grid[idx(r, cc, w)] += run_size; + run_size = 0; + } else ++run_size; + } + } + + for (c = 0; c < w; ++c) { + int run_size = 0, r, rr; + for (r = 0; r <= h; ++r) { + if (r == h || state->grid[idx(r, c, w)] == BLACK) { + for (rr = r - run_size; rr < r; ++rr) + state->grid[idx(rr, c, w)] += run_size; + run_size = 0; + } else ++run_size; + } + } +} + +#define rotate(x) (n - 1 - (x)) + +static int newdesc_strip_clues(game_state *state, int *shuffle_1toN) +{ + int const w = state->params.w, n = w * state->params.h; + + move *const move_buffer = snewn(n, move); + move *buf; + game_state *dupstate; + + /* + * do a partition/pivot of shuffle_1toN into three groups: + * (1) squares rotationally-symmetric to (3) + * (2) squares not in (1) or (3) + * (3) black squares + * + * They go from [0, left), [left, right) and [right, n) in + * shuffle_1toN (and from there into state->grid[ ]) + * + * Then, remove clues from the grid one by one in shuffle_1toN + * order, until the solver becomes unhappy. If we didn't remove + * all of (1), return (-1). Else, we're happy. + */ + + /* do the partition */ + int clues_removed, k = 0, left = 0, right = n; + + for (;; ++k) { + while (k < right && state->grid[shuffle_1toN[k]] == BLACK) { + --right; + SWAP(int, shuffle_1toN[right], shuffle_1toN[k]); + assert(state->grid[shuffle_1toN[right]] == BLACK); + } + if (k >= right) break; + assert (k >= left); + if (state->grid[rotate(shuffle_1toN[k])] == BLACK) { + SWAP(int, shuffle_1toN[k], shuffle_1toN[left]); + ++left; + } + assert (state->grid[rotate(shuffle_1toN[k])] != BLACK + || k == left - 1); + } + + for (k = 0; k < left; ++k) { + assert (state->grid[rotate(shuffle_1toN[k])] == BLACK); + state->grid[shuffle_1toN[k]] = EMPTY; + } + for (k = left; k < right; ++k) { + assert (state->grid[rotate(shuffle_1toN[k])] != BLACK); + assert (state->grid[shuffle_1toN[k]] != BLACK); + } + for (k = right; k < n; ++k) { + assert (state->grid[shuffle_1toN[k]] == BLACK); + state->grid[shuffle_1toN[k]] = EMPTY; + } + + clues_removed = (left - 0) + (n - right); + + dupstate = dup_game(state); + buf = solve_internal(dupstate, move_buffer, DIFF_RECURSION - 1); + free_game(dupstate); + if (buf - move_buffer < clues_removed) { + /* branch prediction: I don't think I'll go here */ + clues_removed = -1; + goto ret; + } + + for (k = left; k < right; ++k) { + const int i = shuffle_1toN[k], j = rotate(i); + int const clue = state->grid[i], clue_rot = state->grid[j]; + if (clue == BLACK) continue; + state->grid[i] = state->grid[j] = EMPTY; + dupstate = dup_game(state); + buf = solve_internal(dupstate, move_buffer, DIFF_RECURSION - 1); + free_game(dupstate); + clues_removed += 2 - (i == j); + /* if i is the center square, then i == (j = rotate(i)) + * when i and j are one, removing i and j removes only one */ + if (buf - move_buffer == clues_removed) continue; + /* if the solver is sound, refilling all removed clues means + * we have filled all squares, i.e. solved the puzzle. */ + state->grid[i] = clue; + state->grid[j] = clue_rot; + clues_removed -= 2 - (i == j); + } + +ret: + sfree(move_buffer); + return clues_removed; +} + +static int dfs_count_rec(puzzle_size *grid, int r, int c, int w, int h) +{ + int const cell = idx(r, c, w); + if (out_of_bounds(r, c, w, h)) return 0; + if (grid[cell] != WHITE) return 0; + grid[cell] = EMPTY; + return 1 + + dfs_count_rec(grid, r + 0, c + 1, w, h) + + dfs_count_rec(grid, r + 0, c - 1, w, h) + + dfs_count_rec(grid, r + 1, c + 0, w, h) + + dfs_count_rec(grid, r - 1, c + 0, w, h); +} + +static int dfs_count_white(game_state *state, int cell) +{ + int const w = state->params.w, h = state->params.h, n = w * h; + int const r = cell / w, c = cell % w; + int i, k = dfs_count_rec(state->grid, r, c, w, h); + for (i = 0; i < n; ++i) + if (state->grid[i] == EMPTY) + state->grid[i] = WHITE; + return k; +} + +static char *validate_params(game_params *params, int full) +{ + int const w = params->w, h = params->h; + if (w < 1) return "Error: width is less than 1"; + if (h < 1) return "Error: height is less than 1"; + if (w * h < 1) return "Error: size is less than 1"; + if (w + h - 1 > SCHAR_MAX) return "Error: w + h is too big"; + /* I might be unable to store clues in my puzzle_size *grid; */ + if (full) { + if (w == 2 && h == 2) return "Error: can't create 2x2 puzzles"; + if (w == 1 && h == 2) return "Error: can't create 1x2 puzzles"; + if (w == 2 && h == 1) return "Error: can't create 2x1 puzzles"; + if (w == 1 && h == 1) return "Error: can't create 1x1 puzzles"; + } + return NULL; +} + +/* Definition: a puzzle instance is _good_ if: + * - it has a unique solution + * - the solver can find this solution without using recursion + * - the solution contains at least one black square + * - the clues are 2-way rotationally symmetric + * + * (the idea being: the generator can not output any _bad_ puzzles) + * + * Theorem: validate_params, when full != 0, discards exactly the set + * of parameters for which there are _no_ good puzzle instances. + * + * Proof: it's an immediate consequence of the five lemmas below. + * + * Observation: not only do puzzles on non-tiny grids exist, the + * generator is pretty fast about coming up with them. On my pre-2004 + * desktop box, it generates 100 puzzles on the highest preset (16x11) + * in 8.383 seconds, or <= 0.1 second per puzzle. + * + * ---------------------------------------------------------------------- + * + * Lemma: On a 1x1 grid, there are no good puzzles. + * + * Proof: the one square can't be a clue because at least one square + * is black. But both a white square and a black square satisfy the + * solution criteria, so the puzzle is ambiguous (and hence bad). + * + * Lemma: On a 1x2 grid, there are no good puzzles. + * + * Proof: let's name the squares l and r. Note that there can be at + * most one black square, or adjacency is violated. By assumption at + * least one square is black, so let's call that one l. By clue + * symmetry, neither l nor r can be given as a clue, so the puzzle + * instance is blank and thus ambiguous. + * + * Corollary: On a 2x1 grid, there are no good puzzles. + * Proof: rotate the above proof 90 degrees ;-) + * + * ---------------------------------------------------------------------- + * + * Lemma: On a 2x2 grid, there are no soluble puzzles with 2-way + * rotational symmetric clues and at least one black square. + * + * Proof: Let's name the squares a, b, c, and d, with a and b on the + * top row, a and c in the left column. Let's consider the case where + * a is black. Then no other square can be black: b and c would both + * violate the adjacency constraint; d would disconnect b from c. + * + * So exactly one square is black (and by 4-way rotation symmetry of + * the 2x2 square, it doesn't matter which one, so let's stick to a). + * By 2-way rotational symmetry of the clues and the rule about not + * painting numbers black, neither a nor d can be clues. A blank + * puzzle would be ambiguous, so one of {b, c} is a clue; by symmetry, + * so is the other one. + * + * It is readily seen that their clue value is 2. But "a is black" + * and "d is black" are both valid solutions in this case, so the + * puzzle is ambiguous (and hence bad). + * + * ---------------------------------------------------------------------- + * + * Lemma: On a wxh grid with w, h >= 1 and (w > 2 or h > 2), there is + * at least one good puzzle. + * + * Proof: assume that w > h (otherwise rotate the proof again). Paint + * the top left and bottom right corners black, and fill a clue into + * all the other squares. Present this board to the solver code (or + * player, hypothetically), except with the two black squares as blank + * squares. + * + * For an Nx1 puzzle, observe that every clue is N - 2, and there are + * N - 2 of them in one connected sequence, so the remaining two + * squares can be deduced to be black, which solves the puzzle. + * + * For any other puzzle, let j be a cell in the same row as a black + * cell, but not in the same column (such a cell doesn't exist in 2x3 + * puzzles, but we assume w > h and such cells exist in 3x2 puzzles). + * + * Note that the number of cells in axis parallel `rays' going out + * from j exceeds j's clue value by one. Only one such cell is a + * non-clue, so it must be black. Similarly for the other corner (let + * j' be a cell in the same row as the _other_ black cell, but not in + * the same column as _any_ black cell; repeat this argument at j'). + * + * This fills the grid and satisfies all clues and the adjacency + * constraint and doesn't paint on top of any clues. All that is left + * to see is connectedness. + * + * Observe that the white cells in each column form a single connected + * `run', and each column contains a white cell adjacent to a white + * cell in the column to the right, if that column exists. + * + * Thus, any cell in the left-most column can reach any other cell: + * first go to the target column (by repeatedly going to the cell in + * your current column that lets you go right, then going right), then + * go up or down to the desired cell. + * + * As reachability is symmetric (in undirected graphs) and transitive, + * any cell can reach any left-column cell, and from there any other + * cell. + */ + +/* ---------------------------------------------------------------------- + * Game encoding and decoding + */ + +#define NDIGITS_BASE '!' + +static char *newdesc_encode_game_description(int area, puzzle_size *grid) +{ + char *desc = NULL; + int desclen = 0, descsize = 0; + int run, i; + + run = 0; + for (i = 0; i <= area; i++) { + int n = (i < area ? grid[i] : -1); + + if (!n) + run++; + else { + if (descsize < desclen + 40) { + descsize = desclen * 3 / 2 + 40; + desc = sresize(desc, descsize, char); + } + if (run) { + while (run > 0) { + int c = 'a' - 1 + run; + if (run > 26) + c = 'z'; + desc[desclen++] = c; + run -= c - ('a' - 1); + } + } else { + /* + * If there's a number in the very top left or + * bottom right, there's no point putting an + * unnecessary _ before or after it. + */ + if (desclen > 0 && n > 0) + desc[desclen++] = '_'; + } + if (n > 0) + desclen += sprintf(desc+desclen, "%d", n); + run = 0; + } + } + desc[desclen] = '\0'; + return desc; +} + +static char *validate_desc(game_params *params, char *desc) +{ + int const n = params->w * params->h; + int squares = 0; + int range = params->w + params->h - 1; /* maximum cell value */ + + while (*desc && *desc != ',') { + int c = *desc++; + if (c >= 'a' && c <= 'z') { + squares += c - 'a' + 1; + } else if (c == '_') { + /* do nothing */; + } else if (c > '0' && c <= '9') { + int val = atoi(desc-1); + if (val < 1 || val > range) + return "Out-of-range number in game description"; + squares++; + while (*desc >= '0' && *desc <= '9') + desc++; + } else + return "Invalid character in game description"; + } + + if (squares < n) + return "Not enough data to fill grid"; + + if (squares > n) + return "Too much data to fit in grid"; + + return NULL; +} + +static game_state *new_game(midend *me, game_params *params, char *desc) +{ + int i; + char *p; + + int const n = params->w * params->h; + game_state *state = snew(game_state); + + me = NULL; /* I don't need it, I shouldn't use it */ + + state->params = *params; /* structure copy */ + state->grid = snewn(n, puzzle_size); + + p = desc; + i = 0; + while (i < n && *p) { + int c = *p++; + if (c >= 'a' && c <= 'z') { + int squares = c - 'a' + 1; + while (squares--) + state->grid[i++] = 0; + } else if (c == '_') { + /* do nothing */; + } else if (c > '0' && c <= '9') { + int val = atoi(p-1); + assert(val >= 1 && val <= params->w+params->h-1); + state->grid[i++] = val; + while (*p >= '0' && *p <= '9') + p++; + } + } + assert(i == n); + state->has_cheated = FALSE; + state->was_solved = FALSE; + + return state; +} + +/* ---------------------------------------------------------------------- + * User interface: ascii + */ + +static int game_can_format_as_text_now(game_params *params) +{ + return TRUE; +} + +static char *game_text_format(game_state *state) +{ + int cellsize, r, c, i, w_string, h_string, n_string; + char *ret, *buf, *gridline; + + int const w = state->params.w, h = state->params.h; + + cellsize = 0; /* or may be used uninitialized */ + + for (c = 0; c < w; ++c) { + for (r = 1; r < h; ++r) { + puzzle_size k = state->grid[idx(r, c, w)]; + int d; + for (d = 0; k; k /= 10, ++d); + cellsize = max(cellsize, d); + } + } + + ++cellsize; + + w_string = w * cellsize + 2; /* "|%d|%d|...|\n" */ + h_string = 2 * h + 1; /* "+--+--+...+\n%s\n+--+--+...+\n" */ + n_string = w_string * h_string; + + gridline = snewn(w_string + 1, char); /* +1: NUL terminator */ + memset(gridline, '-', w_string); + for (c = 0; c <= w; ++c) gridline[c * cellsize] = '+'; + gridline[w_string - 1] = '\n'; + gridline[w_string - 0] = '\0'; + + buf = ret = snewn(n_string + 1, char); /* +1: NUL terminator */ + for (i = r = 0; r < h; ++r) { + memcpy(buf, gridline, w_string); + buf += w_string; + for (c = 0; c < w; ++c, ++i) { + char ch; + switch (state->grid[i]) { + case BLACK: ch = '#'; break; + case WHITE: ch = '.'; break; + case EMPTY: ch = ' '; break; + default: + buf += sprintf(buf, "|%*d", cellsize - 1, state->grid[i]); + continue; + } + *buf++ = '|'; + memset(buf, ch, cellsize - 1); + buf += cellsize - 1; + } + buf += sprintf(buf, "|\n"); + } + memcpy(buf, gridline, w_string); + buf += w_string; + assert (buf - ret == n_string); + *buf = '\0'; + + sfree(gridline); + + return ret; +} + +/* ---------------------------------------------------------------------- + * User interfaces: interactive + */ + +struct game_ui { + puzzle_size r, c; /* cursor position */ + unsigned int cursor_show: 1; + unsigned int cheated: 1; +}; + +static game_ui *new_ui(game_state *state) +{ + struct game_ui *ui = snew(game_ui); + ui->r = ui->c = 0; + ui->cursor_show = ui->cheated = FALSE; + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(ui); +} + +static char *encode_ui(game_ui *ui) +{ + return dupstr(ui->cheated ? "1" : "0"); +} + +static void decode_ui(game_ui *ui, char *encoding) +{ + ui->cheated = (*encoding == '1'); +} + +typedef struct drawcell { + puzzle_size value; + unsigned int error: 1; + unsigned int cursor: 1; + unsigned int flash: 1; +} drawcell; + +struct game_drawstate { + int tilesize; + drawcell *grid; + unsigned int started: 1; +}; + +#define TILESIZE (ds->tilesize) +#define BORDER (TILESIZE / 2) +#define COORD(x) ((x) * TILESIZE + BORDER) +#define FROMCOORD(x) (((x) - BORDER) / TILESIZE) + +static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, + int x, int y, int button) +{ + enum {none, forwards, backwards, hint}; + int const w = state->params.w, h = state->params.h; + int r = ui->r, c = ui->c, action = none, cell; + + if (IS_CURSOR_SELECT(button) && !ui->cursor_show) return NULL; + + if (IS_MOUSE_DOWN(button)) { + r = FROMCOORD(y + TILESIZE) - 1; /* or (x, y) < TILESIZE) */ + c = FROMCOORD(x + TILESIZE) - 1; /* are considered inside */ + if (out_of_bounds(r, c, w, h)) return NULL; + ui->r = r; + ui->c = c; + ui->cursor_show = FALSE; + } + + if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { + /* + * Utterly awful hack, exactly analogous to the one in Slant, + * to configure the left and right mouse buttons the opposite + * way round. + * + * The original puzzle submitter thought it would be more + * useful to have the left button turn an empty square into a + * dotted one, on the grounds that that was what you did most + * often; I (SGT) felt instinctively that the left button + * ought to place black squares and the right button place + * dots, on the grounds that that was consistent with many + * other puzzles in which the left button fills in the data + * used by the solution checker while the right button places + * pencil marks for the user's convenience. + * + * My first beta-player wasn't sure either, so I thought I'd + * pre-emptively put in a 'configuration' mechanism just in + * case. + */ + { + static int swap_buttons = -1; + if (swap_buttons < 0) { + char *env = getenv("RANGE_SWAP_BUTTONS"); + swap_buttons = (env && (env[0] == 'y' || env[0] == 'Y')); + } + if (swap_buttons) { + if (button == LEFT_BUTTON) + button = RIGHT_BUTTON; + else + button = LEFT_BUTTON; + } + } + } + + switch (button) { + case CURSOR_SELECT : case LEFT_BUTTON: action = backwards; break; + case CURSOR_SELECT2: case RIGHT_BUTTON: action = forwards; break; + case 'h': case 'H' : action = hint; break; + case CURSOR_UP: case CURSOR_DOWN: + case CURSOR_LEFT: case CURSOR_RIGHT: + if (ui->cursor_show) { + int i; + for (i = 0; i < 4 && cursors[i] != button; ++i); + assert (i < 4); + if (!out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) { + ui->r += dr[i]; + ui->c += dc[i]; + } + } else ui->cursor_show = TRUE; + return ""; + } + + if (action == hint) { + move *end, *buf = snewn(state->params.w * state->params.h, + struct move); + char *ret = NULL; + end = solve_internal(state, buf, DIFF_RECURSION); + if (end != NULL && end > buf) { + ret = nfmtstr(40, "%c,%d,%d", + buf->colour == M_BLACK ? 'B' : 'W', + buf->square.r, buf->square.c); + ui->cheated = TRUE; /* you are being naughty ;-) */ + } + sfree(buf); + return ret; + } + + cell = state->grid[idx(r, c, state->params.w)]; + if (cell > 0) return NULL; + + if (action == forwards) switch (cell) { + case EMPTY: return nfmtstr(40, "W,%d,%d", r, c); + case WHITE: return nfmtstr(40, "B,%d,%d", r, c); + case BLACK: return nfmtstr(40, "E,%d,%d", r, c); + } + + else if (action == backwards) switch (cell) { + case BLACK: return nfmtstr(40, "W,%d,%d", r, c); + case WHITE: return nfmtstr(40, "E,%d,%d", r, c); + case EMPTY: return nfmtstr(40, "B,%d,%d", r, c); + } + + return NULL; +} + +static int find_errors(game_state *state, int *report) +{ + int const w = state->params.w, h = state->params.h, n = w * h; + + int r, c, i; + + int nblack = 0, any_white_cell = -1; + game_state *dup = dup_game(state); + + for (i = r = 0; r < h; ++r) + for (c = 0; c < w; ++c, ++i) { + switch (state->grid[i]) { + + case BLACK: + { + int j; + ++nblack; + for (j = 0; j < 4; ++j) { + int const rr = r + dr[j], cc = c + dc[j]; + if (out_of_bounds(rr, cc, w, h)) continue; + if (state->grid[idx(rr, cc, w)] != BLACK) continue; + if (!report) goto found_error; + report[i] = TRUE; + break; + } + } + break; + default: + { + int j, runs; + for (runs = 1, j = 0; j < 4; ++j) { + int const rr = r + dr[j], cc = c + dc[j]; + runs += runlength(rr, cc, dr[j], dc[j], state, + ~MASK(BLACK)); + } + if (!report) { + if (runs != state->grid[i]) goto found_error; + } else if (runs < state->grid[i]) report[i] = TRUE; + else { + for (runs = 1, j = 0; j < 4; ++j) { + int const rr = r + dr[j], cc = c + dc[j]; + runs += runlength(rr, cc, dr[j], dc[j], state, + ~(MASK(BLACK) | MASK(EMPTY))); + } + if (runs > state->grid[i]) report[i] = TRUE; + } + } + + /* note: fallthrough _into_ these cases */ + case EMPTY: + case WHITE: any_white_cell = i; + } + } + + for (i = 0; i < n; ++i) if (dup->grid[i] != BLACK) dup->grid[i] = WHITE; + if (nblack + dfs_count_white(dup, any_white_cell) < n) { + if (!report) { + printf("dfs fail at %d\n", any_white_cell); + goto found_error; + } + for (i = 0; i < n; ++i) if (state->grid[i] != BLACK) report[i] = TRUE; + } + + free_game(dup); + return FALSE; /* if report != NULL, this is ignored */ + +found_error: + free_game(dup); + return TRUE; +} + +static game_state *execute_move(game_state *state, char *move) +{ + signed int r, c, value, nchars, ntok; + signed char what_to_do; + game_state *ret; + + assert (move); + + ret = dup_game(state); + + if (*move == 'S') { + ++move; + ret->has_cheated = ret->was_solved = TRUE; + } + + for (; *move; move += nchars) { + ntok = sscanf(move, "%c,%d,%d%n", &what_to_do, &r, &c, &nchars); + if (ntok < 3) goto failure; + switch (what_to_do) { + case 'W': value = WHITE; break; + case 'E': value = EMPTY; break; + case 'B': value = BLACK; break; + default: goto failure; + } + if (out_of_bounds(r, c, ret->params.w, ret->params.h)) goto failure; + ret->grid[idx(r, c, ret->params.w)] = value; + } + + if (ret->was_solved == FALSE) + ret->was_solved = !find_errors(ret, NULL); + + return ret; + +failure: + free_game(ret); + return NULL; +} + +static void game_changed_state(game_ui *ui, game_state *oldstate, + game_state *newstate) +{ + if (newstate->has_cheated) ui->cheated = TRUE; +} + +static float game_anim_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + return 0.0F; +} + +#define FLASH_TIME 0.7F + +static float game_flash_length(game_state *from, game_state *to, + int dir, game_ui *ui) +{ + if (!from->was_solved && to->was_solved && !ui->cheated) + return FLASH_TIME; + return 0.0F; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +#define PREFERRED_TILE_SIZE 32 + +enum { + COL_BACKGROUND = 0, + COL_GRID, + COL_BLACK = COL_GRID, + COL_TEXT = COL_GRID, + COL_USER = COL_GRID, + COL_ERROR, + COL_LOWLIGHT, + COL_HIGHLIGHT = COL_ERROR, /* mkhighlight needs it, I don't */ + COL_CURSOR = COL_LOWLIGHT, + NCOLOURS +}; + +static void game_compute_size(game_params *params, int tilesize, + int *x, int *y) +{ + *x = (1 + params->w) * tilesize; + *y = (1 + params->h) * tilesize; +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +#define COLOUR(ret, i, r, g, b) \ + ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b))) + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); + COLOUR(ret, COL_GRID, 0.0F, 0.0F, 0.0F); + COLOUR(ret, COL_ERROR, 1.0F, 0.0F, 0.0F); + + *ncolours = NCOLOURS; + return ret; +} + +static drawcell makecell(puzzle_size value, int error, int cursor, int flash) +{ + drawcell ret; + setmember(ret, value); + setmember(ret, error); + setmember(ret, cursor); + setmember(ret, flash); + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +{ + int const w = state->params.w, h = state->params.h, n = w * h; + struct game_drawstate *ds = snew(struct game_drawstate); + int i; + + ds->tilesize = 0; + ds->started = FALSE; + + ds->grid = snewn(n, drawcell); + for (i = 0; i < n; ++i) + ds->grid[i] = makecell(w + h, FALSE, FALSE, FALSE); + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->grid); + sfree(ds); +} + +#define cmpmember(a, b, field) ((a) . field == (b) . field) + +static int cell_eq(drawcell a, drawcell b) +{ + return + cmpmember(a, b, value) && + cmpmember(a, b, error) && + cmpmember(a, b, cursor) && + cmpmember(a, b, flash); +} + +static void draw_cell(drawing *dr, game_drawstate *ds, int r, int c, + drawcell cell); + +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, + game_state *state, int dir, game_ui *ui, + float animtime, float flashtime) +{ + int const w = state->params.w, h = state->params.h, n = w * h; + int const wpx = (w+1) * ds->tilesize, hpx = (h+1) * ds->tilesize; + int const flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2; + + int r, c, i; + + int *errors = snewn(n, int); + memset(errors, FALSE, n * sizeof (int)); + find_errors(state, errors); + + assert (oldstate == NULL); /* only happens if animating moves */ + + if (!ds->started) { + ds->started = TRUE; + draw_rect(dr, 0, 0, wpx, hpx, COL_BACKGROUND); + draw_rect(dr, BORDER-1, BORDER-1, + ds->tilesize*w+2, ds->tilesize*h+2, COL_GRID); + draw_update(dr, 0, 0, wpx, hpx); + } + + for (i = r = 0; r < h; ++r) { + for (c = 0; c < w; ++c, ++i) { + drawcell cell = makecell(state->grid[i], errors[i], FALSE, flash); + if (r == ui->r && c == ui->c && ui->cursor_show) + cell.cursor = TRUE; + if (!cell_eq(cell, ds->grid[i])) { + draw_cell(dr, ds, r, c, cell); + ds->grid[i] = cell; + } + } + } + + sfree(errors); +} + +static void draw_cell(drawing *draw, game_drawstate *ds, int r, int c, + drawcell cell) +{ + int const ts = ds->tilesize; + int const y = BORDER + ts * r, x = BORDER + ts * c; + int const tx = x + (ts / 2), ty = y + (ts / 2); + int const dotsz = (ds->tilesize + 9) / 10; + + int const colour = (cell.value == BLACK ? + cell.error ? COL_ERROR : COL_BLACK : + cell.flash || cell.cursor ? + COL_LOWLIGHT : COL_BACKGROUND); + + draw_rect (draw, x, y, ts, ts, colour); + draw_rect_outline(draw, x, y, ts, ts, COL_GRID); + + switch (cell.value) { + case WHITE: draw_rect(draw, tx - dotsz / 2, ty - dotsz / 2, dotsz, dotsz, + cell.error ? COL_ERROR : COL_USER); + case BLACK: break; + case EMPTY: + if (cell.error) + draw_circle(draw, tx, ty, dotsz / 2, COL_ERROR, COL_GRID); + break; + default: + { + int const colour = (cell.error ? COL_ERROR : COL_GRID); + char *msg = nfmtstr(10, "%d", cell.value); + draw_text(draw, tx, ty, FONT_VARIABLE, ts * 3 / 5, + ALIGN_VCENTRE | ALIGN_HCENTRE, colour, msg); + sfree(msg); + } + } + + draw_update(draw, x, y, ts, ts); +} + +static int game_timing_state(game_state *state, game_ui *ui) +{ + puts("warning: game_timing_state was called (this shouldn't happen)"); + return FALSE; /* the (non-existing) timer should not be running */ +} + +/* ---------------------------------------------------------------------- + * User interface: print + */ + +static void game_print_size(game_params *params, float *x, float *y) +{ + int print_width, print_height; + game_compute_size(params, 800, &print_width, &print_height); + *x = print_width / 100.0F; + *y = print_height / 100.0F; +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ + int const w = state->params.w, h = state->params.h; + game_drawstate ds_obj, *ds = &ds_obj; + int r, c, i, colour; + + ds->tilesize = tilesize; + + colour = print_mono_colour(dr, 1); assert(colour == COL_BACKGROUND); + colour = print_mono_colour(dr, 0); assert(colour == COL_GRID); + colour = print_mono_colour(dr, 1); assert(colour == COL_ERROR); + colour = print_mono_colour(dr, 0); assert(colour == COL_LOWLIGHT); + colour = print_mono_colour(dr, 0); assert(colour == NCOLOURS); + + for (i = r = 0; r < h; ++r) + for (c = 0; c < w; ++c, ++i) + draw_cell(dr, ds, r, c, + makecell(state->grid[i], FALSE, FALSE, FALSE)); + + print_line_width(dr, 3 * tilesize / 40); + draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, h*TILESIZE, COL_GRID); +} + +/* And that's about it ;-) **************************************************/ + +#ifdef COMBINED +#define thegame range +#endif + +struct game const thegame = { + "Range", "games.range", "range", + default_params, + game_fetch_preset, + decode_params, + encode_params, + free_params, + dup_params, + TRUE, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + TRUE, solve_game, + TRUE, game_can_format_as_text_now, game_text_format, + new_ui, + free_ui, + encode_ui, + decode_ui, + game_changed_state, + interpret_move, + execute_move, + PREFERRED_TILE_SIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + TRUE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ + FALSE, game_timing_state, + 0, /* flags */ +}; -- 2.11.0