6193da8d |
1 | /* |
2 | * loopy.c: An implementation of the Nikoli game 'Loop the loop'. |
121aae4b |
3 | * (c) Mike Pinna, 2005, 2006 |
6193da8d |
4 | * |
5 | * vim: set shiftwidth=4 :set textwidth=80: |
6 | */ |
7 | |
8 | /* |
9 | * TODO: |
10 | * |
121aae4b |
11 | * - Setting very high recursion depth seems to cause memory munching: are we |
12 | * recursing before checking completion, by any chance? |
6193da8d |
13 | * |
121aae4b |
14 | * - There's an interesting deductive technique which makes use of topology |
15 | * rather than just graph theory. Each _square_ in the grid is either inside |
16 | * or outside the loop; you can tell that two squares are on the same side |
17 | * of the loop if they're separated by an x (or, more generally, by a path |
18 | * crossing no LINE_UNKNOWNs and an even number of LINE_YESes), and on the |
19 | * opposite side of the loop if they're separated by a line (or an odd |
20 | * number of LINE_YESes and no LINE_UNKNOWNs). Oh, and any square separated |
21 | * from the outside of the grid by a LINE_YES or a LINE_NO is on the inside |
22 | * or outside respectively. So if you can track this for all squares, you |
23 | * figure out the state of the line between a pair once their relative |
24 | * insideness is known. |
25 | * |
26 | * - (Just a speed optimisation.) Consider some todo list queue where every |
27 | * time we modify something we mark it for consideration by other bits of |
28 | * the solver, to save iteration over things that have already been done. |
6193da8d |
29 | */ |
30 | |
31 | #include <stdio.h> |
32 | #include <stdlib.h> |
33 | #include <string.h> |
34 | #include <assert.h> |
35 | #include <ctype.h> |
36 | #include <math.h> |
37 | |
38 | #include "puzzles.h" |
39 | #include "tree234.h" |
40 | |
121aae4b |
41 | /* Debugging options */ |
42 | /*#define DEBUG_CACHES*/ |
43 | /*#define SHOW_WORKING*/ |
44 | |
45 | /* ---------------------------------------------------------------------- |
46 | * Struct, enum and function declarations |
47 | */ |
48 | |
49 | enum { |
50 | COL_BACKGROUND, |
51 | COL_FOREGROUND, |
52 | COL_HIGHLIGHT, |
53 | COL_MISTAKE, |
54 | NCOLOURS |
55 | }; |
56 | |
57 | struct game_state { |
58 | int w, h; |
59 | |
60 | /* Put -1 in a square that doesn't get a clue */ |
61 | char *clues; |
62 | |
63 | /* Arrays of line states, stored left-to-right, top-to-bottom */ |
64 | char *hl, *vl; |
65 | |
66 | int solved; |
67 | int cheated; |
68 | |
69 | int recursion_depth; |
70 | }; |
71 | |
72 | enum solver_status { |
73 | SOLVER_SOLVED, /* This is the only solution the solver could find */ |
74 | SOLVER_MISTAKE, /* This is definitely not a solution */ |
75 | SOLVER_AMBIGUOUS, /* This _might_ be an ambiguous solution */ |
76 | SOLVER_INCOMPLETE /* This may be a partial solution */ |
77 | }; |
78 | |
79 | typedef struct normal { |
80 | char *dot_atleastone; |
81 | char *dot_atmostone; |
82 | } normal_mode_state; |
83 | |
84 | typedef struct hard { |
85 | int *linedsf; |
86 | } hard_mode_state; |
87 | |
88 | typedef struct solver_state { |
89 | game_state *state; |
90 | int recursion_remaining; |
91 | enum solver_status solver_status; |
92 | /* NB looplen is the number of dots that are joined together at a point, ie a |
93 | * looplen of 1 means there are no lines to a particular dot */ |
94 | int *looplen; |
95 | |
96 | /* caches */ |
97 | char *dot_yescount; |
98 | char *dot_nocount; |
99 | char *square_yescount; |
100 | char *square_nocount; |
101 | char *dot_solved, *square_solved; |
102 | int *dotdsf; |
103 | |
104 | normal_mode_state *normal; |
105 | hard_mode_state *hard; |
106 | } solver_state; |
107 | |
108 | /* |
109 | * Difficulty levels. I do some macro ickery here to ensure that my |
110 | * enum and the various forms of my name list always match up. |
111 | */ |
112 | |
113 | #define DIFFLIST(A) \ |
114 | A(EASY,Easy,e,easy_mode_deductions) \ |
115 | A(NORMAL,Normal,n,normal_mode_deductions) \ |
116 | A(HARD,Hard,h,hard_mode_deductions) |
117 | #define ENUM(upper,title,lower,fn) DIFF_ ## upper, |
118 | #define TITLE(upper,title,lower,fn) #title, |
119 | #define ENCODE(upper,title,lower,fn) #lower |
120 | #define CONFIG(upper,title,lower,fn) ":" #title |
121 | #define SOLVER_FN_DECL(upper,title,lower,fn) static int fn(solver_state *); |
122 | #define SOLVER_FN(upper,title,lower,fn) &fn, |
1a739e2f |
123 | enum { DIFFLIST(ENUM) DIFF_MAX }; |
121aae4b |
124 | static char const *const diffnames[] = { DIFFLIST(TITLE) }; |
125 | static char const diffchars[] = DIFFLIST(ENCODE); |
126 | #define DIFFCONFIG DIFFLIST(CONFIG) |
127 | DIFFLIST(SOLVER_FN_DECL); |
128 | static int (*(solver_fns[]))(solver_state *) = { DIFFLIST(SOLVER_FN) }; |
129 | |
130 | struct game_params { |
131 | int w, h; |
1a739e2f |
132 | int diff; |
121aae4b |
133 | int rec; |
134 | }; |
135 | |
136 | enum line_state { LINE_YES, LINE_UNKNOWN, LINE_NO }; |
137 | |
138 | #define OPP(state) \ |
139 | (2 - state) |
140 | |
141 | enum direction { UP, LEFT, RIGHT, DOWN }; |
142 | |
143 | #define OPP_DIR(dir) \ |
144 | (3 - dir) |
145 | |
146 | struct game_drawstate { |
147 | int started; |
148 | int tilesize, linewidth; |
149 | int flashing; |
150 | char *hl, *vl; |
151 | char *clue_error; |
152 | }; |
153 | |
154 | static char *game_text_format(game_state *state); |
155 | static char *state_to_text(const game_state *state); |
156 | static char *validate_desc(game_params *params, char *desc); |
157 | static int get_line_status_from_point(const game_state *state, |
158 | int x, int y, enum direction d); |
159 | static int dot_order(const game_state* state, int i, int j, char line_type); |
160 | static int square_order(const game_state* state, int i, int j, char line_type); |
161 | static solver_state *solve_game_rec(const solver_state *sstate, |
1a739e2f |
162 | int diff); |
121aae4b |
163 | |
164 | #ifdef DEBUG_CACHES |
165 | static void check_caches(const solver_state* sstate); |
166 | #else |
167 | #define check_caches(s) |
168 | #endif |
169 | |
170 | /* ---------------------------------------------------------------------- |
171 | * Preprocessor magic |
172 | */ |
173 | |
174 | /* General constants */ |
6193da8d |
175 | #define PREFERRED_TILE_SIZE 32 |
176 | #define TILE_SIZE (ds->tilesize) |
94aa5b7b |
177 | #define LINEWIDTH (ds->linewidth) |
6193da8d |
178 | #define BORDER (TILE_SIZE / 2) |
c0eb17ce |
179 | #define FLASH_TIME 0.5F |
6193da8d |
180 | |
121aae4b |
181 | /* Counts of various things that we're interested in */ |
6193da8d |
182 | #define HL_COUNT(state) ((state)->w * ((state)->h + 1)) |
183 | #define VL_COUNT(state) (((state)->w + 1) * (state)->h) |
121aae4b |
184 | #define LINE_COUNT(state) (HL_COUNT(state) + VL_COUNT(state)) |
6193da8d |
185 | #define DOT_COUNT(state) (((state)->w + 1) * ((state)->h + 1)) |
186 | #define SQUARE_COUNT(state) ((state)->w * (state)->h) |
187 | |
121aae4b |
188 | /* For indexing into arrays */ |
189 | #define DOT_INDEX(state, x, y) ((x) + ((state)->w + 1) * (y)) |
190 | #define SQUARE_INDEX(state, x, y) ((x) + ((state)->w) * (y)) |
191 | #define HL_INDEX(state, x, y) SQUARE_INDEX(state, x, y) |
192 | #define VL_INDEX(state, x, y) DOT_INDEX(state, x, y) |
193 | |
194 | /* Useful utility functions */ |
195 | #define LEGAL_DOT(state, i, j) ((i) >= 0 && (j) >= 0 && \ |
196 | (i) <= (state)->w && (j) <= (state)->h) |
197 | #define LEGAL_SQUARE(state, i, j) ((i) >= 0 && (j) >= 0 && \ |
198 | (i) < (state)->w && (j) < (state)->h) |
199 | |
200 | #define CLUE_AT(state, i, j) (LEGAL_SQUARE(state, i, j) ? \ |
201 | LV_CLUE_AT(state, i, j) : -1) |
202 | |
203 | #define LV_CLUE_AT(state, i, j) ((state)->clues[SQUARE_INDEX(state, i, j)]) |
204 | |
205 | #define BIT_SET(field, bit) ((field) & (1<<(bit))) |
206 | |
207 | #define SET_BIT(field, bit) (BIT_SET(field, bit) ? FALSE : \ |
208 | ((field) |= (1<<(bit)), TRUE)) |
209 | |
210 | #define CLEAR_BIT(field, bit) (BIT_SET(field, bit) ? \ |
211 | ((field) &= ~(1<<(bit)), TRUE) : FALSE) |
212 | |
213 | #define DIR2STR(d) \ |
214 | ((d == UP) ? "up" : \ |
215 | (d == DOWN) ? "down" : \ |
216 | (d == LEFT) ? "left" : \ |
217 | (d == RIGHT) ? "right" : "oops") |
218 | |
219 | #define CLUE2CHAR(c) \ |
220 | ((c < 0) ? ' ' : c + '0') |
221 | |
222 | /* Lines that have particular relationships with given dots or squares */ |
6193da8d |
223 | #define ABOVE_SQUARE(state, i, j) ((state)->hl[(i) + (state)->w * (j)]) |
224 | #define BELOW_SQUARE(state, i, j) ABOVE_SQUARE(state, i, (j)+1) |
6193da8d |
225 | #define LEFTOF_SQUARE(state, i, j) ((state)->vl[(i) + ((state)->w + 1) * (j)]) |
226 | #define RIGHTOF_SQUARE(state, i, j) LEFTOF_SQUARE(state, (i)+1, j) |
227 | |
6193da8d |
228 | /* |
229 | * These macros return rvalues only, but can cope with being passed |
230 | * out-of-range coordinates. |
231 | */ |
121aae4b |
232 | /* XXX replace these with functions so we can create an array of function |
233 | * pointers for nicer iteration over them. This could probably be done with |
234 | * loads of other things for eliminating many nasty hacks. */ |
235 | #define ABOVE_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || j <= 0) ? \ |
6193da8d |
236 | LINE_NO : LV_ABOVE_DOT(state, i, j)) |
237 | #define BELOW_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || j >= (state)->h) ? \ |
238 | LINE_NO : LV_BELOW_DOT(state, i, j)) |
239 | |
240 | #define LEFTOF_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || i <= 0) ? \ |
241 | LINE_NO : LV_LEFTOF_DOT(state, i, j)) |
121aae4b |
242 | #define RIGHTOF_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || i >= (state)->w)? \ |
6193da8d |
243 | LINE_NO : LV_RIGHTOF_DOT(state, i, j)) |
244 | |
245 | /* |
246 | * These macros expect to be passed valid coordinates, and return |
247 | * lvalues. |
248 | */ |
121aae4b |
249 | #define LV_BELOW_DOT(state, i, j) ((state)->vl[VL_INDEX(state, i, j)]) |
6193da8d |
250 | #define LV_ABOVE_DOT(state, i, j) LV_BELOW_DOT(state, i, (j)-1) |
251 | |
121aae4b |
252 | #define LV_RIGHTOF_DOT(state, i, j) ((state)->hl[HL_INDEX(state, i, j)]) |
6193da8d |
253 | #define LV_LEFTOF_DOT(state, i, j) LV_RIGHTOF_DOT(state, (i)-1, j) |
254 | |
121aae4b |
255 | /* Counts of interesting things */ |
256 | #define DOT_YES_COUNT(sstate, i, j) \ |
257 | ((sstate)->dot_yescount[DOT_INDEX((sstate)->state, i, j)]) |
6c42c563 |
258 | |
121aae4b |
259 | #define DOT_NO_COUNT(sstate, i, j) \ |
260 | ((sstate)->dot_nocount[DOT_INDEX((sstate)->state, i, j)]) |
6193da8d |
261 | |
121aae4b |
262 | #define SQUARE_YES_COUNT(sstate, i, j) \ |
263 | ((sstate)->square_yescount[SQUARE_INDEX((sstate)->state, i, j)]) |
6193da8d |
264 | |
121aae4b |
265 | #define SQUARE_NO_COUNT(sstate, i, j) \ |
266 | ((sstate)->square_nocount[SQUARE_INDEX((sstate)->state, i, j)]) |
c0eb17ce |
267 | |
121aae4b |
268 | /* Iterators. NB these iterate over height more slowly than over width so that |
269 | * the elements come out in 'reading' order */ |
270 | /* XXX considering adding a 'current' element to each of these which gets the |
271 | * address of the current dot, say. But expecting we'd need more than that |
272 | * most of the time. */ |
273 | #define FORALL(i, j, w, h) \ |
274 | for ((j) = 0; (j) < (h); ++(j)) \ |
275 | for ((i) = 0; (i) < (w); ++(i)) |
6193da8d |
276 | |
121aae4b |
277 | #define FORALL_DOTS(state, i, j) \ |
278 | FORALL(i, j, (state)->w + 1, (state)->h + 1) |
6193da8d |
279 | |
121aae4b |
280 | #define FORALL_SQUARES(state, i, j) \ |
281 | FORALL(i, j, (state)->w, (state)->h) |
6193da8d |
282 | |
121aae4b |
283 | #define FORALL_HL(state, i, j) \ |
284 | FORALL(i, j, (state)->w, (state)->h+1) |
6193da8d |
285 | |
121aae4b |
286 | #define FORALL_VL(state, i, j) \ |
287 | FORALL(i, j, (state)->w+1, (state)->h) |
6193da8d |
288 | |
121aae4b |
289 | /* ---------------------------------------------------------------------- |
290 | * General struct manipulation and other straightforward code |
291 | */ |
6193da8d |
292 | |
293 | static game_state *dup_game(game_state *state) |
294 | { |
295 | game_state *ret = snew(game_state); |
296 | |
297 | ret->h = state->h; |
298 | ret->w = state->w; |
299 | ret->solved = state->solved; |
300 | ret->cheated = state->cheated; |
301 | |
121aae4b |
302 | ret->clues = snewn(SQUARE_COUNT(state), char); |
6193da8d |
303 | memcpy(ret->clues, state->clues, SQUARE_COUNT(state)); |
304 | |
121aae4b |
305 | ret->hl = snewn(HL_COUNT(state), char); |
6193da8d |
306 | memcpy(ret->hl, state->hl, HL_COUNT(state)); |
307 | |
121aae4b |
308 | ret->vl = snewn(VL_COUNT(state), char); |
6193da8d |
309 | memcpy(ret->vl, state->vl, VL_COUNT(state)); |
310 | |
311 | ret->recursion_depth = state->recursion_depth; |
312 | |
313 | return ret; |
314 | } |
315 | |
316 | static void free_game(game_state *state) |
317 | { |
318 | if (state) { |
319 | sfree(state->clues); |
320 | sfree(state->hl); |
321 | sfree(state->vl); |
322 | sfree(state); |
323 | } |
324 | } |
325 | |
1a739e2f |
326 | static solver_state *new_solver_state(const game_state *state, int diff) { |
121aae4b |
327 | int i, j; |
6193da8d |
328 | solver_state *ret = snew(solver_state); |
6193da8d |
329 | |
121aae4b |
330 | ret->state = dup_game((game_state *)state); |
6193da8d |
331 | |
6193da8d |
332 | ret->recursion_remaining = state->recursion_depth; |
6c42c563 |
333 | ret->solver_status = SOLVER_INCOMPLETE; |
6193da8d |
334 | |
121aae4b |
335 | ret->dotdsf = snew_dsf(DOT_COUNT(state)); |
6193da8d |
336 | ret->looplen = snewn(DOT_COUNT(state), int); |
121aae4b |
337 | |
6193da8d |
338 | for (i = 0; i < DOT_COUNT(state); i++) { |
121aae4b |
339 | ret->looplen[i] = 1; |
340 | } |
341 | |
342 | ret->dot_solved = snewn(DOT_COUNT(state), char); |
343 | ret->square_solved = snewn(SQUARE_COUNT(state), char); |
344 | memset(ret->dot_solved, FALSE, DOT_COUNT(state)); |
345 | memset(ret->square_solved, FALSE, SQUARE_COUNT(state)); |
346 | |
347 | ret->dot_yescount = snewn(DOT_COUNT(state), char); |
348 | memset(ret->dot_yescount, 0, DOT_COUNT(state)); |
349 | ret->dot_nocount = snewn(DOT_COUNT(state), char); |
350 | memset(ret->dot_nocount, 0, DOT_COUNT(state)); |
351 | ret->square_yescount = snewn(SQUARE_COUNT(state), char); |
352 | memset(ret->square_yescount, 0, SQUARE_COUNT(state)); |
353 | ret->square_nocount = snewn(SQUARE_COUNT(state), char); |
354 | memset(ret->square_nocount, 0, SQUARE_COUNT(state)); |
355 | |
356 | /* dot_nocount needs special initialisation as we define lines coming off |
357 | * dots on edges as fixed at NO */ |
358 | |
359 | FORALL_DOTS(state, i, j) { |
360 | if (i == 0 || i == state->w) |
361 | ++ret->dot_nocount[DOT_INDEX(state, i, j)]; |
362 | if (j == 0 || j == state->h) |
363 | ++ret->dot_nocount[DOT_INDEX(state, i, j)]; |
364 | } |
365 | |
366 | if (diff < DIFF_NORMAL) { |
367 | ret->normal = NULL; |
368 | } else { |
369 | ret->normal = snew(normal_mode_state); |
370 | |
371 | ret->normal->dot_atmostone = snewn(DOT_COUNT(state), char); |
372 | memset(ret->normal->dot_atmostone, 0, DOT_COUNT(state)); |
373 | ret->normal->dot_atleastone = snewn(DOT_COUNT(state), char); |
374 | memset(ret->normal->dot_atleastone, 0, DOT_COUNT(state)); |
375 | } |
376 | |
377 | if (diff < DIFF_HARD) { |
378 | ret->hard = NULL; |
379 | } else { |
380 | ret->hard = snew(hard_mode_state); |
381 | ret->hard->linedsf = snew_dsf(LINE_COUNT(state)); |
6193da8d |
382 | } |
383 | |
384 | return ret; |
385 | } |
386 | |
387 | static void free_solver_state(solver_state *sstate) { |
388 | if (sstate) { |
389 | free_game(sstate->state); |
9cfc03b7 |
390 | sfree(sstate->dotdsf); |
391 | sfree(sstate->looplen); |
121aae4b |
392 | sfree(sstate->dot_solved); |
393 | sfree(sstate->square_solved); |
394 | sfree(sstate->dot_yescount); |
395 | sfree(sstate->dot_nocount); |
396 | sfree(sstate->square_yescount); |
397 | sfree(sstate->square_nocount); |
398 | |
399 | if (sstate->normal) { |
400 | sfree(sstate->normal->dot_atleastone); |
401 | sfree(sstate->normal->dot_atmostone); |
402 | sfree(sstate->normal); |
403 | } |
404 | |
405 | if (sstate->hard) { |
406 | sfree(sstate->hard->linedsf); |
407 | sfree(sstate->hard); |
408 | } |
409 | |
9cfc03b7 |
410 | sfree(sstate); |
6193da8d |
411 | } |
412 | } |
413 | |
121aae4b |
414 | static solver_state *dup_solver_state(const solver_state *sstate) { |
9cfc03b7 |
415 | game_state *state; |
6193da8d |
416 | |
417 | solver_state *ret = snew(solver_state); |
418 | |
9cfc03b7 |
419 | ret->state = state = dup_game(sstate->state); |
6193da8d |
420 | |
6193da8d |
421 | ret->recursion_remaining = sstate->recursion_remaining; |
422 | ret->solver_status = sstate->solver_status; |
423 | |
424 | ret->dotdsf = snewn(DOT_COUNT(state), int); |
425 | ret->looplen = snewn(DOT_COUNT(state), int); |
121aae4b |
426 | memcpy(ret->dotdsf, sstate->dotdsf, |
427 | DOT_COUNT(state) * sizeof(int)); |
428 | memcpy(ret->looplen, sstate->looplen, |
429 | DOT_COUNT(state) * sizeof(int)); |
430 | |
431 | ret->dot_solved = snewn(DOT_COUNT(state), char); |
432 | ret->square_solved = snewn(SQUARE_COUNT(state), char); |
433 | memcpy(ret->dot_solved, sstate->dot_solved, |
434 | DOT_COUNT(state)); |
435 | memcpy(ret->square_solved, sstate->square_solved, |
436 | SQUARE_COUNT(state)); |
437 | |
438 | ret->dot_yescount = snewn(DOT_COUNT(state), char); |
439 | memcpy(ret->dot_yescount, sstate->dot_yescount, |
440 | DOT_COUNT(state)); |
441 | ret->dot_nocount = snewn(DOT_COUNT(state), char); |
442 | memcpy(ret->dot_nocount, sstate->dot_nocount, |
443 | DOT_COUNT(state)); |
444 | |
445 | ret->square_yescount = snewn(SQUARE_COUNT(state), char); |
446 | memcpy(ret->square_yescount, sstate->square_yescount, |
447 | SQUARE_COUNT(state)); |
448 | ret->square_nocount = snewn(SQUARE_COUNT(state), char); |
449 | memcpy(ret->square_nocount, sstate->square_nocount, |
450 | SQUARE_COUNT(state)); |
451 | |
452 | if (sstate->normal) { |
453 | ret->normal = snew(normal_mode_state); |
454 | ret->normal->dot_atmostone = snewn(DOT_COUNT(state), char); |
455 | memcpy(ret->normal->dot_atmostone, sstate->normal->dot_atmostone, |
456 | DOT_COUNT(state)); |
457 | |
458 | ret->normal->dot_atleastone = snewn(DOT_COUNT(state), char); |
459 | memcpy(ret->normal->dot_atleastone, sstate->normal->dot_atleastone, |
460 | DOT_COUNT(state)); |
461 | } else { |
462 | ret->normal = NULL; |
463 | } |
464 | |
465 | if (sstate->hard) { |
466 | ret->hard = snew(hard_mode_state); |
467 | ret->hard->linedsf = snewn(LINE_COUNT(state), int); |
468 | memcpy(ret->hard->linedsf, sstate->hard->linedsf, |
469 | LINE_COUNT(state) * sizeof(int)); |
470 | } else { |
471 | ret->hard = NULL; |
472 | } |
6193da8d |
473 | |
474 | return ret; |
475 | } |
476 | |
121aae4b |
477 | static game_params *default_params(void) |
6193da8d |
478 | { |
121aae4b |
479 | game_params *ret = snew(game_params); |
6193da8d |
480 | |
121aae4b |
481 | #ifdef SLOW_SYSTEM |
482 | ret->h = 4; |
483 | ret->w = 4; |
484 | #else |
485 | ret->h = 10; |
486 | ret->w = 10; |
487 | #endif |
488 | ret->diff = DIFF_EASY; |
489 | ret->rec = 0; |
6193da8d |
490 | |
121aae4b |
491 | return ret; |
6193da8d |
492 | } |
493 | |
121aae4b |
494 | static game_params *dup_params(game_params *params) |
6193da8d |
495 | { |
121aae4b |
496 | game_params *ret = snew(game_params); |
497 | *ret = *params; /* structure copy */ |
498 | return ret; |
499 | } |
6193da8d |
500 | |
121aae4b |
501 | static const game_params presets[] = { |
502 | { 4, 4, DIFF_EASY, 0 }, |
503 | { 4, 4, DIFF_NORMAL, 0 }, |
504 | { 4, 4, DIFF_HARD, 0 }, |
505 | { 7, 7, DIFF_EASY, 0 }, |
506 | { 7, 7, DIFF_NORMAL, 0 }, |
507 | { 7, 7, DIFF_HARD, 0 }, |
508 | { 10, 10, DIFF_EASY, 0 }, |
509 | { 10, 10, DIFF_NORMAL, 0 }, |
510 | { 10, 10, DIFF_HARD, 0 }, |
511 | #ifndef SLOW_SYSTEM |
512 | { 15, 15, DIFF_EASY, 0 }, |
513 | { 15, 15, DIFF_NORMAL, 0 }, |
514 | { 15, 15, DIFF_HARD, 0 }, |
515 | { 30, 20, DIFF_EASY, 0 }, |
516 | { 30, 20, DIFF_NORMAL, 0 }, |
517 | { 30, 20, DIFF_HARD, 0 } |
518 | #endif |
519 | }; |
6193da8d |
520 | |
121aae4b |
521 | static int game_fetch_preset(int i, char **name, game_params **params) |
6193da8d |
522 | { |
1a739e2f |
523 | game_params *tmppar; |
121aae4b |
524 | char buf[80]; |
6193da8d |
525 | |
121aae4b |
526 | if (i < 0 || i >= lenof(presets)) |
527 | return FALSE; |
6193da8d |
528 | |
1a739e2f |
529 | tmppar = snew(game_params); |
530 | *tmppar = presets[i]; |
531 | *params = tmppar; |
121aae4b |
532 | sprintf(buf, "%dx%d %s", tmppar->h, tmppar->w, diffnames[tmppar->diff]); |
533 | *name = dupstr(buf); |
534 | |
535 | return TRUE; |
6193da8d |
536 | } |
537 | |
538 | static void free_params(game_params *params) |
539 | { |
540 | sfree(params); |
541 | } |
542 | |
543 | static void decode_params(game_params *params, char const *string) |
544 | { |
545 | params->h = params->w = atoi(string); |
546 | params->rec = 0; |
c0eb17ce |
547 | params->diff = DIFF_EASY; |
6193da8d |
548 | while (*string && isdigit((unsigned char)*string)) string++; |
549 | if (*string == 'x') { |
550 | string++; |
551 | params->h = atoi(string); |
121aae4b |
552 | while (*string && isdigit((unsigned char)*string)) string++; |
6193da8d |
553 | } |
554 | if (*string == 'r') { |
555 | string++; |
556 | params->rec = atoi(string); |
121aae4b |
557 | while (*string && isdigit((unsigned char)*string)) string++; |
6193da8d |
558 | } |
c0eb17ce |
559 | if (*string == 'd') { |
560 | int i; |
c0eb17ce |
561 | string++; |
121aae4b |
562 | for (i = 0; i < DIFF_MAX; i++) |
563 | if (*string == diffchars[i]) |
564 | params->diff = i; |
565 | if (*string) string++; |
c0eb17ce |
566 | } |
6193da8d |
567 | } |
568 | |
569 | static char *encode_params(game_params *params, int full) |
570 | { |
571 | char str[80]; |
572 | sprintf(str, "%dx%d", params->w, params->h); |
573 | if (full) |
121aae4b |
574 | sprintf(str + strlen(str), "r%dd%c", params->rec, diffchars[params->diff]); |
6193da8d |
575 | return dupstr(str); |
576 | } |
577 | |
578 | static config_item *game_configure(game_params *params) |
579 | { |
580 | config_item *ret; |
581 | char buf[80]; |
582 | |
583 | ret = snewn(4, config_item); |
584 | |
585 | ret[0].name = "Width"; |
586 | ret[0].type = C_STRING; |
587 | sprintf(buf, "%d", params->w); |
588 | ret[0].sval = dupstr(buf); |
589 | ret[0].ival = 0; |
590 | |
591 | ret[1].name = "Height"; |
592 | ret[1].type = C_STRING; |
593 | sprintf(buf, "%d", params->h); |
594 | ret[1].sval = dupstr(buf); |
595 | ret[1].ival = 0; |
596 | |
c0eb17ce |
597 | ret[2].name = "Difficulty"; |
598 | ret[2].type = C_CHOICES; |
599 | ret[2].sval = DIFFCONFIG; |
600 | ret[2].ival = params->diff; |
6193da8d |
601 | |
602 | ret[3].name = NULL; |
603 | ret[3].type = C_END; |
604 | ret[3].sval = NULL; |
605 | ret[3].ival = 0; |
606 | |
607 | return ret; |
608 | } |
609 | |
610 | static game_params *custom_params(config_item *cfg) |
611 | { |
612 | game_params *ret = snew(game_params); |
613 | |
614 | ret->w = atoi(cfg[0].sval); |
615 | ret->h = atoi(cfg[1].sval); |
c0eb17ce |
616 | ret->rec = 0; |
617 | ret->diff = cfg[2].ival; |
6193da8d |
618 | |
619 | return ret; |
620 | } |
621 | |
622 | static char *validate_params(game_params *params, int full) |
623 | { |
624 | if (params->w < 4 || params->h < 4) |
625 | return "Width and height must both be at least 4"; |
626 | if (params->rec < 0) |
627 | return "Recursion depth can't be negative"; |
c0eb17ce |
628 | |
629 | /* |
630 | * This shouldn't be able to happen at all, since decode_params |
631 | * and custom_params will never generate anything that isn't |
632 | * within range. |
633 | */ |
1a739e2f |
634 | assert(params->diff < DIFF_MAX); |
c0eb17ce |
635 | |
6193da8d |
636 | return NULL; |
637 | } |
638 | |
121aae4b |
639 | /* Returns a newly allocated string describing the current puzzle */ |
640 | static char *state_to_text(const game_state *state) |
6193da8d |
641 | { |
121aae4b |
642 | char *retval; |
643 | char *description = snewn(SQUARE_COUNT(state) + 1, char); |
644 | char *dp = description; |
645 | int empty_count = 0; |
646 | int i, j; |
6193da8d |
647 | |
121aae4b |
648 | FORALL_SQUARES(state, i, j) { |
649 | if (CLUE_AT(state, i, j) < 0) { |
650 | if (empty_count > 25) { |
651 | dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); |
652 | empty_count = 0; |
653 | } |
654 | empty_count++; |
655 | } else { |
656 | if (empty_count) { |
657 | dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); |
658 | empty_count = 0; |
659 | } |
1a739e2f |
660 | dp += sprintf(dp, "%c", (int)CLUE2CHAR(CLUE_AT(state, i, j))); |
121aae4b |
661 | } |
662 | } |
6193da8d |
663 | |
121aae4b |
664 | if (empty_count) |
1a739e2f |
665 | dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); |
121aae4b |
666 | |
667 | retval = dupstr(description); |
668 | sfree(description); |
669 | |
670 | return retval; |
6193da8d |
671 | } |
672 | |
121aae4b |
673 | /* We require that the params pass the test in validate_params and that the |
674 | * description fills the entire game area */ |
675 | static char *validate_desc(game_params *params, char *desc) |
6193da8d |
676 | { |
121aae4b |
677 | int count = 0; |
6193da8d |
678 | |
121aae4b |
679 | for (; *desc; ++desc) { |
680 | if (*desc >= '0' && *desc <= '9') { |
681 | count++; |
682 | continue; |
683 | } |
684 | if (*desc >= 'a') { |
685 | count += *desc - 'a' + 1; |
686 | continue; |
687 | } |
688 | return "Unknown character in description"; |
6193da8d |
689 | } |
690 | |
121aae4b |
691 | if (count < SQUARE_COUNT(params)) |
692 | return "Description too short for board size"; |
693 | if (count > SQUARE_COUNT(params)) |
694 | return "Description too long for board size"; |
6193da8d |
695 | |
121aae4b |
696 | return NULL; |
6193da8d |
697 | } |
698 | |
121aae4b |
699 | /* Sums the lengths of the numbers in range [0,n) */ |
700 | /* See equivalent function in solo.c for justification of this. */ |
701 | static int len_0_to_n(int n) |
6193da8d |
702 | { |
121aae4b |
703 | int len = 1; /* Counting 0 as a bit of a special case */ |
704 | int i; |
705 | |
706 | for (i = 1; i < n; i *= 10) { |
707 | len += max(n - i, 0); |
6193da8d |
708 | } |
121aae4b |
709 | |
710 | return len; |
6193da8d |
711 | } |
712 | |
121aae4b |
713 | static char *encode_solve_move(const game_state *state) |
714 | { |
715 | int len, i, j; |
716 | char *ret, *p; |
717 | /* This is going to return a string representing the moves needed to set |
718 | * every line in a grid to be the same as the ones in 'state'. The exact |
719 | * length of this string is predictable. */ |
6193da8d |
720 | |
121aae4b |
721 | len = 1; /* Count the 'S' prefix */ |
722 | /* Numbers in horizontal lines */ |
723 | /* Horizontal lines, x position */ |
724 | len += len_0_to_n(state->w) * (state->h + 1); |
725 | /* Horizontal lines, y position */ |
726 | len += len_0_to_n(state->h + 1) * (state->w); |
727 | /* Vertical lines, y position */ |
728 | len += len_0_to_n(state->h) * (state->w + 1); |
729 | /* Vertical lines, x position */ |
730 | len += len_0_to_n(state->w + 1) * (state->h); |
731 | /* For each line we also have two letters and a comma */ |
732 | len += 3 * (LINE_COUNT(state)); |
6193da8d |
733 | |
121aae4b |
734 | ret = snewn(len + 1, char); |
735 | p = ret; |
6193da8d |
736 | |
121aae4b |
737 | p += sprintf(p, "S"); |
6193da8d |
738 | |
121aae4b |
739 | FORALL_HL(state, i, j) { |
740 | switch (RIGHTOF_DOT(state, i, j)) { |
741 | case LINE_YES: |
742 | p += sprintf(p, "%d,%dhy", i, j); |
743 | break; |
744 | case LINE_NO: |
745 | p += sprintf(p, "%d,%dhn", i, j); |
746 | break; |
747 | } |
6193da8d |
748 | } |
121aae4b |
749 | |
750 | FORALL_VL(state, i, j) { |
751 | switch (BELOW_DOT(state, i, j)) { |
752 | case LINE_YES: |
753 | p += sprintf(p, "%d,%dvy", i, j); |
754 | break; |
755 | case LINE_NO: |
756 | p += sprintf(p, "%d,%dvn", i, j); |
757 | break; |
6193da8d |
758 | } |
6193da8d |
759 | } |
121aae4b |
760 | |
761 | /* No point in doing sums like that if they're going to be wrong */ |
762 | assert(strlen(ret) <= (size_t)len); |
763 | return ret; |
6193da8d |
764 | } |
765 | |
121aae4b |
766 | static game_ui *new_ui(game_state *state) |
6193da8d |
767 | { |
121aae4b |
768 | return NULL; |
769 | } |
6193da8d |
770 | |
121aae4b |
771 | static void free_ui(game_ui *ui) |
772 | { |
773 | } |
6193da8d |
774 | |
121aae4b |
775 | static char *encode_ui(game_ui *ui) |
776 | { |
777 | return NULL; |
778 | } |
6193da8d |
779 | |
121aae4b |
780 | static void decode_ui(game_ui *ui, char *encoding) |
781 | { |
782 | } |
6193da8d |
783 | |
121aae4b |
784 | static void game_changed_state(game_ui *ui, game_state *oldstate, |
785 | game_state *newstate) |
786 | { |
787 | } |
6193da8d |
788 | |
121aae4b |
789 | #define SIZE(d) ((d) * TILE_SIZE + 2 * BORDER + 1) |
6193da8d |
790 | |
121aae4b |
791 | static void game_compute_size(game_params *params, int tilesize, |
792 | int *x, int *y) |
793 | { |
794 | struct { int tilesize; } ads, *ds = &ads; |
795 | ads.tilesize = tilesize; |
6193da8d |
796 | |
121aae4b |
797 | *x = SIZE(params->w); |
798 | *y = SIZE(params->h); |
799 | } |
6193da8d |
800 | |
121aae4b |
801 | static void game_set_size(drawing *dr, game_drawstate *ds, |
802 | game_params *params, int tilesize) |
803 | { |
804 | ds->tilesize = tilesize; |
805 | ds->linewidth = max(1,tilesize/16); |
806 | } |
6193da8d |
807 | |
121aae4b |
808 | static float *game_colours(frontend *fe, int *ncolours) |
809 | { |
810 | float *ret = snewn(4 * NCOLOURS, float); |
6193da8d |
811 | |
121aae4b |
812 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); |
813 | |
814 | ret[COL_FOREGROUND * 3 + 0] = 0.0F; |
815 | ret[COL_FOREGROUND * 3 + 1] = 0.0F; |
816 | ret[COL_FOREGROUND * 3 + 2] = 0.0F; |
817 | |
818 | ret[COL_HIGHLIGHT * 3 + 0] = 1.0F; |
819 | ret[COL_HIGHLIGHT * 3 + 1] = 1.0F; |
820 | ret[COL_HIGHLIGHT * 3 + 2] = 1.0F; |
821 | |
822 | ret[COL_MISTAKE * 3 + 0] = 1.0F; |
823 | ret[COL_MISTAKE * 3 + 1] = 0.0F; |
824 | ret[COL_MISTAKE * 3 + 2] = 0.0F; |
825 | |
826 | *ncolours = NCOLOURS; |
827 | return ret; |
828 | } |
829 | |
830 | static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) |
831 | { |
832 | struct game_drawstate *ds = snew(struct game_drawstate); |
833 | |
834 | ds->tilesize = ds->linewidth = 0; |
835 | ds->started = 0; |
836 | ds->hl = snewn(HL_COUNT(state), char); |
837 | ds->vl = snewn(VL_COUNT(state), char); |
838 | ds->clue_error = snewn(SQUARE_COUNT(state), char); |
839 | ds->flashing = 0; |
840 | |
841 | memset(ds->hl, LINE_UNKNOWN, HL_COUNT(state)); |
842 | memset(ds->vl, LINE_UNKNOWN, VL_COUNT(state)); |
843 | memset(ds->clue_error, 0, SQUARE_COUNT(state)); |
844 | |
845 | return ds; |
846 | } |
847 | |
848 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) |
849 | { |
850 | sfree(ds->clue_error); |
851 | sfree(ds->hl); |
852 | sfree(ds->vl); |
853 | sfree(ds); |
854 | } |
855 | |
856 | static int game_timing_state(game_state *state, game_ui *ui) |
857 | { |
858 | return TRUE; |
859 | } |
860 | |
861 | static float game_anim_length(game_state *oldstate, game_state *newstate, |
862 | int dir, game_ui *ui) |
863 | { |
864 | return 0.0F; |
865 | } |
866 | |
867 | static char *game_text_format(game_state *state) |
868 | { |
869 | int i, j; |
870 | int len; |
871 | char *ret, *rp; |
872 | |
873 | len = (2 * state->w + 2) * (2 * state->h + 1); |
874 | rp = ret = snewn(len + 1, char); |
875 | |
876 | #define DRAW_HL \ |
877 | switch (ABOVE_SQUARE(state, i, j)) { \ |
878 | case LINE_YES: \ |
879 | rp += sprintf(rp, " -"); \ |
880 | break; \ |
881 | case LINE_NO: \ |
882 | rp += sprintf(rp, " x"); \ |
883 | break; \ |
884 | case LINE_UNKNOWN: \ |
885 | rp += sprintf(rp, " "); \ |
886 | break; \ |
887 | default: \ |
888 | assert(!"Illegal line state for HL"); \ |
889 | } |
890 | |
891 | #define DRAW_VL \ |
892 | switch (LEFTOF_SQUARE(state, i, j)) { \ |
893 | case LINE_YES: \ |
894 | rp += sprintf(rp, "|"); \ |
895 | break; \ |
896 | case LINE_NO: \ |
897 | rp += sprintf(rp, "x"); \ |
898 | break; \ |
899 | case LINE_UNKNOWN: \ |
900 | rp += sprintf(rp, " "); \ |
901 | break; \ |
902 | default: \ |
903 | assert(!"Illegal line state for VL"); \ |
904 | } |
905 | |
906 | for (j = 0; j < state->h; ++j) { |
907 | for (i = 0; i < state->w; ++i) { |
908 | DRAW_HL; |
909 | } |
910 | rp += sprintf(rp, " \n"); |
911 | for (i = 0; i < state->w; ++i) { |
912 | DRAW_VL; |
1a739e2f |
913 | rp += sprintf(rp, "%c", (int)CLUE2CHAR(CLUE_AT(state, i, j))); |
121aae4b |
914 | } |
915 | DRAW_VL; |
916 | rp += sprintf(rp, "\n"); |
917 | } |
918 | for (i = 0; i < state->w; ++i) { |
919 | DRAW_HL; |
920 | } |
921 | rp += sprintf(rp, " \n"); |
922 | |
923 | assert(strlen(ret) == len); |
924 | return ret; |
925 | } |
926 | |
927 | /* ---------------------------------------------------------------------- |
928 | * Debug code |
929 | */ |
930 | |
931 | #ifdef DEBUG_CACHES |
932 | static void check_caches(const solver_state* sstate) |
933 | { |
934 | int i, j; |
935 | const game_state *state = sstate->state; |
936 | |
937 | FORALL_DOTS(state, i, j) { |
938 | #if 0 |
939 | fprintf(stderr, "dot [%d,%d] y: %d %d n: %d %d\n", i, j, |
940 | dot_order(state, i, j, LINE_YES), |
941 | sstate->dot_yescount[i + (state->w + 1) * j], |
942 | dot_order(state, i, j, LINE_NO), |
943 | sstate->dot_nocount[i + (state->w + 1) * j]); |
944 | #endif |
945 | |
946 | assert(dot_order(state, i, j, LINE_YES) == |
947 | DOT_YES_COUNT(sstate, i, j)); |
948 | assert(dot_order(state, i, j, LINE_NO) == |
949 | DOT_NO_COUNT(sstate, i, j)); |
950 | } |
951 | |
952 | FORALL_SQUARES(state, i, j) { |
953 | #if 0 |
954 | fprintf(stderr, "square [%d,%d] y: %d %d n: %d %d\n", i, j, |
955 | square_order(state, i, j, LINE_YES), |
956 | sstate->square_yescount[i + state->w * j], |
957 | square_order(state, i, j, LINE_NO), |
958 | sstate->square_nocount[i + state->w * j]); |
959 | #endif |
960 | |
961 | assert(square_order(state, i, j, LINE_YES) == |
962 | SQUARE_YES_COUNT(sstate, i, j)); |
963 | assert(square_order(state, i, j, LINE_NO) == |
964 | SQUARE_NO_COUNT(sstate, i, j)); |
965 | } |
966 | } |
967 | |
968 | #if 0 |
969 | #define check_caches(s) \ |
970 | do { \ |
971 | fprintf(stderr, "check_caches at line %d\n", __LINE__); \ |
972 | check_caches(s); \ |
973 | } while (0) |
974 | #endif |
975 | #endif /* DEBUG_CACHES */ |
976 | |
977 | /* ---------------------------------------------------------------------- |
978 | * Solver utility functions |
979 | */ |
980 | |
981 | static int set_line_bydot(solver_state *sstate, int x, int y, enum direction d, |
982 | enum line_state line_new |
983 | #ifdef SHOW_WORKING |
984 | , const char *reason |
985 | #endif |
986 | ) |
987 | { |
988 | game_state *state = sstate->state; |
989 | |
990 | /* This line borders at most two squares in our board. We figure out the |
991 | * x and y positions of those squares so we can record that their yes or no |
992 | * counts have been changed */ |
993 | int sq1_x=-1, sq1_y=-1, sq2_x=-1, sq2_y=-1; |
994 | int otherdot_x=-1, otherdot_y=-1; |
995 | |
996 | int progress = FALSE; |
997 | |
998 | #if 0 |
999 | fprintf(stderr, "set_line_bydot [%d,%d], %s, %d\n", |
1000 | x, y, DIR2STR(d), line_new); |
1001 | #endif |
1002 | |
1003 | assert(line_new != LINE_UNKNOWN); |
1004 | |
1005 | check_caches(sstate); |
1006 | |
1007 | switch (d) { |
1008 | case LEFT: |
1009 | assert(x > 0); |
1010 | |
1011 | if (LEFTOF_DOT(state, x, y) != line_new) { |
1012 | LV_LEFTOF_DOT(state, x, y) = line_new; |
1013 | |
1014 | otherdot_x = x-1; |
1015 | otherdot_y = y; |
1016 | |
1017 | sq1_x = x-1; |
1018 | sq1_y = y-1; |
1019 | sq2_x = x-1; |
1020 | sq2_y = y; |
1021 | |
1022 | progress = TRUE; |
1023 | } |
1024 | break; |
1025 | case RIGHT: |
1026 | assert(x < state->w); |
1027 | if (RIGHTOF_DOT(state, x, y) != line_new) { |
1028 | LV_RIGHTOF_DOT(state, x, y) = line_new; |
1029 | |
1030 | otherdot_x = x+1; |
1031 | otherdot_y = y; |
1032 | |
1033 | sq1_x = x; |
1034 | sq1_y = y-1; |
1035 | sq2_x = x; |
1036 | sq2_y = y; |
1037 | |
1038 | progress = TRUE; |
1039 | } |
1040 | break; |
1041 | case UP: |
1042 | assert(y > 0); |
1043 | if (ABOVE_DOT(state, x, y) != line_new) { |
1044 | LV_ABOVE_DOT(state, x, y) = line_new; |
1045 | |
1046 | otherdot_x = x; |
1047 | otherdot_y = y-1; |
1048 | |
1049 | sq1_x = x-1; |
1050 | sq1_y = y-1; |
1051 | sq2_x = x; |
1052 | sq2_y = y-1; |
1053 | |
1054 | progress = TRUE; |
1055 | } |
1056 | break; |
1057 | case DOWN: |
1058 | assert(y < state->h); |
1059 | if (BELOW_DOT(state, x, y) != line_new) { |
1060 | LV_BELOW_DOT(state, x, y) = line_new; |
1061 | |
1062 | otherdot_x = x; |
1063 | otherdot_y = y+1; |
1064 | |
1065 | sq1_x = x-1; |
1066 | sq1_y = y; |
1067 | sq2_x = x; |
1068 | sq2_y = y; |
1069 | |
1070 | progress = TRUE; |
1071 | } |
1072 | break; |
1073 | } |
1074 | |
1075 | if (!progress) |
1076 | return progress; |
1077 | |
1078 | #ifdef SHOW_WORKING |
1079 | fprintf(stderr, "set line [%d,%d] -> [%d,%d] to %s (%s)\n", |
1080 | x, y, otherdot_x, otherdot_y, line_new == LINE_YES ? "YES" : "NO", |
1081 | reason); |
1082 | #endif |
1083 | |
1084 | /* Above we updated the cache for the dot that the line in question reaches |
1085 | * from the dot we've been told about. Here we update that for the dot |
1086 | * named in our arguments. */ |
1087 | if (line_new == LINE_YES) { |
1088 | if (sq1_x >= 0 && sq1_y >= 0) |
1089 | ++SQUARE_YES_COUNT(sstate, sq1_x, sq1_y); |
1090 | if (sq2_x < state->w && sq2_y < state->h) |
1091 | ++SQUARE_YES_COUNT(sstate, sq2_x, sq2_y); |
1092 | ++DOT_YES_COUNT(sstate, x, y); |
1093 | ++DOT_YES_COUNT(sstate, otherdot_x, otherdot_y); |
1094 | } else { |
1095 | if (sq1_x >= 0 && sq1_y >= 0) |
1096 | ++SQUARE_NO_COUNT(sstate, sq1_x, sq1_y); |
1097 | if (sq2_x < state->w && sq2_y < state->h) |
1098 | ++SQUARE_NO_COUNT(sstate, sq2_x, sq2_y); |
1099 | ++DOT_NO_COUNT(sstate, x, y); |
1100 | ++DOT_NO_COUNT(sstate, otherdot_x, otherdot_y); |
1101 | } |
1102 | |
1103 | check_caches(sstate); |
1104 | return progress; |
1105 | } |
1106 | |
1107 | #ifdef SHOW_WORKING |
1108 | #define set_line_bydot(a, b, c, d, e) \ |
1109 | set_line_bydot(a, b, c, d, e, __FUNCTION__) |
1110 | #endif |
1111 | |
1112 | /* |
1113 | * Merge two dots due to the existence of an edge between them. |
1114 | * Updates the dsf tracking equivalence classes, and keeps track of |
1115 | * the length of path each dot is currently a part of. |
1116 | * Returns TRUE if the dots were already linked, ie if they are part of a |
1117 | * closed loop, and false otherwise. |
1118 | */ |
1119 | static int merge_dots(solver_state *sstate, int x1, int y1, int x2, int y2) |
1120 | { |
1121 | int i, j, len; |
1122 | |
1123 | i = y1 * (sstate->state->w + 1) + x1; |
1124 | j = y2 * (sstate->state->w + 1) + x2; |
1125 | |
1126 | i = dsf_canonify(sstate->dotdsf, i); |
1127 | j = dsf_canonify(sstate->dotdsf, j); |
1128 | |
1129 | if (i == j) { |
1130 | return TRUE; |
1131 | } else { |
1132 | len = sstate->looplen[i] + sstate->looplen[j]; |
1133 | dsf_merge(sstate->dotdsf, i, j); |
1134 | i = dsf_canonify(sstate->dotdsf, i); |
1135 | sstate->looplen[i] = len; |
1136 | return FALSE; |
1137 | } |
1138 | } |
1139 | |
1140 | /* Seriously, these should be functions */ |
1141 | |
1142 | #define LINEDSF_INDEX(state, x, y, d) \ |
1143 | ((d == UP) ? ((y-1) * (state->w + 1) + x) : \ |
1144 | (d == DOWN) ? ((y) * (state->w + 1) + x) : \ |
1145 | (d == LEFT) ? ((y) * (state->w) + x-1 + VL_COUNT(state)) : \ |
1146 | (d == RIGHT) ? ((y) * (state->w) + x + VL_COUNT(state)) : \ |
1147 | (assert(!"bad direction value"), 0)) |
1148 | |
1149 | static void linedsf_deindex(const game_state *state, int i, |
1150 | int *px, int *py, enum direction *pd) |
1151 | { |
1152 | int i_mod; |
1153 | if (i < VL_COUNT(state)) { |
1154 | *(pd) = DOWN; |
1155 | *(px) = (i) % (state->w+1); |
1156 | *(py) = (i) / (state->w+1); |
1157 | } else { |
1158 | i_mod = i - VL_COUNT(state); |
1159 | *(pd) = RIGHT; |
1160 | *(px) = (i_mod) % (state->w); |
1161 | *(py) = (i_mod) / (state->w); |
1162 | } |
1163 | } |
1164 | |
1165 | /* Merge two lines because the solver has deduced that they must be either |
1166 | * identical or opposite. Returns TRUE if this is new information, otherwise |
1167 | * FALSE. */ |
1168 | static int merge_lines(solver_state *sstate, |
1169 | int x1, int y1, enum direction d1, |
1170 | int x2, int y2, enum direction d2, |
1171 | int inverse |
1172 | #ifdef SHOW_WORKING |
1173 | , const char *reason |
1174 | #endif |
1175 | ) |
1176 | { |
1177 | int i, j, inv_tmp; |
1178 | |
1179 | i = LINEDSF_INDEX(sstate->state, x1, y1, d1); |
1180 | j = LINEDSF_INDEX(sstate->state, x2, y2, d2); |
1181 | |
1182 | assert(i < LINE_COUNT(sstate->state)); |
1183 | assert(j < LINE_COUNT(sstate->state)); |
1184 | |
1185 | i = edsf_canonify(sstate->hard->linedsf, i, &inv_tmp); |
1186 | inverse ^= inv_tmp; |
1187 | j = edsf_canonify(sstate->hard->linedsf, j, &inv_tmp); |
1188 | inverse ^= inv_tmp; |
1189 | |
1190 | edsf_merge(sstate->hard->linedsf, i, j, inverse); |
1191 | |
1192 | #ifdef SHOW_WORKING |
1193 | if (i != j) { |
1194 | fprintf(stderr, "%s [%d,%d,%s] [%d,%d,%s] %s(%s)\n", |
1195 | __FUNCTION__, |
1196 | x1, y1, DIR2STR(d1), |
1197 | x2, y2, DIR2STR(d2), |
1198 | inverse ? "inverse " : "", reason); |
1199 | } |
1200 | #endif |
1201 | return (i != j); |
1202 | } |
1203 | |
1204 | #ifdef SHOW_WORKING |
1205 | #define merge_lines(a, b, c, d, e, f, g, h) \ |
1206 | merge_lines(a, b, c, d, e, f, g, h, __FUNCTION__) |
1207 | #endif |
1208 | |
1209 | /* Return 0 if the given lines are not in the same equivalence class, 1 if they |
1210 | * are known identical, or 2 if they are known opposite */ |
1211 | #if 0 |
1212 | static int lines_related(solver_state *sstate, |
1213 | int x1, int y1, enum direction d1, |
1214 | int x2, int y2, enum direction d2) |
1215 | { |
1216 | int i, j, inv1, inv2; |
1217 | |
1218 | i = LINEDSF_INDEX(sstate->state, x1, y1, d1); |
1219 | j = LINEDSF_INDEX(sstate->state, x2, y2, d2); |
1220 | |
1221 | i = edsf_canonify(sstate->hard->linedsf, i, &inv1); |
1222 | j = edsf_canonify(sstate->hard->linedsf, j, &inv2); |
1223 | |
1224 | if (i == j) |
1225 | return (inv1 == inv2) ? 1 : 2; |
1226 | else |
1227 | return 0; |
1228 | } |
1229 | #endif |
1230 | |
1231 | /* Count the number of lines of a particular type currently going into the |
1232 | * given dot. Lines going off the edge of the board are assumed fixed no. */ |
1233 | static int dot_order(const game_state* state, int i, int j, char line_type) |
1234 | { |
1235 | int n = 0; |
1236 | |
1237 | if (i > 0) { |
1238 | if (line_type == LV_LEFTOF_DOT(state, i, j)) |
1239 | ++n; |
1240 | } else { |
1241 | if (line_type == LINE_NO) |
1242 | ++n; |
1243 | } |
1244 | if (i < state->w) { |
1245 | if (line_type == LV_RIGHTOF_DOT(state, i, j)) |
1246 | ++n; |
1247 | } else { |
1248 | if (line_type == LINE_NO) |
1249 | ++n; |
1250 | } |
1251 | if (j > 0) { |
1252 | if (line_type == LV_ABOVE_DOT(state, i, j)) |
1253 | ++n; |
1254 | } else { |
1255 | if (line_type == LINE_NO) |
1256 | ++n; |
1257 | } |
1258 | if (j < state->h) { |
1259 | if (line_type == LV_BELOW_DOT(state, i, j)) |
1260 | ++n; |
1261 | } else { |
1262 | if (line_type == LINE_NO) |
1263 | ++n; |
1264 | } |
1265 | |
1266 | return n; |
1267 | } |
1268 | |
1269 | /* Count the number of lines of a particular type currently surrounding the |
1270 | * given square */ |
1271 | static int square_order(const game_state* state, int i, int j, char line_type) |
1272 | { |
1273 | int n = 0; |
1274 | |
1275 | if (ABOVE_SQUARE(state, i, j) == line_type) |
1276 | ++n; |
1277 | if (BELOW_SQUARE(state, i, j) == line_type) |
1278 | ++n; |
1279 | if (LEFTOF_SQUARE(state, i, j) == line_type) |
1280 | ++n; |
1281 | if (RIGHTOF_SQUARE(state, i, j) == line_type) |
1282 | ++n; |
1283 | |
1284 | return n; |
1285 | } |
1286 | |
1287 | /* Set all lines bordering a dot of type old_type to type new_type |
1288 | * Return value tells caller whether this function actually did anything */ |
1289 | static int dot_setall(solver_state *sstate, int i, int j, |
1290 | char old_type, char new_type) |
1291 | { |
1292 | int retval = FALSE, r; |
1293 | game_state *state = sstate->state; |
1294 | |
1295 | if (old_type == new_type) |
1296 | return FALSE; |
1297 | |
1298 | if (i > 0 && LEFTOF_DOT(state, i, j) == old_type) { |
1299 | r = set_line_bydot(sstate, i, j, LEFT, new_type); |
1300 | assert(r == TRUE); |
1301 | retval = TRUE; |
1302 | } |
1303 | |
1304 | if (i < state->w && RIGHTOF_DOT(state, i, j) == old_type) { |
1305 | r = set_line_bydot(sstate, i, j, RIGHT, new_type); |
1306 | assert(r == TRUE); |
1307 | retval = TRUE; |
1308 | } |
1309 | |
1310 | if (j > 0 && ABOVE_DOT(state, i, j) == old_type) { |
1311 | r = set_line_bydot(sstate, i, j, UP, new_type); |
1312 | assert(r == TRUE); |
1313 | retval = TRUE; |
1314 | } |
1315 | |
1316 | if (j < state->h && BELOW_DOT(state, i, j) == old_type) { |
1317 | r = set_line_bydot(sstate, i, j, DOWN, new_type); |
1318 | assert(r == TRUE); |
1319 | retval = TRUE; |
1320 | } |
1321 | |
1322 | return retval; |
1323 | } |
1324 | |
1325 | /* Set all lines bordering a square of type old_type to type new_type */ |
1326 | static int square_setall(solver_state *sstate, int i, int j, |
1327 | char old_type, char new_type) |
1328 | { |
1329 | int r = FALSE; |
1330 | game_state *state = sstate->state; |
1331 | |
1332 | #if 0 |
1333 | fprintf(stderr, "square_setall [%d,%d] from %d to %d\n", i, j, |
1334 | old_type, new_type); |
1335 | #endif |
1336 | if (ABOVE_SQUARE(state, i, j) == old_type) { |
1337 | r = set_line_bydot(sstate, i, j, RIGHT, new_type); |
1338 | assert(r == TRUE); |
1339 | } |
1340 | if (BELOW_SQUARE(state, i, j) == old_type) { |
1341 | r = set_line_bydot(sstate, i, j+1, RIGHT, new_type); |
1342 | assert(r == TRUE); |
1343 | } |
1344 | if (LEFTOF_SQUARE(state, i, j) == old_type) { |
1345 | r = set_line_bydot(sstate, i, j, DOWN, new_type); |
1346 | assert(r == TRUE); |
1347 | } |
1348 | if (RIGHTOF_SQUARE(state, i, j) == old_type) { |
1349 | r = set_line_bydot(sstate, i+1, j, DOWN, new_type); |
1350 | assert(r == TRUE); |
1351 | } |
1352 | |
1353 | return r; |
1354 | } |
1355 | |
1356 | /* ---------------------------------------------------------------------- |
1357 | * Loop generation and clue removal |
1358 | */ |
1359 | |
1360 | /* We're going to store a list of current candidate squares for lighting. |
1361 | * Each square gets a 'score', which tells us how adding that square right |
1362 | * now would affect the length of the solution loop. We're trying to |
1363 | * maximise that quantity so will bias our random selection of squares to |
1364 | * light towards those with high scores */ |
1365 | struct square { |
1366 | int score; |
1367 | unsigned long random; |
1368 | int x, y; |
1369 | }; |
1370 | |
1371 | static int get_square_cmpfn(void *v1, void *v2) |
1372 | { |
1373 | struct square *s1 = v1; |
1374 | struct square *s2 = v2; |
1375 | int r; |
1376 | |
1377 | r = s1->x - s2->x; |
1378 | if (r) |
1379 | return r; |
1380 | |
1381 | r = s1->y - s2->y; |
1382 | if (r) |
1383 | return r; |
1384 | |
1385 | return 0; |
1386 | } |
1387 | |
1388 | static int square_sort_cmpfn(void *v1, void *v2) |
1389 | { |
1390 | struct square *s1 = v1; |
1391 | struct square *s2 = v2; |
1392 | int r; |
1393 | |
1394 | r = s2->score - s1->score; |
1395 | if (r) { |
1396 | return r; |
1397 | } |
1398 | |
1399 | if (s1->random < s2->random) |
1400 | return -1; |
1401 | else if (s1->random > s2->random) |
1402 | return 1; |
1403 | |
1404 | /* |
1405 | * It's _just_ possible that two squares might have been given |
1406 | * the same random value. In that situation, fall back to |
1407 | * comparing based on the coordinates. This introduces a tiny |
1408 | * directional bias, but not a significant one. |
1409 | */ |
1410 | return get_square_cmpfn(v1, v2); |
1411 | } |
1412 | |
1413 | enum { SQUARE_LIT, SQUARE_UNLIT }; |
1414 | |
1415 | #define SQUARE_STATE(i, j) \ |
1416 | ( LEGAL_SQUARE(state, i, j) ? \ |
1417 | LV_SQUARE_STATE(i,j) : \ |
1418 | SQUARE_UNLIT ) |
1419 | |
1420 | #define LV_SQUARE_STATE(i, j) board[SQUARE_INDEX(state, i, j)] |
1421 | |
1422 | /* Generate a new complete set of clues for the given game_state (respecting |
1423 | * the dimensions provided by said game_state) */ |
1424 | static void add_full_clues(game_state *state, random_state *rs) |
1425 | { |
1426 | char *clues; |
1427 | char *board; |
1428 | int i, j, a, b, c; |
1429 | int board_area = SQUARE_COUNT(state); |
1430 | int t; |
1431 | |
1432 | struct square *square, *tmpsquare, *sq; |
1433 | struct square square_pos; |
1434 | |
1435 | /* These will contain exactly the same information, sorted into different |
1436 | * orders */ |
1437 | tree234 *lightable_squares_sorted, *lightable_squares_gettable; |
1438 | |
1439 | #define SQUARE_REACHABLE(i,j) \ |
1440 | (t = (SQUARE_STATE(i-1, j) == SQUARE_LIT || \ |
1441 | SQUARE_STATE(i+1, j) == SQUARE_LIT || \ |
1442 | SQUARE_STATE(i, j-1) == SQUARE_LIT || \ |
1443 | SQUARE_STATE(i, j+1) == SQUARE_LIT), \ |
1444 | t) |
1445 | |
1446 | /* One situation in which we may not light a square is if that'll leave one |
1447 | * square above/below and one left/right of us unlit, separated by a lit |
1448 | * square diagnonal from us */ |
1449 | #define SQUARE_DIAGONAL_VIOLATION(i, j, h, v) \ |
1450 | (t = (SQUARE_STATE((i)+(h), (j)) == SQUARE_UNLIT && \ |
1451 | SQUARE_STATE((i), (j)+(v)) == SQUARE_UNLIT && \ |
1452 | SQUARE_STATE((i)+(h), (j)+(v)) == SQUARE_LIT), \ |
1453 | t) |
1454 | |
1455 | /* We also may not light a square if it will form a loop of lit squares |
1456 | * around some unlit squares, as then the game soln won't have a single |
1457 | * loop */ |
1458 | #define SQUARE_LOOP_VIOLATION(i, j, lit1, lit2) \ |
1459 | (SQUARE_STATE((i)+1, (j)) == lit1 && \ |
1460 | SQUARE_STATE((i)-1, (j)) == lit1 && \ |
1461 | SQUARE_STATE((i), (j)+1) == lit2 && \ |
1462 | SQUARE_STATE((i), (j)-1) == lit2) |
1463 | |
1464 | #define CAN_LIGHT_SQUARE(i, j) \ |
1465 | (SQUARE_REACHABLE(i, j) && \ |
1466 | !SQUARE_DIAGONAL_VIOLATION(i, j, -1, -1) && \ |
1467 | !SQUARE_DIAGONAL_VIOLATION(i, j, +1, -1) && \ |
1468 | !SQUARE_DIAGONAL_VIOLATION(i, j, -1, +1) && \ |
1469 | !SQUARE_DIAGONAL_VIOLATION(i, j, +1, +1) && \ |
1470 | !SQUARE_LOOP_VIOLATION(i, j, SQUARE_LIT, SQUARE_UNLIT) && \ |
1471 | !SQUARE_LOOP_VIOLATION(i, j, SQUARE_UNLIT, SQUARE_LIT)) |
1472 | |
1473 | #define IS_LIGHTING_CANDIDATE(i, j) \ |
1474 | (SQUARE_STATE(i, j) == SQUARE_UNLIT && \ |
1475 | CAN_LIGHT_SQUARE(i,j)) |
1476 | |
1477 | /* The 'score' of a square reflects its current desirability for selection |
1478 | * as the next square to light. We want to encourage moving into uncharted |
1479 | * areas so we give scores according to how many of the square's neighbours |
1480 | * are currently unlit. */ |
1481 | |
1482 | /* UNLIT SCORE |
6193da8d |
1483 | * 3 2 |
1484 | * 2 0 |
1485 | * 1 -2 |
1486 | */ |
121aae4b |
1487 | #define SQUARE_SCORE(i,j) \ |
1488 | (2*((SQUARE_STATE(i-1, j) == SQUARE_UNLIT) + \ |
1489 | (SQUARE_STATE(i+1, j) == SQUARE_UNLIT) + \ |
1490 | (SQUARE_STATE(i, j-1) == SQUARE_UNLIT) + \ |
6193da8d |
1491 | (SQUARE_STATE(i, j+1) == SQUARE_UNLIT)) - 4) |
1492 | |
121aae4b |
1493 | /* When a square gets lit, this defines how far away from that square we |
1494 | * need to go recomputing scores */ |
1495 | #define SCORE_DISTANCE 1 |
1496 | |
1497 | board = snewn(board_area, char); |
1498 | clues = state->clues; |
1499 | |
1500 | /* Make a board */ |
1501 | memset(board, SQUARE_UNLIT, board_area); |
1502 | |
1503 | /* Seed the board with a single lit square near the middle */ |
1504 | i = state->w / 2; |
1505 | j = state->h / 2; |
1506 | if (state->w & 1 && random_bits(rs, 1)) |
1507 | ++i; |
1508 | if (state->h & 1 && random_bits(rs, 1)) |
1509 | ++j; |
1510 | |
1511 | LV_SQUARE_STATE(i, j) = SQUARE_LIT; |
1512 | |
1513 | /* We need a way of favouring squares that will increase our loopiness. |
1514 | * We do this by maintaining a list of all candidate squares sorted by |
1515 | * their score and choose randomly from that with appropriate skew. |
1516 | * In order to avoid consistently biasing towards particular squares, we |
1517 | * need the sort order _within_ each group of scores to be completely |
1518 | * random. But it would be abusing the hospitality of the tree234 data |
1519 | * structure if our comparison function were nondeterministic :-). So with |
1520 | * each square we associate a random number that does not change during a |
1521 | * particular run of the generator, and use that as a secondary sort key. |
1522 | * Yes, this means we will be biased towards particular random squares in |
1523 | * any one run but that doesn't actually matter. */ |
1524 | |
1525 | lightable_squares_sorted = newtree234(square_sort_cmpfn); |
1526 | lightable_squares_gettable = newtree234(get_square_cmpfn); |
1527 | #define ADD_SQUARE(s) \ |
1528 | do { \ |
1529 | sq = add234(lightable_squares_sorted, s); \ |
1530 | assert(sq == s); \ |
1531 | sq = add234(lightable_squares_gettable, s); \ |
1532 | assert(sq == s); \ |
1533 | } while (0) |
1534 | |
1535 | #define REMOVE_SQUARE(s) \ |
1536 | do { \ |
1537 | sq = del234(lightable_squares_sorted, s); \ |
1538 | assert(sq); \ |
1539 | sq = del234(lightable_squares_gettable, s); \ |
1540 | assert(sq); \ |
1541 | } while (0) |
1542 | |
1543 | #define HANDLE_DIR(a, b) \ |
1544 | square = snew(struct square); \ |
1545 | square->x = (i)+(a); \ |
1546 | square->y = (j)+(b); \ |
1547 | square->score = 2; \ |
1548 | square->random = random_bits(rs, 31); \ |
1549 | ADD_SQUARE(square); |
1550 | HANDLE_DIR(-1, 0); |
1551 | HANDLE_DIR( 1, 0); |
1552 | HANDLE_DIR( 0,-1); |
1553 | HANDLE_DIR( 0, 1); |
1554 | #undef HANDLE_DIR |
1555 | |
1556 | /* Light squares one at a time until the board is interesting enough */ |
1557 | while (TRUE) |
1558 | { |
1559 | /* We have count234(lightable_squares) possibilities, and in |
1560 | * lightable_squares_sorted they are sorted with the most desirable |
1561 | * first. */ |
1562 | c = count234(lightable_squares_sorted); |
1563 | if (c == 0) |
1564 | break; |
1565 | assert(c == count234(lightable_squares_gettable)); |
1566 | |
1567 | /* Check that the best square available is any good */ |
1568 | square = (struct square *)index234(lightable_squares_sorted, 0); |
1569 | assert(square); |
1570 | |
1571 | /* |
1572 | * We never want to _decrease_ the loop's perimeter. Making |
1573 | * moves that leave the perimeter the same is occasionally |
1574 | * useful: if it were _never_ done then the user would be |
1575 | * able to deduce illicitly that any degree-zero vertex was |
1576 | * on the outside of the loop. So we do it sometimes but |
1577 | * not always. |
1578 | */ |
1579 | if (square->score < 0 || (square->score == 0 && |
1580 | random_upto(rs, 2) == 0)) { |
1581 | break; |
1582 | } |
1583 | |
1584 | assert(square->score == SQUARE_SCORE(square->x, square->y)); |
1585 | assert(SQUARE_STATE(square->x, square->y) == SQUARE_UNLIT); |
1586 | assert(square->x >= 0 && square->x < state->w); |
1587 | assert(square->y >= 0 && square->y < state->h); |
1588 | |
1589 | /* Update data structures */ |
1590 | LV_SQUARE_STATE(square->x, square->y) = SQUARE_LIT; |
1591 | REMOVE_SQUARE(square); |
1592 | |
1593 | /* We might have changed the score of any squares up to 2 units away in |
1594 | * any direction */ |
1595 | for (b = -SCORE_DISTANCE; b <= SCORE_DISTANCE; b++) { |
1596 | for (a = -SCORE_DISTANCE; a <= SCORE_DISTANCE; a++) { |
1597 | if (!a && !b) |
1598 | continue; |
1599 | square_pos.x = square->x + a; |
1600 | square_pos.y = square->y + b; |
1601 | if (square_pos.x < 0 || square_pos.x >= state->w || |
1602 | square_pos.y < 0 || square_pos.y >= state->h) { |
1603 | continue; |
1604 | } |
1605 | tmpsquare = find234(lightable_squares_gettable, &square_pos, |
1606 | NULL); |
1607 | if (tmpsquare) { |
1608 | assert(tmpsquare->x == square_pos.x); |
1609 | assert(tmpsquare->y == square_pos.y); |
1610 | assert(SQUARE_STATE(tmpsquare->x, tmpsquare->y) == |
1611 | SQUARE_UNLIT); |
1612 | REMOVE_SQUARE(tmpsquare); |
1613 | } else { |
1614 | tmpsquare = snew(struct square); |
1615 | tmpsquare->x = square_pos.x; |
1616 | tmpsquare->y = square_pos.y; |
1617 | tmpsquare->random = random_bits(rs, 31); |
1618 | } |
1619 | tmpsquare->score = SQUARE_SCORE(tmpsquare->x, tmpsquare->y); |
1620 | |
1621 | if (IS_LIGHTING_CANDIDATE(tmpsquare->x, tmpsquare->y)) { |
1622 | ADD_SQUARE(tmpsquare); |
1623 | } else { |
1624 | sfree(tmpsquare); |
1625 | } |
1626 | } |
1627 | } |
1628 | sfree(square); |
1629 | } |
1630 | |
1631 | /* Clean up */ |
1632 | while ((square = delpos234(lightable_squares_gettable, 0)) != NULL) |
1633 | sfree(square); |
1634 | freetree234(lightable_squares_gettable); |
1635 | freetree234(lightable_squares_sorted); |
1636 | |
1637 | /* Copy out all the clues */ |
1638 | FORALL_SQUARES(state, i, j) { |
1639 | c = SQUARE_STATE(i, j); |
1640 | LV_CLUE_AT(state, i, j) = 0; |
1641 | if (SQUARE_STATE(i-1, j) != c) ++LV_CLUE_AT(state, i, j); |
1642 | if (SQUARE_STATE(i+1, j) != c) ++LV_CLUE_AT(state, i, j); |
1643 | if (SQUARE_STATE(i, j-1) != c) ++LV_CLUE_AT(state, i, j); |
1644 | if (SQUARE_STATE(i, j+1) != c) ++LV_CLUE_AT(state, i, j); |
1645 | } |
1646 | |
1647 | sfree(board); |
1648 | } |
1649 | |
1a739e2f |
1650 | static int game_has_unique_soln(const game_state *state, int diff) |
121aae4b |
1651 | { |
1652 | int ret; |
1653 | solver_state *sstate_new; |
1654 | solver_state *sstate = new_solver_state((game_state *)state, diff); |
1655 | |
1656 | sstate_new = solve_game_rec(sstate, diff); |
1657 | |
1658 | assert(sstate_new->solver_status != SOLVER_MISTAKE); |
1659 | ret = (sstate_new->solver_status == SOLVER_SOLVED); |
1660 | |
1661 | free_solver_state(sstate_new); |
1662 | free_solver_state(sstate); |
1663 | |
1664 | return ret; |
1665 | } |
1666 | |
1667 | /* Remove clues one at a time at random. */ |
1668 | static game_state *remove_clues(game_state *state, random_state *rs, |
1a739e2f |
1669 | int diff) |
121aae4b |
1670 | { |
1671 | int *square_list, squares; |
1672 | game_state *ret = dup_game(state), *saved_ret; |
1673 | int n; |
1674 | #ifdef SHOW_WORKING |
1675 | char *desc; |
1676 | #endif |
1677 | |
1678 | /* We need to remove some clues. We'll do this by forming a list of all |
1679 | * available clues, shuffling it, then going along one at a |
1680 | * time clearing each clue in turn for which doing so doesn't render the |
1681 | * board unsolvable. */ |
1682 | squares = state->w * state->h; |
1683 | square_list = snewn(squares, int); |
1684 | for (n = 0; n < squares; ++n) { |
1685 | square_list[n] = n; |
1686 | } |
1687 | |
1688 | shuffle(square_list, squares, sizeof(int), rs); |
1689 | |
1690 | for (n = 0; n < squares; ++n) { |
1691 | saved_ret = dup_game(ret); |
1692 | LV_CLUE_AT(ret, square_list[n] % state->w, |
1693 | square_list[n] / state->w) = -1; |
1694 | |
1695 | #ifdef SHOW_WORKING |
1696 | desc = state_to_text(ret); |
1697 | fprintf(stderr, "%dx%d:%s\n", state->w, state->h, desc); |
1698 | sfree(desc); |
1699 | #endif |
1700 | |
1701 | if (game_has_unique_soln(ret, diff)) { |
1702 | free_game(saved_ret); |
1703 | } else { |
1704 | free_game(ret); |
1705 | ret = saved_ret; |
1706 | } |
1707 | } |
1708 | sfree(square_list); |
1709 | |
1710 | return ret; |
1711 | } |
1712 | |
1713 | static char *new_game_desc(game_params *params, random_state *rs, |
1714 | char **aux, int interactive) |
1715 | { |
1716 | /* solution and description both use run-length encoding in obvious ways */ |
1717 | char *retval; |
1718 | game_state *state = snew(game_state), *state_new; |
1719 | |
1720 | state->h = params->h; |
1721 | state->w = params->w; |
1722 | |
1723 | state->clues = snewn(SQUARE_COUNT(params), char); |
1724 | state->hl = snewn(HL_COUNT(params), char); |
1725 | state->vl = snewn(VL_COUNT(params), char); |
1726 | |
1727 | newboard_please: |
1728 | memset(state->hl, LINE_UNKNOWN, HL_COUNT(params)); |
1729 | memset(state->vl, LINE_UNKNOWN, VL_COUNT(params)); |
1730 | |
1731 | state->solved = state->cheated = FALSE; |
1732 | state->recursion_depth = params->rec; |
1733 | |
1734 | /* Get a new random solvable board with all its clues filled in. Yes, this |
1735 | * can loop for ever if the params are suitably unfavourable, but |
1736 | * preventing games smaller than 4x4 seems to stop this happening */ |
1737 | |
1738 | do { |
1739 | add_full_clues(state, rs); |
1740 | } while (!game_has_unique_soln(state, params->diff)); |
1741 | |
1742 | state_new = remove_clues(state, rs, params->diff); |
1743 | free_game(state); |
1744 | state = state_new; |
1745 | |
1746 | if (params->diff > 0 && game_has_unique_soln(state, params->diff-1)) { |
1a739e2f |
1747 | #ifdef SHOW_WORKING |
121aae4b |
1748 | fprintf(stderr, "Rejecting board, it is too easy\n"); |
1a739e2f |
1749 | #endif |
121aae4b |
1750 | goto newboard_please; |
1751 | } |
1752 | |
1753 | retval = state_to_text(state); |
1754 | |
1755 | free_game(state); |
1756 | |
1757 | assert(!validate_desc(params, retval)); |
1758 | |
1759 | return retval; |
1760 | } |
1761 | |
1762 | static game_state *new_game(midend *me, game_params *params, char *desc) |
1763 | { |
1764 | int i,j; |
1765 | game_state *state = snew(game_state); |
1766 | int empties_to_make = 0; |
1767 | int n; |
1768 | const char *dp = desc; |
1769 | |
1770 | state->recursion_depth = 0; /* XXX pending removal, probably */ |
1771 | |
1772 | state->h = params->h; |
1773 | state->w = params->w; |
1774 | |
1775 | state->clues = snewn(SQUARE_COUNT(params), char); |
1776 | state->hl = snewn(HL_COUNT(params), char); |
1777 | state->vl = snewn(VL_COUNT(params), char); |
1778 | |
1779 | state->solved = state->cheated = FALSE; |
1780 | |
1781 | FORALL_SQUARES(params, i, j) { |
1782 | if (empties_to_make) { |
1783 | empties_to_make--; |
1784 | LV_CLUE_AT(state, i, j) = -1; |
1785 | continue; |
1786 | } |
1787 | |
1788 | assert(*dp); |
1789 | n = *dp - '0'; |
1790 | if (n >= 0 && n < 10) { |
1791 | LV_CLUE_AT(state, i, j) = n; |
1792 | } else { |
1793 | n = *dp - 'a' + 1; |
1794 | assert(n > 0); |
1795 | LV_CLUE_AT(state, i, j) = -1; |
1796 | empties_to_make = n - 1; |
1797 | } |
1798 | ++dp; |
1799 | } |
1800 | |
1801 | memset(state->hl, LINE_UNKNOWN, HL_COUNT(params)); |
1802 | memset(state->vl, LINE_UNKNOWN, VL_COUNT(params)); |
1803 | |
1804 | return state; |
1805 | } |
1806 | |
1807 | enum { LOOP_NONE=0, LOOP_SOLN, LOOP_NOT_SOLN }; |
1808 | |
1809 | /* ---------------------------------------------------------------------- |
1810 | * Solver logic |
1811 | * |
1812 | * Our solver modes operate as follows. Each mode also uses the modes above it. |
1813 | * |
1814 | * Easy Mode |
1815 | * Just implement the rules of the game. |
1816 | * |
1817 | * Normal Mode |
1818 | * For each pair of lines through each dot we store a bit for whether |
1819 | * at least one of them is on and whether at most one is on. (If we know |
1820 | * both or neither is on that's already stored more directly.) That's six |
1821 | * bits per dot. Bit number n represents the lines shown in dline_desc. |
1822 | * |
1823 | * Advanced Mode |
1824 | * Use edsf data structure to make equivalence classes of lines that are |
1825 | * known identical to or opposite to one another. |
1826 | */ |
1827 | |
1828 | /* The order the following are defined in is very important, see below. |
1829 | * The last two fields may seem non-obvious: they specify that when talking |
1830 | * about a square the dx and dy offsets should be added to the square coords to |
1831 | * get to the right dot. Where dx and dy are -1 this means that the dline |
1832 | * doesn't make sense for a square. */ |
1833 | /* XXX can this be done with a struct instead? */ |
1834 | #define DLINES \ |
1835 | DLINE(DLINE_UD, UP, DOWN, -1, -1) \ |
1836 | DLINE(DLINE_LR, LEFT, RIGHT, -1, -1) \ |
1837 | DLINE(DLINE_UR, UP, RIGHT, 0, 1) \ |
1838 | DLINE(DLINE_DL, DOWN, LEFT, 1, 0) \ |
1839 | DLINE(DLINE_UL, UP, LEFT, 1, 1) \ |
1840 | DLINE(DLINE_DR, DOWN, RIGHT, 0, 0) |
1841 | |
1842 | #define OPP_DLINE(dline_desc) ((dline_desc) ^ 1) |
1843 | |
1844 | enum dline_desc { |
1845 | #define DLINE(desc, dir1, dir2, dx, dy) \ |
1846 | desc, |
1847 | DLINES |
1848 | #undef DLINE |
1849 | }; |
1850 | |
1851 | struct dline { |
1852 | enum dline_desc desc; |
1853 | enum direction dir1, dir2; |
1854 | int dx, dy; |
1855 | }; |
1856 | |
1857 | const static struct dline dlines[] = { |
1858 | #define DLINE(desc, dir1, dir2, dx, dy) \ |
1859 | { desc, dir1, dir2, dx, dy }, |
1860 | DLINES |
1861 | #undef DLINE |
1862 | }; |
1863 | |
1864 | #define FORALL_DOT_DLINES(dl_iter) \ |
1865 | for (dl_iter = 0; dl_iter < lenof(dlines); ++dl_iter) |
1866 | |
1867 | #define FORALL_SQUARE_DLINES(dl_iter) \ |
1868 | for (dl_iter = 2; dl_iter < lenof(dlines); ++dl_iter) |
1869 | |
1870 | #define DL2STR(d) \ |
1871 | ((d==DLINE_UD) ? "DLINE_UD": \ |
1872 | (d==DLINE_LR) ? "DLINE_LR": \ |
1873 | (d==DLINE_UR) ? "DLINE_UR": \ |
1874 | (d==DLINE_DL) ? "DLINE_DL": \ |
1875 | (d==DLINE_UL) ? "DLINE_UL": \ |
1876 | (d==DLINE_DR) ? "DLINE_DR": \ |
1877 | "oops") |
1878 | |
5d868dc1 |
1879 | #define CHECK_DLINE_SENSIBLE(d) assert(dlines[(d)].dx != -1 && dlines[(d)].dy != -1) |
121aae4b |
1880 | |
1881 | /* This will fail an assertion if the directions handed to it are the same, as |
1882 | * no dline corresponds to that */ |
1883 | static enum dline_desc dline_desc_from_dirs(enum direction dir1, |
1884 | enum direction dir2) |
1885 | { |
121aae4b |
1886 | int i; |
1887 | |
1888 | assert (dir1 != dir2); |
1889 | |
1890 | for (i = 0; i < lenof(dlines); ++i) { |
1a739e2f |
1891 | if ((dir1 == dlines[i].dir1 && dir2 == dlines[i].dir2) || |
1892 | (dir1 == dlines[i].dir2 && dir2 == dlines[i].dir1)) { |
1893 | return dlines[i].desc; |
121aae4b |
1894 | } |
1895 | } |
1896 | |
1897 | assert(!"dline not found"); |
1898 | return DLINE_UD; /* placate compiler */ |
1899 | } |
1900 | |
1901 | /* The following functions allow you to get or set info about the selected |
1902 | * dline corresponding to the dot or square at [i,j]. You'll get an assertion |
1903 | * failure if you talk about a dline that doesn't exist, ie if you ask about |
1904 | * non-touching lines around a square. */ |
1a739e2f |
1905 | static int get_dot_dline(const game_state *state, const char *dline_array, |
121aae4b |
1906 | int i, int j, enum dline_desc desc) |
1907 | { |
1908 | /* fprintf(stderr, "get_dot_dline %p [%d,%d] %s\n", dline_array, i, j, DL2STR(desc)); */ |
1909 | return BIT_SET(dline_array[i + (state->w + 1) * j], desc); |
1910 | } |
1911 | |
1912 | static int set_dot_dline(game_state *state, char *dline_array, |
1913 | int i, int j, enum dline_desc desc |
1914 | #ifdef SHOW_WORKING |
1915 | , const char *reason |
1916 | #endif |
1917 | ) |
1918 | { |
1919 | int ret; |
1920 | ret = SET_BIT(dline_array[i + (state->w + 1) * j], desc); |
1921 | |
1922 | #ifdef SHOW_WORKING |
1923 | if (ret) |
1924 | fprintf(stderr, "set_dot_dline %p [%d,%d] %s (%s)\n", dline_array, i, j, DL2STR(desc), reason); |
1925 | #endif |
1926 | return ret; |
1927 | } |
1928 | |
1929 | static int get_square_dline(game_state *state, char *dline_array, |
1930 | int i, int j, enum dline_desc desc) |
1931 | { |
5d868dc1 |
1932 | CHECK_DLINE_SENSIBLE(desc); |
121aae4b |
1933 | /* fprintf(stderr, "get_square_dline %p [%d,%d] %s\n", dline_array, i, j, DL2STR(desc)); */ |
5d868dc1 |
1934 | return BIT_SET(dline_array[(i+dlines[desc].dx) + (state->w + 1) * (j+dlines[desc].dy)], |
121aae4b |
1935 | desc); |
1936 | } |
1937 | |
1938 | static int set_square_dline(game_state *state, char *dline_array, |
1939 | int i, int j, enum dline_desc desc |
1940 | #ifdef SHOW_WORKING |
1941 | , const char *reason |
1942 | #endif |
1943 | ) |
1944 | { |
121aae4b |
1945 | int ret; |
5d868dc1 |
1946 | CHECK_DLINE_SENSIBLE(desc); |
1947 | ret = SET_BIT(dline_array[(i+dlines[desc].dx) + (state->w + 1) * (j+dlines[desc].dy)], desc); |
121aae4b |
1948 | #ifdef SHOW_WORKING |
1949 | if (ret) |
1950 | fprintf(stderr, "set_square_dline %p [%d,%d] %s (%s)\n", dline_array, i, j, DL2STR(desc), reason); |
1951 | #endif |
1952 | return ret; |
1953 | } |
1954 | |
1955 | #ifdef SHOW_WORKING |
1956 | #define set_dot_dline(a, b, c, d, e) \ |
1957 | set_dot_dline(a, b, c, d, e, __FUNCTION__) |
1958 | #define set_square_dline(a, b, c, d, e) \ |
1959 | set_square_dline(a, b, c, d, e, __FUNCTION__) |
1960 | #endif |
1961 | |
1962 | static int set_dot_opp_dline(game_state *state, char *dline_array, |
1963 | int i, int j, enum dline_desc desc) |
1964 | { |
1965 | return set_dot_dline(state, dline_array, i, j, OPP_DLINE(desc)); |
1966 | } |
1967 | |
1968 | static int set_square_opp_dline(game_state *state, char *dline_array, |
1969 | int i, int j, enum dline_desc desc) |
1970 | { |
1971 | return set_square_dline(state, dline_array, i, j, OPP_DLINE(desc)); |
1972 | } |
1973 | |
1974 | /* Find out if both the lines in the given dline are UNKNOWN */ |
1975 | static int dline_both_unknown(const game_state *state, int i, int j, |
1976 | enum dline_desc desc) |
1977 | { |
121aae4b |
1978 | return |
5d868dc1 |
1979 | (get_line_status_from_point(state, i, j, dlines[desc].dir1) == LINE_UNKNOWN) && |
1980 | (get_line_status_from_point(state, i, j, dlines[desc].dir2) == LINE_UNKNOWN); |
121aae4b |
1981 | } |
1982 | |
1983 | #define SQUARE_DLINES \ |
1984 | HANDLE_DLINE(DLINE_UL, RIGHTOF_SQUARE, BELOW_SQUARE, 1, 1); \ |
1985 | HANDLE_DLINE(DLINE_UR, LEFTOF_SQUARE, BELOW_SQUARE, 0, 1); \ |
1986 | HANDLE_DLINE(DLINE_DL, RIGHTOF_SQUARE, ABOVE_SQUARE, 1, 0); \ |
1987 | HANDLE_DLINE(DLINE_DR, LEFTOF_SQUARE, ABOVE_SQUARE, 0, 0); |
1988 | |
1989 | #define DOT_DLINES \ |
1990 | HANDLE_DLINE(DLINE_UD, ABOVE_DOT, BELOW_DOT); \ |
1991 | HANDLE_DLINE(DLINE_LR, LEFTOF_DOT, RIGHTOF_DOT); \ |
1992 | HANDLE_DLINE(DLINE_UL, ABOVE_DOT, LEFTOF_DOT); \ |
1993 | HANDLE_DLINE(DLINE_UR, ABOVE_DOT, RIGHTOF_DOT); \ |
1994 | HANDLE_DLINE(DLINE_DL, BELOW_DOT, LEFTOF_DOT); \ |
1995 | HANDLE_DLINE(DLINE_DR, BELOW_DOT, RIGHTOF_DOT); |
1996 | |
1997 | static void array_setall(char *array, char from, char to, int len) |
1998 | { |
1999 | char *p = array, *p_old = p; |
2000 | int len_remaining = len; |
2001 | |
2002 | while ((p = memchr(p, from, len_remaining))) { |
2003 | *p = to; |
2004 | len_remaining -= p - p_old; |
2005 | p_old = p; |
2006 | } |
2007 | } |
6193da8d |
2008 | |
6193da8d |
2009 | |
6193da8d |
2010 | |
121aae4b |
2011 | static int get_line_status_from_point(const game_state *state, |
2012 | int x, int y, enum direction d) |
2013 | { |
2014 | switch (d) { |
2015 | case LEFT: |
2016 | return LEFTOF_DOT(state, x, y); |
2017 | case RIGHT: |
2018 | return RIGHTOF_DOT(state, x, y); |
2019 | case UP: |
2020 | return ABOVE_DOT(state, x, y); |
2021 | case DOWN: |
2022 | return BELOW_DOT(state, x, y); |
2023 | } |
6193da8d |
2024 | |
121aae4b |
2025 | return 0; |
2026 | } |
6193da8d |
2027 | |
121aae4b |
2028 | /* First and second args are coord offset from top left of square to one end |
2029 | * of line in question, third and fourth args are the direction from the first |
2030 | * end of the line to the second. Fifth arg is the direction of the line from |
2031 | * the coord offset position. |
2032 | * How confusing. |
2033 | */ |
2034 | #define SQUARE_LINES \ |
2035 | SQUARE_LINE( 0, 0, RIGHT, RIGHTOF_DOT, UP); \ |
2036 | SQUARE_LINE( 0, +1, RIGHT, RIGHTOF_DOT, DOWN); \ |
2037 | SQUARE_LINE( 0, 0, DOWN, BELOW_DOT, LEFT); \ |
2038 | SQUARE_LINE(+1, 0, DOWN, BELOW_DOT, RIGHT); |
2039 | |
2040 | /* Set pairs of lines around this square which are known to be identical to |
2041 | * the given line_state */ |
2042 | static int square_setall_identical(solver_state *sstate, int x, int y, |
2043 | enum line_state line_new) |
2044 | { |
2045 | /* can[dir] contains the canonical line associated with the line in |
2046 | * direction dir from the square in question. Similarly inv[dir] is |
2047 | * whether or not the line in question is inverse to its canonical |
2048 | * element. */ |
2049 | int can[4], inv[4], i, j; |
2050 | int retval = FALSE; |
6193da8d |
2051 | |
121aae4b |
2052 | i = 0; |
6193da8d |
2053 | |
121aae4b |
2054 | #if 0 |
2055 | fprintf(stderr, "Setting all identical unknown lines around square " |
2056 | "[%d,%d] to %d:\n", x, y, line_new); |
2057 | #endif |
6193da8d |
2058 | |
121aae4b |
2059 | #define SQUARE_LINE(dx, dy, linedir, dir_dot, sqdir) \ |
2060 | can[sqdir] = \ |
2061 | edsf_canonify(sstate->hard->linedsf, \ |
1a739e2f |
2062 | LINEDSF_INDEX(sstate->state, x+(dx), y+(dy), linedir), \ |
121aae4b |
2063 | &inv[sqdir]); |
2064 | |
2065 | SQUARE_LINES; |
6193da8d |
2066 | |
121aae4b |
2067 | #undef SQUARE_LINE |
6193da8d |
2068 | |
121aae4b |
2069 | for (j = 0; j < 4; ++j) { |
2070 | for (i = 0; i < 4; ++i) { |
2071 | if (i == j) |
2072 | continue; |
6193da8d |
2073 | |
121aae4b |
2074 | if (can[i] == can[j] && inv[i] == inv[j]) { |
2075 | |
2076 | /* Lines in directions i and j are identical. |
2077 | * Only do j now, we'll do i when the loop causes us to |
2078 | * consider {i,j} in the opposite order. */ |
2079 | #define SQUARE_LINE(dx, dy, dir, c, sqdir) \ |
2080 | if (j == sqdir) { \ |
1a739e2f |
2081 | retval = set_line_bydot(sstate, x+(dx), y+(dy), dir, line_new); \ |
121aae4b |
2082 | if (retval) { \ |
2083 | break; \ |
2084 | } \ |
6193da8d |
2085 | } |
121aae4b |
2086 | |
2087 | SQUARE_LINES; |
6193da8d |
2088 | |
121aae4b |
2089 | #undef SQUARE_LINE |
6193da8d |
2090 | } |
2091 | } |
6193da8d |
2092 | } |
2093 | |
121aae4b |
2094 | return retval; |
2095 | } |
2096 | |
2097 | #if 0 |
2098 | /* Set all identical lines passing through the current dot to the chosen line |
2099 | * state. (implicitly this only looks at UNKNOWN lines) */ |
2100 | static int dot_setall_identical(solver_state *sstate, int x, int y, |
2101 | enum line_state line_new) |
2102 | { |
2103 | /* The implementation of this is a little naughty but I can't see how to do |
2104 | * it elegantly any other way */ |
2105 | int can[4], inv[4], i, j; |
2106 | enum direction d; |
2107 | int retval = FALSE; |
2108 | |
2109 | for (d = 0; d < 4; ++d) { |
2110 | can[d] = edsf_canonify(sstate->hard->linedsf, |
2111 | LINEDSF_INDEX(sstate->state, x, y, d), |
2112 | inv+d); |
2113 | } |
2114 | |
2115 | for (j = 0; j < 4; ++j) { |
2116 | next_j: |
2117 | for (i = 0; i < j; ++i) { |
2118 | if (can[i] == can[j] && inv[i] == inv[j]) { |
2119 | /* Lines in directions i and j are identical */ |
2120 | if (get_line_status_from_point(sstate->state, x, y, j) == |
2121 | LINE_UNKNOWN) { |
2122 | set_line_bydot(sstate->state, x, y, j, |
2123 | line_new); |
2124 | retval = TRUE; |
2125 | goto next_j; |
2126 | } |
2127 | } |
6193da8d |
2128 | |
6193da8d |
2129 | } |
2130 | } |
2131 | |
121aae4b |
2132 | return retval; |
6193da8d |
2133 | } |
121aae4b |
2134 | #endif |
2135 | |
2136 | static int square_setboth_in_dline(solver_state *sstate, enum dline_desc dd, |
2137 | int i, int j, enum line_state line_new) |
2138 | { |
2139 | int retval = FALSE; |
5d868dc1 |
2140 | const struct dline dll = dlines[dd], *dl = &dll; |
121aae4b |
2141 | |
2142 | #if 0 |
2143 | fprintf(stderr, "square_setboth_in_dline %s [%d,%d] to %d\n", |
2144 | DL2STR(dd), i, j, line_new); |
2145 | #endif |
2146 | |
5d868dc1 |
2147 | CHECK_DLINE_SENSIBLE(dd); |
121aae4b |
2148 | |
2149 | retval |= |
2150 | set_line_bydot(sstate, i+dl->dx, j+dl->dy, dl->dir1, line_new); |
2151 | retval |= |
2152 | set_line_bydot(sstate, i+dl->dx, j+dl->dy, dl->dir2, line_new); |
6193da8d |
2153 | |
121aae4b |
2154 | return retval; |
2155 | } |
6193da8d |
2156 | |
121aae4b |
2157 | /* Call this function to register that the two unknown lines going into the dot |
2158 | * [x,y] are identical or opposite (depending on the value of 'inverse'). This |
2159 | * function will cause an assertion failure if anything other than exactly two |
2160 | * lines into the dot are unknown. |
2161 | * As usual returns TRUE if any progress was made, otherwise FALSE. */ |
2162 | static int dot_relate_2_unknowns(solver_state *sstate, int x, int y, int inverse) |
6193da8d |
2163 | { |
121aae4b |
2164 | enum direction d1=DOWN, d2=DOWN; /* Just to keep compiler quiet */ |
2165 | int dirs_set = 0; |
2166 | |
2167 | #define TRY_DIR(d) \ |
2168 | if (get_line_status_from_point(sstate->state, x, y, d) == \ |
2169 | LINE_UNKNOWN) { \ |
2170 | if (dirs_set == 0) \ |
2171 | d1 = d; \ |
2172 | else { \ |
2173 | assert(dirs_set == 1); \ |
2174 | d2 = d; \ |
2175 | } \ |
2176 | dirs_set++; \ |
2177 | } while (0) |
6193da8d |
2178 | |
121aae4b |
2179 | TRY_DIR(UP); |
2180 | TRY_DIR(DOWN); |
2181 | TRY_DIR(LEFT); |
2182 | TRY_DIR(RIGHT); |
2183 | #undef TRY_DIR |
6193da8d |
2184 | |
121aae4b |
2185 | assert(dirs_set == 2); |
2186 | assert(d1 != d2); |
6193da8d |
2187 | |
121aae4b |
2188 | #if 0 |
2189 | fprintf(stderr, "Lines in direction %s and %s from dot [%d,%d] are %s\n", |
2190 | DIR2STR(d1), DIR2STR(d2), x, y, inverse?"opposite":"the same"); |
2191 | #endif |
6193da8d |
2192 | |
121aae4b |
2193 | return merge_lines(sstate, x, y, d1, x, y, d2, inverse); |
6193da8d |
2194 | } |
2195 | |
121aae4b |
2196 | /* Very similar to dot_relate_2_unknowns. */ |
2197 | static int square_relate_2_unknowns(solver_state *sstate, int x, int y, int inverse) |
6193da8d |
2198 | { |
121aae4b |
2199 | enum direction d1=DOWN, d2=DOWN; |
2200 | int x1=-1, y1=-1, x2=-1, y2=-1; |
2201 | int dirs_set = 0; |
6193da8d |
2202 | |
121aae4b |
2203 | #if 0 |
2204 | fprintf(stderr, "2 unknowns around square [%d,%d] are %s\n", |
2205 | x, y, inverse?"opposite":"the same"); |
2206 | #endif |
6193da8d |
2207 | |
121aae4b |
2208 | #define TRY_DIR(i, j, d, dir_sq) \ |
2209 | do { \ |
2210 | if (dir_sq(sstate->state, x, y) == LINE_UNKNOWN) { \ |
2211 | if (dirs_set == 0) { \ |
2212 | d1 = d; x1 = i; y1 = j; \ |
2213 | } else { \ |
2214 | assert(dirs_set == 1); \ |
2215 | d2 = d; x2 = i; y2 = j; \ |
2216 | } \ |
2217 | dirs_set++; \ |
2218 | } \ |
2219 | } while (0) |
6193da8d |
2220 | |
121aae4b |
2221 | TRY_DIR(x, y, RIGHT, ABOVE_SQUARE); |
2222 | TRY_DIR(x, y, DOWN, LEFTOF_SQUARE); |
2223 | TRY_DIR(x+1, y, DOWN, RIGHTOF_SQUARE); |
2224 | TRY_DIR(x, y+1, RIGHT, BELOW_SQUARE); |
2225 | #undef TRY_DIR |
2226 | |
2227 | assert(dirs_set == 2); |
2228 | |
2229 | #if 0 |
2230 | fprintf(stderr, "Line in direction %s from dot [%d,%d] and line in direction %s from dot [%2d,%2d] are %s\n", |
2231 | DIR2STR(d1), x1, y1, DIR2STR(d2), x2, y2, inverse?"opposite":"the same"); |
2232 | #endif |
2233 | |
2234 | return merge_lines(sstate, x1, y1, d1, x2, y2, d2, inverse); |
2235 | } |
2236 | |
2237 | /* Figure out if any dlines can be 'collapsed' (and do so if they can). This |
2238 | * can happen if one of the lines is known and due to the dline status this |
2239 | * tells us state of the other, or if there's an interaction with the linedsf |
2240 | * (ie if atmostone is set for a dline and the lines are known identical they |
2241 | * must both be LINE_NO, etc). XXX at the moment only the former is |
2242 | * implemented, and indeed the latter should be implemented in the hard mode |
2243 | * solver only. |
2244 | */ |
2245 | static int dot_collapse_dlines(solver_state *sstate, int i, int j) |
2246 | { |
2247 | int progress = FALSE; |
2248 | enum direction dir1, dir2; |
2249 | int dir1st; |
2250 | int dlset; |
2251 | game_state *state = sstate->state; |
2252 | enum dline_desc dd; |
2253 | |
2254 | for (dir1 = 0; dir1 < 4; dir1++) { |
2255 | dir1st = get_line_status_from_point(state, i, j, dir1); |
2256 | if (dir1st == LINE_UNKNOWN) |
2257 | continue; |
2258 | /* dir2 iterates over the whole range rather than starting at dir1+1 |
2259 | * because test below is asymmetric */ |
2260 | for (dir2 = 0; dir2 < 4; dir2++) { |
2261 | if (dir1 == dir2) |
2262 | continue; |
2263 | |
2264 | if ((i == 0 && (dir1 == LEFT || dir2 == LEFT)) || |
2265 | (j == 0 && (dir1 == UP || dir2 == UP)) || |
2266 | (i == state->w && (dir1 == RIGHT || dir2 == RIGHT)) || |
2267 | (j == state->h && (dir1 == DOWN || dir2 == DOWN))) { |
2268 | continue; |
2269 | } |
2270 | |
2271 | #if 0 |
2272 | fprintf(stderr, "dot_collapse_dlines [%d,%d], %s %s\n", i, j, |
2273 | DIR2STR(dir1), DIR2STR(dir2)); |
2274 | #endif |
2275 | |
2276 | if (get_line_status_from_point(state, i, j, dir2) == |
2277 | LINE_UNKNOWN) { |
2278 | dd = dline_desc_from_dirs(dir1, dir2); |
2279 | |
2280 | dlset = get_dot_dline(state, sstate->normal->dot_atmostone, i, j, dd); |
2281 | if (dlset && dir1st == LINE_YES) { |
2282 | /* fprintf(stderr, "setting %s to NO\n", DIR2STR(dir2)); */ |
2283 | progress |= |
2284 | set_line_bydot(sstate, i, j, dir2, LINE_NO); |
2285 | } |
2286 | |
2287 | dlset = get_dot_dline(state, sstate->normal->dot_atleastone, i, j, dd); |
2288 | if (dlset && dir1st == LINE_NO) { |
2289 | /* fprintf(stderr, "setting %s to YES\n", DIR2STR(dir2)); */ |
2290 | progress |= |
2291 | set_line_bydot(sstate, i, j, dir2, LINE_YES); |
2292 | } |
2293 | } |
6193da8d |
2294 | } |
2295 | } |
2296 | |
121aae4b |
2297 | return progress; |
6193da8d |
2298 | } |
2299 | |
121aae4b |
2300 | /* |
2301 | * These are the main solver functions. |
2302 | * |
2303 | * Their return values are diff values corresponding to the lowest mode solver |
2304 | * that would notice the work that they have done. For example if the normal |
2305 | * mode solver adds actual lines or crosses, it will return DIFF_EASY as the |
2306 | * easy mode solver might be able to make progress using that. It doesn't make |
2307 | * sense for one of them to return a diff value higher than that of the |
2308 | * function itself. |
2309 | * |
2310 | * Each function returns the lowest value it can, as early as possible, in |
2311 | * order to try and pass as much work as possible back to the lower level |
2312 | * solvers which progress more quickly. |
2313 | */ |
6193da8d |
2314 | |
121aae4b |
2315 | /* PROPOSED NEW DESIGN: |
2316 | * We have a work queue consisting of 'events' notifying us that something has |
2317 | * happened that a particular solver mode might be interested in. For example |
2318 | * the hard mode solver might do something that helps the normal mode solver at |
2319 | * dot [x,y] in which case it will enqueue an event recording this fact. Then |
2320 | * we pull events off the work queue, and hand each in turn to the solver that |
2321 | * is interested in them. If a solver reports that it failed we pass the same |
2322 | * event on to progressively more advanced solvers and the loop detector. Once |
2323 | * we've exhausted an event, or it has helped us progress, we drop it and |
2324 | * continue to the next one. The events are sorted first in order of solver |
2325 | * complexity (easy first) then order of insertion (oldest first). |
2326 | * Once we run out of events we loop over each permitted solver in turn |
2327 | * (easiest first) until either a deduction is made (and an event therefore |
2328 | * emerges) or no further deductions can be made (in which case we've failed). |
2329 | * |
2330 | * QUESTIONS: |
2331 | * * How do we 'loop over' a solver when both dots and squares are concerned. |
2332 | * Answer: first all squares then all dots. |
2333 | */ |
2334 | |
2335 | static int easy_mode_deductions(solver_state *sstate) |
6193da8d |
2336 | { |
121aae4b |
2337 | int i, j, h, w, current_yes, current_no; |
2338 | game_state *state; |
1a739e2f |
2339 | int diff = DIFF_MAX; |
6193da8d |
2340 | |
121aae4b |
2341 | state = sstate->state; |
2342 | h = state->h; |
2343 | w = state->w; |
2344 | |
2345 | /* Per-square deductions */ |
2346 | FORALL_SQUARES(state, i, j) { |
2347 | if (sstate->square_solved[SQUARE_INDEX(state, i, j)]) |
2348 | continue; |
6193da8d |
2349 | |
121aae4b |
2350 | current_yes = SQUARE_YES_COUNT(sstate, i, j); |
2351 | current_no = SQUARE_NO_COUNT(sstate, i, j); |
c0eb17ce |
2352 | |
121aae4b |
2353 | if (current_yes + current_no == 4) { |
2354 | sstate->square_solved[SQUARE_INDEX(state, i, j)] = TRUE; |
2355 | /* diff = min(diff, DIFF_EASY); */ |
2356 | continue; |
2357 | } |
6193da8d |
2358 | |
121aae4b |
2359 | if (CLUE_AT(state, i, j) < 0) |
2360 | continue; |
6193da8d |
2361 | |
121aae4b |
2362 | if (CLUE_AT(state, i, j) < current_yes) { |
2363 | #if 0 |
2364 | fprintf(stderr, "detected error [%d,%d] in %s at line %d\n", i, j, __FUNCTION__, __LINE__); |
2365 | #endif |
2366 | sstate->solver_status = SOLVER_MISTAKE; |
2367 | return DIFF_EASY; |
2368 | } |
2369 | if (CLUE_AT(state, i, j) == current_yes) { |
2370 | if (square_setall(sstate, i, j, LINE_UNKNOWN, LINE_NO)) |
2371 | diff = min(diff, DIFF_EASY); |
2372 | sstate->square_solved[SQUARE_INDEX(state, i, j)] = TRUE; |
2373 | continue; |
2374 | } |
c0eb17ce |
2375 | |
121aae4b |
2376 | if (4 - CLUE_AT(state, i, j) < current_no) { |
2377 | #if 0 |
2378 | fprintf(stderr, "detected error [%d,%d] in %s at line %d\n", i, j, __FUNCTION__, __LINE__); |
2379 | #endif |
2380 | sstate->solver_status = SOLVER_MISTAKE; |
2381 | return DIFF_EASY; |
2382 | } |
2383 | if (4 - CLUE_AT(state, i, j) == current_no) { |
2384 | if (square_setall(sstate, i, j, LINE_UNKNOWN, LINE_YES)) |
2385 | diff = min(diff, DIFF_EASY); |
2386 | sstate->square_solved[SQUARE_INDEX(state, i, j)] = TRUE; |
2387 | continue; |
2388 | } |
2389 | } |
6193da8d |
2390 | |
121aae4b |
2391 | check_caches(sstate); |
6193da8d |
2392 | |
121aae4b |
2393 | /* Per-dot deductions */ |
2394 | FORALL_DOTS(state, i, j) { |
2395 | if (sstate->dot_solved[DOT_INDEX(state, i, j)]) |
2396 | continue; |
c0eb17ce |
2397 | |
121aae4b |
2398 | switch (DOT_YES_COUNT(sstate, i, j)) { |
2399 | case 0: |
2400 | switch (DOT_NO_COUNT(sstate, i, j)) { |
2401 | case 3: |
2402 | #if 0 |
2403 | fprintf(stderr, "dot [%d,%d]: 0 yes, 3 no\n", i, j); |
2404 | #endif |
2405 | dot_setall(sstate, i, j, LINE_UNKNOWN, LINE_NO); |
2406 | diff = min(diff, DIFF_EASY); |
2407 | /* fall through */ |
2408 | case 4: |
2409 | sstate->dot_solved[DOT_INDEX(state, i, j)] = TRUE; |
2410 | break; |
6193da8d |
2411 | } |
121aae4b |
2412 | break; |
2413 | case 1: |
2414 | switch (DOT_NO_COUNT(sstate, i, j)) { |
2415 | case 2: /* 1 yes, 2 no */ |
2416 | #if 0 |
2417 | fprintf(stderr, "dot [%d,%d]: 1 yes, 2 no\n", i, j); |
2418 | #endif |
2419 | dot_setall(sstate, i, j, LINE_UNKNOWN, LINE_YES); |
2420 | diff = min(diff, DIFF_EASY); |
2421 | sstate->dot_solved[DOT_INDEX(state, i, j)] = TRUE; |
2422 | break; |
2423 | case 3: /* 1 yes, 3 no */ |
2424 | #if 0 |
2425 | fprintf(stderr, "detected error [%d,%d] in %s at line %d\n", i, j, __FUNCTION__, __LINE__); |
2426 | #endif |
2427 | sstate->solver_status = SOLVER_MISTAKE; |
2428 | return DIFF_EASY; |
6193da8d |
2429 | } |
121aae4b |
2430 | break; |
2431 | case 2: |
2432 | #if 0 |
2433 | fprintf(stderr, "dot [%d,%d]: 2 yes\n", i, j); |
2434 | #endif |
2435 | dot_setall(sstate, i, j, LINE_UNKNOWN, LINE_NO); |
2436 | diff = min(diff, DIFF_EASY); |
2437 | sstate->dot_solved[DOT_INDEX(state, i, j)] = TRUE; |
2438 | break; |
2439 | case 3: |
2440 | case 4: |
2441 | #if 0 |
2442 | fprintf(stderr, "detected error [%d,%d] in %s at line %d\n", i, j, __FUNCTION__, __LINE__); |
2443 | #endif |
2444 | sstate->solver_status = SOLVER_MISTAKE; |
2445 | return DIFF_EASY; |
6193da8d |
2446 | } |
2447 | } |
6193da8d |
2448 | |
121aae4b |
2449 | check_caches(sstate); |
6193da8d |
2450 | |
121aae4b |
2451 | return diff; |
6193da8d |
2452 | } |
2453 | |
121aae4b |
2454 | static int normal_mode_deductions(solver_state *sstate) |
6193da8d |
2455 | { |
121aae4b |
2456 | int i, j; |
2457 | game_state *state = sstate->state; |
2458 | enum dline_desc dd; |
1a739e2f |
2459 | int diff = DIFF_MAX; |
6193da8d |
2460 | |
121aae4b |
2461 | FORALL_SQUARES(state, i, j) { |
2462 | if (sstate->square_solved[SQUARE_INDEX(state, i, j)]) |
6193da8d |
2463 | continue; |
121aae4b |
2464 | |
2465 | if (CLUE_AT(state, i, j) < 0) |
6193da8d |
2466 | continue; |
121aae4b |
2467 | |
2468 | switch (CLUE_AT(state, i, j)) { |
2469 | case 1: |
2470 | #if 0 |
2471 | fprintf(stderr, "clue [%d,%d] is 1, doing dline ops\n", |
2472 | i, j); |
2473 | #endif |
2474 | FORALL_SQUARE_DLINES(dd) { |
2475 | /* At most one of any DLINE can be set */ |
2476 | if (set_square_dline(state, |
2477 | sstate->normal->dot_atmostone, |
2478 | i, j, dd)) { |
2479 | diff = min(diff, DIFF_NORMAL); |
2480 | } |
2481 | |
2482 | if (get_square_dline(state, |
2483 | sstate->normal->dot_atleastone, |
2484 | i, j, dd)) { |
2485 | /* This DLINE provides enough YESes to solve the clue */ |
2486 | if (square_setboth_in_dline(sstate, OPP_DLINE(dd), |
2487 | i, j, LINE_NO)) { |
2488 | diff = min(diff, DIFF_EASY); |
2489 | } |
2490 | } |
2491 | } |
2492 | |
2493 | break; |
2494 | case 2: |
2495 | /* If at least one of one DLINE is set, at most one |
2496 | * of the opposing one is and vice versa */ |
2497 | #if 0 |
2498 | fprintf(stderr, "clue [%d,%d] is 2, doing dline ops\n", |
2499 | i, j); |
2500 | #endif |
2501 | FORALL_SQUARE_DLINES(dd) { |
2502 | if (get_square_dline(state, |
2503 | sstate->normal->dot_atmostone, |
2504 | i, j, dd)) { |
2505 | if (set_square_opp_dline(state, |
2506 | sstate->normal->dot_atleastone, |
2507 | i, j, dd)) { |
2508 | diff = min(diff, DIFF_NORMAL); |
2509 | } |
2510 | } |
2511 | if (get_square_dline(state, |
2512 | sstate->normal->dot_atleastone, |
2513 | i, j, dd)) { |
2514 | if (set_square_opp_dline(state, |
2515 | sstate->normal->dot_atmostone, |
2516 | i, j, dd)) { |
2517 | diff = min(diff, DIFF_NORMAL); |
2518 | } |
2519 | } |
2520 | } |
2521 | break; |
2522 | case 3: |
2523 | #if 0 |
2524 | fprintf(stderr, "clue [%d,%d] is 3, doing dline ops\n", |
2525 | i, j); |
2526 | #endif |
2527 | FORALL_SQUARE_DLINES(dd) { |
2528 | /* At least one of any DLINE must be set */ |
2529 | if (set_square_dline(state, |
2530 | sstate->normal->dot_atleastone, |
2531 | i, j, dd)) { |
2532 | diff = min(diff, DIFF_NORMAL); |
2533 | } |
2534 | |
2535 | if (get_square_dline(state, |
2536 | sstate->normal->dot_atmostone, |
2537 | i, j, dd)) { |
2538 | /* This DLINE provides enough NOs to solve the clue */ |
2539 | if (square_setboth_in_dline(sstate, OPP_DLINE(dd), |
2540 | i, j, LINE_YES)) { |
2541 | diff = min(diff, DIFF_EASY); |
2542 | } |
2543 | } |
2544 | } |
2545 | break; |
6193da8d |
2546 | } |
6193da8d |
2547 | } |
2548 | |
121aae4b |
2549 | check_caches(sstate); |
6193da8d |
2550 | |
121aae4b |
2551 | if (diff < DIFF_NORMAL) |
2552 | return diff; |
6193da8d |
2553 | |
121aae4b |
2554 | FORALL_DOTS(state, i, j) { |
2555 | if (sstate->dot_solved[DOT_INDEX(state, i, j)]) |
2556 | continue; |
6193da8d |
2557 | |
121aae4b |
2558 | #if 0 |
2559 | text = game_text_format(state); |
2560 | fprintf(stderr, "-----------------\n%s", text); |
2561 | sfree(text); |
2562 | #endif |
6193da8d |
2563 | |
121aae4b |
2564 | switch (DOT_YES_COUNT(sstate, i, j)) { |
2565 | case 0: |
2566 | switch (DOT_NO_COUNT(sstate, i, j)) { |
2567 | case 1: |
2568 | /* Make note that at most one of each unknown DLINE |
2569 | * is YES */ |
2570 | break; |
2571 | } |
2572 | break; |
6193da8d |
2573 | |
121aae4b |
2574 | case 1: |
2575 | switch (DOT_NO_COUNT(sstate, i, j)) { |
2576 | case 1: |
2577 | /* 1 yes, 1 no, so exactly one of unknowns is |
2578 | * yes */ |
2579 | #if 0 |
2580 | fprintf(stderr, "dot [%d,%d]: 1 yes, 1 no\n", i, j); |
2581 | #endif |
2582 | FORALL_DOT_DLINES(dd) { |
2583 | if (dline_both_unknown(state, |
2584 | i, j, dd)) { |
2585 | if (set_dot_dline(state, |
2586 | sstate->normal->dot_atleastone, |
2587 | i, j, dd)) { |
2588 | diff = min(diff, DIFF_NORMAL); |
2589 | } |
2590 | } |
2591 | } |
6193da8d |
2592 | |
121aae4b |
2593 | /* fall through */ |
2594 | case 0: |
2595 | #if 0 |
2596 | fprintf(stderr, "dot [%d,%d]: 1 yes, 0 or 1 no\n", i, j); |
2597 | #endif |
2598 | /* 1 yes, fewer than 2 no, so at most one of |
2599 | * unknowns is yes */ |
2600 | FORALL_DOT_DLINES(dd) { |
2601 | if (dline_both_unknown(state, |
2602 | i, j, dd)) { |
2603 | if (set_dot_dline(state, |
2604 | sstate->normal->dot_atmostone, |
2605 | i, j, dd)) { |
2606 | diff = min(diff, DIFF_NORMAL); |
2607 | } |
2608 | } |
2609 | } |
2610 | break; |
6193da8d |
2611 | } |
121aae4b |
2612 | break; |
2613 | } |
6193da8d |
2614 | |
121aae4b |
2615 | /* DLINE deductions that don't depend on the exact number of |
2616 | * LINE_YESs or LINE_NOs */ |
2617 | |
2618 | /* If at least one of a dline in a dot is YES, at most one |
2619 | * of the opposite dline to that dot must be YES. */ |
2620 | FORALL_DOT_DLINES(dd) { |
2621 | if (get_dot_dline(state, |
2622 | sstate->normal->dot_atleastone, |
2623 | i, j, dd)) { |
2624 | if (set_dot_opp_dline(state, |
2625 | sstate->normal->dot_atmostone, |
2626 | i, j, dd)) { |
2627 | diff = min(diff, DIFF_NORMAL); |
2628 | } |
6193da8d |
2629 | } |
6193da8d |
2630 | } |
6193da8d |
2631 | |
121aae4b |
2632 | if (dot_collapse_dlines(sstate, i, j)) |
2633 | diff = min(diff, DIFF_EASY); |
2634 | } |
2635 | check_caches(sstate); |
6193da8d |
2636 | |
121aae4b |
2637 | return diff; |
6193da8d |
2638 | } |
2639 | |
121aae4b |
2640 | static int hard_mode_deductions(solver_state *sstate) |
6193da8d |
2641 | { |
121aae4b |
2642 | int i, j, a, b, s; |
2643 | game_state *state = sstate->state; |
2644 | const int h=state->h, w=state->w; |
2645 | enum direction dir1, dir2; |
2646 | int can1, can2, inv1, inv2; |
1a739e2f |
2647 | int diff = DIFF_MAX; |
121aae4b |
2648 | enum dline_desc dd; |
2649 | |
2650 | FORALL_SQUARES(state, i, j) { |
2651 | if (sstate->square_solved[SQUARE_INDEX(state, i, j)]) |
2652 | continue; |
6193da8d |
2653 | |
121aae4b |
2654 | switch (CLUE_AT(state, i, j)) { |
2655 | case -1: |
2656 | continue; |
2657 | |
2658 | case 1: |
2659 | if (square_setall_identical(sstate, i, j, LINE_NO)) |
2660 | diff = min(diff, DIFF_EASY); |
2661 | break; |
2662 | case 3: |
2663 | if (square_setall_identical(sstate, i, j, LINE_YES)) |
2664 | diff = min(diff, DIFF_EASY); |
2665 | break; |
2666 | } |
2667 | |
2668 | if (SQUARE_YES_COUNT(sstate, i, j) + |
2669 | SQUARE_NO_COUNT(sstate, i, j) == 2) { |
2670 | /* There are exactly two unknown lines bordering this |
2671 | * square. */ |
2672 | if (SQUARE_YES_COUNT(sstate, i, j) + 1 == |
2673 | CLUE_AT(state, i, j)) { |
2674 | /* They must be different */ |
2675 | if (square_relate_2_unknowns(sstate, i, j, TRUE)) |
2676 | diff = min(diff, DIFF_HARD); |
2677 | } |
2678 | } |
6193da8d |
2679 | } |
2680 | |
121aae4b |
2681 | check_caches(sstate); |
6193da8d |
2682 | |
121aae4b |
2683 | FORALL_DOTS(state, i, j) { |
2684 | if (DOT_YES_COUNT(sstate, i, j) == 1 && |
2685 | DOT_NO_COUNT(sstate, i, j) == 1) { |
2686 | if (dot_relate_2_unknowns(sstate, i, j, TRUE)) |
2687 | diff = min(diff, DIFF_HARD); |
2688 | continue; |
2689 | } |
6193da8d |
2690 | |
121aae4b |
2691 | if (DOT_YES_COUNT(sstate, i, j) == 0 && |
2692 | DOT_NO_COUNT(sstate, i, j) == 2) { |
2693 | if (dot_relate_2_unknowns(sstate, i, j, FALSE)) |
2694 | diff = min(diff, DIFF_HARD); |
2695 | continue; |
2696 | } |
2697 | } |
6193da8d |
2698 | |
121aae4b |
2699 | /* If two lines into a dot are related, the other two lines into that dot |
2700 | * are related in the same way. */ |
6193da8d |
2701 | |
121aae4b |
2702 | /* iter over points that aren't on edges */ |
2703 | for (i = 1; i < w; ++i) { |
2704 | for (j = 1; j < h; ++j) { |
2705 | if (sstate->dot_solved[DOT_INDEX(state, i, j)]) |
2706 | continue; |
6193da8d |
2707 | |
121aae4b |
2708 | /* iter over directions */ |
2709 | for (dir1 = 0; dir1 < 4; ++dir1) { |
2710 | for (dir2 = dir1+1; dir2 < 4; ++dir2) { |
2711 | /* canonify both lines */ |
2712 | can1 = edsf_canonify |
2713 | (sstate->hard->linedsf, |
2714 | LINEDSF_INDEX(state, i, j, dir1), |
2715 | &inv1); |
2716 | can2 = edsf_canonify |
2717 | (sstate->hard->linedsf, |
2718 | LINEDSF_INDEX(state, i, j, dir2), |
2719 | &inv2); |
2720 | /* merge opposite lines */ |
2721 | if (can1 == can2) { |
2722 | if (merge_lines(sstate, |
2723 | i, j, OPP_DIR(dir1), |
2724 | i, j, OPP_DIR(dir2), |
2725 | inv1 ^ inv2)) { |
2726 | diff = min(diff, DIFF_HARD); |
2727 | } |
2728 | } |
2729 | } |
6193da8d |
2730 | } |
2731 | } |
2732 | } |
2733 | |
121aae4b |
2734 | /* If the state of a line is known, deduce the state of its canonical line |
2735 | * too. */ |
2736 | FORALL_DOTS(state, i, j) { |
2737 | /* Do this even if the dot we're on is solved */ |
2738 | if (i < w) { |
2739 | can1 = edsf_canonify(sstate->hard->linedsf, |
2740 | LINEDSF_INDEX(state, i, j, RIGHT), |
2741 | &inv1); |
2742 | linedsf_deindex(state, can1, &a, &b, &dir1); |
2743 | s = RIGHTOF_DOT(state, i, j); |
2744 | if (s != LINE_UNKNOWN) |
2745 | { |
2746 | if (set_line_bydot(sstate, a, b, dir1, inv1 ? OPP(s) : s)) |
2747 | diff = min(diff, DIFF_EASY); |
2748 | } |
2749 | } |
2750 | if (j < h) { |
2751 | can1 = edsf_canonify(sstate->hard->linedsf, |
2752 | LINEDSF_INDEX(state, i, j, DOWN), |
2753 | &inv1); |
2754 | linedsf_deindex(state, can1, &a, &b, &dir1); |
2755 | s = BELOW_DOT(state, i, j); |
2756 | if (s != LINE_UNKNOWN) |
2757 | { |
2758 | if (set_line_bydot(sstate, a, b, dir1, inv1 ? OPP(s) : s)) |
2759 | diff = min(diff, DIFF_EASY); |
6193da8d |
2760 | } |
2761 | } |
2762 | } |
2763 | |
121aae4b |
2764 | /* Interactions between dline and linedsf */ |
2765 | FORALL_DOTS(state, i, j) { |
2766 | if (sstate->dot_solved[DOT_INDEX(state, i, j)]) |
2767 | continue; |
6193da8d |
2768 | |
121aae4b |
2769 | FORALL_DOT_DLINES(dd) { |
5d868dc1 |
2770 | const struct dline dll = dlines[dd], *dl = &dll; |
121aae4b |
2771 | if (i == 0 && (dl->dir1 == LEFT || dl->dir2 == LEFT)) |
2772 | continue; |
2773 | if (i == w && (dl->dir1 == RIGHT || dl->dir2 == RIGHT)) |
2774 | continue; |
2775 | if (j == 0 && (dl->dir1 == UP || dl->dir2 == UP)) |
2776 | continue; |
2777 | if (j == h && (dl->dir1 == DOWN || dl->dir2 == DOWN)) |
2778 | continue; |
6193da8d |
2779 | |
121aae4b |
2780 | if (get_dot_dline(state, sstate->normal->dot_atleastone, |
2781 | i, j, dd) && |
2782 | get_dot_dline(state, sstate->normal->dot_atmostone, |
2783 | i, j, dd)) { |
2784 | /* atleastone && atmostone => inverse */ |
2785 | if (merge_lines(sstate, i, j, dl->dir1, i, j, dl->dir2, 1)) { |
2786 | diff = min(diff, DIFF_HARD); |
2787 | } |
2788 | } else { |
2789 | /* don't have atleastone and atmostone for this dline */ |
2790 | can1 = edsf_canonify(sstate->hard->linedsf, |
2791 | LINEDSF_INDEX(state, i, j, dl->dir1), |
2792 | &inv1); |
2793 | can2 = edsf_canonify(sstate->hard->linedsf, |
2794 | LINEDSF_INDEX(state, i, j, dl->dir2), |
2795 | &inv2); |
2796 | if (can1 == can2) { |
2797 | if (inv1 == inv2) { |
2798 | /* identical => collapse dline */ |
2799 | if (get_dot_dline(state, |
2800 | sstate->normal->dot_atleastone, |
2801 | i, j, dd)) { |
2802 | if (set_line_bydot(sstate, i, j, |
2803 | dl->dir1, LINE_YES)) { |
2804 | diff = min(diff, DIFF_EASY); |
2805 | } |
2806 | if (set_line_bydot(sstate, i, j, |
2807 | dl->dir2, LINE_YES)) { |
2808 | diff = min(diff, DIFF_EASY); |
2809 | } |
2810 | } else if (get_dot_dline(state, |
2811 | sstate->normal->dot_atmostone, |
2812 | i, j, dd)) { |
2813 | if (set_line_bydot(sstate, i, j, |
2814 | dl->dir1, LINE_NO)) { |
2815 | diff = min(diff, DIFF_EASY); |
2816 | } |
2817 | if (set_line_bydot(sstate, i, j, |
2818 | dl->dir2, LINE_NO)) { |
2819 | diff = min(diff, DIFF_EASY); |
2820 | } |
2821 | } |
2822 | } else { |
2823 | /* inverse => atleastone && atmostone */ |
2824 | if (set_dot_dline(state, |
2825 | sstate->normal->dot_atleastone, |
2826 | i, j, dd)) { |
2827 | diff = min(diff, DIFF_NORMAL); |
2828 | } |
2829 | if (set_dot_dline(state, |
2830 | sstate->normal->dot_atmostone, |
2831 | i, j, dd)) { |
2832 | diff = min(diff, DIFF_NORMAL); |
2833 | } |
2834 | } |
2835 | } |
2836 | } |
2837 | } |
2838 | } |
2839 | |
2840 | /* If the state of the canonical line for line 'l' is known, deduce the |
2841 | * state of 'l' */ |
2842 | FORALL_DOTS(state, i, j) { |
2843 | if (sstate->dot_solved[DOT_INDEX(state, i, j)]) |
2844 | continue; |
6193da8d |
2845 | |
121aae4b |
2846 | if (i < w) { |
2847 | can1 = edsf_canonify(sstate->hard->linedsf, |
2848 | LINEDSF_INDEX(state, i, j, RIGHT), |
2849 | &inv1); |
2850 | linedsf_deindex(state, can1, &a, &b, &dir1); |
2851 | s = get_line_status_from_point(state, a, b, dir1); |
2852 | if (s != LINE_UNKNOWN) |
2853 | { |
2854 | if (set_line_bydot(sstate, i, j, RIGHT, inv1 ? OPP(s) : s)) |
2855 | diff = min(diff, DIFF_EASY); |
2856 | } |
2857 | } |
2858 | if (j < h) { |
2859 | can1 = edsf_canonify(sstate->hard->linedsf, |
2860 | LINEDSF_INDEX(state, i, j, DOWN), |
2861 | &inv1); |
2862 | linedsf_deindex(state, can1, &a, &b, &dir1); |
2863 | s = get_line_status_from_point(state, a, b, dir1); |
2864 | if (s != LINE_UNKNOWN) |
2865 | { |
2866 | if (set_line_bydot(sstate, i, j, DOWN, inv1 ? OPP(s) : s)) |
2867 | diff = min(diff, DIFF_EASY); |
2868 | } |
2869 | } |
2870 | } |
6193da8d |
2871 | |
121aae4b |
2872 | return diff; |
2873 | } |
6193da8d |
2874 | |
121aae4b |
2875 | static int loop_deductions(solver_state *sstate) |
2876 | { |
2877 | int edgecount = 0, clues = 0, satclues = 0, sm1clues = 0; |
2878 | game_state *state = sstate->state; |
2879 | int shortest_chainlen = DOT_COUNT(state); |
2880 | int loop_found = FALSE; |
2881 | int d; |
2882 | int dots_connected; |
2883 | int progress = FALSE; |
2884 | int i, j; |
6193da8d |
2885 | |
121aae4b |
2886 | /* |
2887 | * Go through the grid and update for all the new edges. |
2888 | * Since merge_dots() is idempotent, the simplest way to |
2889 | * do this is just to update for _all_ the edges. |
2890 | * |
2891 | * Also, while we're here, we count the edges, count the |
2892 | * clues, count the satisfied clues, and count the |
2893 | * satisfied-minus-one clues. |
2894 | */ |
2895 | FORALL_DOTS(state, i, j) { |
2896 | if (RIGHTOF_DOT(state, i, j) == LINE_YES) { |
2897 | loop_found |= merge_dots(sstate, i, j, i+1, j); |
2898 | edgecount++; |
2899 | } |
2900 | if (BELOW_DOT(state, i, j) == LINE_YES) { |
2901 | loop_found |= merge_dots(sstate, i, j, i, j+1); |
2902 | edgecount++; |
2903 | } |
6193da8d |
2904 | |
121aae4b |
2905 | if (CLUE_AT(state, i, j) >= 0) { |
2906 | int c = CLUE_AT(state, i, j); |
2907 | int o = SQUARE_YES_COUNT(sstate, i, j); |
2908 | if (o == c) |
2909 | satclues++; |
2910 | else if (o == c-1) |
2911 | sm1clues++; |
2912 | clues++; |
2913 | } |
2914 | } |
6193da8d |
2915 | |
121aae4b |
2916 | for (i = 0; i < DOT_COUNT(state); ++i) { |
2917 | dots_connected = |
2918 | sstate->looplen[dsf_canonify(sstate->dotdsf, i)]; |
2919 | if (dots_connected > 1) |
2920 | shortest_chainlen = min(shortest_chainlen, dots_connected); |
6193da8d |
2921 | } |
6193da8d |
2922 | |
121aae4b |
2923 | assert(sstate->solver_status == SOLVER_INCOMPLETE); |
6c42c563 |
2924 | |
121aae4b |
2925 | if (satclues == clues && shortest_chainlen == edgecount) { |
2926 | sstate->solver_status = SOLVER_SOLVED; |
2927 | /* This discovery clearly counts as progress, even if we haven't |
2928 | * just added any lines or anything */ |
2929 | progress = TRUE; |
2930 | goto finished_loop_deductionsing; |
2931 | } |
6193da8d |
2932 | |
121aae4b |
2933 | /* |
2934 | * Now go through looking for LINE_UNKNOWN edges which |
2935 | * connect two dots that are already in the same |
2936 | * equivalence class. If we find one, test to see if the |
2937 | * loop it would create is a solution. |
2938 | */ |
2939 | FORALL_DOTS(state, i, j) { |
2940 | for (d = 0; d < 2; d++) { |
2941 | int i2, j2, eqclass, val; |
2942 | |
2943 | if (d == 0) { |
2944 | if (RIGHTOF_DOT(state, i, j) != |
2945 | LINE_UNKNOWN) |
2946 | continue; |
2947 | i2 = i+1; |
2948 | j2 = j; |
2949 | } else { |
2950 | if (BELOW_DOT(state, i, j) != |
2951 | LINE_UNKNOWN) { |
2952 | continue; |
2953 | } |
2954 | i2 = i; |
2955 | j2 = j+1; |
6c42c563 |
2956 | } |
121aae4b |
2957 | |
2958 | eqclass = dsf_canonify(sstate->dotdsf, j * (state->w+1) + i); |
2959 | if (eqclass != dsf_canonify(sstate->dotdsf, |
2960 | j2 * (state->w+1) + i2)) { |
2961 | continue; |
6c42c563 |
2962 | } |
6193da8d |
2963 | |
121aae4b |
2964 | val = LINE_NO; /* loop is bad until proven otherwise */ |
2965 | |
2966 | /* |
2967 | * This edge would form a loop. Next |
2968 | * question: how long would the loop be? |
2969 | * Would it equal the total number of edges |
2970 | * (plus the one we'd be adding if we added |
2971 | * it)? |
2972 | */ |
2973 | if (sstate->looplen[eqclass] == edgecount + 1) { |
2974 | int sm1_nearby; |
2975 | int cx, cy; |
2976 | |
2977 | /* |
2978 | * This edge would form a loop which |
2979 | * took in all the edges in the entire |
2980 | * grid. So now we need to work out |
2981 | * whether it would be a valid solution |
2982 | * to the puzzle, which means we have to |
2983 | * check if it satisfies all the clues. |
2984 | * This means that every clue must be |
2985 | * either satisfied or satisfied-minus- |
2986 | * 1, and also that the number of |
2987 | * satisfied-minus-1 clues must be at |
2988 | * most two and they must lie on either |
2989 | * side of this edge. |
2990 | */ |
2991 | sm1_nearby = 0; |
2992 | cx = i - (j2-j); |
2993 | cy = j - (i2-i); |
2994 | if (CLUE_AT(state, cx,cy) >= 0 && |
2995 | square_order(state, cx,cy, LINE_YES) == |
2996 | CLUE_AT(state, cx,cy) - 1) { |
2997 | sm1_nearby++; |
2998 | } |
2999 | if (CLUE_AT(state, i, j) >= 0 && |
3000 | SQUARE_YES_COUNT(sstate, i, j) == |
3001 | CLUE_AT(state, i, j) - 1) { |
3002 | sm1_nearby++; |
3003 | } |
3004 | if (sm1clues == sm1_nearby && |
3005 | sm1clues + satclues == clues) { |
3006 | val = LINE_YES; /* loop is good! */ |
3007 | } |
6c42c563 |
3008 | } |
121aae4b |
3009 | |
3010 | /* |
3011 | * Right. Now we know that adding this edge |
3012 | * would form a loop, and we know whether |
3013 | * that loop would be a viable solution or |
3014 | * not. |
3015 | * |
3016 | * If adding this edge produces a solution, |
3017 | * then we know we've found _a_ solution but |
3018 | * we don't know that it's _the_ solution - |
3019 | * if it were provably the solution then |
3020 | * we'd have deduced this edge some time ago |
3021 | * without the need to do loop detection. So |
3022 | * in this state we return SOLVER_AMBIGUOUS, |
3023 | * which has the effect that hitting Solve |
3024 | * on a user-provided puzzle will fill in a |
3025 | * solution but using the solver to |
3026 | * construct new puzzles won't consider this |
3027 | * a reasonable deduction for the user to |
3028 | * make. |
3029 | */ |
3030 | if (d == 0) { |
3031 | progress = set_line_bydot(sstate, i, j, RIGHT, val); |
3032 | assert(progress == TRUE); |
3033 | } else { |
3034 | progress = set_line_bydot(sstate, i, j, DOWN, val); |
3035 | assert(progress == TRUE); |
6c42c563 |
3036 | } |
121aae4b |
3037 | if (val == LINE_YES) { |
3038 | sstate->solver_status = SOLVER_AMBIGUOUS; |
3039 | goto finished_loop_deductionsing; |
6c42c563 |
3040 | } |
121aae4b |
3041 | } |
6193da8d |
3042 | } |
6193da8d |
3043 | |
121aae4b |
3044 | finished_loop_deductionsing: |
3045 | return progress ? DIFF_EASY : DIFF_MAX; |
c0eb17ce |
3046 | } |
6193da8d |
3047 | |
3048 | /* This will return a dynamically allocated solver_state containing the (more) |
3049 | * solved grid */ |
121aae4b |
3050 | static solver_state *solve_game_rec(const solver_state *sstate_start, |
1a739e2f |
3051 | int diff) |
121aae4b |
3052 | { |
3053 | int i, j; |
3054 | int w, h; |
3055 | solver_state *sstate, *sstate_saved, *sstate_tmp; |
3056 | solver_state *sstate_rec_solved; |
3057 | int recursive_soln_count; |
3058 | int solver_progress; |
3059 | game_state *state; |
6193da8d |
3060 | |
121aae4b |
3061 | /* Indicates which solver we should call next. This is a sensible starting |
3062 | * point */ |
3063 | int current_solver = DIFF_EASY, next_solver; |
3064 | #ifdef SHOW_WORKING |
3065 | char *text; |
6193da8d |
3066 | #endif |
3067 | |
121aae4b |
3068 | #if 0 |
3069 | printf("solve_game_rec: recursion_remaining = %d\n", |
3070 | sstate_start->recursion_remaining); |
3071 | #endif |
6193da8d |
3072 | |
121aae4b |
3073 | sstate = dup_solver_state(sstate_start); |
3074 | |
3075 | /* Cache the values of some variables for readability */ |
3076 | state = sstate->state; |
3077 | h = state->h; |
3078 | w = state->w; |
c0eb17ce |
3079 | |
121aae4b |
3080 | sstate_saved = NULL; |
6193da8d |
3081 | |
3082 | nonrecursive_solver: |
121aae4b |
3083 | solver_progress = FALSE; |
99dd160e |
3084 | |
121aae4b |
3085 | check_caches(sstate); |
6193da8d |
3086 | |
121aae4b |
3087 | do { |
3088 | #ifdef SHOW_WORKING |
3089 | text = game_text_format(state); |
3090 | fprintf(stderr, "-----------------\n%s", text); |
3091 | sfree(text); |
3092 | #endif |
6193da8d |
3093 | |
121aae4b |
3094 | if (sstate->solver_status == SOLVER_MISTAKE) |
3095 | return sstate; |
3096 | |
3097 | /* fprintf(stderr, "Invoking solver %d\n", current_solver); */ |
3098 | next_solver = solver_fns[current_solver](sstate); |
3099 | |
3100 | if (next_solver == DIFF_MAX) { |
3101 | /* fprintf(stderr, "Current solver failed\n"); */ |
3102 | if (current_solver < diff && current_solver + 1 < DIFF_MAX) { |
3103 | /* Try next beefier solver */ |
3104 | next_solver = current_solver + 1; |
3105 | } else { |
3106 | /* fprintf(stderr, "Doing loop deductions\n"); */ |
3107 | next_solver = loop_deductions(sstate); |
3108 | } |
3109 | } |
3110 | |
3111 | if (sstate->solver_status == SOLVER_SOLVED || |
3112 | sstate->solver_status == SOLVER_AMBIGUOUS) { |
3113 | /* fprintf(stderr, "Solver completed\n"); */ |
3114 | break; |
3115 | } |
99dd160e |
3116 | |
121aae4b |
3117 | /* Once we've looped over all permitted solvers then the loop |
3118 | * deductions without making any progress, we'll exit this while loop */ |
3119 | current_solver = next_solver; |
3120 | } while (current_solver < DIFF_MAX); |
3121 | |
3122 | if (sstate->solver_status == SOLVER_SOLVED || |
3123 | sstate->solver_status == SOLVER_AMBIGUOUS) { |
3124 | /* s/LINE_UNKNOWN/LINE_NO/g */ |
3125 | array_setall(sstate->state->hl, LINE_UNKNOWN, LINE_NO, |
3126 | HL_COUNT(sstate->state)); |
3127 | array_setall(sstate->state->vl, LINE_UNKNOWN, LINE_NO, |
3128 | VL_COUNT(sstate->state)); |
3129 | return sstate; |
3130 | } |
6193da8d |
3131 | |
121aae4b |
3132 | /* Perform recursive calls */ |
3133 | if (sstate->recursion_remaining) { |
3134 | sstate_saved = dup_solver_state(sstate); |
6193da8d |
3135 | |
121aae4b |
3136 | sstate->recursion_remaining--; |
6c42c563 |
3137 | |
121aae4b |
3138 | recursive_soln_count = 0; |
3139 | sstate_rec_solved = NULL; |
6c42c563 |
3140 | |
121aae4b |
3141 | /* Memory management: |
3142 | * sstate_saved won't be modified but needs to be freed when we have |
3143 | * finished with it. |
3144 | * sstate is expected to contain our 'best' solution by the time we |
3145 | * finish this section of code. It's the thing we'll try adding lines |
3146 | * to, seeing if they make it more solvable. |
3147 | * If sstate_rec_solved is non-NULL, it will supersede sstate |
3148 | * eventually. sstate_tmp should not hold a value persistently. |
3149 | */ |
6c42c563 |
3150 | |
121aae4b |
3151 | /* NB SOLVER_AMBIGUOUS is like SOLVER_SOLVED except the solver is aware |
3152 | * of the possibility of additional solutions. So as soon as we have a |
3153 | * SOLVER_AMBIGUOUS we can safely propagate it back to our caller, but |
3154 | * if we get a SOLVER_SOLVED we want to keep trying in case we find |
3155 | * further solutions and have to mark it ambiguous. |
3156 | */ |
6c42c563 |
3157 | |
121aae4b |
3158 | #define DO_RECURSIVE_CALL(dir_dot) \ |
3159 | if (dir_dot(sstate->state, i, j) == LINE_UNKNOWN) { \ |
3160 | debug(("Trying " #dir_dot " at [%d,%d]\n", i, j)); \ |
3161 | LV_##dir_dot(sstate->state, i, j) = LINE_YES; \ |
3162 | sstate_tmp = solve_game_rec(sstate, diff); \ |
3163 | switch (sstate_tmp->solver_status) { \ |
3164 | case SOLVER_AMBIGUOUS: \ |
3165 | debug(("Solver ambiguous, returning\n")); \ |
3166 | sstate_rec_solved = sstate_tmp; \ |
3167 | goto finished_recursion; \ |
3168 | case SOLVER_SOLVED: \ |
3169 | switch (++recursive_soln_count) { \ |
3170 | case 1: \ |
3171 | debug(("One solution found\n")); \ |
3172 | sstate_rec_solved = sstate_tmp; \ |
3173 | break; \ |
3174 | case 2: \ |
3175 | debug(("Ambiguous solutions found\n")); \ |
3176 | free_solver_state(sstate_tmp); \ |
3177 | sstate_rec_solved->solver_status = SOLVER_AMBIGUOUS; \ |
3178 | goto finished_recursion; \ |
3179 | default: \ |
3180 | assert(!"recursive_soln_count out of range"); \ |
3181 | break; \ |
3182 | } \ |
3183 | break; \ |
3184 | case SOLVER_MISTAKE: \ |
3185 | debug(("Non-solution found\n")); \ |
3186 | free_solver_state(sstate_tmp); \ |
3187 | free_solver_state(sstate_saved); \ |
3188 | LV_##dir_dot(sstate->state, i, j) = LINE_NO; \ |
3189 | goto nonrecursive_solver; \ |
3190 | case SOLVER_INCOMPLETE: \ |
3191 | debug(("Recursive step inconclusive\n")); \ |
3192 | free_solver_state(sstate_tmp); \ |
3193 | break; \ |
3194 | } \ |
3195 | free_solver_state(sstate); \ |
3196 | sstate = dup_solver_state(sstate_saved); \ |
3197 | } |
6193da8d |
3198 | |
121aae4b |
3199 | FORALL_DOTS(state, i, j) { |
3200 | /* Only perform recursive calls on 'loose ends' */ |
3201 | if (DOT_YES_COUNT(sstate, i, j) == 1) { |
3202 | DO_RECURSIVE_CALL(LEFTOF_DOT); |
3203 | DO_RECURSIVE_CALL(RIGHTOF_DOT); |
3204 | DO_RECURSIVE_CALL(ABOVE_DOT); |
3205 | DO_RECURSIVE_CALL(BELOW_DOT); |
6193da8d |
3206 | } |
3207 | } |
3208 | |
3209 | finished_recursion: |
3210 | |
3211 | if (sstate_rec_solved) { |
3212 | free_solver_state(sstate); |
3213 | sstate = sstate_rec_solved; |
3214 | } |
121aae4b |
3215 | } |
6193da8d |
3216 | |
121aae4b |
3217 | return sstate; |
6193da8d |
3218 | } |
3219 | |
6193da8d |
3220 | #if 0 |
3221 | #define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \ |
121aae4b |
3222 | if (sstate->normal->dot_atmostone[i+a + (sstate->state->w + 1) * (j+b)] & \ |
3223 | 1<<dline) { \ |
3224 | if (square_order(sstate->state, i, j, LINE_UNKNOWN) - 1 == \ |
3225 | CLUE_AT(sstate->state, i, j) - '0') { \ |
6193da8d |
3226 | square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES); \ |
3227 | /* XXX the following may overwrite known data! */ \ |
121aae4b |
3228 | dir1_sq(sstate->state, i, j) = LINE_UNKNOWN; \ |
3229 | dir2_sq(sstate->state, i, j) = LINE_UNKNOWN; \ |
3230 | } \ |
6193da8d |
3231 | } |
3232 | SQUARE_DLINES; |
3233 | #undef HANDLE_DLINE |
3234 | #endif |
3235 | |
6193da8d |
3236 | static char *solve_game(game_state *state, game_state *currstate, |
3237 | char *aux, char **error) |
3238 | { |
3239 | char *soln = NULL; |
3240 | solver_state *sstate, *new_sstate; |
3241 | |
121aae4b |
3242 | sstate = new_solver_state(state, DIFF_MAX); |
3243 | new_sstate = solve_game_rec(sstate, DIFF_MAX); |
6193da8d |
3244 | |
3245 | if (new_sstate->solver_status == SOLVER_SOLVED) { |
3246 | soln = encode_solve_move(new_sstate->state); |
3247 | } else if (new_sstate->solver_status == SOLVER_AMBIGUOUS) { |
3248 | soln = encode_solve_move(new_sstate->state); |
3249 | /**error = "Solver found ambiguous solutions"; */ |
3250 | } else { |
3251 | soln = encode_solve_move(new_sstate->state); |
3252 | /**error = "Solver failed"; */ |
3253 | } |
3254 | |
3255 | free_solver_state(new_sstate); |
3256 | free_solver_state(sstate); |
3257 | |
3258 | return soln; |
3259 | } |
3260 | |
121aae4b |
3261 | /* ---------------------------------------------------------------------- |
3262 | * Drawing and mouse-handling |
3263 | */ |
6193da8d |
3264 | |
3265 | static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, |
3266 | int x, int y, int button) |
3267 | { |
3268 | int hl_selected; |
3269 | int i, j, p, q; |
3270 | char *ret, buf[80]; |
3271 | char button_char = ' '; |
3272 | enum line_state old_state; |
3273 | |
3274 | button &= ~MOD_MASK; |
3275 | |
3276 | /* Around each line is a diamond-shaped region where points within that |
3277 | * region are closer to this line than any other. We assume any click |
3278 | * within a line's diamond was meant for that line. It would all be a lot |
3279 | * simpler if the / and % operators respected modulo arithmetic properly |
3280 | * for negative numbers. */ |
3281 | |
3282 | x -= BORDER; |
3283 | y -= BORDER; |
3284 | |
3285 | /* Get the coordinates of the square the click was in */ |
3286 | i = (x + TILE_SIZE) / TILE_SIZE - 1; |
3287 | j = (y + TILE_SIZE) / TILE_SIZE - 1; |
3288 | |
3289 | /* Get the precise position inside square [i,j] */ |
3290 | p = (x + TILE_SIZE) % TILE_SIZE; |
3291 | q = (y + TILE_SIZE) % TILE_SIZE; |
3292 | |
3293 | /* After this bit of magic [i,j] will correspond to the point either above |
3294 | * or to the left of the line selected */ |
3295 | if (p > q) { |
3296 | if (TILE_SIZE - p > q) { |
3297 | hl_selected = TRUE; |
3298 | } else { |
3299 | hl_selected = FALSE; |
3300 | ++i; |
3301 | } |
3302 | } else { |
3303 | if (TILE_SIZE - q > p) { |
3304 | hl_selected = FALSE; |
3305 | } else { |
3306 | hl_selected = TRUE; |
3307 | ++j; |
3308 | } |
3309 | } |
3310 | |
3311 | if (i < 0 || j < 0) |
3312 | return NULL; |
3313 | |
3314 | if (hl_selected) { |
3315 | if (i >= state->w || j >= state->h + 1) |
3316 | return NULL; |
3317 | } else { |
3318 | if (i >= state->w + 1 || j >= state->h) |
3319 | return NULL; |
3320 | } |
3321 | |
3322 | /* I think it's only possible to play this game with mouse clicks, sorry */ |
3323 | /* Maybe will add mouse drag support some time */ |
3324 | if (hl_selected) |
3325 | old_state = RIGHTOF_DOT(state, i, j); |
3326 | else |
3327 | old_state = BELOW_DOT(state, i, j); |
3328 | |
3329 | switch (button) { |
3330 | case LEFT_BUTTON: |
3331 | switch (old_state) { |
3332 | case LINE_UNKNOWN: |
3333 | button_char = 'y'; |
3334 | break; |
3335 | case LINE_YES: |
3336 | case LINE_NO: |
3337 | button_char = 'u'; |
3338 | break; |
3339 | } |
3340 | break; |
3341 | case MIDDLE_BUTTON: |
3342 | button_char = 'u'; |
3343 | break; |
3344 | case RIGHT_BUTTON: |
3345 | switch (old_state) { |
3346 | case LINE_UNKNOWN: |
3347 | button_char = 'n'; |
3348 | break; |
3349 | case LINE_NO: |
3350 | case LINE_YES: |
3351 | button_char = 'u'; |
3352 | break; |
3353 | } |
3354 | break; |
3355 | default: |
3356 | return NULL; |
3357 | } |
3358 | |
3359 | |
9cfc03b7 |
3360 | sprintf(buf, "%d,%d%c%c", i, j, (int)(hl_selected ? 'h' : 'v'), (int)button_char); |
6193da8d |
3361 | ret = dupstr(buf); |
3362 | |
3363 | return ret; |
3364 | } |
3365 | |
3366 | static game_state *execute_move(game_state *state, char *move) |
3367 | { |
3368 | int i, j; |
3369 | game_state *newstate = dup_game(state); |
3370 | |
3371 | if (move[0] == 'S') { |
3372 | move++; |
3373 | newstate->cheated = TRUE; |
3374 | } |
3375 | |
3376 | while (*move) { |
3377 | i = atoi(move); |
3378 | move = strchr(move, ','); |
3379 | if (!move) |
3380 | goto fail; |
3381 | j = atoi(++move); |
3382 | move += strspn(move, "1234567890"); |
3383 | switch (*(move++)) { |
3384 | case 'h': |
3385 | if (i >= newstate->w || j > newstate->h) |
3386 | goto fail; |
3387 | switch (*(move++)) { |
3388 | case 'y': |
3389 | LV_RIGHTOF_DOT(newstate, i, j) = LINE_YES; |
3390 | break; |
3391 | case 'n': |
3392 | LV_RIGHTOF_DOT(newstate, i, j) = LINE_NO; |
3393 | break; |
3394 | case 'u': |
3395 | LV_RIGHTOF_DOT(newstate, i, j) = LINE_UNKNOWN; |
3396 | break; |
3397 | default: |
3398 | goto fail; |
3399 | } |
3400 | break; |
3401 | case 'v': |
3402 | if (i > newstate->w || j >= newstate->h) |
3403 | goto fail; |
3404 | switch (*(move++)) { |
3405 | case 'y': |
3406 | LV_BELOW_DOT(newstate, i, j) = LINE_YES; |
3407 | break; |
3408 | case 'n': |
3409 | LV_BELOW_DOT(newstate, i, j) = LINE_NO; |
3410 | break; |
3411 | case 'u': |
3412 | LV_BELOW_DOT(newstate, i, j) = LINE_UNKNOWN; |
3413 | break; |
3414 | default: |
3415 | goto fail; |
3416 | } |
3417 | break; |
3418 | default: |
3419 | goto fail; |
3420 | } |
3421 | } |
3422 | |
3423 | /* |
3424 | * Check for completion. |
3425 | */ |
121aae4b |
3426 | i = 0; /* placate optimiser */ |
6193da8d |
3427 | for (j = 0; j <= newstate->h; j++) { |
121aae4b |
3428 | for (i = 0; i < newstate->w; i++) |
3429 | if (LV_RIGHTOF_DOT(newstate, i, j) == LINE_YES) |
3430 | break; |
3431 | if (i < newstate->w) |
3432 | break; |
6193da8d |
3433 | } |
3434 | if (j <= newstate->h) { |
121aae4b |
3435 | int prevdir = 'R'; |
3436 | int x = i, y = j; |
3437 | int looplen, count; |
3438 | |
3439 | /* |
3440 | * We've found a horizontal edge at (i,j). Follow it round |
3441 | * to see if it's part of a loop. |
3442 | */ |
3443 | looplen = 0; |
3444 | while (1) { |
3445 | int order = dot_order(newstate, x, y, LINE_YES); |
3446 | if (order != 2) |
3447 | goto completion_check_done; |
3448 | |
3449 | if (LEFTOF_DOT(newstate, x, y) == LINE_YES && prevdir != 'L') { |
3450 | x--; |
3451 | prevdir = 'R'; |
3452 | } else if (RIGHTOF_DOT(newstate, x, y) == LINE_YES && |
3453 | prevdir != 'R') { |
3454 | x++; |
3455 | prevdir = 'L'; |
3456 | } else if (ABOVE_DOT(newstate, x, y) == LINE_YES && |
3457 | prevdir != 'U') { |
3458 | y--; |
3459 | prevdir = 'D'; |
3460 | } else if (BELOW_DOT(newstate, x, y) == LINE_YES && |
3461 | prevdir != 'D') { |
3462 | y++; |
3463 | prevdir = 'U'; |
3464 | } else { |
3465 | assert(!"Can't happen"); /* dot_order guarantees success */ |
3466 | } |
3467 | |
3468 | looplen++; |
3469 | |
3470 | if (x == i && y == j) |
3471 | break; |
3472 | } |
3473 | |
3474 | if (x != i || y != j || looplen == 0) |
3475 | goto completion_check_done; |
3476 | |
3477 | /* |
3478 | * We've traced our way round a loop, and we know how many |
3479 | * line segments were involved. Count _all_ the line |
3480 | * segments in the grid, to see if the loop includes them |
3481 | * all. |
3482 | */ |
3483 | count = 0; |
3484 | FORALL_DOTS(newstate, i, j) { |
3485 | count += ((RIGHTOF_DOT(newstate, i, j) == LINE_YES) + |
3486 | (BELOW_DOT(newstate, i, j) == LINE_YES)); |
3487 | } |
3488 | assert(count >= looplen); |
3489 | if (count != looplen) |
3490 | goto completion_check_done; |
3491 | |
3492 | /* |
3493 | * The grid contains one closed loop and nothing else. |
3494 | * Check that all the clues are satisfied. |
3495 | */ |
3496 | FORALL_SQUARES(newstate, i, j) { |
3497 | if (CLUE_AT(newstate, i, j) >= 0) { |
3498 | if (square_order(newstate, i, j, LINE_YES) != |
3499 | CLUE_AT(newstate, i, j)) { |
3500 | goto completion_check_done; |
3501 | } |
3502 | } |
3503 | } |
3504 | |
3505 | /* |
3506 | * Completed! |
3507 | */ |
3508 | newstate->solved = TRUE; |
6193da8d |
3509 | } |
3510 | |
3511 | completion_check_done: |
3512 | return newstate; |
3513 | |
3514 | fail: |
3515 | free_game(newstate); |
3516 | return NULL; |
3517 | } |
3518 | |
3519 | /* ---------------------------------------------------------------------- |
3520 | * Drawing routines. |
3521 | */ |
6193da8d |
3522 | static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, |
3523 | game_state *state, int dir, game_ui *ui, |
3524 | float animtime, float flashtime) |
3525 | { |
c0eb17ce |
3526 | int i, j, n; |
6193da8d |
3527 | char c[2]; |
3528 | int line_colour, flash_changed; |
c0eb17ce |
3529 | int clue_mistake; |
6193da8d |
3530 | |
3531 | if (!ds->started) { |
3532 | /* |
3533 | * The initial contents of the window are not guaranteed and |
3534 | * can vary with front ends. To be on the safe side, all games |
3535 | * should start by drawing a big background-colour rectangle |
3536 | * covering the whole window. |
3537 | */ |
3538 | draw_rect(dr, 0, 0, SIZE(state->w), SIZE(state->h), COL_BACKGROUND); |
3539 | |
3540 | /* Draw dots */ |
121aae4b |
3541 | FORALL_DOTS(state, i, j) { |
3542 | draw_rect(dr, |
3543 | BORDER + i * TILE_SIZE - LINEWIDTH/2, |
3544 | BORDER + j * TILE_SIZE - LINEWIDTH/2, |
3545 | LINEWIDTH, LINEWIDTH, COL_FOREGROUND); |
6193da8d |
3546 | } |
3547 | |
3548 | /* Draw clues */ |
121aae4b |
3549 | FORALL_SQUARES(state, i, j) { |
3550 | c[0] = CLUE2CHAR(CLUE_AT(state, i, j)); |
3551 | c[1] = '\0'; |
3552 | draw_text(dr, |
3553 | BORDER + i * TILE_SIZE + TILE_SIZE/2, |
3554 | BORDER + j * TILE_SIZE + TILE_SIZE/2, |
3555 | FONT_VARIABLE, TILE_SIZE/2, |
3556 | ALIGN_VCENTRE | ALIGN_HCENTRE, COL_FOREGROUND, c); |
6193da8d |
3557 | } |
3558 | draw_update(dr, 0, 0, |
3559 | state->w * TILE_SIZE + 2*BORDER + 1, |
3560 | state->h * TILE_SIZE + 2*BORDER + 1); |
3561 | ds->started = TRUE; |
3562 | } |
3563 | |
3564 | if (flashtime > 0 && |
3565 | (flashtime <= FLASH_TIME/3 || |
3566 | flashtime >= FLASH_TIME*2/3)) { |
3567 | flash_changed = !ds->flashing; |
3568 | ds->flashing = TRUE; |
3569 | line_colour = COL_HIGHLIGHT; |
3570 | } else { |
3571 | flash_changed = ds->flashing; |
3572 | ds->flashing = FALSE; |
3573 | line_colour = COL_FOREGROUND; |
3574 | } |
3575 | |
3576 | #define CROSS_SIZE (3 * LINEWIDTH / 2) |
3577 | |
c0eb17ce |
3578 | /* Redraw clue colours if necessary */ |
121aae4b |
3579 | FORALL_SQUARES(state, i, j) { |
3580 | n = CLUE_AT(state, i, j); |
3581 | if (n < 0) |
3582 | continue; |
c0eb17ce |
3583 | |
121aae4b |
3584 | assert(n >= 0 && n <= 4); |
3585 | |
3586 | c[0] = CLUE2CHAR(CLUE_AT(state, i, j)); |
3587 | c[1] = '\0'; |
3588 | |
3589 | clue_mistake = (square_order(state, i, j, LINE_YES) > n || |
3590 | square_order(state, i, j, LINE_NO ) > (4-n)); |
3591 | |
3592 | if (clue_mistake != ds->clue_error[SQUARE_INDEX(state, i, j)]) { |
3593 | draw_rect(dr, |
3594 | BORDER + i * TILE_SIZE + CROSS_SIZE, |
3595 | BORDER + j * TILE_SIZE + CROSS_SIZE, |
3596 | TILE_SIZE - CROSS_SIZE * 2, TILE_SIZE - CROSS_SIZE * 2, |
3597 | COL_BACKGROUND); |
3598 | draw_text(dr, |
3599 | BORDER + i * TILE_SIZE + TILE_SIZE/2, |
3600 | BORDER + j * TILE_SIZE + TILE_SIZE/2, |
3601 | FONT_VARIABLE, TILE_SIZE/2, |
3602 | ALIGN_VCENTRE | ALIGN_HCENTRE, |
3603 | clue_mistake ? COL_MISTAKE : COL_FOREGROUND, c); |
3604 | draw_update(dr, i * TILE_SIZE + BORDER, j * TILE_SIZE + BORDER, |
3605 | TILE_SIZE, TILE_SIZE); |
3606 | |
3607 | ds->clue_error[SQUARE_INDEX(state, i, j)] = clue_mistake; |
c0eb17ce |
3608 | } |
3609 | } |
3610 | |
3611 | /* I've also had a request to colour lines red if they make a non-solution |
3612 | * loop, or if more than two lines go into any point. I think that would |
3613 | * be good some time. */ |
3614 | |
121aae4b |
3615 | #define CLEAR_VL(i, j) \ |
3616 | do { \ |
3617 | draw_rect(dr, \ |
3618 | BORDER + i * TILE_SIZE - CROSS_SIZE, \ |
3619 | BORDER + j * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, \ |
3620 | CROSS_SIZE * 2, \ |
3621 | TILE_SIZE - LINEWIDTH, \ |
3622 | COL_BACKGROUND); \ |
3623 | draw_update(dr, \ |
3624 | BORDER + i * TILE_SIZE - CROSS_SIZE, \ |
3625 | BORDER + j * TILE_SIZE - CROSS_SIZE, \ |
3626 | CROSS_SIZE*2, \ |
3627 | TILE_SIZE + CROSS_SIZE*2); \ |
3628 | } while (0) |
3629 | |
3630 | #define CLEAR_HL(i, j) \ |
3631 | do { \ |
3632 | draw_rect(dr, \ |
3633 | BORDER + i * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, \ |
3634 | BORDER + j * TILE_SIZE - CROSS_SIZE, \ |
3635 | TILE_SIZE - LINEWIDTH, \ |
3636 | CROSS_SIZE * 2, \ |
3637 | COL_BACKGROUND); \ |
3638 | draw_update(dr, \ |
3639 | BORDER + i * TILE_SIZE - CROSS_SIZE, \ |
3640 | BORDER + j * TILE_SIZE - CROSS_SIZE, \ |
3641 | TILE_SIZE + CROSS_SIZE*2, \ |
3642 | CROSS_SIZE*2); \ |
3643 | } while (0) |
6193da8d |
3644 | |
3645 | /* Vertical lines */ |
121aae4b |
3646 | FORALL_VL(state, i, j) { |
3647 | switch (BELOW_DOT(state, i, j)) { |
3648 | case LINE_UNKNOWN: |
3649 | if (ds->vl[VL_INDEX(state, i, j)] != BELOW_DOT(state, i, j)) { |
3650 | CLEAR_VL(i, j); |
3651 | } |
3652 | break; |
3653 | case LINE_YES: |
3654 | if (ds->vl[VL_INDEX(state, i, j)] != BELOW_DOT(state, i, j) || |
3655 | flash_changed) { |
3656 | CLEAR_VL(i, j); |
3657 | draw_rect(dr, |
3658 | BORDER + i * TILE_SIZE - LINEWIDTH/2, |
3659 | BORDER + j * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, |
3660 | LINEWIDTH, TILE_SIZE - LINEWIDTH, |
3661 | line_colour); |
3662 | } |
3663 | break; |
3664 | case LINE_NO: |
3665 | if (ds->vl[VL_INDEX(state, i, j)] != BELOW_DOT(state, i, j)) { |
3666 | CLEAR_VL(i, j); |
3667 | draw_line(dr, |
3668 | BORDER + i * TILE_SIZE - CROSS_SIZE, |
3669 | BORDER + j * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE, |
3670 | BORDER + i * TILE_SIZE + CROSS_SIZE - 1, |
3671 | BORDER + j * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1, |
3672 | COL_FOREGROUND); |
3673 | draw_line(dr, |
3674 | BORDER + i * TILE_SIZE + CROSS_SIZE - 1, |
3675 | BORDER + j * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE, |
3676 | BORDER + i * TILE_SIZE - CROSS_SIZE, |
3677 | BORDER + j * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1, |
3678 | COL_FOREGROUND); |
3679 | } |
3680 | break; |
6193da8d |
3681 | } |
121aae4b |
3682 | ds->vl[VL_INDEX(state, i, j)] = BELOW_DOT(state, i, j); |
6193da8d |
3683 | } |
3684 | |
3685 | /* Horizontal lines */ |
121aae4b |
3686 | FORALL_HL(state, i, j) { |
3687 | switch (RIGHTOF_DOT(state, i, j)) { |
3688 | case LINE_UNKNOWN: |
3689 | if (ds->hl[HL_INDEX(state, i, j)] != RIGHTOF_DOT(state, i, j)) { |
3690 | CLEAR_HL(i, j); |
3691 | } |
3692 | break; |
3693 | case LINE_YES: |
3694 | if (ds->hl[HL_INDEX(state, i, j)] != RIGHTOF_DOT(state, i, j) || |
3695 | flash_changed) { |
3696 | CLEAR_HL(i, j); |
3697 | draw_rect(dr, |
3698 | BORDER + i * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, |
3699 | BORDER + j * TILE_SIZE - LINEWIDTH/2, |
3700 | TILE_SIZE - LINEWIDTH, LINEWIDTH, |
3701 | line_colour); |
3702 | } |
3703 | break; |
3704 | case LINE_NO: |
3705 | if (ds->hl[HL_INDEX(state, i, j)] != RIGHTOF_DOT(state, i, j)) { |
3706 | CLEAR_HL(i, j); |
3707 | draw_line(dr, |
3708 | BORDER + i * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE, |
3709 | BORDER + j * TILE_SIZE + CROSS_SIZE - 1, |
3710 | BORDER + i * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1, |
3711 | BORDER + j * TILE_SIZE - CROSS_SIZE, |
3712 | COL_FOREGROUND); |
3713 | draw_line(dr, |
3714 | BORDER + i * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE, |
3715 | BORDER + j * TILE_SIZE - CROSS_SIZE, |
3716 | BORDER + i * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1, |
3717 | BORDER + j * TILE_SIZE + CROSS_SIZE - 1, |
3718 | COL_FOREGROUND); |
3719 | break; |
6193da8d |
3720 | } |
6193da8d |
3721 | } |
121aae4b |
3722 | ds->hl[HL_INDEX(state, i, j)] = RIGHTOF_DOT(state, i, j); |
6193da8d |
3723 | } |
3724 | } |
3725 | |
6193da8d |
3726 | static float game_flash_length(game_state *oldstate, game_state *newstate, |
3727 | int dir, game_ui *ui) |
3728 | { |
3729 | if (!oldstate->solved && newstate->solved && |
3730 | !oldstate->cheated && !newstate->cheated) { |
3731 | return FLASH_TIME; |
3732 | } |
3733 | |
3734 | return 0.0F; |
3735 | } |
3736 | |
6193da8d |
3737 | static void game_print_size(game_params *params, float *x, float *y) |
3738 | { |
3739 | int pw, ph; |
3740 | |
3741 | /* |
3742 | * I'll use 7mm squares by default. |
3743 | */ |
3744 | game_compute_size(params, 700, &pw, &ph); |
3745 | *x = pw / 100.0F; |
3746 | *y = ph / 100.0F; |
3747 | } |
3748 | |
3749 | static void game_print(drawing *dr, game_state *state, int tilesize) |
3750 | { |
6193da8d |
3751 | int ink = print_mono_colour(dr, 0); |
3752 | int x, y; |
3753 | game_drawstate ads, *ds = &ads; |
4413ef0f |
3754 | |
3755 | game_set_size(dr, ds, NULL, tilesize); |
6193da8d |
3756 | |
3757 | /* |
3758 | * Dots. I'll deliberately make the dots a bit wider than the |
3759 | * lines, so you can still see them. (And also because it's |
3760 | * annoyingly tricky to make them _exactly_ the same size...) |
3761 | */ |
121aae4b |
3762 | FORALL_DOTS(state, x, y) { |
3763 | draw_circle(dr, BORDER + x * TILE_SIZE, BORDER + y * TILE_SIZE, |
3764 | LINEWIDTH, ink, ink); |
3765 | } |
6193da8d |
3766 | |
3767 | /* |
3768 | * Clues. |
3769 | */ |
121aae4b |
3770 | FORALL_SQUARES(state, x, y) { |
3771 | if (CLUE_AT(state, x, y) >= 0) { |
3772 | char c[2]; |
3773 | |
3774 | c[0] = CLUE2CHAR(CLUE_AT(state, x, y)); |
3775 | c[1] = '\0'; |
3776 | draw_text(dr, |
3777 | BORDER + x * TILE_SIZE + TILE_SIZE/2, |
3778 | BORDER + y * TILE_SIZE + TILE_SIZE/2, |
3779 | FONT_VARIABLE, TILE_SIZE/2, |
3780 | ALIGN_VCENTRE | ALIGN_HCENTRE, ink, c); |
3781 | } |
3782 | } |
6193da8d |
3783 | |
3784 | /* |
3785 | * Lines. (At the moment, I'm not bothering with crosses.) |
3786 | */ |
bb526d66 |
3787 | FORALL_HL(state, x, y) { |
121aae4b |
3788 | if (RIGHTOF_DOT(state, x, y) == LINE_YES) |
3789 | draw_rect(dr, BORDER + x * TILE_SIZE, |
3790 | BORDER + y * TILE_SIZE - LINEWIDTH/2, |
3791 | TILE_SIZE, (LINEWIDTH/2) * 2 + 1, ink); |
3792 | } |
3793 | |
bb526d66 |
3794 | FORALL_VL(state, x, y) { |
121aae4b |
3795 | if (BELOW_DOT(state, x, y) == LINE_YES) |
3796 | draw_rect(dr, BORDER + x * TILE_SIZE - LINEWIDTH/2, |
3797 | BORDER + y * TILE_SIZE, |
3798 | (LINEWIDTH/2) * 2 + 1, TILE_SIZE, ink); |
3799 | } |
6193da8d |
3800 | } |
3801 | |
3802 | #ifdef COMBINED |
3803 | #define thegame loopy |
3804 | #endif |
3805 | |
3806 | const struct game thegame = { |
750037d7 |
3807 | "Loopy", "games.loopy", "loopy", |
6193da8d |
3808 | default_params, |
3809 | game_fetch_preset, |
3810 | decode_params, |
3811 | encode_params, |
3812 | free_params, |
3813 | dup_params, |
3814 | TRUE, game_configure, custom_params, |
3815 | validate_params, |
3816 | new_game_desc, |
3817 | validate_desc, |
3818 | new_game, |
3819 | dup_game, |
3820 | free_game, |
3821 | 1, solve_game, |
3822 | TRUE, game_text_format, |
3823 | new_ui, |
3824 | free_ui, |
3825 | encode_ui, |
3826 | decode_ui, |
3827 | game_changed_state, |
3828 | interpret_move, |
3829 | execute_move, |
3830 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, |
3831 | game_colours, |
3832 | game_new_drawstate, |
3833 | game_free_drawstate, |
3834 | game_redraw, |
3835 | game_anim_length, |
3836 | game_flash_length, |
3837 | TRUE, FALSE, game_print_size, game_print, |
121aae4b |
3838 | FALSE /* wants_statusbar */, |
6193da8d |
3839 | FALSE, game_timing_state, |
121aae4b |
3840 | 0, /* mouse_priorities */ |
6193da8d |
3841 | }; |