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