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 static int game_is_solved(game_state
*state
)
1485 return state
->was_solved
;
1488 /* ----------------------------------------------------------------------
1492 #define PREFERRED_TILE_SIZE 32
1497 COL_BLACK
= COL_GRID
,
1498 COL_TEXT
= COL_GRID
,
1499 COL_USER
= COL_GRID
,
1502 COL_HIGHLIGHT
= COL_ERROR
, /* mkhighlight needs it, I don't */
1503 COL_CURSOR
= COL_LOWLIGHT
,
1507 static void game_compute_size(game_params
*params
, int tilesize
,
1510 *x
= (1 + params
->w
) * tilesize
;
1511 *y
= (1 + params
->h
) * tilesize
;
1514 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1515 game_params
*params
, int tilesize
)
1517 ds
->tilesize
= tilesize
;
1520 #define COLOUR(ret, i, r, g, b) \
1521 ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1523 static float *game_colours(frontend
*fe
, int *ncolours
)
1525 float *ret
= snewn(3 * NCOLOURS
, float);
1527 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
1528 COLOUR(ret
, COL_GRID
, 0.0F
, 0.0F
, 0.0F
);
1529 COLOUR(ret
, COL_ERROR
, 1.0F
, 0.0F
, 0.0F
);
1531 *ncolours
= NCOLOURS
;
1535 static drawcell
makecell(puzzle_size value
, int error
, int cursor
, int flash
)
1538 setmember(ret
, value
);
1539 setmember(ret
, error
);
1540 setmember(ret
, cursor
);
1541 setmember(ret
, flash
);
1545 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1547 int const w
= state
->params
.w
, h
= state
->params
.h
, n
= w
* h
;
1548 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1552 ds
->started
= FALSE
;
1554 ds
->grid
= snewn(n
, drawcell
);
1555 for (i
= 0; i
< n
; ++i
)
1556 ds
->grid
[i
] = makecell(w
+ h
, FALSE
, FALSE
, FALSE
);
1561 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1567 #define cmpmember(a, b, field) ((a) . field == (b) . field)
1569 static int cell_eq(drawcell a
, drawcell b
)
1572 cmpmember(a
, b
, value
) &&
1573 cmpmember(a
, b
, error
) &&
1574 cmpmember(a
, b
, cursor
) &&
1575 cmpmember(a
, b
, flash
);
1578 static void draw_cell(drawing
*dr
, game_drawstate
*ds
, int r
, int c
,
1581 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1582 game_state
*state
, int dir
, game_ui
*ui
,
1583 float animtime
, float flashtime
)
1585 int const w
= state
->params
.w
, h
= state
->params
.h
, n
= w
* h
;
1586 int const wpx
= (w
+1) * ds
->tilesize
, hpx
= (h
+1) * ds
->tilesize
;
1587 int const flash
= ((int) (flashtime
* 5 / FLASH_TIME
)) % 2;
1591 int *errors
= snewn(n
, int);
1592 memset(errors
, FALSE
, n
* sizeof (int));
1593 find_errors(state
, errors
);
1595 assert (oldstate
== NULL
); /* only happens if animating moves */
1599 draw_rect(dr
, 0, 0, wpx
, hpx
, COL_BACKGROUND
);
1600 draw_rect(dr
, BORDER
-1, BORDER
-1,
1601 ds
->tilesize
*w
+2, ds
->tilesize
*h
+2, COL_GRID
);
1602 draw_update(dr
, 0, 0, wpx
, hpx
);
1605 for (i
= r
= 0; r
< h
; ++r
) {
1606 for (c
= 0; c
< w
; ++c
, ++i
) {
1607 drawcell cell
= makecell(state
->grid
[i
], errors
[i
], FALSE
, flash
);
1608 if (r
== ui
->r
&& c
== ui
->c
&& ui
->cursor_show
)
1610 if (!cell_eq(cell
, ds
->grid
[i
])) {
1611 draw_cell(dr
, ds
, r
, c
, cell
);
1620 static void draw_cell(drawing
*draw
, game_drawstate
*ds
, int r
, int c
,
1623 int const ts
= ds
->tilesize
;
1624 int const y
= BORDER
+ ts
* r
, x
= BORDER
+ ts
* c
;
1625 int const tx
= x
+ (ts
/ 2), ty
= y
+ (ts
/ 2);
1626 int const dotsz
= (ds
->tilesize
+ 9) / 10;
1628 int const colour
= (cell
.value
== BLACK ?
1629 cell
.error ? COL_ERROR
: COL_BLACK
:
1630 cell
.flash
|| cell
.cursor ?
1631 COL_LOWLIGHT
: COL_BACKGROUND
);
1633 draw_rect (draw
, x
, y
, ts
, ts
, colour
);
1634 draw_rect_outline(draw
, x
, y
, ts
, ts
, COL_GRID
);
1636 switch (cell
.value
) {
1637 case WHITE
: draw_rect(draw
, tx
- dotsz
/ 2, ty
- dotsz
/ 2, dotsz
, dotsz
,
1638 cell
.error ? COL_ERROR
: COL_USER
);
1642 draw_circle(draw
, tx
, ty
, dotsz
/ 2, COL_ERROR
, COL_GRID
);
1646 int const colour
= (cell
.error ? COL_ERROR
: COL_GRID
);
1647 char *msg
= nfmtstr(10, "%d", cell
.value
);
1648 draw_text(draw
, tx
, ty
, FONT_VARIABLE
, ts
* 3 / 5,
1649 ALIGN_VCENTRE
| ALIGN_HCENTRE
, colour
, msg
);
1654 draw_update(draw
, x
, y
, ts
, ts
);
1657 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1659 puts("warning: game_timing_state was called (this shouldn't happen)");
1660 return FALSE
; /* the (non-existing) timer should not be running */
1663 /* ----------------------------------------------------------------------
1664 * User interface: print
1667 static void game_print_size(game_params
*params
, float *x
, float *y
)
1669 int print_width
, print_height
;
1670 game_compute_size(params
, 800, &print_width
, &print_height
);
1671 *x
= print_width
/ 100.0F
;
1672 *y
= print_height
/ 100.0F
;
1675 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1677 int const w
= state
->params
.w
, h
= state
->params
.h
;
1678 game_drawstate ds_obj
, *ds
= &ds_obj
;
1679 int r
, c
, i
, colour
;
1681 ds
->tilesize
= tilesize
;
1683 colour
= print_mono_colour(dr
, 1); assert(colour
== COL_BACKGROUND
);
1684 colour
= print_mono_colour(dr
, 0); assert(colour
== COL_GRID
);
1685 colour
= print_mono_colour(dr
, 1); assert(colour
== COL_ERROR
);
1686 colour
= print_mono_colour(dr
, 0); assert(colour
== COL_LOWLIGHT
);
1687 colour
= print_mono_colour(dr
, 0); assert(colour
== NCOLOURS
);
1689 for (i
= r
= 0; r
< h
; ++r
)
1690 for (c
= 0; c
< w
; ++c
, ++i
)
1691 draw_cell(dr
, ds
, r
, c
,
1692 makecell(state
->grid
[i
], FALSE
, FALSE
, FALSE
));
1694 print_line_width(dr
, 3 * tilesize
/ 40);
1695 draw_rect_outline(dr
, BORDER
, BORDER
, w
*TILESIZE
, h
*TILESIZE
, COL_GRID
);
1698 /* And that's about it ;-) **************************************************/
1701 #define thegame range
1704 struct game
const thegame
= {
1705 "Range", "games.range", "range",
1712 TRUE
, game_configure
, custom_params
,
1720 TRUE
, game_can_format_as_text_now
, game_text_format
,
1728 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1731 game_free_drawstate
,
1736 TRUE
, FALSE
, game_print_size
, game_print
,
1737 FALSE
, /* wants_statusbar */
1738 FALSE
, game_timing_state
,