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:
20
* +--+--+--+--+--+--+--+
22
* +--+--+--+--+--+--+--+
24
* +--+--+--+--+--+--+--+
26
* +--+--+--+--+--+--+--+
28
* +--+--+--+--+--+--+--+
30
* +--+--+--+--+--+--+--+
32
* +--+--+--+--+--+--+--+
34
* +--+--+--+--+--+--+--+
36
* 7x7:d7b3e8e5c7a7c13e4d8b4d
50
#define setmember(obj, field) ( (obj) . field = field )
52
char *nfmtstr(int n, char *fmt, ...) {
54
char *ret = snewn(n+1, char);
56
vsprintf(ret, fmt, va);
61
#define SWAP(type, lvar1, lvar2) do { \
67
/* ----------------------------------------------------------------------
68
* Game parameters, presets, states
71
typedef signed char puzzle_size;
79
struct game_params params;
80
unsigned int has_cheated: 1;
81
unsigned int was_solved: 1;
85
#define DEFAULT_PRESET 0
86
static struct game_params presets[] = {{9, 6}, {12, 8}, {13, 9}, {16, 11}};
87
/* rationale: I want all four combinations of {odd/even, odd/even}, as
88
* they play out differently with respect to two-way symmetry. I also
89
* want them to be generated relatively fast yet still be large enough
90
* to be entertaining for a decent amount of time, and I want them to
91
* make good use of monitor real estate (the typical screen resolution
92
* is why I do 13x9 and not 9x13).
95
static game_params *default_params(void)
97
game_params *ret = snew(game_params);
98
*ret = presets[DEFAULT_PRESET]; /* structure copy */
102
static game_params *dup_params(game_params *params)
104
game_params *ret = snew(game_params);
105
*ret = *params; /* structure copy */
109
static int game_fetch_preset(int i, char **name, game_params **params)
111
if (i < 0 || i >= lenof(presets)) return FALSE;
113
*name = nfmtstr(40, "%d x %d", presets[i].w, presets[i].h);
114
*params = dup_params(&presets[i]);
119
static void free_params(game_params *params)
124
static void decode_params(game_params *params, char const *string)
126
/* FIXME check for puzzle_size overflow and decoding issues */
127
params->w = params->h = atoi(string);
128
while (*string && isdigit((unsigned char) *string)) ++string;
129
if (*string == 'x') {
131
params->h = atoi(string);
132
while (*string && isdigit((unsigned char)*string)) string++;
136
static char *encode_params(game_params *params, int full)
139
sprintf(str, "%dx%d", params->w, params->h);
143
static config_item *game_configure(game_params *params)
147
ret = snewn(3, config_item);
149
ret[0].name = "Width";
150
ret[0].type = C_STRING;
151
ret[0].sval = nfmtstr(10, "%d", params->w);
154
ret[1].name = "Height";
155
ret[1].type = C_STRING;
156
ret[1].sval = nfmtstr(10, "%d", params->h);
167
static game_params *custom_params(config_item *configuration)
169
game_params *ret = snew(game_params);
170
ret->w = atoi(configuration[0].sval);
171
ret->h = atoi(configuration[1].sval);
175
#define memdup(dst, src, n, type) do { \
176
dst = snewn(n, type); \
177
memcpy(dst, src, n * sizeof (type)); \
180
static game_state *dup_game(game_state *state)
182
game_state *ret = snew(game_state);
183
int const n = state->params.w * state->params.h;
185
*ret = *state; /* structure copy */
187
/* copy the poin_tee_, set a new value of the poin_ter_ */
188
memdup(ret->grid, state->grid, n, puzzle_size);
193
static void free_game(game_state *state)
200
/* ----------------------------------------------------------------------
201
* The solver subsystem.
203
* The solver is used for two purposes:
204
* - To solve puzzles when the user selects `Solve'.
205
* - To test solubility of a grid as clues are being removed from it
206
* during the puzzle generation.
208
* It supports the following ways of reasoning:
210
* - A cell adjacent to a black cell must be white.
212
* - If painting a square black would bisect the white regions, that
213
* square is white (by finding biconnected components' cut points)
215
* - A cell with number n, covering at most k white squares in three
216
* directions must white-cover n-k squares in the last direction.
218
* - A cell with number n known to cover k squares, if extending the
219
* cover by one square in a given direction causes the cell to
220
* cover _more_ than n squares, that extension cell must be black.
222
* (either if the square already covers n, or if it extends into a
223
* chunk of size > n - k)
225
* - Recursion. Pick any cell and see if this leads to either a
226
* contradiction or a solution (and then act appropriately).
231
* (propagation upper limit)
232
* - If one has two numbers on the same line, the smaller limits the
233
* larger. Example: in |b|_|_|8|4|_|_|b|, only two _'s can be both
234
* white and connected to the "8" cell; so that cell will propagate
235
* at least four cells orthogonally to the displayed line (which is
236
* better than the current "at least 2").
238
* (propagation upper limit)
239
* - cells can't propagate into other cells if doing so exceeds that
240
* number. Example: in |b|4|.|.|2|b|, at most one _ can be white;
241
* otherwise, the |2| would have too many reaching white cells.
243
* (propagation lower and upper limit)
244
* - `Full Combo': in each four directions d_1 ... d_4, find a set of
245
* possible propagation distances S_1 ... S_4. For each i=1..4,
246
* for each x in S_i: if not exists (y, z, w) in the other sets
247
* such that (x+y+z+w+1 == clue value): then remove x from S_i.
248
* Repeat until this stabilizes. If any cell would contradict
251
#define idx(i, j, w) ((i)*(w) + (j))
252
#define out_of_bounds(r, c, w, h) \
253
((r) < 0 || (r) >= h || (c) < 0 || (c) >= w)
255
typedef struct square {
259
enum {BLACK = -2, WHITE, EMPTY};
260
/* white is for pencil marks, empty is undecided */
262
static int const dr[4] = {+1, 0, -1, 0};
263
static int const dc[4] = { 0, +1, 0, -1};
264
static int const cursors[4] = /* must match dr and dc */
265
{CURSOR_DOWN, CURSOR_RIGHT, CURSOR_UP, CURSOR_LEFT};
267
typedef struct move {
269
unsigned int colour: 1;
271
enum {M_BLACK = 0, M_WHITE = 1};
273
typedef move *(reasoning)(game_state *state,
278
static reasoning solver_reasoning_not_too_big;
279
static reasoning solver_reasoning_adjacency;
280
static reasoning solver_reasoning_connectedness;
281
static reasoning solver_reasoning_recursion;
290
static move *solve_internal(game_state *state, move *base, int diff);
292
static char *solve_game(game_state *orig, game_state *curpos,
293
char *aux, char **error)
295
int const n = orig->params.w * orig->params.h;
296
move *const base = snewn(n, move);
297
move *moves = solve_internal(orig, base, DIFF_RECURSION);
302
int const k = moves - base;
303
char *str = ret = snewn(15*k + 2, char);
304
char colour[2] = "BW";
308
for (it = base; it < moves; ++it)
309
str += sprintf(str, "%c,%d,%d", colour[it->colour],
310
it->square.r, it->square.c);
311
} else *error = "This puzzle instance contains a contradiction";
317
static square *find_clues(game_state *state, int *ret_nclues);
318
static move *do_solve(game_state *state,
324
/* new_game_desc entry point in the solver subsystem */
325
static move *solve_internal(game_state *state, move *base, int diff)
328
square *const clues = find_clues(state, &nclues);
329
game_state *dup = dup_game(state);
330
move *const moves = do_solve(dup, nclues, clues, base, diff);
336
static move *do_solve(game_state *state,
342
reasoning *reasonings[] = {
343
solver_reasoning_not_too_big,
344
solver_reasoning_adjacency,
345
solver_reasoning_connectedness,
346
solver_reasoning_recursion
349
struct move *buf = move_buffer, *oldbuf;
354
for (i = 0; i < lenof(reasonings) && i <= difficulty; ++i) {
355
/* only recurse if all else fails */
356
if (i == DIFF_RECURSION && buf > oldbuf) continue;
357
buf = (*reasonings[i])(state, nclues, clues, buf);
358
if (buf == NULL) return NULL;
360
} while (buf > oldbuf);
365
#define MASK(n) (1 << ((n) + 2))
367
static int runlength(puzzle_size r, puzzle_size c,
368
puzzle_size dr, puzzle_size dc,
369
game_state *state, int colourmask)
371
int const w = state->params.w, h = state->params.h;
374
int cell = idx(r, c, w);
375
if (out_of_bounds(r, c, w, h)) break;
376
if (state->grid[cell] > 0) {
377
if (!(colourmask & ~(MASK(BLACK) | MASK(WHITE) | MASK(EMPTY))))
379
} else if (!(MASK(state->grid[cell]) & colourmask)) break;
387
static void solver_makemove(puzzle_size r, puzzle_size c, int colour,
388
game_state *state, move **buffer_ptr)
390
int const cell = idx(r, c, state->params.w);
391
if (out_of_bounds(r, c, state->params.w, state->params.h)) return;
392
if (state->grid[cell] != EMPTY) return;
393
setmember((*buffer_ptr)->square, r);
394
setmember((*buffer_ptr)->square, c);
395
setmember(**buffer_ptr, colour);
397
state->grid[cell] = (colour == M_BLACK ? BLACK : WHITE);
400
static move *solver_reasoning_adjacency(game_state *state,
406
for (r = 0; r < state->params.h; ++r)
407
for (c = 0; c < state->params.w; ++c) {
408
int const cell = idx(r, c, state->params.w);
409
if (state->grid[cell] != BLACK) continue;
410
for (i = 0; i < 4; ++i)
411
solver_makemove(r + dr[i], c + dc[i], M_WHITE, state, &buf);
416
enum {NOT_VISITED = -1};
418
static int dfs_biconnect_visit(puzzle_size r, puzzle_size c,
420
square *dfs_parent, int *dfs_depth,
423
static move *solver_reasoning_connectedness(game_state *state,
428
int const w = state->params.w, h = state->params.h, n = w * h;
430
square *const dfs_parent = snewn(n, square);
431
int *const dfs_depth = snewn(n, int);
434
for (i = 0; i < n; ++i) {
435
dfs_parent[i].r = NOT_VISITED;
439
for (i = 0; i < n && state->grid[i] == BLACK; ++i);
441
dfs_parent[i].r = i / w;
442
dfs_parent[i].c = i % w; /* `dfs root`.parent == `dfs root` */
445
dfs_biconnect_visit(i / w, i % w, state, dfs_parent, dfs_depth, &buf);
453
/* returns the `lowpoint` of (r, c) */
454
static int dfs_biconnect_visit(puzzle_size r, puzzle_size c,
456
square *dfs_parent, int *dfs_depth,
459
const puzzle_size w = state->params.w, h = state->params.h;
460
int const i = idx(r, c, w), mydepth = dfs_depth[i];
461
int lowpoint = mydepth, j, nchildren = 0;
463
for (j = 0; j < 4; ++j) {
464
const puzzle_size rr = r + dr[j], cc = c + dc[j];
465
int const cell = idx(rr, cc, w);
467
if (out_of_bounds(rr, cc, w, h)) continue;
468
if (state->grid[cell] == BLACK) continue;
470
if (dfs_parent[cell].r == NOT_VISITED) {
472
dfs_parent[cell].r = r;
473
dfs_parent[cell].c = c;
474
dfs_depth[cell] = mydepth + 1;
475
child_lowpoint = dfs_biconnect_visit(rr, cc, state, dfs_parent,
478
if (child_lowpoint >= mydepth && mydepth > 0)
479
solver_makemove(r, c, M_WHITE, state, buf);
481
lowpoint = min(lowpoint, child_lowpoint);
483
} else if (rr != dfs_parent[i].r || cc != dfs_parent[i].c) {
484
lowpoint = min(lowpoint, dfs_depth[cell]);
488
if (mydepth == 0 && nchildren >= 2)
489
solver_makemove(r, c, M_WHITE, state, buf);
494
static move *solver_reasoning_not_too_big(game_state *state,
499
int const w = state->params.w, runmasks[4] = {
500
~(MASK(BLACK) | MASK(EMPTY)),
502
~(MASK(BLACK) | MASK(EMPTY)),
505
enum {RUN_WHITE, RUN_EMPTY, RUN_BEYOND, RUN_SPACE};
507
int i, runlengths[4][4];
509
for (i = 0; i < nclues; ++i) {
510
int j, k, whites, space;
512
const puzzle_size row = clues[i].r, col = clues[i].c;
513
int const clue = state->grid[idx(row, col, w)];
515
for (j = 0; j < 4; ++j) {
516
puzzle_size r = row + dr[j], c = col + dc[j];
517
runlengths[RUN_SPACE][j] = 0;
518
for (k = 0; k <= RUN_SPACE; ++k) {
519
int l = runlength(r, c, dr[j], dc[j], state, runmasks[k]);
521
runlengths[k][j] = l;
525
runlengths[RUN_SPACE][j] += l;
530
for (j = 0; j < 4; ++j) whites += runlengths[RUN_WHITE][j];
532
for (j = 0; j < 4; ++j) {
533
int const delta = 1 + runlengths[RUN_WHITE][j];
534
const puzzle_size r = row + delta * dr[j];
535
const puzzle_size c = col + delta * dc[j];
537
if (whites == clue) {
538
solver_makemove(r, c, M_BLACK, state, &buf);
542
if (runlengths[RUN_EMPTY][j] == 1 &&
544
+ runlengths[RUN_EMPTY][j]
545
+ runlengths[RUN_BEYOND][j]
547
solver_makemove(r, c, M_BLACK, state, &buf);
552
+ runlengths[RUN_EMPTY][j]
553
+ runlengths[RUN_BEYOND][j]
555
runlengths[RUN_SPACE][j] =
556
runlengths[RUN_WHITE][j] +
557
runlengths[RUN_EMPTY][j] - 1;
559
if (runlengths[RUN_EMPTY][j] == 1)
560
solver_makemove(r, c, M_BLACK, state, &buf);
565
for (j = 0; j < 4; ++j) space += runlengths[RUN_SPACE][j];
566
for (j = 0; j < 4; ++j) {
567
puzzle_size r = row + dr[j], c = col + dc[j];
569
int k = space - runlengths[RUN_SPACE][j];
570
if (k >= clue) continue;
572
for (; k < clue; ++k, r += dr[j], c += dc[j])
573
solver_makemove(r, c, M_WHITE, state, &buf);
579
static move *solver_reasoning_recursion(game_state *state,
584
int const w = state->params.w, n = w * state->params.h;
587
for (cell = 0; cell < n; ++cell) {
588
int const r = cell / w, c = cell % w;
590
game_state *newstate;
591
move *recursive_result;
593
if (state->grid[cell] != EMPTY) continue;
595
/* FIXME: add enum alias for smallest and largest (or N) */
596
for (colour = M_BLACK; colour <= M_WHITE; ++colour) {
597
newstate = dup_game(state);
598
newstate->grid[cell] = colour;
599
recursive_result = do_solve(newstate, nclues, clues, buf,
602
if (recursive_result == NULL) {
603
solver_makemove(r, c, M_BLACK + M_WHITE - colour, state, &buf);
606
for (i = 0; i < n && newstate->grid[i] != EMPTY; ++i);
607
if (i == n) return buf;
613
static square *find_clues(game_state *state, int *ret_nclues)
615
int r, c, i, nclues = 0;
616
square *ret = snewn(state->params.w * state->params.h, struct square);
618
for (i = r = 0; r < state->params.h; ++r)
619
for (c = 0; c < state->params.w; ++c, ++i)
620
if (state->grid[i] > 0) {
626
*ret_nclues = nclues;
627
return sresize(ret, nclues + (nclues == 0), square);
630
/* ----------------------------------------------------------------------
633
* Generating kurodoko instances is rather straightforward:
635
* - Start with a white grid and add black squares at randomly chosen
636
* locations, unless colouring that square black would violate
637
* either the adjacency or connectedness constraints.
639
* - For each white square, compute the number it would contain if it
640
* were given as a clue.
642
* - From a starting point of "give _every_ white square as a clue",
643
* for each white square (in a random order), see if the board is
644
* solvable when that square is not given as a clue. If not, don't
645
* give it as a clue, otherwise do.
647
* This never fails, but it's only _almost_ what I do. The real final
650
* - From a starting point of "give _every_ white square as a clue",
651
* first remove all clues that are two-way rotationally symmetric
652
* to a black square. If this leaves the puzzle unsolvable, throw
653
* it out and try again. Otherwise, remove all _pairs_ of clues
654
* (that are rotationally symmetric) which can be removed without
655
* rendering the puzzle unsolvable.
657
* This can fail even if one only removes the black and symmetric
658
* clues; indeed it happens often (avg. once or twice per puzzle) when
659
* generating 1xN instances. (If you add black cells they must be in
660
* the end, and if you only add one, it's ambiguous where).
663
/* forward declarations of internal calls */
664
static void newdesc_choose_black_squares(game_state *state,
665
const int *shuffle_1toN);
666
static void newdesc_compute_clues(game_state *state);
667
static int newdesc_strip_clues(game_state *state, int *shuffle_1toN);
668
static char *newdesc_encode_game_description(int n, puzzle_size *grid);
670
static char *new_game_desc(game_params *params, random_state *rs,
671
char **aux, int interactive)
673
int const w = params->w, h = params->h, n = w * h;
675
puzzle_size *const grid = snewn(n, puzzle_size);
676
int *const shuffle_1toN = snewn(n, int);
678
int i, clues_removed;
683
state.params = *params;
686
interactive = 0; /* I don't need it, I shouldn't use it*/
688
for (i = 0; i < n; ++i) shuffle_1toN[i] = i;
691
shuffle(shuffle_1toN, n, sizeof (int), rs);
692
newdesc_choose_black_squares(&state, shuffle_1toN);
694
newdesc_compute_clues(&state);
696
shuffle(shuffle_1toN, n, sizeof (int), rs);
697
clues_removed = newdesc_strip_clues(&state, shuffle_1toN);
699
if (clues_removed < 0) continue; else break;
702
encoding = newdesc_encode_game_description(n, grid);
710
static int dfs_count_white(game_state *state, int cell);
712
static void newdesc_choose_black_squares(game_state *state,
713
const int *shuffle_1toN)
715
int const w = state->params.w, h = state->params.h, n = w * h;
717
int k, any_white_cell, n_black_cells;
719
for (k = 0; k < n; ++k) state->grid[k] = WHITE;
721
any_white_cell = shuffle_1toN[n - 1];
724
/* I like the puzzles that result from n / 3, but maybe this
725
* could be made a (generation, i.e. non-full) parameter? */
726
for (k = 0; k < n / 3; ++k) {
727
int const i = shuffle_1toN[k], c = i % w, r = i / w;
730
for (j = 0; j < 4; ++j) {
731
int const rr = r + dr[j], cc = c + dc[j], cell = idx(rr, cc, w);
732
/* if you're out of bounds, we skip you */
733
if (out_of_bounds(rr, cc, w, h)) continue;
734
if (state->grid[cell] == BLACK) break; /* I can't be black */
735
} if (j < 4) continue; /* I have black neighbour: I'm white */
737
state->grid[i] = BLACK;
740
j = dfs_count_white(state, any_white_cell);
741
if (j + n_black_cells < n) {
742
state->grid[i] = WHITE;
748
static void newdesc_compute_clues(game_state *state)
750
int const w = state->params.w, h = state->params.h;
753
for (r = 0; r < h; ++r) {
754
int run_size = 0, c, cc;
755
for (c = 0; c <= w; ++c) {
756
if (c == w || state->grid[idx(r, c, w)] == BLACK) {
757
for (cc = c - run_size; cc < c; ++cc)
758
state->grid[idx(r, cc, w)] += run_size;
764
for (c = 0; c < w; ++c) {
765
int run_size = 0, r, rr;
766
for (r = 0; r <= h; ++r) {
767
if (r == h || state->grid[idx(r, c, w)] == BLACK) {
768
for (rr = r - run_size; rr < r; ++rr)
769
state->grid[idx(rr, c, w)] += run_size;
776
#define rotate(x) (n - 1 - (x))
778
static int newdesc_strip_clues(game_state *state, int *shuffle_1toN)
780
int const w = state->params.w, n = w * state->params.h;
782
move *const move_buffer = snewn(n, move);
784
game_state *dupstate;
787
* do a partition/pivot of shuffle_1toN into three groups:
788
* (1) squares rotationally-symmetric to (3)
789
* (2) squares not in (1) or (3)
792
* They go from [0, left), [left, right) and [right, n) in
793
* shuffle_1toN (and from there into state->grid[ ])
795
* Then, remove clues from the grid one by one in shuffle_1toN
796
* order, until the solver becomes unhappy. If we didn't remove
797
* all of (1), return (-1). Else, we're happy.
800
/* do the partition */
801
int clues_removed, k = 0, left = 0, right = n;
804
while (k < right && state->grid[shuffle_1toN[k]] == BLACK) {
806
SWAP(int, shuffle_1toN[right], shuffle_1toN[k]);
807
assert(state->grid[shuffle_1toN[right]] == BLACK);
809
if (k >= right) break;
811
if (state->grid[rotate(shuffle_1toN[k])] == BLACK) {
812
SWAP(int, shuffle_1toN[k], shuffle_1toN[left]);
815
assert (state->grid[rotate(shuffle_1toN[k])] != BLACK
819
for (k = 0; k < left; ++k) {
820
assert (state->grid[rotate(shuffle_1toN[k])] == BLACK);
821
state->grid[shuffle_1toN[k]] = EMPTY;
823
for (k = left; k < right; ++k) {
824
assert (state->grid[rotate(shuffle_1toN[k])] != BLACK);
825
assert (state->grid[shuffle_1toN[k]] != BLACK);
827
for (k = right; k < n; ++k) {
828
assert (state->grid[shuffle_1toN[k]] == BLACK);
829
state->grid[shuffle_1toN[k]] = EMPTY;
832
clues_removed = (left - 0) + (n - right);
834
dupstate = dup_game(state);
835
buf = solve_internal(dupstate, move_buffer, DIFF_RECURSION - 1);
837
if (buf - move_buffer < clues_removed) {
838
/* branch prediction: I don't think I'll go here */
843
for (k = left; k < right; ++k) {
844
const int i = shuffle_1toN[k], j = rotate(i);
845
int const clue = state->grid[i], clue_rot = state->grid[j];
846
if (clue == BLACK) continue;
847
state->grid[i] = state->grid[j] = EMPTY;
848
dupstate = dup_game(state);
849
buf = solve_internal(dupstate, move_buffer, DIFF_RECURSION - 1);
851
clues_removed += 2 - (i == j);
852
/* if i is the center square, then i == (j = rotate(i))
853
* when i and j are one, removing i and j removes only one */
854
if (buf - move_buffer == clues_removed) continue;
855
/* if the solver is sound, refilling all removed clues means
856
* we have filled all squares, i.e. solved the puzzle. */
857
state->grid[i] = clue;
858
state->grid[j] = clue_rot;
859
clues_removed -= 2 - (i == j);
864
return clues_removed;
867
static int dfs_count_rec(puzzle_size *grid, int r, int c, int w, int h)
869
int const cell = idx(r, c, w);
870
if (out_of_bounds(r, c, w, h)) return 0;
871
if (grid[cell] != WHITE) return 0;
874
dfs_count_rec(grid, r + 0, c + 1, w, h) +
875
dfs_count_rec(grid, r + 0, c - 1, w, h) +
876
dfs_count_rec(grid, r + 1, c + 0, w, h) +
877
dfs_count_rec(grid, r - 1, c + 0, w, h);
880
static int dfs_count_white(game_state *state, int cell)
882
int const w = state->params.w, h = state->params.h, n = w * h;
883
int const r = cell / w, c = cell % w;
884
int i, k = dfs_count_rec(state->grid, r, c, w, h);
885
for (i = 0; i < n; ++i)
886
if (state->grid[i] == EMPTY)
887
state->grid[i] = WHITE;
891
static char *validate_params(game_params *params, int full)
893
int const w = params->w, h = params->h;
894
if (w < 1) return "Error: width is less than 1";
895
if (h < 1) return "Error: height is less than 1";
896
if (w * h < 1) return "Error: size is less than 1";
897
if (w + h - 1 > SCHAR_MAX) return "Error: w + h is too big";
898
/* I might be unable to store clues in my puzzle_size *grid; */
900
if (w == 2 && h == 2) return "Error: can't create 2x2 puzzles";
901
if (w == 1 && h == 2) return "Error: can't create 1x2 puzzles";
902
if (w == 2 && h == 1) return "Error: can't create 2x1 puzzles";
903
if (w == 1 && h == 1) return "Error: can't create 1x1 puzzles";
908
/* Definition: a puzzle instance is _good_ if:
909
* - it has a unique solution
910
* - the solver can find this solution without using recursion
911
* - the solution contains at least one black square
912
* - the clues are 2-way rotationally symmetric
914
* (the idea being: the generator can not output any _bad_ puzzles)
916
* Theorem: validate_params, when full != 0, discards exactly the set
917
* of parameters for which there are _no_ good puzzle instances.
919
* Proof: it's an immediate consequence of the five lemmas below.
921
* Observation: not only do puzzles on non-tiny grids exist, the
922
* generator is pretty fast about coming up with them. On my pre-2004
923
* desktop box, it generates 100 puzzles on the highest preset (16x11)
924
* in 8.383 seconds, or <= 0.1 second per puzzle.
926
* ----------------------------------------------------------------------
928
* Lemma: On a 1x1 grid, there are no good puzzles.
930
* Proof: the one square can't be a clue because at least one square
931
* is black. But both a white square and a black square satisfy the
932
* solution criteria, so the puzzle is ambiguous (and hence bad).
934
* Lemma: On a 1x2 grid, there are no good puzzles.
936
* Proof: let's name the squares l and r. Note that there can be at
937
* most one black square, or adjacency is violated. By assumption at
938
* least one square is black, so let's call that one l. By clue
939
* symmetry, neither l nor r can be given as a clue, so the puzzle
940
* instance is blank and thus ambiguous.
942
* Corollary: On a 2x1 grid, there are no good puzzles.
943
* Proof: rotate the above proof 90 degrees ;-)
945
* ----------------------------------------------------------------------
947
* Lemma: On a 2x2 grid, there are no soluble puzzles with 2-way
948
* rotational symmetric clues and at least one black square.
950
* Proof: Let's name the squares a, b, c, and d, with a and b on the
951
* top row, a and c in the left column. Let's consider the case where
952
* a is black. Then no other square can be black: b and c would both
953
* violate the adjacency constraint; d would disconnect b from c.
955
* So exactly one square is black (and by 4-way rotation symmetry of
956
* the 2x2 square, it doesn't matter which one, so let's stick to a).
957
* By 2-way rotational symmetry of the clues and the rule about not
958
* painting numbers black, neither a nor d can be clues. A blank
959
* puzzle would be ambiguous, so one of {b, c} is a clue; by symmetry,
960
* so is the other one.
962
* It is readily seen that their clue value is 2. But "a is black"
963
* and "d is black" are both valid solutions in this case, so the
964
* puzzle is ambiguous (and hence bad).
966
* ----------------------------------------------------------------------
968
* Lemma: On a wxh grid with w, h >= 1 and (w > 2 or h > 2), there is
969
* at least one good puzzle.
971
* Proof: assume that w > h (otherwise rotate the proof again). Paint
972
* the top left and bottom right corners black, and fill a clue into
973
* all the other squares. Present this board to the solver code (or
974
* player, hypothetically), except with the two black squares as blank
977
* For an Nx1 puzzle, observe that every clue is N - 2, and there are
978
* N - 2 of them in one connected sequence, so the remaining two
979
* squares can be deduced to be black, which solves the puzzle.
981
* For any other puzzle, let j be a cell in the same row as a black
982
* cell, but not in the same column (such a cell doesn't exist in 2x3
983
* puzzles, but we assume w > h and such cells exist in 3x2 puzzles).
985
* Note that the number of cells in axis parallel `rays' going out
986
* from j exceeds j's clue value by one. Only one such cell is a
987
* non-clue, so it must be black. Similarly for the other corner (let
988
* j' be a cell in the same row as the _other_ black cell, but not in
989
* the same column as _any_ black cell; repeat this argument at j').
991
* This fills the grid and satisfies all clues and the adjacency
992
* constraint and doesn't paint on top of any clues. All that is left
993
* to see is connectedness.
995
* Observe that the white cells in each column form a single connected
996
* `run', and each column contains a white cell adjacent to a white
997
* cell in the column to the right, if that column exists.
999
* Thus, any cell in the left-most column can reach any other cell:
1000
* first go to the target column (by repeatedly going to the cell in
1001
* your current column that lets you go right, then going right), then
1002
* go up or down to the desired cell.
1004
* As reachability is symmetric (in undirected graphs) and transitive,
1005
* any cell can reach any left-column cell, and from there any other
1009
/* ----------------------------------------------------------------------
1010
* Game encoding and decoding
1013
#define NDIGITS_BASE '!'
1015
static char *newdesc_encode_game_description(int area, puzzle_size *grid)
1018
int desclen = 0, descsize = 0;
1022
for (i = 0; i <= area; i++) {
1023
int n = (i < area ? grid[i] : -1);
1028
if (descsize < desclen + 40) {
1029
descsize = desclen * 3 / 2 + 40;
1030
desc = sresize(desc, descsize, char);
1034
int c = 'a' - 1 + run;
1037
desc[desclen++] = c;
1038
run -= c - ('a' - 1);
1042
* If there's a number in the very top left or
1043
* bottom right, there's no point putting an
1044
* unnecessary _ before or after it.
1046
if (desclen > 0 && n > 0)
1047
desc[desclen++] = '_';
1050
desclen += sprintf(desc+desclen, "%d", n);
1054
desc[desclen] = '\0';
1058
static char *validate_desc(game_params *params, char *desc)
1060
int const n = params->w * params->h;
1062
int range = params->w + params->h - 1; /* maximum cell value */
1064
while (*desc && *desc != ',') {
1066
if (c >= 'a' && c <= 'z') {
1067
squares += c - 'a' + 1;
1068
} else if (c == '_') {
1070
} else if (c > '0' && c <= '9') {
1071
int val = atoi(desc-1);
1072
if (val < 1 || val > range)
1073
return "Out-of-range number in game description";
1075
while (*desc >= '0' && *desc <= '9')
1078
return "Invalid character in game description";
1082
return "Not enough data to fill grid";
1085
return "Too much data to fit in grid";
1090
static game_state *new_game(midend *me, game_params *params, char *desc)
1095
int const n = params->w * params->h;
1096
game_state *state = snew(game_state);
1098
me = NULL; /* I don't need it, I shouldn't use it */
1100
state->params = *params; /* structure copy */
1101
state->grid = snewn(n, puzzle_size);
1105
while (i < n && *p) {
1107
if (c >= 'a' && c <= 'z') {
1108
int squares = c - 'a' + 1;
1110
state->grid[i++] = 0;
1111
} else if (c == '_') {
1113
} else if (c > '0' && c <= '9') {
1114
int val = atoi(p-1);
1115
assert(val >= 1 && val <= params->w+params->h-1);
1116
state->grid[i++] = val;
1117
while (*p >= '0' && *p <= '9')
1122
state->has_cheated = FALSE;
1123
state->was_solved = FALSE;
1128
/* ----------------------------------------------------------------------
1129
* User interface: ascii
1132
static int game_can_format_as_text_now(game_params *params)
1137
static char *game_text_format(game_state *state)
1139
int cellsize, r, c, i, w_string, h_string, n_string;
1140
char *ret, *buf, *gridline;
1142
int const w = state->params.w, h = state->params.h;
1144
cellsize = 0; /* or may be used uninitialized */
1146
for (c = 0; c < w; ++c) {
1147
for (r = 1; r < h; ++r) {
1148
puzzle_size k = state->grid[idx(r, c, w)];
1150
for (d = 0; k; k /= 10, ++d);
1151
cellsize = max(cellsize, d);
1157
w_string = w * cellsize + 2; /* "|%d|%d|...|\n" */
1158
h_string = 2 * h + 1; /* "+--+--+...+\n%s\n+--+--+...+\n" */
1159
n_string = w_string * h_string;
1161
gridline = snewn(w_string + 1, char); /* +1: NUL terminator */
1162
memset(gridline, '-', w_string);
1163
for (c = 0; c <= w; ++c) gridline[c * cellsize] = '+';
1164
gridline[w_string - 1] = '\n';
1165
gridline[w_string - 0] = '\0';
1167
buf = ret = snewn(n_string + 1, char); /* +1: NUL terminator */
1168
for (i = r = 0; r < h; ++r) {
1169
memcpy(buf, gridline, w_string);
1171
for (c = 0; c < w; ++c, ++i) {
1173
switch (state->grid[i]) {
1174
case BLACK: ch = '#'; break;
1175
case WHITE: ch = '.'; break;
1176
case EMPTY: ch = ' '; break;
1178
buf += sprintf(buf, "|%*d", cellsize - 1, state->grid[i]);
1182
memset(buf, ch, cellsize - 1);
1183
buf += cellsize - 1;
1185
buf += sprintf(buf, "|\n");
1187
memcpy(buf, gridline, w_string);
1189
assert (buf - ret == n_string);
1197
/* ----------------------------------------------------------------------
1198
* User interfaces: interactive
1202
puzzle_size r, c; /* cursor position */
1203
unsigned int cursor_show: 1;
1204
unsigned int cheated: 1;
1207
static game_ui *new_ui(game_state *state)
1209
struct game_ui *ui = snew(game_ui);
1211
ui->cursor_show = ui->cheated = FALSE;
1215
static void free_ui(game_ui *ui)
1220
static char *encode_ui(game_ui *ui)
1222
return dupstr(ui->cheated ? "1" : "0");
1225
static void decode_ui(game_ui *ui, char *encoding)
1227
ui->cheated = (*encoding == '1');
1230
typedef struct drawcell {
1232
unsigned int error: 1;
1233
unsigned int cursor: 1;
1234
unsigned int flash: 1;
1237
struct game_drawstate {
1240
unsigned int started: 1;
1243
#define TILESIZE (ds->tilesize)
1244
#define BORDER (TILESIZE / 2)
1245
#define COORD(x) ((x) * TILESIZE + BORDER)
1246
#define FROMCOORD(x) (((x) - BORDER) / TILESIZE)
1248
static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1249
int x, int y, int button)
1251
enum {none, forwards, backwards, hint};
1252
int const w = state->params.w, h = state->params.h;
1253
int r = ui->r, c = ui->c, action = none, cell;
1255
if (IS_CURSOR_SELECT(button) && !ui->cursor_show) return NULL;
1257
if (IS_MOUSE_DOWN(button)) {
1258
r = FROMCOORD(y + TILESIZE) - 1; /* or (x, y) < TILESIZE) */
1259
c = FROMCOORD(x + TILESIZE) - 1; /* are considered inside */
1260
if (out_of_bounds(r, c, w, h)) return NULL;
1263
ui->cursor_show = FALSE;
1266
if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1268
* Utterly awful hack, exactly analogous to the one in Slant,
1269
* to configure the left and right mouse buttons the opposite
1272
* The original puzzle submitter thought it would be more
1273
* useful to have the left button turn an empty square into a
1274
* dotted one, on the grounds that that was what you did most
1275
* often; I (SGT) felt instinctively that the left button
1276
* ought to place black squares and the right button place
1277
* dots, on the grounds that that was consistent with many
1278
* other puzzles in which the left button fills in the data
1279
* used by the solution checker while the right button places
1280
* pencil marks for the user's convenience.
1282
* My first beta-player wasn't sure either, so I thought I'd
1283
* pre-emptively put in a 'configuration' mechanism just in
1287
static int swap_buttons = -1;
1288
if (swap_buttons < 0) {
1289
char *env = getenv("RANGE_SWAP_BUTTONS");
1290
swap_buttons = (env && (env[0] == 'y' || env[0] == 'Y'));
1293
if (button == LEFT_BUTTON)
1294
button = RIGHT_BUTTON;
1296
button = LEFT_BUTTON;
1302
case CURSOR_SELECT : case LEFT_BUTTON: action = backwards; break;
1303
case CURSOR_SELECT2: case RIGHT_BUTTON: action = forwards; break;
1304
case 'h': case 'H' : action = hint; break;
1305
case CURSOR_UP: case CURSOR_DOWN:
1306
case CURSOR_LEFT: case CURSOR_RIGHT:
1307
if (ui->cursor_show) {
1309
for (i = 0; i < 4 && cursors[i] != button; ++i);
1311
if (!out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
1315
} else ui->cursor_show = TRUE;
1319
if (action == hint) {
1320
move *end, *buf = snewn(state->params.w * state->params.h,
1323
end = solve_internal(state, buf, DIFF_RECURSION);
1324
if (end != NULL && end > buf) {
1325
ret = nfmtstr(40, "%c,%d,%d",
1326
buf->colour == M_BLACK ? 'B' : 'W',
1327
buf->square.r, buf->square.c);
1328
ui->cheated = TRUE; /* you are being naughty ;-) */
1334
cell = state->grid[idx(r, c, state->params.w)];
1335
if (cell > 0) return NULL;
1337
if (action == forwards) switch (cell) {
1338
case EMPTY: return nfmtstr(40, "W,%d,%d", r, c);
1339
case WHITE: return nfmtstr(40, "B,%d,%d", r, c);
1340
case BLACK: return nfmtstr(40, "E,%d,%d", r, c);
1343
else if (action == backwards) switch (cell) {
1344
case BLACK: return nfmtstr(40, "W,%d,%d", r, c);
1345
case WHITE: return nfmtstr(40, "E,%d,%d", r, c);
1346
case EMPTY: return nfmtstr(40, "B,%d,%d", r, c);
1352
static int find_errors(game_state *state, int *report)
1354
int const w = state->params.w, h = state->params.h, n = w * h;
1358
int nblack = 0, any_white_cell = -1;
1359
game_state *dup = dup_game(state);
1361
for (i = r = 0; r < h; ++r)
1362
for (c = 0; c < w; ++c, ++i) {
1363
switch (state->grid[i]) {
1369
for (j = 0; j < 4; ++j) {
1370
int const rr = r + dr[j], cc = c + dc[j];
1371
if (out_of_bounds(rr, cc, w, h)) continue;
1372
if (state->grid[idx(rr, cc, w)] != BLACK) continue;
1373
if (!report) goto found_error;
1382
for (runs = 1, j = 0; j < 4; ++j) {
1383
int const rr = r + dr[j], cc = c + dc[j];
1384
runs += runlength(rr, cc, dr[j], dc[j], state,
1388
if (runs != state->grid[i]) goto found_error;
1389
} else if (runs < state->grid[i]) report[i] = TRUE;
1391
for (runs = 1, j = 0; j < 4; ++j) {
1392
int const rr = r + dr[j], cc = c + dc[j];
1393
runs += runlength(rr, cc, dr[j], dc[j], state,
1394
~(MASK(BLACK) | MASK(EMPTY)));
1396
if (runs > state->grid[i]) report[i] = TRUE;
1400
/* note: fallthrough _into_ these cases */
1402
case WHITE: any_white_cell = i;
1406
for (i = 0; i < n; ++i) if (dup->grid[i] != BLACK) dup->grid[i] = WHITE;
1407
if (nblack + dfs_count_white(dup, any_white_cell) < n) {
1409
printf("dfs fail at %d\n", any_white_cell);
1412
for (i = 0; i < n; ++i) if (state->grid[i] != BLACK) report[i] = TRUE;
1416
return FALSE; /* if report != NULL, this is ignored */
1423
static game_state *execute_move(game_state *state, char *move)
1425
signed int r, c, value, nchars, ntok;
1426
signed char what_to_do;
1431
ret = dup_game(state);
1435
ret->has_cheated = ret->was_solved = TRUE;
1438
for (; *move; move += nchars) {
1439
ntok = sscanf(move, "%c,%d,%d%n", &what_to_do, &r, &c, &nchars);
1440
if (ntok < 3) goto failure;
1441
switch (what_to_do) {
1442
case 'W': value = WHITE; break;
1443
case 'E': value = EMPTY; break;
1444
case 'B': value = BLACK; break;
1445
default: goto failure;
1447
if (out_of_bounds(r, c, ret->params.w, ret->params.h)) goto failure;
1448
ret->grid[idx(r, c, ret->params.w)] = value;
1451
if (ret->was_solved == FALSE)
1452
ret->was_solved = !find_errors(ret, NULL);
1461
static void game_changed_state(game_ui *ui, game_state *oldstate,
1462
game_state *newstate)
1464
if (newstate->has_cheated) ui->cheated = TRUE;
1467
static float game_anim_length(game_state *oldstate, game_state *newstate,
1468
int dir, game_ui *ui)
1473
#define FLASH_TIME 0.7F
1475
static float game_flash_length(game_state *from, game_state *to,
1476
int dir, game_ui *ui)
1478
if (!from->was_solved && to->was_solved && !ui->cheated)
1483
/* ----------------------------------------------------------------------
1487
#define PREFERRED_TILE_SIZE 32
1492
COL_BLACK = COL_GRID,
1493
COL_TEXT = COL_GRID,
1494
COL_USER = COL_GRID,
1497
COL_HIGHLIGHT = COL_ERROR, /* mkhighlight needs it, I don't */
1498
COL_CURSOR = COL_LOWLIGHT,
1502
static void game_compute_size(game_params *params, int tilesize,
1505
*x = (1 + params->w) * tilesize;
1506
*y = (1 + params->h) * tilesize;
1509
static void game_set_size(drawing *dr, game_drawstate *ds,
1510
game_params *params, int tilesize)
1512
ds->tilesize = tilesize;
1515
#define COLOUR(ret, i, r, g, b) \
1516
((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1518
static float *game_colours(frontend *fe, int *ncolours)
1520
float *ret = snewn(3 * NCOLOURS, float);
1522
game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1523
COLOUR(ret, COL_GRID, 0.0F, 0.0F, 0.0F);
1524
COLOUR(ret, COL_ERROR, 1.0F, 0.0F, 0.0F);
1526
*ncolours = NCOLOURS;
1530
static drawcell makecell(puzzle_size value, int error, int cursor, int flash)
1533
setmember(ret, value);
1534
setmember(ret, error);
1535
setmember(ret, cursor);
1536
setmember(ret, flash);
1540
static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1542
int const w = state->params.w, h = state->params.h, n = w * h;
1543
struct game_drawstate *ds = snew(struct game_drawstate);
1547
ds->started = FALSE;
1549
ds->grid = snewn(n, drawcell);
1550
for (i = 0; i < n; ++i)
1551
ds->grid[i] = makecell(w + h, FALSE, FALSE, FALSE);
1556
static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1562
#define cmpmember(a, b, field) ((a) . field == (b) . field)
1564
static int cell_eq(drawcell a, drawcell b)
1567
cmpmember(a, b, value) &&
1568
cmpmember(a, b, error) &&
1569
cmpmember(a, b, cursor) &&
1570
cmpmember(a, b, flash);
1573
static void draw_cell(drawing *dr, game_drawstate *ds, int r, int c,
1576
static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1577
game_state *state, int dir, game_ui *ui,
1578
float animtime, float flashtime)
1580
int const w = state->params.w, h = state->params.h, n = w * h;
1581
int const wpx = (w+1) * ds->tilesize, hpx = (h+1) * ds->tilesize;
1582
int const flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2;
1586
int *errors = snewn(n, int);
1587
memset(errors, FALSE, n * sizeof (int));
1588
find_errors(state, errors);
1590
assert (oldstate == NULL); /* only happens if animating moves */
1594
draw_rect(dr, 0, 0, wpx, hpx, COL_BACKGROUND);
1595
draw_rect(dr, BORDER-1, BORDER-1,
1596
ds->tilesize*w+2, ds->tilesize*h+2, COL_GRID);
1597
draw_update(dr, 0, 0, wpx, hpx);
1600
for (i = r = 0; r < h; ++r) {
1601
for (c = 0; c < w; ++c, ++i) {
1602
drawcell cell = makecell(state->grid[i], errors[i], FALSE, flash);
1603
if (r == ui->r && c == ui->c && ui->cursor_show)
1605
if (!cell_eq(cell, ds->grid[i])) {
1606
draw_cell(dr, ds, r, c, cell);
1615
static void draw_cell(drawing *draw, game_drawstate *ds, int r, int c,
1618
int const ts = ds->tilesize;
1619
int const y = BORDER + ts * r, x = BORDER + ts * c;
1620
int const tx = x + (ts / 2), ty = y + (ts / 2);
1621
int const dotsz = (ds->tilesize + 9) / 10;
1623
int const colour = (cell.value == BLACK ?
1624
cell.error ? COL_ERROR : COL_BLACK :
1625
cell.flash || cell.cursor ?
1626
COL_LOWLIGHT : COL_BACKGROUND);
1628
draw_rect (draw, x, y, ts, ts, colour);
1629
draw_rect_outline(draw, x, y, ts, ts, COL_GRID);
1631
switch (cell.value) {
1632
case WHITE: draw_rect(draw, tx - dotsz / 2, ty - dotsz / 2, dotsz, dotsz,
1633
cell.error ? COL_ERROR : COL_USER);
1637
draw_circle(draw, tx, ty, dotsz / 2, COL_ERROR, COL_GRID);
1641
int const colour = (cell.error ? COL_ERROR : COL_GRID);
1642
char *msg = nfmtstr(10, "%d", cell.value);
1643
draw_text(draw, tx, ty, FONT_VARIABLE, ts * 3 / 5,
1644
ALIGN_VCENTRE | ALIGN_HCENTRE, colour, msg);
1649
draw_update(draw, x, y, ts, ts);
1652
static int game_timing_state(game_state *state, game_ui *ui)
1654
puts("warning: game_timing_state was called (this shouldn't happen)");
1655
return FALSE; /* the (non-existing) timer should not be running */
1658
/* ----------------------------------------------------------------------
1659
* User interface: print
1662
static void game_print_size(game_params *params, float *x, float *y)
1664
int print_width, print_height;
1665
game_compute_size(params, 800, &print_width, &print_height);
1666
*x = print_width / 100.0F;
1667
*y = print_height / 100.0F;
1670
static void game_print(drawing *dr, game_state *state, int tilesize)
1672
int const w = state->params.w, h = state->params.h;
1673
game_drawstate ds_obj, *ds = &ds_obj;
1674
int r, c, i, colour;
1676
ds->tilesize = tilesize;
1678
colour = print_mono_colour(dr, 1); assert(colour == COL_BACKGROUND);
1679
colour = print_mono_colour(dr, 0); assert(colour == COL_GRID);
1680
colour = print_mono_colour(dr, 1); assert(colour == COL_ERROR);
1681
colour = print_mono_colour(dr, 0); assert(colour == COL_LOWLIGHT);
1682
colour = print_mono_colour(dr, 0); assert(colour == NCOLOURS);
1684
for (i = r = 0; r < h; ++r)
1685
for (c = 0; c < w; ++c, ++i)
1686
draw_cell(dr, ds, r, c,
1687
makecell(state->grid[i], FALSE, FALSE, FALSE));
1689
print_line_width(dr, 3 * tilesize / 40);
1690
draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, h*TILESIZE, COL_GRID);
1693
/* And that's about it ;-) **************************************************/
1696
#define thegame range
1699
struct game const thegame = {
1700
"Range", "games.range", "range",
1707
TRUE, game_configure, custom_params,
1715
TRUE, game_can_format_as_text_now, game_text_format,
1723
PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1726
game_free_drawstate,
1730
TRUE, FALSE, game_print_size, game_print,
1731
FALSE, /* wants_statusbar */
1732
FALSE, game_timing_state,
added
removed
range.c
