diff options
author | Franklin Wei <frankhwei536@gmail.com> | 2016-11-20 15:16:41 -0500 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2016-12-18 18:13:22 +0100 |
commit | 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 (patch) | |
tree | 8e7f2d6b0cbdb5d15c13457b2c3e1de69f598440 /apps/plugins/puzzles/loopy.c | |
parent | 3ee79724f6fb033d50e26ef37b33d3f8cedf0c5b (diff) | |
download | rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.tar.gz rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.zip |
Port of Simon Tatham's Puzzle Collection
Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9
MIT Licensed. Some games still crash and others are unplayable due to
issues with controls. Still need a "real" polygon filling algorithm.
Currently builds one plugin per puzzle (about 40 in total, around 100K
each on ARM), but can easily be made to build a single monolithic
overlay (800K or so on ARM).
The following games are at least partially broken for various reasons,
and have been disabled on this commit:
Cube: failed assertion with "Icosahedron" setting
Keen: input issues
Mines: weird stuff happens on target
Palisade: input issues
Solo: input issues, occasional crash on target
Towers: input issues
Undead: input issues
Unequal: input and drawing issues (concave polys)
Untangle: input issues
Features left to do:
- In-game help system
- Figure out the weird bugs
Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368
Diffstat (limited to 'apps/plugins/puzzles/loopy.c')
-rw-r--r-- | apps/plugins/puzzles/loopy.c | 3688 |
1 files changed, 3688 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/loopy.c b/apps/plugins/puzzles/loopy.c new file mode 100644 index 0000000000..a931b31c37 --- /dev/null +++ b/apps/plugins/puzzles/loopy.c | |||
@@ -0,0 +1,3688 @@ | |||
1 | /* | ||
2 | * loopy.c: | ||
3 | * | ||
4 | * An implementation of the Nikoli game 'Loop the loop'. | ||
5 | * (c) Mike Pinna, 2005, 2006 | ||
6 | * Substantially rewritten to allowing for more general types of grid. | ||
7 | * (c) Lambros Lambrou 2008 | ||
8 | * | ||
9 | * vim: set shiftwidth=4 :set textwidth=80: | ||
10 | */ | ||
11 | |||
12 | /* | ||
13 | * Possible future solver enhancements: | ||
14 | * | ||
15 | * - There's an interesting deductive technique which makes use | ||
16 | * of topology rather than just graph theory. Each _face_ in | ||
17 | * the grid is either inside or outside the loop; you can tell | ||
18 | * that two faces are on the same side of the loop if they're | ||
19 | * separated by a LINE_NO (or, more generally, by a path | ||
20 | * crossing no LINE_UNKNOWNs and an even number of LINE_YESes), | ||
21 | * and on the opposite side of the loop if they're separated by | ||
22 | * a LINE_YES (or an odd number of LINE_YESes and no | ||
23 | * LINE_UNKNOWNs). Oh, and any face separated from the outside | ||
24 | * of the grid by a LINE_YES or a LINE_NO is on the inside or | ||
25 | * outside respectively. So if you can track this for all | ||
26 | * faces, you figure out the state of the line between a pair | ||
27 | * once their relative insideness is known. | ||
28 | * + The way I envisage this working is simply to keep an edsf | ||
29 | * of all _faces_, which indicates whether they're on | ||
30 | * opposite sides of the loop from one another. We also | ||
31 | * include a special entry in the edsf for the infinite | ||
32 | * exterior "face". | ||
33 | * + So, the simple way to do this is to just go through the | ||
34 | * edges: every time we see an edge in a state other than | ||
35 | * LINE_UNKNOWN which separates two faces that aren't in the | ||
36 | * same edsf class, we can rectify that by merging the | ||
37 | * classes. Then, conversely, an edge in LINE_UNKNOWN state | ||
38 | * which separates two faces that _are_ in the same edsf | ||
39 | * class can immediately have its state determined. | ||
40 | * + But you can go one better, if you're prepared to loop | ||
41 | * over all _pairs_ of edges. Suppose we have edges A and B, | ||
42 | * which respectively separate faces A1,A2 and B1,B2. | ||
43 | * Suppose that A,B are in the same edge-edsf class and that | ||
44 | * A1,B1 (wlog) are in the same face-edsf class; then we can | ||
45 | * immediately place A2,B2 into the same face-edsf class (as | ||
46 | * each other, not as A1 and A2) one way round or the other. | ||
47 | * And conversely again, if A1,B1 are in the same face-edsf | ||
48 | * class and so are A2,B2, then we can put A,B into the same | ||
49 | * face-edsf class. | ||
50 | * * Of course, this deduction requires a quadratic-time | ||
51 | * loop over all pairs of edges in the grid, so it should | ||
52 | * be reserved until there's nothing easier left to be | ||
53 | * done. | ||
54 | * | ||
55 | * - The generalised grid support has made me (SGT) notice a | ||
56 | * possible extension to the loop-avoidance code. When you have | ||
57 | * a path of connected edges such that no other edges at all | ||
58 | * are incident on any vertex in the middle of the path - or, | ||
59 | * alternatively, such that any such edges are already known to | ||
60 | * be LINE_NO - then you know those edges are either all | ||
61 | * LINE_YES or all LINE_NO. Hence you can mentally merge the | ||
62 | * entire path into a single long curly edge for the purposes | ||
63 | * of loop avoidance, and look directly at whether or not the | ||
64 | * extreme endpoints of the path are connected by some other | ||
65 | * route. I find this coming up fairly often when I play on the | ||
66 | * octagonal grid setting, so it might be worth implementing in | ||
67 | * the solver. | ||
68 | * | ||
69 | * - (Just a speed optimisation.) Consider some todo list queue where every | ||
70 | * time we modify something we mark it for consideration by other bits of | ||
71 | * the solver, to save iteration over things that have already been done. | ||
72 | */ | ||
73 | |||
74 | #include <stdio.h> | ||
75 | #include <stdlib.h> | ||
76 | #include <stddef.h> | ||
77 | #include <string.h> | ||
78 | #include "rbassert.h" | ||
79 | #include <ctype.h> | ||
80 | #include <math.h> | ||
81 | |||
82 | #include "puzzles.h" | ||
83 | #include "tree234.h" | ||
84 | #include "grid.h" | ||
85 | #include "loopgen.h" | ||
86 | |||
87 | /* Debugging options */ | ||
88 | |||
89 | /* | ||
90 | #define DEBUG_CACHES | ||
91 | #define SHOW_WORKING | ||
92 | #define DEBUG_DLINES | ||
93 | */ | ||
94 | |||
95 | /* ---------------------------------------------------------------------- | ||
96 | * Struct, enum and function declarations | ||
97 | */ | ||
98 | |||
99 | enum { | ||
100 | COL_BACKGROUND, | ||
101 | COL_FOREGROUND, | ||
102 | COL_LINEUNKNOWN, | ||
103 | COL_HIGHLIGHT, | ||
104 | COL_MISTAKE, | ||
105 | COL_SATISFIED, | ||
106 | COL_FAINT, | ||
107 | NCOLOURS | ||
108 | }; | ||
109 | |||
110 | struct game_state { | ||
111 | grid *game_grid; /* ref-counted (internally) */ | ||
112 | |||
113 | /* Put -1 in a face that doesn't get a clue */ | ||
114 | signed char *clues; | ||
115 | |||
116 | /* Array of line states, to store whether each line is | ||
117 | * YES, NO or UNKNOWN */ | ||
118 | char *lines; | ||
119 | |||
120 | unsigned char *line_errors; | ||
121 | int exactly_one_loop; | ||
122 | |||
123 | int solved; | ||
124 | int cheated; | ||
125 | |||
126 | /* Used in game_text_format(), so that it knows what type of | ||
127 | * grid it's trying to render as ASCII text. */ | ||
128 | int grid_type; | ||
129 | }; | ||
130 | |||
131 | enum solver_status { | ||
132 | SOLVER_SOLVED, /* This is the only solution the solver could find */ | ||
133 | SOLVER_MISTAKE, /* This is definitely not a solution */ | ||
134 | SOLVER_AMBIGUOUS, /* This _might_ be an ambiguous solution */ | ||
135 | SOLVER_INCOMPLETE /* This may be a partial solution */ | ||
136 | }; | ||
137 | |||
138 | /* ------ Solver state ------ */ | ||
139 | typedef struct solver_state { | ||
140 | game_state *state; | ||
141 | enum solver_status solver_status; | ||
142 | /* NB looplen is the number of dots that are joined together at a point, ie a | ||
143 | * looplen of 1 means there are no lines to a particular dot */ | ||
144 | int *looplen; | ||
145 | |||
146 | /* Difficulty level of solver. Used by solver functions that want to | ||
147 | * vary their behaviour depending on the requested difficulty level. */ | ||
148 | int diff; | ||
149 | |||
150 | /* caches */ | ||
151 | char *dot_yes_count; | ||
152 | char *dot_no_count; | ||
153 | char *face_yes_count; | ||
154 | char *face_no_count; | ||
155 | char *dot_solved, *face_solved; | ||
156 | int *dotdsf; | ||
157 | |||
158 | /* Information for Normal level deductions: | ||
159 | * For each dline, store a bitmask for whether we know: | ||
160 | * (bit 0) at least one is YES | ||
161 | * (bit 1) at most one is YES */ | ||
162 | char *dlines; | ||
163 | |||
164 | /* Hard level information */ | ||
165 | int *linedsf; | ||
166 | } solver_state; | ||
167 | |||
168 | /* | ||
169 | * Difficulty levels. I do some macro ickery here to ensure that my | ||
170 | * enum and the various forms of my name list always match up. | ||
171 | */ | ||
172 | |||
173 | #define DIFFLIST(A) \ | ||
174 | A(EASY,Easy,e) \ | ||
175 | A(NORMAL,Normal,n) \ | ||
176 | A(TRICKY,Tricky,t) \ | ||
177 | A(HARD,Hard,h) | ||
178 | #define ENUM(upper,title,lower) DIFF_ ## upper, | ||
179 | #define TITLE(upper,title,lower) #title, | ||
180 | #define ENCODE(upper,title,lower) #lower | ||
181 | #define CONFIG(upper,title,lower) ":" #title | ||
182 | enum { DIFFLIST(ENUM) DIFF_MAX }; | ||
183 | static char const *const diffnames[] = { DIFFLIST(TITLE) }; | ||
184 | static char const diffchars[] = DIFFLIST(ENCODE); | ||
185 | #define DIFFCONFIG DIFFLIST(CONFIG) | ||
186 | |||
187 | /* | ||
188 | * Solver routines, sorted roughly in order of computational cost. | ||
189 | * The solver will run the faster deductions first, and slower deductions are | ||
190 | * only invoked when the faster deductions are unable to make progress. | ||
191 | * Each function is associated with a difficulty level, so that the generated | ||
192 | * puzzles are solvable by applying only the functions with the chosen | ||
193 | * difficulty level or lower. | ||
194 | */ | ||
195 | #define SOLVERLIST(A) \ | ||
196 | A(trivial_deductions, DIFF_EASY) \ | ||
197 | A(dline_deductions, DIFF_NORMAL) \ | ||
198 | A(linedsf_deductions, DIFF_HARD) \ | ||
199 | A(loop_deductions, DIFF_EASY) | ||
200 | #define SOLVER_FN_DECL(fn,diff) static int fn(solver_state *); | ||
201 | #define SOLVER_FN(fn,diff) &fn, | ||
202 | #define SOLVER_DIFF(fn,diff) diff, | ||
203 | SOLVERLIST(SOLVER_FN_DECL) | ||
204 | static int (*(solver_fns[]))(solver_state *) = { SOLVERLIST(SOLVER_FN) }; | ||
205 | static int const solver_diffs[] = { SOLVERLIST(SOLVER_DIFF) }; | ||
206 | static const int NUM_SOLVERS = sizeof(solver_diffs)/sizeof(*solver_diffs); | ||
207 | |||
208 | struct game_params { | ||
209 | int w, h; | ||
210 | int diff; | ||
211 | int type; | ||
212 | }; | ||
213 | |||
214 | /* line_drawstate is the same as line_state, but with the extra ERROR | ||
215 | * possibility. The drawing code copies line_state to line_drawstate, | ||
216 | * except in the case that the line is an error. */ | ||
217 | enum line_state { LINE_YES, LINE_UNKNOWN, LINE_NO }; | ||
218 | enum line_drawstate { DS_LINE_YES, DS_LINE_UNKNOWN, | ||
219 | DS_LINE_NO, DS_LINE_ERROR }; | ||
220 | |||
221 | #define OPP(line_state) \ | ||
222 | (2 - line_state) | ||
223 | |||
224 | |||
225 | struct game_drawstate { | ||
226 | int started; | ||
227 | int tilesize; | ||
228 | int flashing; | ||
229 | int *textx, *texty; | ||
230 | char *lines; | ||
231 | char *clue_error; | ||
232 | char *clue_satisfied; | ||
233 | }; | ||
234 | |||
235 | static char *validate_desc(const game_params *params, const char *desc); | ||
236 | static int dot_order(const game_state* state, int i, char line_type); | ||
237 | static int face_order(const game_state* state, int i, char line_type); | ||
238 | static solver_state *solve_game_rec(const solver_state *sstate); | ||
239 | |||
240 | #ifdef DEBUG_CACHES | ||
241 | static void check_caches(const solver_state* sstate); | ||
242 | #else | ||
243 | #define check_caches(s) | ||
244 | #endif | ||
245 | |||
246 | /* ------- List of grid generators ------- */ | ||
247 | #define GRIDLIST(A) \ | ||
248 | A(Squares,GRID_SQUARE,3,3) \ | ||
249 | A(Triangular,GRID_TRIANGULAR,3,3) \ | ||
250 | A(Honeycomb,GRID_HONEYCOMB,3,3) \ | ||
251 | A(Snub-Square,GRID_SNUBSQUARE,3,3) \ | ||
252 | A(Cairo,GRID_CAIRO,3,4) \ | ||
253 | A(Great-Hexagonal,GRID_GREATHEXAGONAL,3,3) \ | ||
254 | A(Octagonal,GRID_OCTAGONAL,3,3) \ | ||
255 | A(Kites,GRID_KITE,3,3) \ | ||
256 | A(Floret,GRID_FLORET,1,2) \ | ||
257 | A(Dodecagonal,GRID_DODECAGONAL,2,2) \ | ||
258 | A(Great-Dodecagonal,GRID_GREATDODECAGONAL,2,2) \ | ||
259 | A(Penrose (kite/dart),GRID_PENROSE_P2,3,3) \ | ||
260 | A(Penrose (rhombs),GRID_PENROSE_P3,3,3) | ||
261 | |||
262 | #define GRID_NAME(title,type,amin,omin) #title, | ||
263 | #define GRID_CONFIG(title,type,amin,omin) ":" #title | ||
264 | #define GRID_TYPE(title,type,amin,omin) type, | ||
265 | #define GRID_SIZES(title,type,amin,omin) \ | ||
266 | {amin, omin, \ | ||
267 | "Width and height for this grid type must both be at least " #amin, \ | ||
268 | "At least one of width and height for this grid type must be at least " #omin,}, | ||
269 | static char const *const gridnames[] = { GRIDLIST(GRID_NAME) }; | ||
270 | #define GRID_CONFIGS GRIDLIST(GRID_CONFIG) | ||
271 | static grid_type grid_types[] = { GRIDLIST(GRID_TYPE) }; | ||
272 | #define NUM_GRID_TYPES (sizeof(grid_types) / sizeof(grid_types[0])) | ||
273 | static const struct { | ||
274 | int amin, omin; | ||
275 | char *aerr, *oerr; | ||
276 | } grid_size_limits[] = { GRIDLIST(GRID_SIZES) }; | ||
277 | |||
278 | /* Generates a (dynamically allocated) new grid, according to the | ||
279 | * type and size requested in params. Does nothing if the grid is already | ||
280 | * generated. */ | ||
281 | static grid *loopy_generate_grid(const game_params *params, | ||
282 | const char *grid_desc) | ||
283 | { | ||
284 | return grid_new(grid_types[params->type], params->w, params->h, grid_desc); | ||
285 | } | ||
286 | |||
287 | /* ---------------------------------------------------------------------- | ||
288 | * Preprocessor magic | ||
289 | */ | ||
290 | |||
291 | /* General constants */ | ||
292 | #define PREFERRED_TILE_SIZE 32 | ||
293 | #define BORDER(tilesize) ((tilesize) / 2) | ||
294 | #define FLASH_TIME 0.5F | ||
295 | |||
296 | #define BIT_SET(field, bit) ((field) & (1<<(bit))) | ||
297 | |||
298 | #define SET_BIT(field, bit) (BIT_SET(field, bit) ? FALSE : \ | ||
299 | ((field) |= (1<<(bit)), TRUE)) | ||
300 | |||
301 | #define CLEAR_BIT(field, bit) (BIT_SET(field, bit) ? \ | ||
302 | ((field) &= ~(1<<(bit)), TRUE) : FALSE) | ||
303 | |||
304 | #define CLUE2CHAR(c) \ | ||
305 | ((c < 0) ? ' ' : c < 10 ? c + '0' : c - 10 + 'A') | ||
306 | |||
307 | /* ---------------------------------------------------------------------- | ||
308 | * General struct manipulation and other straightforward code | ||
309 | */ | ||
310 | |||
311 | static game_state *dup_game(const game_state *state) | ||
312 | { | ||
313 | game_state *ret = snew(game_state); | ||
314 | |||
315 | ret->game_grid = state->game_grid; | ||
316 | ret->game_grid->refcount++; | ||
317 | |||
318 | ret->solved = state->solved; | ||
319 | ret->cheated = state->cheated; | ||
320 | |||
321 | ret->clues = snewn(state->game_grid->num_faces, signed char); | ||
322 | memcpy(ret->clues, state->clues, state->game_grid->num_faces); | ||
323 | |||
324 | ret->lines = snewn(state->game_grid->num_edges, char); | ||
325 | memcpy(ret->lines, state->lines, state->game_grid->num_edges); | ||
326 | |||
327 | ret->line_errors = snewn(state->game_grid->num_edges, unsigned char); | ||
328 | memcpy(ret->line_errors, state->line_errors, state->game_grid->num_edges); | ||
329 | ret->exactly_one_loop = state->exactly_one_loop; | ||
330 | |||
331 | ret->grid_type = state->grid_type; | ||
332 | return ret; | ||
333 | } | ||
334 | |||
335 | static void free_game(game_state *state) | ||
336 | { | ||
337 | if (state) { | ||
338 | grid_free(state->game_grid); | ||
339 | sfree(state->clues); | ||
340 | sfree(state->lines); | ||
341 | sfree(state->line_errors); | ||
342 | sfree(state); | ||
343 | } | ||
344 | } | ||
345 | |||
346 | static solver_state *new_solver_state(const game_state *state, int diff) { | ||
347 | int i; | ||
348 | int num_dots = state->game_grid->num_dots; | ||
349 | int num_faces = state->game_grid->num_faces; | ||
350 | int num_edges = state->game_grid->num_edges; | ||
351 | solver_state *ret = snew(solver_state); | ||
352 | |||
353 | ret->state = dup_game(state); | ||
354 | |||
355 | ret->solver_status = SOLVER_INCOMPLETE; | ||
356 | ret->diff = diff; | ||
357 | |||
358 | ret->dotdsf = snew_dsf(num_dots); | ||
359 | ret->looplen = snewn(num_dots, int); | ||
360 | |||
361 | for (i = 0; i < num_dots; i++) { | ||
362 | ret->looplen[i] = 1; | ||
363 | } | ||
364 | |||
365 | ret->dot_solved = snewn(num_dots, char); | ||
366 | ret->face_solved = snewn(num_faces, char); | ||
367 | memset(ret->dot_solved, FALSE, num_dots); | ||
368 | memset(ret->face_solved, FALSE, num_faces); | ||
369 | |||
370 | ret->dot_yes_count = snewn(num_dots, char); | ||
371 | memset(ret->dot_yes_count, 0, num_dots); | ||
372 | ret->dot_no_count = snewn(num_dots, char); | ||
373 | memset(ret->dot_no_count, 0, num_dots); | ||
374 | ret->face_yes_count = snewn(num_faces, char); | ||
375 | memset(ret->face_yes_count, 0, num_faces); | ||
376 | ret->face_no_count = snewn(num_faces, char); | ||
377 | memset(ret->face_no_count, 0, num_faces); | ||
378 | |||
379 | if (diff < DIFF_NORMAL) { | ||
380 | ret->dlines = NULL; | ||
381 | } else { | ||
382 | ret->dlines = snewn(2*num_edges, char); | ||
383 | memset(ret->dlines, 0, 2*num_edges); | ||
384 | } | ||
385 | |||
386 | if (diff < DIFF_HARD) { | ||
387 | ret->linedsf = NULL; | ||
388 | } else { | ||
389 | ret->linedsf = snew_dsf(state->game_grid->num_edges); | ||
390 | } | ||
391 | |||
392 | return ret; | ||
393 | } | ||
394 | |||
395 | static void free_solver_state(solver_state *sstate) { | ||
396 | if (sstate) { | ||
397 | free_game(sstate->state); | ||
398 | sfree(sstate->dotdsf); | ||
399 | sfree(sstate->looplen); | ||
400 | sfree(sstate->dot_solved); | ||
401 | sfree(sstate->face_solved); | ||
402 | sfree(sstate->dot_yes_count); | ||
403 | sfree(sstate->dot_no_count); | ||
404 | sfree(sstate->face_yes_count); | ||
405 | sfree(sstate->face_no_count); | ||
406 | |||
407 | /* OK, because sfree(NULL) is a no-op */ | ||
408 | sfree(sstate->dlines); | ||
409 | sfree(sstate->linedsf); | ||
410 | |||
411 | sfree(sstate); | ||
412 | } | ||
413 | } | ||
414 | |||
415 | static solver_state *dup_solver_state(const solver_state *sstate) { | ||
416 | game_state *state = sstate->state; | ||
417 | int num_dots = state->game_grid->num_dots; | ||
418 | int num_faces = state->game_grid->num_faces; | ||
419 | int num_edges = state->game_grid->num_edges; | ||
420 | solver_state *ret = snew(solver_state); | ||
421 | |||
422 | ret->state = state = dup_game(sstate->state); | ||
423 | |||
424 | ret->solver_status = sstate->solver_status; | ||
425 | ret->diff = sstate->diff; | ||
426 | |||
427 | ret->dotdsf = snewn(num_dots, int); | ||
428 | ret->looplen = snewn(num_dots, int); | ||
429 | memcpy(ret->dotdsf, sstate->dotdsf, | ||
430 | num_dots * sizeof(int)); | ||
431 | memcpy(ret->looplen, sstate->looplen, | ||
432 | num_dots * sizeof(int)); | ||
433 | |||
434 | ret->dot_solved = snewn(num_dots, char); | ||
435 | ret->face_solved = snewn(num_faces, char); | ||
436 | memcpy(ret->dot_solved, sstate->dot_solved, num_dots); | ||
437 | memcpy(ret->face_solved, sstate->face_solved, num_faces); | ||
438 | |||
439 | ret->dot_yes_count = snewn(num_dots, char); | ||
440 | memcpy(ret->dot_yes_count, sstate->dot_yes_count, num_dots); | ||
441 | ret->dot_no_count = snewn(num_dots, char); | ||
442 | memcpy(ret->dot_no_count, sstate->dot_no_count, num_dots); | ||
443 | |||
444 | ret->face_yes_count = snewn(num_faces, char); | ||
445 | memcpy(ret->face_yes_count, sstate->face_yes_count, num_faces); | ||
446 | ret->face_no_count = snewn(num_faces, char); | ||
447 | memcpy(ret->face_no_count, sstate->face_no_count, num_faces); | ||
448 | |||
449 | if (sstate->dlines) { | ||
450 | ret->dlines = snewn(2*num_edges, char); | ||
451 | memcpy(ret->dlines, sstate->dlines, | ||
452 | 2*num_edges); | ||
453 | } else { | ||
454 | ret->dlines = NULL; | ||
455 | } | ||
456 | |||
457 | if (sstate->linedsf) { | ||
458 | ret->linedsf = snewn(num_edges, int); | ||
459 | memcpy(ret->linedsf, sstate->linedsf, | ||
460 | num_edges * sizeof(int)); | ||
461 | } else { | ||
462 | ret->linedsf = NULL; | ||
463 | } | ||
464 | |||
465 | return ret; | ||
466 | } | ||
467 | |||
468 | static game_params *default_params(void) | ||
469 | { | ||
470 | game_params *ret = snew(game_params); | ||
471 | |||
472 | #ifdef SLOW_SYSTEM | ||
473 | ret->h = 7; | ||
474 | ret->w = 7; | ||
475 | #else | ||
476 | ret->h = 10; | ||
477 | ret->w = 10; | ||
478 | #endif | ||
479 | ret->diff = DIFF_EASY; | ||
480 | ret->type = 0; | ||
481 | |||
482 | return ret; | ||
483 | } | ||
484 | |||
485 | static game_params *dup_params(const game_params *params) | ||
486 | { | ||
487 | game_params *ret = snew(game_params); | ||
488 | |||
489 | *ret = *params; /* structure copy */ | ||
490 | return ret; | ||
491 | } | ||
492 | |||
493 | static const game_params presets[] = { | ||
494 | #ifdef SMALL_SCREEN | ||
495 | { 7, 7, DIFF_EASY, 0 }, | ||
496 | { 7, 7, DIFF_NORMAL, 0 }, | ||
497 | { 7, 7, DIFF_HARD, 0 }, | ||
498 | { 7, 7, DIFF_HARD, 1 }, | ||
499 | { 7, 7, DIFF_HARD, 2 }, | ||
500 | { 5, 5, DIFF_HARD, 3 }, | ||
501 | { 7, 7, DIFF_HARD, 4 }, | ||
502 | { 5, 4, DIFF_HARD, 5 }, | ||
503 | { 5, 5, DIFF_HARD, 6 }, | ||
504 | { 5, 5, DIFF_HARD, 7 }, | ||
505 | { 3, 3, DIFF_HARD, 8 }, | ||
506 | { 3, 3, DIFF_HARD, 9 }, | ||
507 | { 3, 3, DIFF_HARD, 10 }, | ||
508 | { 6, 6, DIFF_HARD, 11 }, | ||
509 | { 6, 6, DIFF_HARD, 12 }, | ||
510 | #else | ||
511 | { 7, 7, DIFF_EASY, 0 }, | ||
512 | { 10, 10, DIFF_EASY, 0 }, | ||
513 | { 7, 7, DIFF_NORMAL, 0 }, | ||
514 | { 10, 10, DIFF_NORMAL, 0 }, | ||
515 | { 7, 7, DIFF_HARD, 0 }, | ||
516 | { 10, 10, DIFF_HARD, 0 }, | ||
517 | { 10, 10, DIFF_HARD, 1 }, | ||
518 | { 12, 10, DIFF_HARD, 2 }, | ||
519 | { 7, 7, DIFF_HARD, 3 }, | ||
520 | { 9, 9, DIFF_HARD, 4 }, | ||
521 | { 5, 4, DIFF_HARD, 5 }, | ||
522 | { 7, 7, DIFF_HARD, 6 }, | ||
523 | { 5, 5, DIFF_HARD, 7 }, | ||
524 | { 5, 5, DIFF_HARD, 8 }, | ||
525 | { 5, 4, DIFF_HARD, 9 }, | ||
526 | { 5, 4, DIFF_HARD, 10 }, | ||
527 | { 10, 10, DIFF_HARD, 11 }, | ||
528 | { 10, 10, DIFF_HARD, 12 } | ||
529 | #endif | ||
530 | }; | ||
531 | |||
532 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
533 | { | ||
534 | game_params *tmppar; | ||
535 | char buf[80]; | ||
536 | |||
537 | if (i < 0 || i >= lenof(presets)) | ||
538 | return FALSE; | ||
539 | |||
540 | tmppar = snew(game_params); | ||
541 | *tmppar = presets[i]; | ||
542 | *params = tmppar; | ||
543 | sprintf(buf, "%dx%d %s - %s", tmppar->h, tmppar->w, | ||
544 | gridnames[tmppar->type], diffnames[tmppar->diff]); | ||
545 | *name = dupstr(buf); | ||
546 | |||
547 | return TRUE; | ||
548 | } | ||
549 | |||
550 | static void free_params(game_params *params) | ||
551 | { | ||
552 | sfree(params); | ||
553 | } | ||
554 | |||
555 | static void decode_params(game_params *params, char const *string) | ||
556 | { | ||
557 | params->h = params->w = atoi(string); | ||
558 | params->diff = DIFF_EASY; | ||
559 | while (*string && isdigit((unsigned char)*string)) string++; | ||
560 | if (*string == 'x') { | ||
561 | string++; | ||
562 | params->h = atoi(string); | ||
563 | while (*string && isdigit((unsigned char)*string)) string++; | ||
564 | } | ||
565 | if (*string == 't') { | ||
566 | string++; | ||
567 | params->type = atoi(string); | ||
568 | while (*string && isdigit((unsigned char)*string)) string++; | ||
569 | } | ||
570 | if (*string == 'd') { | ||
571 | int i; | ||
572 | string++; | ||
573 | for (i = 0; i < DIFF_MAX; i++) | ||
574 | if (*string == diffchars[i]) | ||
575 | params->diff = i; | ||
576 | if (*string) string++; | ||
577 | } | ||
578 | } | ||
579 | |||
580 | static char *encode_params(const game_params *params, int full) | ||
581 | { | ||
582 | char str[80]; | ||
583 | sprintf(str, "%dx%dt%d", params->w, params->h, params->type); | ||
584 | if (full) | ||
585 | sprintf(str + strlen(str), "d%c", diffchars[params->diff]); | ||
586 | return dupstr(str); | ||
587 | } | ||
588 | |||
589 | static config_item *game_configure(const game_params *params) | ||
590 | { | ||
591 | config_item *ret; | ||
592 | char buf[80]; | ||
593 | |||
594 | ret = snewn(5, config_item); | ||
595 | |||
596 | ret[0].name = "Width"; | ||
597 | ret[0].type = C_STRING; | ||
598 | sprintf(buf, "%d", params->w); | ||
599 | ret[0].sval = dupstr(buf); | ||
600 | ret[0].ival = 0; | ||
601 | |||
602 | ret[1].name = "Height"; | ||
603 | ret[1].type = C_STRING; | ||
604 | sprintf(buf, "%d", params->h); | ||
605 | ret[1].sval = dupstr(buf); | ||
606 | ret[1].ival = 0; | ||
607 | |||
608 | ret[2].name = "Grid type"; | ||
609 | ret[2].type = C_CHOICES; | ||
610 | ret[2].sval = GRID_CONFIGS; | ||
611 | ret[2].ival = params->type; | ||
612 | |||
613 | ret[3].name = "Difficulty"; | ||
614 | ret[3].type = C_CHOICES; | ||
615 | ret[3].sval = DIFFCONFIG; | ||
616 | ret[3].ival = params->diff; | ||
617 | |||
618 | ret[4].name = NULL; | ||
619 | ret[4].type = C_END; | ||
620 | ret[4].sval = NULL; | ||
621 | ret[4].ival = 0; | ||
622 | |||
623 | return ret; | ||
624 | } | ||
625 | |||
626 | static game_params *custom_params(const config_item *cfg) | ||
627 | { | ||
628 | game_params *ret = snew(game_params); | ||
629 | |||
630 | ret->w = atoi(cfg[0].sval); | ||
631 | ret->h = atoi(cfg[1].sval); | ||
632 | ret->type = cfg[2].ival; | ||
633 | ret->diff = cfg[3].ival; | ||
634 | |||
635 | return ret; | ||
636 | } | ||
637 | |||
638 | static char *validate_params(const game_params *params, int full) | ||
639 | { | ||
640 | if (params->type < 0 || params->type >= NUM_GRID_TYPES) | ||
641 | return "Illegal grid type"; | ||
642 | if (params->w < grid_size_limits[params->type].amin || | ||
643 | params->h < grid_size_limits[params->type].amin) | ||
644 | return grid_size_limits[params->type].aerr; | ||
645 | if (params->w < grid_size_limits[params->type].omin && | ||
646 | params->h < grid_size_limits[params->type].omin) | ||
647 | return grid_size_limits[params->type].oerr; | ||
648 | |||
649 | /* | ||
650 | * This shouldn't be able to happen at all, since decode_params | ||
651 | * and custom_params will never generate anything that isn't | ||
652 | * within range. | ||
653 | */ | ||
654 | assert(params->diff < DIFF_MAX); | ||
655 | |||
656 | return NULL; | ||
657 | } | ||
658 | |||
659 | /* Returns a newly allocated string describing the current puzzle */ | ||
660 | static char *state_to_text(const game_state *state) | ||
661 | { | ||
662 | grid *g = state->game_grid; | ||
663 | char *retval; | ||
664 | int num_faces = g->num_faces; | ||
665 | char *description = snewn(num_faces + 1, char); | ||
666 | char *dp = description; | ||
667 | int empty_count = 0; | ||
668 | int i; | ||
669 | |||
670 | for (i = 0; i < num_faces; i++) { | ||
671 | if (state->clues[i] < 0) { | ||
672 | if (empty_count > 25) { | ||
673 | dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); | ||
674 | empty_count = 0; | ||
675 | } | ||
676 | empty_count++; | ||
677 | } else { | ||
678 | if (empty_count) { | ||
679 | dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); | ||
680 | empty_count = 0; | ||
681 | } | ||
682 | dp += sprintf(dp, "%c", (int)CLUE2CHAR(state->clues[i])); | ||
683 | } | ||
684 | } | ||
685 | |||
686 | if (empty_count) | ||
687 | dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1)); | ||
688 | |||
689 | retval = dupstr(description); | ||
690 | sfree(description); | ||
691 | |||
692 | return retval; | ||
693 | } | ||
694 | |||
695 | #define GRID_DESC_SEP '_' | ||
696 | |||
697 | /* Splits up a (optional) grid_desc from the game desc. Returns the | ||
698 | * grid_desc (which needs freeing) and updates the desc pointer to | ||
699 | * start of real desc, or returns NULL if no desc. */ | ||
700 | static char *extract_grid_desc(const char **desc) | ||
701 | { | ||
702 | char *sep = strchr(*desc, GRID_DESC_SEP), *gd; | ||
703 | int gd_len; | ||
704 | |||
705 | if (!sep) return NULL; | ||
706 | |||
707 | gd_len = sep - (*desc); | ||
708 | gd = snewn(gd_len+1, char); | ||
709 | memcpy(gd, *desc, gd_len); | ||
710 | gd[gd_len] = '\0'; | ||
711 | |||
712 | *desc = sep+1; | ||
713 | |||
714 | return gd; | ||
715 | } | ||
716 | |||
717 | /* We require that the params pass the test in validate_params and that the | ||
718 | * description fills the entire game area */ | ||
719 | static char *validate_desc(const game_params *params, const char *desc) | ||
720 | { | ||
721 | int count = 0; | ||
722 | grid *g; | ||
723 | char *grid_desc, *ret; | ||
724 | |||
725 | /* It's pretty inefficient to do this just for validation. All we need to | ||
726 | * know is the precise number of faces. */ | ||
727 | grid_desc = extract_grid_desc(&desc); | ||
728 | ret = grid_validate_desc(grid_types[params->type], params->w, params->h, grid_desc); | ||
729 | if (ret) return ret; | ||
730 | |||
731 | g = loopy_generate_grid(params, grid_desc); | ||
732 | if (grid_desc) sfree(grid_desc); | ||
733 | |||
734 | for (; *desc; ++desc) { | ||
735 | if ((*desc >= '0' && *desc <= '9') || (*desc >= 'A' && *desc <= 'Z')) { | ||
736 | count++; | ||
737 | continue; | ||
738 | } | ||
739 | if (*desc >= 'a') { | ||
740 | count += *desc - 'a' + 1; | ||
741 | continue; | ||
742 | } | ||
743 | return "Unknown character in description"; | ||
744 | } | ||
745 | |||
746 | if (count < g->num_faces) | ||
747 | return "Description too short for board size"; | ||
748 | if (count > g->num_faces) | ||
749 | return "Description too long for board size"; | ||
750 | |||
751 | grid_free(g); | ||
752 | |||
753 | return NULL; | ||
754 | } | ||
755 | |||
756 | /* Sums the lengths of the numbers in range [0,n) */ | ||
757 | /* See equivalent function in solo.c for justification of this. */ | ||
758 | static int len_0_to_n(int n) | ||
759 | { | ||
760 | int len = 1; /* Counting 0 as a bit of a special case */ | ||
761 | int i; | ||
762 | |||
763 | for (i = 1; i < n; i *= 10) { | ||
764 | len += max(n - i, 0); | ||
765 | } | ||
766 | |||
767 | return len; | ||
768 | } | ||
769 | |||
770 | static char *encode_solve_move(const game_state *state) | ||
771 | { | ||
772 | int len; | ||
773 | char *ret, *p; | ||
774 | int i; | ||
775 | int num_edges = state->game_grid->num_edges; | ||
776 | |||
777 | /* This is going to return a string representing the moves needed to set | ||
778 | * every line in a grid to be the same as the ones in 'state'. The exact | ||
779 | * length of this string is predictable. */ | ||
780 | |||
781 | len = 1; /* Count the 'S' prefix */ | ||
782 | /* Numbers in all lines */ | ||
783 | len += len_0_to_n(num_edges); | ||
784 | /* For each line we also have a letter */ | ||
785 | len += num_edges; | ||
786 | |||
787 | ret = snewn(len + 1, char); | ||
788 | p = ret; | ||
789 | |||
790 | p += sprintf(p, "S"); | ||
791 | |||
792 | for (i = 0; i < num_edges; i++) { | ||
793 | switch (state->lines[i]) { | ||
794 | case LINE_YES: | ||
795 | p += sprintf(p, "%dy", i); | ||
796 | break; | ||
797 | case LINE_NO: | ||
798 | p += sprintf(p, "%dn", i); | ||
799 | break; | ||
800 | } | ||
801 | } | ||
802 | |||
803 | /* No point in doing sums like that if they're going to be wrong */ | ||
804 | assert(strlen(ret) <= (size_t)len); | ||
805 | return ret; | ||
806 | } | ||
807 | |||
808 | static game_ui *new_ui(const game_state *state) | ||
809 | { | ||
810 | return NULL; | ||
811 | } | ||
812 | |||
813 | static void free_ui(game_ui *ui) | ||
814 | { | ||
815 | } | ||
816 | |||
817 | static char *encode_ui(const game_ui *ui) | ||
818 | { | ||
819 | return NULL; | ||
820 | } | ||
821 | |||
822 | static void decode_ui(game_ui *ui, const char *encoding) | ||
823 | { | ||
824 | } | ||
825 | |||
826 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
827 | const game_state *newstate) | ||
828 | { | ||
829 | } | ||
830 | |||
831 | static void game_compute_size(const game_params *params, int tilesize, | ||
832 | int *x, int *y) | ||
833 | { | ||
834 | int grid_width, grid_height, rendered_width, rendered_height; | ||
835 | int g_tilesize; | ||
836 | |||
837 | grid_compute_size(grid_types[params->type], params->w, params->h, | ||
838 | &g_tilesize, &grid_width, &grid_height); | ||
839 | |||
840 | /* multiply first to minimise rounding error on integer division */ | ||
841 | rendered_width = grid_width * tilesize / g_tilesize; | ||
842 | rendered_height = grid_height * tilesize / g_tilesize; | ||
843 | *x = rendered_width + 2 * BORDER(tilesize) + 1; | ||
844 | *y = rendered_height + 2 * BORDER(tilesize) + 1; | ||
845 | } | ||
846 | |||
847 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
848 | const game_params *params, int tilesize) | ||
849 | { | ||
850 | ds->tilesize = tilesize; | ||
851 | } | ||
852 | |||
853 | static float *game_colours(frontend *fe, int *ncolours) | ||
854 | { | ||
855 | float *ret = snewn(3 * NCOLOURS, float); | ||
856 | |||
857 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
858 | |||
859 | ret[COL_FOREGROUND * 3 + 0] = 0.0F; | ||
860 | ret[COL_FOREGROUND * 3 + 1] = 0.0F; | ||
861 | ret[COL_FOREGROUND * 3 + 2] = 0.0F; | ||
862 | |||
863 | /* | ||
864 | * We want COL_LINEUNKNOWN to be a yellow which is a bit darker | ||
865 | * than the background. (I previously set it to 0.8,0.8,0, but | ||
866 | * found that this went badly with the 0.8,0.8,0.8 favoured as a | ||
867 | * background by the Java frontend.) | ||
868 | */ | ||
869 | ret[COL_LINEUNKNOWN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F; | ||
870 | ret[COL_LINEUNKNOWN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F; | ||
871 | ret[COL_LINEUNKNOWN * 3 + 2] = 0.0F; | ||
872 | |||
873 | ret[COL_HIGHLIGHT * 3 + 0] = 1.0F; | ||
874 | ret[COL_HIGHLIGHT * 3 + 1] = 1.0F; | ||
875 | ret[COL_HIGHLIGHT * 3 + 2] = 1.0F; | ||
876 | |||
877 | ret[COL_MISTAKE * 3 + 0] = 1.0F; | ||
878 | ret[COL_MISTAKE * 3 + 1] = 0.0F; | ||
879 | ret[COL_MISTAKE * 3 + 2] = 0.0F; | ||
880 | |||
881 | ret[COL_SATISFIED * 3 + 0] = 0.0F; | ||
882 | ret[COL_SATISFIED * 3 + 1] = 0.0F; | ||
883 | ret[COL_SATISFIED * 3 + 2] = 0.0F; | ||
884 | |||
885 | /* We want the faint lines to be a bit darker than the background. | ||
886 | * Except if the background is pretty dark already; then it ought to be a | ||
887 | * bit lighter. Oy vey. | ||
888 | */ | ||
889 | ret[COL_FAINT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F; | ||
890 | ret[COL_FAINT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F; | ||
891 | ret[COL_FAINT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.9F; | ||
892 | |||
893 | *ncolours = NCOLOURS; | ||
894 | return ret; | ||
895 | } | ||
896 | |||
897 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
898 | { | ||
899 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
900 | int num_faces = state->game_grid->num_faces; | ||
901 | int num_edges = state->game_grid->num_edges; | ||
902 | int i; | ||
903 | |||
904 | ds->tilesize = 0; | ||
905 | ds->started = 0; | ||
906 | ds->lines = snewn(num_edges, char); | ||
907 | ds->clue_error = snewn(num_faces, char); | ||
908 | ds->clue_satisfied = snewn(num_faces, char); | ||
909 | ds->textx = snewn(num_faces, int); | ||
910 | ds->texty = snewn(num_faces, int); | ||
911 | ds->flashing = 0; | ||
912 | |||
913 | memset(ds->lines, LINE_UNKNOWN, num_edges); | ||
914 | memset(ds->clue_error, 0, num_faces); | ||
915 | memset(ds->clue_satisfied, 0, num_faces); | ||
916 | for (i = 0; i < num_faces; i++) | ||
917 | ds->textx[i] = ds->texty[i] = -1; | ||
918 | |||
919 | return ds; | ||
920 | } | ||
921 | |||
922 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
923 | { | ||
924 | sfree(ds->textx); | ||
925 | sfree(ds->texty); | ||
926 | sfree(ds->clue_error); | ||
927 | sfree(ds->clue_satisfied); | ||
928 | sfree(ds->lines); | ||
929 | sfree(ds); | ||
930 | } | ||
931 | |||
932 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
933 | { | ||
934 | return TRUE; | ||
935 | } | ||
936 | |||
937 | static float game_anim_length(const game_state *oldstate, | ||
938 | const game_state *newstate, int dir, game_ui *ui) | ||
939 | { | ||
940 | return 0.0F; | ||
941 | } | ||
942 | |||
943 | static int game_can_format_as_text_now(const game_params *params) | ||
944 | { | ||
945 | if (params->type != 0) | ||
946 | return FALSE; | ||
947 | return TRUE; | ||
948 | } | ||
949 | |||
950 | static char *game_text_format(const game_state *state) | ||
951 | { | ||
952 | int w, h, W, H; | ||
953 | int x, y, i; | ||
954 | int cell_size; | ||
955 | char *ret; | ||
956 | grid *g = state->game_grid; | ||
957 | grid_face *f; | ||
958 | |||
959 | assert(state->grid_type == 0); | ||
960 | |||
961 | /* Work out the basic size unit */ | ||
962 | f = g->faces; /* first face */ | ||
963 | assert(f->order == 4); | ||
964 | /* The dots are ordered clockwise, so the two opposite | ||
965 | * corners are guaranteed to span the square */ | ||
966 | cell_size = abs(f->dots[0]->x - f->dots[2]->x); | ||
967 | |||
968 | w = (g->highest_x - g->lowest_x) / cell_size; | ||
969 | h = (g->highest_y - g->lowest_y) / cell_size; | ||
970 | |||
971 | /* Create a blank "canvas" to "draw" on */ | ||
972 | W = 2 * w + 2; | ||
973 | H = 2 * h + 1; | ||
974 | ret = snewn(W * H + 1, char); | ||
975 | for (y = 0; y < H; y++) { | ||
976 | for (x = 0; x < W-1; x++) { | ||
977 | ret[y*W + x] = ' '; | ||
978 | } | ||
979 | ret[y*W + W-1] = '\n'; | ||
980 | } | ||
981 | ret[H*W] = '\0'; | ||
982 | |||
983 | /* Fill in edge info */ | ||
984 | for (i = 0; i < g->num_edges; i++) { | ||
985 | grid_edge *e = g->edges + i; | ||
986 | /* Cell coordinates, from (0,0) to (w-1,h-1) */ | ||
987 | int x1 = (e->dot1->x - g->lowest_x) / cell_size; | ||
988 | int x2 = (e->dot2->x - g->lowest_x) / cell_size; | ||
989 | int y1 = (e->dot1->y - g->lowest_y) / cell_size; | ||
990 | int y2 = (e->dot2->y - g->lowest_y) / cell_size; | ||
991 | /* Midpoint, in canvas coordinates (canvas coordinates are just twice | ||
992 | * cell coordinates) */ | ||
993 | x = x1 + x2; | ||
994 | y = y1 + y2; | ||
995 | switch (state->lines[i]) { | ||
996 | case LINE_YES: | ||
997 | ret[y*W + x] = (y1 == y2) ? '-' : '|'; | ||
998 | break; | ||
999 | case LINE_NO: | ||
1000 | ret[y*W + x] = 'x'; | ||
1001 | break; | ||
1002 | case LINE_UNKNOWN: | ||
1003 | break; /* already a space */ | ||
1004 | default: | ||
1005 | assert(!"Illegal line state"); | ||
1006 | } | ||
1007 | } | ||
1008 | |||
1009 | /* Fill in clues */ | ||
1010 | for (i = 0; i < g->num_faces; i++) { | ||
1011 | int x1, x2, y1, y2; | ||
1012 | |||
1013 | f = g->faces + i; | ||
1014 | assert(f->order == 4); | ||
1015 | /* Cell coordinates, from (0,0) to (w-1,h-1) */ | ||
1016 | x1 = (f->dots[0]->x - g->lowest_x) / cell_size; | ||
1017 | x2 = (f->dots[2]->x - g->lowest_x) / cell_size; | ||
1018 | y1 = (f->dots[0]->y - g->lowest_y) / cell_size; | ||
1019 | y2 = (f->dots[2]->y - g->lowest_y) / cell_size; | ||
1020 | /* Midpoint, in canvas coordinates */ | ||
1021 | x = x1 + x2; | ||
1022 | y = y1 + y2; | ||
1023 | ret[y*W + x] = CLUE2CHAR(state->clues[i]); | ||
1024 | } | ||
1025 | return ret; | ||
1026 | } | ||
1027 | |||
1028 | /* ---------------------------------------------------------------------- | ||
1029 | * Debug code | ||
1030 | */ | ||
1031 | |||
1032 | #ifdef DEBUG_CACHES | ||
1033 | static void check_caches(const solver_state* sstate) | ||
1034 | { | ||
1035 | int i; | ||
1036 | const game_state *state = sstate->state; | ||
1037 | const grid *g = state->game_grid; | ||
1038 | |||
1039 | for (i = 0; i < g->num_dots; i++) { | ||
1040 | assert(dot_order(state, i, LINE_YES) == sstate->dot_yes_count[i]); | ||
1041 | assert(dot_order(state, i, LINE_NO) == sstate->dot_no_count[i]); | ||
1042 | } | ||
1043 | |||
1044 | for (i = 0; i < g->num_faces; i++) { | ||
1045 | assert(face_order(state, i, LINE_YES) == sstate->face_yes_count[i]); | ||
1046 | assert(face_order(state, i, LINE_NO) == sstate->face_no_count[i]); | ||
1047 | } | ||
1048 | } | ||
1049 | |||
1050 | #if 0 | ||
1051 | #define check_caches(s) \ | ||
1052 | do { \ | ||
1053 | fprintf(stderr, "check_caches at line %d\n", __LINE__); \ | ||
1054 | check_caches(s); \ | ||
1055 | } while (0) | ||
1056 | #endif | ||
1057 | #endif /* DEBUG_CACHES */ | ||
1058 | |||
1059 | /* ---------------------------------------------------------------------- | ||
1060 | * Solver utility functions | ||
1061 | */ | ||
1062 | |||
1063 | /* Sets the line (with index i) to the new state 'line_new', and updates | ||
1064 | * the cached counts of any affected faces and dots. | ||
1065 | * Returns TRUE if this actually changed the line's state. */ | ||
1066 | static int solver_set_line(solver_state *sstate, int i, | ||
1067 | enum line_state line_new | ||
1068 | #ifdef SHOW_WORKING | ||
1069 | , const char *reason | ||
1070 | #endif | ||
1071 | ) | ||
1072 | { | ||
1073 | game_state *state = sstate->state; | ||
1074 | grid *g; | ||
1075 | grid_edge *e; | ||
1076 | |||
1077 | assert(line_new != LINE_UNKNOWN); | ||
1078 | |||
1079 | check_caches(sstate); | ||
1080 | |||
1081 | if (state->lines[i] == line_new) { | ||
1082 | return FALSE; /* nothing changed */ | ||
1083 | } | ||
1084 | state->lines[i] = line_new; | ||
1085 | |||
1086 | #ifdef SHOW_WORKING | ||
1087 | fprintf(stderr, "solver: set line [%d] to %s (%s)\n", | ||
1088 | i, line_new == LINE_YES ? "YES" : "NO", | ||
1089 | reason); | ||
1090 | #endif | ||
1091 | |||
1092 | g = state->game_grid; | ||
1093 | e = g->edges + i; | ||
1094 | |||
1095 | /* Update the cache for both dots and both faces affected by this. */ | ||
1096 | if (line_new == LINE_YES) { | ||
1097 | sstate->dot_yes_count[e->dot1 - g->dots]++; | ||
1098 | sstate->dot_yes_count[e->dot2 - g->dots]++; | ||
1099 | if (e->face1) { | ||
1100 | sstate->face_yes_count[e->face1 - g->faces]++; | ||
1101 | } | ||
1102 | if (e->face2) { | ||
1103 | sstate->face_yes_count[e->face2 - g->faces]++; | ||
1104 | } | ||
1105 | } else { | ||
1106 | sstate->dot_no_count[e->dot1 - g->dots]++; | ||
1107 | sstate->dot_no_count[e->dot2 - g->dots]++; | ||
1108 | if (e->face1) { | ||
1109 | sstate->face_no_count[e->face1 - g->faces]++; | ||
1110 | } | ||
1111 | if (e->face2) { | ||
1112 | sstate->face_no_count[e->face2 - g->faces]++; | ||
1113 | } | ||
1114 | } | ||
1115 | |||
1116 | check_caches(sstate); | ||
1117 | return TRUE; | ||
1118 | } | ||
1119 | |||
1120 | #ifdef SHOW_WORKING | ||
1121 | #define solver_set_line(a, b, c) \ | ||
1122 | solver_set_line(a, b, c, __FUNCTION__) | ||
1123 | #endif | ||
1124 | |||
1125 | /* | ||
1126 | * Merge two dots due to the existence of an edge between them. | ||
1127 | * Updates the dsf tracking equivalence classes, and keeps track of | ||
1128 | * the length of path each dot is currently a part of. | ||
1129 | * Returns TRUE if the dots were already linked, ie if they are part of a | ||
1130 | * closed loop, and false otherwise. | ||
1131 | */ | ||
1132 | static int merge_dots(solver_state *sstate, int edge_index) | ||
1133 | { | ||
1134 | int i, j, len; | ||
1135 | grid *g = sstate->state->game_grid; | ||
1136 | grid_edge *e = g->edges + edge_index; | ||
1137 | |||
1138 | i = e->dot1 - g->dots; | ||
1139 | j = e->dot2 - g->dots; | ||
1140 | |||
1141 | i = dsf_canonify(sstate->dotdsf, i); | ||
1142 | j = dsf_canonify(sstate->dotdsf, j); | ||
1143 | |||
1144 | if (i == j) { | ||
1145 | return TRUE; | ||
1146 | } else { | ||
1147 | len = sstate->looplen[i] + sstate->looplen[j]; | ||
1148 | dsf_merge(sstate->dotdsf, i, j); | ||
1149 | i = dsf_canonify(sstate->dotdsf, i); | ||
1150 | sstate->looplen[i] = len; | ||
1151 | return FALSE; | ||
1152 | } | ||
1153 | } | ||
1154 | |||
1155 | /* Merge two lines because the solver has deduced that they must be either | ||
1156 | * identical or opposite. Returns TRUE if this is new information, otherwise | ||
1157 | * FALSE. */ | ||
1158 | static int merge_lines(solver_state *sstate, int i, int j, int inverse | ||
1159 | #ifdef SHOW_WORKING | ||
1160 | , const char *reason | ||
1161 | #endif | ||
1162 | ) | ||
1163 | { | ||
1164 | int inv_tmp; | ||
1165 | |||
1166 | assert(i < sstate->state->game_grid->num_edges); | ||
1167 | assert(j < sstate->state->game_grid->num_edges); | ||
1168 | |||
1169 | i = edsf_canonify(sstate->linedsf, i, &inv_tmp); | ||
1170 | inverse ^= inv_tmp; | ||
1171 | j = edsf_canonify(sstate->linedsf, j, &inv_tmp); | ||
1172 | inverse ^= inv_tmp; | ||
1173 | |||
1174 | edsf_merge(sstate->linedsf, i, j, inverse); | ||
1175 | |||
1176 | #ifdef SHOW_WORKING | ||
1177 | if (i != j) { | ||
1178 | fprintf(stderr, "%s [%d] [%d] %s(%s)\n", | ||
1179 | __FUNCTION__, i, j, | ||
1180 | inverse ? "inverse " : "", reason); | ||
1181 | } | ||
1182 | #endif | ||
1183 | return (i != j); | ||
1184 | } | ||
1185 | |||
1186 | #ifdef SHOW_WORKING | ||
1187 | #define merge_lines(a, b, c, d) \ | ||
1188 | merge_lines(a, b, c, d, __FUNCTION__) | ||
1189 | #endif | ||
1190 | |||
1191 | /* Count the number of lines of a particular type currently going into the | ||
1192 | * given dot. */ | ||
1193 | static int dot_order(const game_state* state, int dot, char line_type) | ||
1194 | { | ||
1195 | int n = 0; | ||
1196 | grid *g = state->game_grid; | ||
1197 | grid_dot *d = g->dots + dot; | ||
1198 | int i; | ||
1199 | |||
1200 | for (i = 0; i < d->order; i++) { | ||
1201 | grid_edge *e = d->edges[i]; | ||
1202 | if (state->lines[e - g->edges] == line_type) | ||
1203 | ++n; | ||
1204 | } | ||
1205 | return n; | ||
1206 | } | ||
1207 | |||
1208 | /* Count the number of lines of a particular type currently surrounding the | ||
1209 | * given face */ | ||
1210 | static int face_order(const game_state* state, int face, char line_type) | ||
1211 | { | ||
1212 | int n = 0; | ||
1213 | grid *g = state->game_grid; | ||
1214 | grid_face *f = g->faces + face; | ||
1215 | int i; | ||
1216 | |||
1217 | for (i = 0; i < f->order; i++) { | ||
1218 | grid_edge *e = f->edges[i]; | ||
1219 | if (state->lines[e - g->edges] == line_type) | ||
1220 | ++n; | ||
1221 | } | ||
1222 | return n; | ||
1223 | } | ||
1224 | |||
1225 | /* Set all lines bordering a dot of type old_type to type new_type | ||
1226 | * Return value tells caller whether this function actually did anything */ | ||
1227 | static int dot_setall(solver_state *sstate, int dot, | ||
1228 | char old_type, char new_type) | ||
1229 | { | ||
1230 | int retval = FALSE, r; | ||
1231 | game_state *state = sstate->state; | ||
1232 | grid *g; | ||
1233 | grid_dot *d; | ||
1234 | int i; | ||
1235 | |||
1236 | if (old_type == new_type) | ||
1237 | return FALSE; | ||
1238 | |||
1239 | g = state->game_grid; | ||
1240 | d = g->dots + dot; | ||
1241 | |||
1242 | for (i = 0; i < d->order; i++) { | ||
1243 | int line_index = d->edges[i] - g->edges; | ||
1244 | if (state->lines[line_index] == old_type) { | ||
1245 | r = solver_set_line(sstate, line_index, new_type); | ||
1246 | assert(r == TRUE); | ||
1247 | retval = TRUE; | ||
1248 | } | ||
1249 | } | ||
1250 | return retval; | ||
1251 | } | ||
1252 | |||
1253 | /* Set all lines bordering a face of type old_type to type new_type */ | ||
1254 | static int face_setall(solver_state *sstate, int face, | ||
1255 | char old_type, char new_type) | ||
1256 | { | ||
1257 | int retval = FALSE, r; | ||
1258 | game_state *state = sstate->state; | ||
1259 | grid *g; | ||
1260 | grid_face *f; | ||
1261 | int i; | ||
1262 | |||
1263 | if (old_type == new_type) | ||
1264 | return FALSE; | ||
1265 | |||
1266 | g = state->game_grid; | ||
1267 | f = g->faces + face; | ||
1268 | |||
1269 | for (i = 0; i < f->order; i++) { | ||
1270 | int line_index = f->edges[i] - g->edges; | ||
1271 | if (state->lines[line_index] == old_type) { | ||
1272 | r = solver_set_line(sstate, line_index, new_type); | ||
1273 | assert(r == TRUE); | ||
1274 | retval = TRUE; | ||
1275 | } | ||
1276 | } | ||
1277 | return retval; | ||
1278 | } | ||
1279 | |||
1280 | /* ---------------------------------------------------------------------- | ||
1281 | * Loop generation and clue removal | ||
1282 | */ | ||
1283 | |||
1284 | static void add_full_clues(game_state *state, random_state *rs) | ||
1285 | { | ||
1286 | signed char *clues = state->clues; | ||
1287 | grid *g = state->game_grid; | ||
1288 | char *board = snewn(g->num_faces, char); | ||
1289 | int i; | ||
1290 | |||
1291 | generate_loop(g, board, rs, NULL, NULL); | ||
1292 | |||
1293 | /* Fill out all the clues by initialising to 0, then iterating over | ||
1294 | * all edges and incrementing each clue as we find edges that border | ||
1295 | * between BLACK/WHITE faces. While we're at it, we verify that the | ||
1296 | * algorithm does work, and there aren't any GREY faces still there. */ | ||
1297 | memset(clues, 0, g->num_faces); | ||
1298 | for (i = 0; i < g->num_edges; i++) { | ||
1299 | grid_edge *e = g->edges + i; | ||
1300 | grid_face *f1 = e->face1; | ||
1301 | grid_face *f2 = e->face2; | ||
1302 | enum face_colour c1 = FACE_COLOUR(f1); | ||
1303 | enum face_colour c2 = FACE_COLOUR(f2); | ||
1304 | assert(c1 != FACE_GREY); | ||
1305 | assert(c2 != FACE_GREY); | ||
1306 | if (c1 != c2) { | ||
1307 | if (f1) clues[f1 - g->faces]++; | ||
1308 | if (f2) clues[f2 - g->faces]++; | ||
1309 | } | ||
1310 | } | ||
1311 | sfree(board); | ||
1312 | } | ||
1313 | |||
1314 | |||
1315 | static int game_has_unique_soln(const game_state *state, int diff) | ||
1316 | { | ||
1317 | int ret; | ||
1318 | solver_state *sstate_new; | ||
1319 | solver_state *sstate = new_solver_state((game_state *)state, diff); | ||
1320 | |||
1321 | sstate_new = solve_game_rec(sstate); | ||
1322 | |||
1323 | assert(sstate_new->solver_status != SOLVER_MISTAKE); | ||
1324 | ret = (sstate_new->solver_status == SOLVER_SOLVED); | ||
1325 | |||
1326 | free_solver_state(sstate_new); | ||
1327 | free_solver_state(sstate); | ||
1328 | |||
1329 | return ret; | ||
1330 | } | ||
1331 | |||
1332 | |||
1333 | /* Remove clues one at a time at random. */ | ||
1334 | static game_state *remove_clues(game_state *state, random_state *rs, | ||
1335 | int diff) | ||
1336 | { | ||
1337 | int *face_list; | ||
1338 | int num_faces = state->game_grid->num_faces; | ||
1339 | game_state *ret = dup_game(state), *saved_ret; | ||
1340 | int n; | ||
1341 | |||
1342 | /* We need to remove some clues. We'll do this by forming a list of all | ||
1343 | * available clues, shuffling it, then going along one at a | ||
1344 | * time clearing each clue in turn for which doing so doesn't render the | ||
1345 | * board unsolvable. */ | ||
1346 | face_list = snewn(num_faces, int); | ||
1347 | for (n = 0; n < num_faces; ++n) { | ||
1348 | face_list[n] = n; | ||
1349 | } | ||
1350 | |||
1351 | shuffle(face_list, num_faces, sizeof(int), rs); | ||
1352 | |||
1353 | for (n = 0; n < num_faces; ++n) { | ||
1354 | saved_ret = dup_game(ret); | ||
1355 | ret->clues[face_list[n]] = -1; | ||
1356 | |||
1357 | if (game_has_unique_soln(ret, diff)) { | ||
1358 | free_game(saved_ret); | ||
1359 | } else { | ||
1360 | free_game(ret); | ||
1361 | ret = saved_ret; | ||
1362 | } | ||
1363 | } | ||
1364 | sfree(face_list); | ||
1365 | |||
1366 | return ret; | ||
1367 | } | ||
1368 | |||
1369 | |||
1370 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
1371 | char **aux, int interactive) | ||
1372 | { | ||
1373 | /* solution and description both use run-length encoding in obvious ways */ | ||
1374 | char *retval, *game_desc, *grid_desc; | ||
1375 | grid *g; | ||
1376 | game_state *state = snew(game_state); | ||
1377 | game_state *state_new; | ||
1378 | |||
1379 | grid_desc = grid_new_desc(grid_types[params->type], params->w, params->h, rs); | ||
1380 | state->game_grid = g = loopy_generate_grid(params, grid_desc); | ||
1381 | |||
1382 | state->clues = snewn(g->num_faces, signed char); | ||
1383 | state->lines = snewn(g->num_edges, char); | ||
1384 | state->line_errors = snewn(g->num_edges, unsigned char); | ||
1385 | state->exactly_one_loop = FALSE; | ||
1386 | |||
1387 | state->grid_type = params->type; | ||
1388 | |||
1389 | newboard_please: | ||
1390 | |||
1391 | memset(state->lines, LINE_UNKNOWN, g->num_edges); | ||
1392 | memset(state->line_errors, 0, g->num_edges); | ||
1393 | |||
1394 | state->solved = state->cheated = FALSE; | ||
1395 | |||
1396 | /* Get a new random solvable board with all its clues filled in. Yes, this | ||
1397 | * can loop for ever if the params are suitably unfavourable, but | ||
1398 | * preventing games smaller than 4x4 seems to stop this happening */ | ||
1399 | do { | ||
1400 | add_full_clues(state, rs); | ||
1401 | } while (!game_has_unique_soln(state, params->diff)); | ||
1402 | |||
1403 | state_new = remove_clues(state, rs, params->diff); | ||
1404 | free_game(state); | ||
1405 | state = state_new; | ||
1406 | |||
1407 | |||
1408 | if (params->diff > 0 && game_has_unique_soln(state, params->diff-1)) { | ||
1409 | #ifdef SHOW_WORKING | ||
1410 | fprintf(stderr, "Rejecting board, it is too easy\n"); | ||
1411 | #endif | ||
1412 | goto newboard_please; | ||
1413 | } | ||
1414 | |||
1415 | game_desc = state_to_text(state); | ||
1416 | |||
1417 | free_game(state); | ||
1418 | |||
1419 | if (grid_desc) { | ||
1420 | retval = snewn(strlen(grid_desc) + 1 + strlen(game_desc) + 1, char); | ||
1421 | sprintf(retval, "%s%c%s", grid_desc, (int)GRID_DESC_SEP, game_desc); | ||
1422 | sfree(grid_desc); | ||
1423 | sfree(game_desc); | ||
1424 | } else { | ||
1425 | retval = game_desc; | ||
1426 | } | ||
1427 | |||
1428 | assert(!validate_desc(params, retval)); | ||
1429 | |||
1430 | return retval; | ||
1431 | } | ||
1432 | |||
1433 | static game_state *new_game(midend *me, const game_params *params, | ||
1434 | const char *desc) | ||
1435 | { | ||
1436 | int i; | ||
1437 | game_state *state = snew(game_state); | ||
1438 | int empties_to_make = 0; | ||
1439 | int n,n2; | ||
1440 | const char *dp; | ||
1441 | char *grid_desc; | ||
1442 | grid *g; | ||
1443 | int num_faces, num_edges; | ||
1444 | |||
1445 | grid_desc = extract_grid_desc(&desc); | ||
1446 | state->game_grid = g = loopy_generate_grid(params, grid_desc); | ||
1447 | if (grid_desc) sfree(grid_desc); | ||
1448 | |||
1449 | dp = desc; | ||
1450 | |||
1451 | num_faces = g->num_faces; | ||
1452 | num_edges = g->num_edges; | ||
1453 | |||
1454 | state->clues = snewn(num_faces, signed char); | ||
1455 | state->lines = snewn(num_edges, char); | ||
1456 | state->line_errors = snewn(num_edges, unsigned char); | ||
1457 | state->exactly_one_loop = FALSE; | ||
1458 | |||
1459 | state->solved = state->cheated = FALSE; | ||
1460 | |||
1461 | state->grid_type = params->type; | ||
1462 | |||
1463 | for (i = 0; i < num_faces; i++) { | ||
1464 | if (empties_to_make) { | ||
1465 | empties_to_make--; | ||
1466 | state->clues[i] = -1; | ||
1467 | continue; | ||
1468 | } | ||
1469 | |||
1470 | assert(*dp); | ||
1471 | n = *dp - '0'; | ||
1472 | n2 = *dp - 'A' + 10; | ||
1473 | if (n >= 0 && n < 10) { | ||
1474 | state->clues[i] = n; | ||
1475 | } else if (n2 >= 10 && n2 < 36) { | ||
1476 | state->clues[i] = n2; | ||
1477 | } else { | ||
1478 | n = *dp - 'a' + 1; | ||
1479 | assert(n > 0); | ||
1480 | state->clues[i] = -1; | ||
1481 | empties_to_make = n - 1; | ||
1482 | } | ||
1483 | ++dp; | ||
1484 | } | ||
1485 | |||
1486 | memset(state->lines, LINE_UNKNOWN, num_edges); | ||
1487 | memset(state->line_errors, 0, num_edges); | ||
1488 | return state; | ||
1489 | } | ||
1490 | |||
1491 | /* Calculates the line_errors data, and checks if the current state is a | ||
1492 | * solution */ | ||
1493 | static int check_completion(game_state *state) | ||
1494 | { | ||
1495 | grid *g = state->game_grid; | ||
1496 | int i, ret; | ||
1497 | int *dsf, *component_state; | ||
1498 | int nsilly, nloop, npath, largest_comp, largest_size, total_pathsize; | ||
1499 | enum { COMP_NONE, COMP_LOOP, COMP_PATH, COMP_SILLY, COMP_EMPTY }; | ||
1500 | |||
1501 | memset(state->line_errors, 0, g->num_edges); | ||
1502 | |||
1503 | /* | ||
1504 | * Find loops in the grid, and determine whether the puzzle is | ||
1505 | * solved. | ||
1506 | * | ||
1507 | * Loopy is a bit more complicated than most puzzles that care | ||
1508 | * about loop detection. In most of them, loops are simply | ||
1509 | * _forbidden_; so the obviously right way to do | ||
1510 | * error-highlighting during play is to light up a graph edge red | ||
1511 | * iff it is part of a loop, which is exactly what the centralised | ||
1512 | * findloop.c makes easy. | ||
1513 | * | ||
1514 | * But Loopy is unusual in that you're _supposed_ to be making a | ||
1515 | * loop - and yet _some_ loops are not the right loop. So we need | ||
1516 | * to be more discriminating, by identifying loops one by one and | ||
1517 | * then thinking about which ones to highlight, and so findloop.c | ||
1518 | * isn't quite the right tool for the job in this case. | ||
1519 | * | ||
1520 | * Worse still, consider situations in which the grid contains a | ||
1521 | * loop and also some non-loop edges: there are some cases like | ||
1522 | * this in which the user's intuitive expectation would be to | ||
1523 | * highlight the loop (if you're only about half way through the | ||
1524 | * puzzle and have accidentally made a little loop in some corner | ||
1525 | * of the grid), and others in which they'd be more likely to | ||
1526 | * expect you to highlight the non-loop edges (if you've just | ||
1527 | * closed off a whole loop that you thought was the entire | ||
1528 | * solution, but forgot some disconnected edges in a corner | ||
1529 | * somewhere). So while it's easy enough to check whether the | ||
1530 | * solution is _right_, highlighting the wrong parts is a tricky | ||
1531 | * problem for this puzzle! | ||
1532 | * | ||
1533 | * I'd quite like, in some situations, to identify the largest | ||
1534 | * loop among the player's YES edges, and then light up everything | ||
1535 | * other than that. But finding the longest cycle in a graph is an | ||
1536 | * NP-complete problem (because, in particular, it must return a | ||
1537 | * Hamilton cycle if one exists). | ||
1538 | * | ||
1539 | * However, I think we can make the problem tractable by | ||
1540 | * exercising the Puzzles principle that it isn't absolutely | ||
1541 | * necessary to highlight _all_ errors: the key point is that by | ||
1542 | * the time the user has filled in the whole grid, they should | ||
1543 | * either have seen a completion flash, or have _some_ error | ||
1544 | * highlight showing them why the solution isn't right. So in | ||
1545 | * principle it would be *just about* good enough to highlight | ||
1546 | * just one error in the whole grid, if there was really no better | ||
1547 | * way. But we'd like to highlight as many errors as possible. | ||
1548 | * | ||
1549 | * In this case, I think the simple approach is to make use of the | ||
1550 | * fact that no vertex may have degree > 2, and that's really | ||
1551 | * simple to detect. So the plan goes like this: | ||
1552 | * | ||
1553 | * - Form the dsf of connected components of the graph vertices. | ||
1554 | * | ||
1555 | * - Highlight an error at any vertex with degree > 2. (It so | ||
1556 | * happens that we do this by lighting up all the edges | ||
1557 | * incident to that vertex, but that's an output detail.) | ||
1558 | * | ||
1559 | * - Any component that contains such a vertex is now excluded | ||
1560 | * from further consideration, because it already has a | ||
1561 | * highlight. | ||
1562 | * | ||
1563 | * - The remaining components have no vertex with degree > 2, and | ||
1564 | * hence they all consist of either a simple loop, or a simple | ||
1565 | * path with two endpoints. | ||
1566 | * | ||
1567 | * - For these purposes, group together all the paths and imagine | ||
1568 | * them to be a single component (because in most normal | ||
1569 | * situations the player will gradually build up the solution | ||
1570 | * _not_ all in one connected segment, but as lots of separate | ||
1571 | * little path pieces that gradually connect to each other). | ||
1572 | * | ||
1573 | * - After doing that, if there is exactly one (sensible) | ||
1574 | * component - be it a collection of paths or a loop - then | ||
1575 | * highlight no further edge errors. (The former case is normal | ||
1576 | * during play, and the latter is a potentially solved puzzle.) | ||
1577 | * | ||
1578 | * - Otherwise, find the largest of the sensible components, | ||
1579 | * leave that one unhighlighted, and light the rest up in red. | ||
1580 | */ | ||
1581 | |||
1582 | dsf = snew_dsf(g->num_dots); | ||
1583 | |||
1584 | /* Build the dsf. */ | ||
1585 | for (i = 0; i < g->num_edges; i++) { | ||
1586 | if (state->lines[i] == LINE_YES) { | ||
1587 | grid_edge *e = g->edges + i; | ||
1588 | int d1 = e->dot1 - g->dots, d2 = e->dot2 - g->dots; | ||
1589 | dsf_merge(dsf, d1, d2); | ||
1590 | } | ||
1591 | } | ||
1592 | |||
1593 | /* Initialise a state variable for each connected component. */ | ||
1594 | component_state = snewn(g->num_dots, int); | ||
1595 | for (i = 0; i < g->num_dots; i++) { | ||
1596 | if (dsf_canonify(dsf, i) == i) | ||
1597 | component_state[i] = COMP_LOOP; | ||
1598 | else | ||
1599 | component_state[i] = COMP_NONE; | ||
1600 | } | ||
1601 | |||
1602 | /* Check for dots with degree > 3. Here we also spot dots of | ||
1603 | * degree 1 in which the user has marked all the non-edges as | ||
1604 | * LINE_NO, because those are also clear vertex-level errors, so | ||
1605 | * we give them the same treatment of excluding their connected | ||
1606 | * component from the subsequent loop analysis. */ | ||
1607 | for (i = 0; i < g->num_dots; i++) { | ||
1608 | int comp = dsf_canonify(dsf, i); | ||
1609 | int yes = dot_order(state, i, LINE_YES); | ||
1610 | int unknown = dot_order(state, i, LINE_UNKNOWN); | ||
1611 | if ((yes == 1 && unknown == 0) || (yes >= 3)) { | ||
1612 | /* violation, so mark all YES edges as errors */ | ||
1613 | grid_dot *d = g->dots + i; | ||
1614 | int j; | ||
1615 | for (j = 0; j < d->order; j++) { | ||
1616 | int e = d->edges[j] - g->edges; | ||
1617 | if (state->lines[e] == LINE_YES) | ||
1618 | state->line_errors[e] = TRUE; | ||
1619 | } | ||
1620 | /* And mark this component as not worthy of further | ||
1621 | * consideration. */ | ||
1622 | component_state[comp] = COMP_SILLY; | ||
1623 | |||
1624 | } else if (yes == 0) { | ||
1625 | /* A completely isolated dot must also be excluded it from | ||
1626 | * the subsequent loop highlighting pass, but we tag it | ||
1627 | * with a different enum value to avoid it counting | ||
1628 | * towards the components that inhibit returning a win | ||
1629 | * status. */ | ||
1630 | component_state[comp] = COMP_EMPTY; | ||
1631 | } else if (yes == 1) { | ||
1632 | /* A dot with degree 1 that didn't fall into the 'clearly | ||
1633 | * erroneous' case above indicates that this connected | ||
1634 | * component will be a path rather than a loop - unless | ||
1635 | * something worse elsewhere in the component has | ||
1636 | * classified it as silly. */ | ||
1637 | if (component_state[comp] != COMP_SILLY) | ||
1638 | component_state[comp] = COMP_PATH; | ||
1639 | } | ||
1640 | } | ||
1641 | |||
1642 | /* Count up the components. Also, find the largest sensible | ||
1643 | * component. (Tie-breaking condition is derived from the order of | ||
1644 | * vertices in the grid data structure, which is fairly arbitrary | ||
1645 | * but at least stays stable throughout the game.) */ | ||
1646 | nsilly = nloop = npath = 0; | ||
1647 | total_pathsize = 0; | ||
1648 | largest_comp = largest_size = -1; | ||
1649 | for (i = 0; i < g->num_dots; i++) { | ||
1650 | if (component_state[i] == COMP_SILLY) { | ||
1651 | nsilly++; | ||
1652 | } else if (component_state[i] == COMP_PATH) { | ||
1653 | total_pathsize += dsf_size(dsf, i); | ||
1654 | npath = 1; | ||
1655 | } else if (component_state[i] == COMP_LOOP) { | ||
1656 | int this_size; | ||
1657 | |||
1658 | nloop++; | ||
1659 | |||
1660 | if ((this_size = dsf_size(dsf, i)) > largest_size) { | ||
1661 | largest_comp = i; | ||
1662 | largest_size = this_size; | ||
1663 | } | ||
1664 | } | ||
1665 | } | ||
1666 | if (largest_size < total_pathsize) { | ||
1667 | largest_comp = -1; /* means the paths */ | ||
1668 | largest_size = total_pathsize; | ||
1669 | } | ||
1670 | |||
1671 | if (nloop > 0 && nloop + npath > 1) { | ||
1672 | /* | ||
1673 | * If there are at least two sensible components including at | ||
1674 | * least one loop, highlight all edges in every sensible | ||
1675 | * component that is not the largest one. | ||
1676 | */ | ||
1677 | for (i = 0; i < g->num_edges; i++) { | ||
1678 | if (state->lines[i] == LINE_YES) { | ||
1679 | grid_edge *e = g->edges + i; | ||
1680 | int d1 = e->dot1 - g->dots; /* either endpoint is good enough */ | ||
1681 | int comp = dsf_canonify(dsf, d1); | ||
1682 | if ((component_state[comp] == COMP_PATH && | ||
1683 | -1 != largest_comp) || | ||
1684 | (component_state[comp] == COMP_LOOP && | ||
1685 | comp != largest_comp)) | ||
1686 | state->line_errors[i] = TRUE; | ||
1687 | } | ||
1688 | } | ||
1689 | } | ||
1690 | |||
1691 | if (nloop == 1 && npath == 0 && nsilly == 0) { | ||
1692 | /* | ||
1693 | * If there is exactly one component and it is a loop, then | ||
1694 | * the puzzle is potentially complete, so check the clues. | ||
1695 | */ | ||
1696 | ret = TRUE; | ||
1697 | |||
1698 | for (i = 0; i < g->num_faces; i++) { | ||
1699 | int c = state->clues[i]; | ||
1700 | if (c >= 0 && face_order(state, i, LINE_YES) != c) { | ||
1701 | ret = FALSE; | ||
1702 | break; | ||
1703 | } | ||
1704 | } | ||
1705 | |||
1706 | /* | ||
1707 | * Also, whether or not the puzzle is actually complete, set | ||
1708 | * the flag that says this game_state has exactly one loop and | ||
1709 | * nothing else, which will be used to vary the semantics of | ||
1710 | * clue highlighting at display time. | ||
1711 | */ | ||
1712 | state->exactly_one_loop = TRUE; | ||
1713 | } else { | ||
1714 | ret = FALSE; | ||
1715 | state->exactly_one_loop = FALSE; | ||
1716 | } | ||
1717 | |||
1718 | sfree(component_state); | ||
1719 | sfree(dsf); | ||
1720 | |||
1721 | return ret; | ||
1722 | } | ||
1723 | |||
1724 | /* ---------------------------------------------------------------------- | ||
1725 | * Solver logic | ||
1726 | * | ||
1727 | * Our solver modes operate as follows. Each mode also uses the modes above it. | ||
1728 | * | ||
1729 | * Easy Mode | ||
1730 | * Just implement the rules of the game. | ||
1731 | * | ||
1732 | * Normal and Tricky Modes | ||
1733 | * For each (adjacent) pair of lines through each dot we store a bit for | ||
1734 | * whether at least one of them is on and whether at most one is on. (If we | ||
1735 | * know both or neither is on that's already stored more directly.) | ||
1736 | * | ||
1737 | * Advanced Mode | ||
1738 | * Use edsf data structure to make equivalence classes of lines that are | ||
1739 | * known identical to or opposite to one another. | ||
1740 | */ | ||
1741 | |||
1742 | |||
1743 | /* DLines: | ||
1744 | * For general grids, we consider "dlines" to be pairs of lines joined | ||
1745 | * at a dot. The lines must be adjacent around the dot, so we can think of | ||
1746 | * a dline as being a dot+face combination. Or, a dot+edge combination where | ||
1747 | * the second edge is taken to be the next clockwise edge from the dot. | ||
1748 | * Original loopy code didn't have this extra restriction of the lines being | ||
1749 | * adjacent. From my tests with square grids, this extra restriction seems to | ||
1750 | * take little, if anything, away from the quality of the puzzles. | ||
1751 | * A dline can be uniquely identified by an edge/dot combination, given that | ||
1752 | * a dline-pair always goes clockwise around its common dot. The edge/dot | ||
1753 | * combination can be represented by an edge/bool combination - if bool is | ||
1754 | * TRUE, use edge->dot1 else use edge->dot2. So the total number of dlines is | ||
1755 | * exactly twice the number of edges in the grid - although the dlines | ||
1756 | * spanning the infinite face are not all that useful to the solver. | ||
1757 | * Note that, by convention, a dline goes clockwise around its common dot, | ||
1758 | * which means the dline goes anti-clockwise around its common face. | ||
1759 | */ | ||
1760 | |||
1761 | /* Helper functions for obtaining an index into an array of dlines, given | ||
1762 | * various information. We assume the grid layout conventions about how | ||
1763 | * the various lists are interleaved - see grid_make_consistent() for | ||
1764 | * details. */ | ||
1765 | |||
1766 | /* i points to the first edge of the dline pair, reading clockwise around | ||
1767 | * the dot. */ | ||
1768 | static int dline_index_from_dot(grid *g, grid_dot *d, int i) | ||
1769 | { | ||
1770 | grid_edge *e = d->edges[i]; | ||
1771 | int ret; | ||
1772 | #ifdef DEBUG_DLINES | ||
1773 | grid_edge *e2; | ||
1774 | int i2 = i+1; | ||
1775 | if (i2 == d->order) i2 = 0; | ||
1776 | e2 = d->edges[i2]; | ||
1777 | #endif | ||
1778 | ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0); | ||
1779 | #ifdef DEBUG_DLINES | ||
1780 | printf("dline_index_from_dot: d=%d,i=%d, edges [%d,%d] - %d\n", | ||
1781 | (int)(d - g->dots), i, (int)(e - g->edges), | ||
1782 | (int)(e2 - g->edges), ret); | ||
1783 | #endif | ||
1784 | return ret; | ||
1785 | } | ||
1786 | /* i points to the second edge of the dline pair, reading clockwise around | ||
1787 | * the face. That is, the edges of the dline, starting at edge{i}, read | ||
1788 | * anti-clockwise around the face. By layout conventions, the common dot | ||
1789 | * of the dline will be f->dots[i] */ | ||
1790 | static int dline_index_from_face(grid *g, grid_face *f, int i) | ||
1791 | { | ||
1792 | grid_edge *e = f->edges[i]; | ||
1793 | grid_dot *d = f->dots[i]; | ||
1794 | int ret; | ||
1795 | #ifdef DEBUG_DLINES | ||
1796 | grid_edge *e2; | ||
1797 | int i2 = i - 1; | ||
1798 | if (i2 < 0) i2 += f->order; | ||
1799 | e2 = f->edges[i2]; | ||
1800 | #endif | ||
1801 | ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0); | ||
1802 | #ifdef DEBUG_DLINES | ||
1803 | printf("dline_index_from_face: f=%d,i=%d, edges [%d,%d] - %d\n", | ||
1804 | (int)(f - g->faces), i, (int)(e - g->edges), | ||
1805 | (int)(e2 - g->edges), ret); | ||
1806 | #endif | ||
1807 | return ret; | ||
1808 | } | ||
1809 | static int is_atleastone(const char *dline_array, int index) | ||
1810 | { | ||
1811 | return BIT_SET(dline_array[index], 0); | ||
1812 | } | ||
1813 | static int set_atleastone(char *dline_array, int index) | ||
1814 | { | ||
1815 | return SET_BIT(dline_array[index], 0); | ||
1816 | } | ||
1817 | static int is_atmostone(const char *dline_array, int index) | ||
1818 | { | ||
1819 | return BIT_SET(dline_array[index], 1); | ||
1820 | } | ||
1821 | static int set_atmostone(char *dline_array, int index) | ||
1822 | { | ||
1823 | return SET_BIT(dline_array[index], 1); | ||
1824 | } | ||
1825 | |||
1826 | static void array_setall(char *array, char from, char to, int len) | ||
1827 | { | ||
1828 | char *p = array, *p_old = p; | ||
1829 | int len_remaining = len; | ||
1830 | |||
1831 | while ((p = memchr(p, from, len_remaining))) { | ||
1832 | *p = to; | ||
1833 | len_remaining -= p - p_old; | ||
1834 | p_old = p; | ||
1835 | } | ||
1836 | } | ||
1837 | |||
1838 | /* Helper, called when doing dline dot deductions, in the case where we | ||
1839 | * have 4 UNKNOWNs, and two of them (adjacent) have *exactly* one YES between | ||
1840 | * them (because of dline atmostone/atleastone). | ||
1841 | * On entry, edge points to the first of these two UNKNOWNs. This function | ||
1842 | * will find the opposite UNKNOWNS (if they are adjacent to one another) | ||
1843 | * and set their corresponding dline to atleastone. (Setting atmostone | ||
1844 | * already happens in earlier dline deductions) */ | ||
1845 | static int dline_set_opp_atleastone(solver_state *sstate, | ||
1846 | grid_dot *d, int edge) | ||
1847 | { | ||
1848 | game_state *state = sstate->state; | ||
1849 | grid *g = state->game_grid; | ||
1850 | int N = d->order; | ||
1851 | int opp, opp2; | ||
1852 | for (opp = 0; opp < N; opp++) { | ||
1853 | int opp_dline_index; | ||
1854 | if (opp == edge || opp == edge+1 || opp == edge-1) | ||
1855 | continue; | ||
1856 | if (opp == 0 && edge == N-1) | ||
1857 | continue; | ||
1858 | if (opp == N-1 && edge == 0) | ||
1859 | continue; | ||
1860 | opp2 = opp + 1; | ||
1861 | if (opp2 == N) opp2 = 0; | ||
1862 | /* Check if opp, opp2 point to LINE_UNKNOWNs */ | ||
1863 | if (state->lines[d->edges[opp] - g->edges] != LINE_UNKNOWN) | ||
1864 | continue; | ||
1865 | if (state->lines[d->edges[opp2] - g->edges] != LINE_UNKNOWN) | ||
1866 | continue; | ||
1867 | /* Found opposite UNKNOWNS and they're next to each other */ | ||
1868 | opp_dline_index = dline_index_from_dot(g, d, opp); | ||
1869 | return set_atleastone(sstate->dlines, opp_dline_index); | ||
1870 | } | ||
1871 | return FALSE; | ||
1872 | } | ||
1873 | |||
1874 | |||
1875 | /* Set pairs of lines around this face which are known to be identical, to | ||
1876 | * the given line_state */ | ||
1877 | static int face_setall_identical(solver_state *sstate, int face_index, | ||
1878 | enum line_state line_new) | ||
1879 | { | ||
1880 | /* can[dir] contains the canonical line associated with the line in | ||
1881 | * direction dir from the square in question. Similarly inv[dir] is | ||
1882 | * whether or not the line in question is inverse to its canonical | ||
1883 | * element. */ | ||
1884 | int retval = FALSE; | ||
1885 | game_state *state = sstate->state; | ||
1886 | grid *g = state->game_grid; | ||
1887 | grid_face *f = g->faces + face_index; | ||
1888 | int N = f->order; | ||
1889 | int i, j; | ||
1890 | int can1, can2, inv1, inv2; | ||
1891 | |||
1892 | for (i = 0; i < N; i++) { | ||
1893 | int line1_index = f->edges[i] - g->edges; | ||
1894 | if (state->lines[line1_index] != LINE_UNKNOWN) | ||
1895 | continue; | ||
1896 | for (j = i + 1; j < N; j++) { | ||
1897 | int line2_index = f->edges[j] - g->edges; | ||
1898 | if (state->lines[line2_index] != LINE_UNKNOWN) | ||
1899 | continue; | ||
1900 | |||
1901 | /* Found two UNKNOWNS */ | ||
1902 | can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1); | ||
1903 | can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2); | ||
1904 | if (can1 == can2 && inv1 == inv2) { | ||
1905 | solver_set_line(sstate, line1_index, line_new); | ||
1906 | solver_set_line(sstate, line2_index, line_new); | ||
1907 | } | ||
1908 | } | ||
1909 | } | ||
1910 | return retval; | ||
1911 | } | ||
1912 | |||
1913 | /* Given a dot or face, and a count of LINE_UNKNOWNs, find them and | ||
1914 | * return the edge indices into e. */ | ||
1915 | static void find_unknowns(game_state *state, | ||
1916 | grid_edge **edge_list, /* Edge list to search (from a face or a dot) */ | ||
1917 | int expected_count, /* Number of UNKNOWNs (comes from solver's cache) */ | ||
1918 | int *e /* Returned edge indices */) | ||
1919 | { | ||
1920 | int c = 0; | ||
1921 | grid *g = state->game_grid; | ||
1922 | while (c < expected_count) { | ||
1923 | int line_index = *edge_list - g->edges; | ||
1924 | if (state->lines[line_index] == LINE_UNKNOWN) { | ||
1925 | e[c] = line_index; | ||
1926 | c++; | ||
1927 | } | ||
1928 | ++edge_list; | ||
1929 | } | ||
1930 | } | ||
1931 | |||
1932 | /* If we have a list of edges, and we know whether the number of YESs should | ||
1933 | * be odd or even, and there are only a few UNKNOWNs, we can do some simple | ||
1934 | * linedsf deductions. This can be used for both face and dot deductions. | ||
1935 | * Returns the difficulty level of the next solver that should be used, | ||
1936 | * or DIFF_MAX if no progress was made. */ | ||
1937 | static int parity_deductions(solver_state *sstate, | ||
1938 | grid_edge **edge_list, /* Edge list (from a face or a dot) */ | ||
1939 | int total_parity, /* Expected number of YESs modulo 2 (either 0 or 1) */ | ||
1940 | int unknown_count) | ||
1941 | { | ||
1942 | game_state *state = sstate->state; | ||
1943 | int diff = DIFF_MAX; | ||
1944 | int *linedsf = sstate->linedsf; | ||
1945 | |||
1946 | if (unknown_count == 2) { | ||
1947 | /* Lines are known alike/opposite, depending on inv. */ | ||
1948 | int e[2]; | ||
1949 | find_unknowns(state, edge_list, 2, e); | ||
1950 | if (merge_lines(sstate, e[0], e[1], total_parity)) | ||
1951 | diff = min(diff, DIFF_HARD); | ||
1952 | } else if (unknown_count == 3) { | ||
1953 | int e[3]; | ||
1954 | int can[3]; /* canonical edges */ | ||
1955 | int inv[3]; /* whether can[x] is inverse to e[x] */ | ||
1956 | find_unknowns(state, edge_list, 3, e); | ||
1957 | can[0] = edsf_canonify(linedsf, e[0], inv); | ||
1958 | can[1] = edsf_canonify(linedsf, e[1], inv+1); | ||
1959 | can[2] = edsf_canonify(linedsf, e[2], inv+2); | ||
1960 | if (can[0] == can[1]) { | ||
1961 | if (solver_set_line(sstate, e[2], (total_parity^inv[0]^inv[1]) ? | ||
1962 | LINE_YES : LINE_NO)) | ||
1963 | diff = min(diff, DIFF_EASY); | ||
1964 | } | ||
1965 | if (can[0] == can[2]) { | ||
1966 | if (solver_set_line(sstate, e[1], (total_parity^inv[0]^inv[2]) ? | ||
1967 | LINE_YES : LINE_NO)) | ||
1968 | diff = min(diff, DIFF_EASY); | ||
1969 | } | ||
1970 | if (can[1] == can[2]) { | ||
1971 | if (solver_set_line(sstate, e[0], (total_parity^inv[1]^inv[2]) ? | ||
1972 | LINE_YES : LINE_NO)) | ||
1973 | diff = min(diff, DIFF_EASY); | ||
1974 | } | ||
1975 | } else if (unknown_count == 4) { | ||
1976 | int e[4]; | ||
1977 | int can[4]; /* canonical edges */ | ||
1978 | int inv[4]; /* whether can[x] is inverse to e[x] */ | ||
1979 | find_unknowns(state, edge_list, 4, e); | ||
1980 | can[0] = edsf_canonify(linedsf, e[0], inv); | ||
1981 | can[1] = edsf_canonify(linedsf, e[1], inv+1); | ||
1982 | can[2] = edsf_canonify(linedsf, e[2], inv+2); | ||
1983 | can[3] = edsf_canonify(linedsf, e[3], inv+3); | ||
1984 | if (can[0] == can[1]) { | ||
1985 | if (merge_lines(sstate, e[2], e[3], total_parity^inv[0]^inv[1])) | ||
1986 | diff = min(diff, DIFF_HARD); | ||
1987 | } else if (can[0] == can[2]) { | ||
1988 | if (merge_lines(sstate, e[1], e[3], total_parity^inv[0]^inv[2])) | ||
1989 | diff = min(diff, DIFF_HARD); | ||
1990 | } else if (can[0] == can[3]) { | ||
1991 | if (merge_lines(sstate, e[1], e[2], total_parity^inv[0]^inv[3])) | ||
1992 | diff = min(diff, DIFF_HARD); | ||
1993 | } else if (can[1] == can[2]) { | ||
1994 | if (merge_lines(sstate, e[0], e[3], total_parity^inv[1]^inv[2])) | ||
1995 | diff = min(diff, DIFF_HARD); | ||
1996 | } else if (can[1] == can[3]) { | ||
1997 | if (merge_lines(sstate, e[0], e[2], total_parity^inv[1]^inv[3])) | ||
1998 | diff = min(diff, DIFF_HARD); | ||
1999 | } else if (can[2] == can[3]) { | ||
2000 | if (merge_lines(sstate, e[0], e[1], total_parity^inv[2]^inv[3])) | ||
2001 | diff = min(diff, DIFF_HARD); | ||
2002 | } | ||
2003 | } | ||
2004 | return diff; | ||
2005 | } | ||
2006 | |||
2007 | |||
2008 | /* | ||
2009 | * These are the main solver functions. | ||
2010 | * | ||
2011 | * Their return values are diff values corresponding to the lowest mode solver | ||
2012 | * that would notice the work that they have done. For example if the normal | ||
2013 | * mode solver adds actual lines or crosses, it will return DIFF_EASY as the | ||
2014 | * easy mode solver might be able to make progress using that. It doesn't make | ||
2015 | * sense for one of them to return a diff value higher than that of the | ||
2016 | * function itself. | ||
2017 | * | ||
2018 | * Each function returns the lowest value it can, as early as possible, in | ||
2019 | * order to try and pass as much work as possible back to the lower level | ||
2020 | * solvers which progress more quickly. | ||
2021 | */ | ||
2022 | |||
2023 | /* PROPOSED NEW DESIGN: | ||
2024 | * We have a work queue consisting of 'events' notifying us that something has | ||
2025 | * happened that a particular solver mode might be interested in. For example | ||
2026 | * the hard mode solver might do something that helps the normal mode solver at | ||
2027 | * dot [x,y] in which case it will enqueue an event recording this fact. Then | ||
2028 | * we pull events off the work queue, and hand each in turn to the solver that | ||
2029 | * is interested in them. If a solver reports that it failed we pass the same | ||
2030 | * event on to progressively more advanced solvers and the loop detector. Once | ||
2031 | * we've exhausted an event, or it has helped us progress, we drop it and | ||
2032 | * continue to the next one. The events are sorted first in order of solver | ||
2033 | * complexity (easy first) then order of insertion (oldest first). | ||
2034 | * Once we run out of events we loop over each permitted solver in turn | ||
2035 | * (easiest first) until either a deduction is made (and an event therefore | ||
2036 | * emerges) or no further deductions can be made (in which case we've failed). | ||
2037 | * | ||
2038 | * QUESTIONS: | ||
2039 | * * How do we 'loop over' a solver when both dots and squares are concerned. | ||
2040 | * Answer: first all squares then all dots. | ||
2041 | */ | ||
2042 | |||
2043 | static int trivial_deductions(solver_state *sstate) | ||
2044 | { | ||
2045 | int i, current_yes, current_no; | ||
2046 | game_state *state = sstate->state; | ||
2047 | grid *g = state->game_grid; | ||
2048 | int diff = DIFF_MAX; | ||
2049 | |||
2050 | /* Per-face deductions */ | ||
2051 | for (i = 0; i < g->num_faces; i++) { | ||
2052 | grid_face *f = g->faces + i; | ||
2053 | |||
2054 | if (sstate->face_solved[i]) | ||
2055 | continue; | ||
2056 | |||
2057 | current_yes = sstate->face_yes_count[i]; | ||
2058 | current_no = sstate->face_no_count[i]; | ||
2059 | |||
2060 | if (current_yes + current_no == f->order) { | ||
2061 | sstate->face_solved[i] = TRUE; | ||
2062 | continue; | ||
2063 | } | ||
2064 | |||
2065 | if (state->clues[i] < 0) | ||
2066 | continue; | ||
2067 | |||
2068 | /* | ||
2069 | * This code checks whether the numeric clue on a face is so | ||
2070 | * large as to permit all its remaining LINE_UNKNOWNs to be | ||
2071 | * filled in as LINE_YES, or alternatively so small as to | ||
2072 | * permit them all to be filled in as LINE_NO. | ||
2073 | */ | ||
2074 | |||
2075 | if (state->clues[i] < current_yes) { | ||
2076 | sstate->solver_status = SOLVER_MISTAKE; | ||
2077 | return DIFF_EASY; | ||
2078 | } | ||
2079 | if (state->clues[i] == current_yes) { | ||
2080 | if (face_setall(sstate, i, LINE_UNKNOWN, LINE_NO)) | ||
2081 | diff = min(diff, DIFF_EASY); | ||
2082 | sstate->face_solved[i] = TRUE; | ||
2083 | continue; | ||
2084 | } | ||
2085 | |||
2086 | if (f->order - state->clues[i] < current_no) { | ||
2087 | sstate->solver_status = SOLVER_MISTAKE; | ||
2088 | return DIFF_EASY; | ||
2089 | } | ||
2090 | if (f->order - state->clues[i] == current_no) { | ||
2091 | if (face_setall(sstate, i, LINE_UNKNOWN, LINE_YES)) | ||
2092 | diff = min(diff, DIFF_EASY); | ||
2093 | sstate->face_solved[i] = TRUE; | ||
2094 | continue; | ||
2095 | } | ||
2096 | |||
2097 | if (f->order - state->clues[i] == current_no + 1 && | ||
2098 | f->order - current_yes - current_no > 2) { | ||
2099 | /* | ||
2100 | * One small refinement to the above: we also look for any | ||
2101 | * adjacent pair of LINE_UNKNOWNs around the face with | ||
2102 | * some LINE_YES incident on it from elsewhere. If we find | ||
2103 | * one, then we know that pair of LINE_UNKNOWNs can't | ||
2104 | * _both_ be LINE_YES, and hence that pushes us one line | ||
2105 | * closer to being able to determine all the rest. | ||
2106 | */ | ||
2107 | int j, k, e1, e2, e, d; | ||
2108 | |||
2109 | for (j = 0; j < f->order; j++) { | ||
2110 | e1 = f->edges[j] - g->edges; | ||
2111 | e2 = f->edges[j+1 < f->order ? j+1 : 0] - g->edges; | ||
2112 | |||
2113 | if (g->edges[e1].dot1 == g->edges[e2].dot1 || | ||
2114 | g->edges[e1].dot1 == g->edges[e2].dot2) { | ||
2115 | d = g->edges[e1].dot1 - g->dots; | ||
2116 | } else { | ||
2117 | assert(g->edges[e1].dot2 == g->edges[e2].dot1 || | ||
2118 | g->edges[e1].dot2 == g->edges[e2].dot2); | ||
2119 | d = g->edges[e1].dot2 - g->dots; | ||
2120 | } | ||
2121 | |||
2122 | if (state->lines[e1] == LINE_UNKNOWN && | ||
2123 | state->lines[e2] == LINE_UNKNOWN) { | ||
2124 | for (k = 0; k < g->dots[d].order; k++) { | ||
2125 | int e = g->dots[d].edges[k] - g->edges; | ||
2126 | if (state->lines[e] == LINE_YES) | ||
2127 | goto found; /* multi-level break */ | ||
2128 | } | ||
2129 | } | ||
2130 | } | ||
2131 | continue; | ||
2132 | |||
2133 | found: | ||
2134 | /* | ||
2135 | * If we get here, we've found such a pair of edges, and | ||
2136 | * they're e1 and e2. | ||
2137 | */ | ||
2138 | for (j = 0; j < f->order; j++) { | ||
2139 | e = f->edges[j] - g->edges; | ||
2140 | if (state->lines[e] == LINE_UNKNOWN && e != e1 && e != e2) { | ||
2141 | int r = solver_set_line(sstate, e, LINE_YES); | ||
2142 | assert(r); | ||
2143 | diff = min(diff, DIFF_EASY); | ||
2144 | } | ||
2145 | } | ||
2146 | } | ||
2147 | } | ||
2148 | |||
2149 | check_caches(sstate); | ||
2150 | |||
2151 | /* Per-dot deductions */ | ||
2152 | for (i = 0; i < g->num_dots; i++) { | ||
2153 | grid_dot *d = g->dots + i; | ||
2154 | int yes, no, unknown; | ||
2155 | |||
2156 | if (sstate->dot_solved[i]) | ||
2157 | continue; | ||
2158 | |||
2159 | yes = sstate->dot_yes_count[i]; | ||
2160 | no = sstate->dot_no_count[i]; | ||
2161 | unknown = d->order - yes - no; | ||
2162 | |||
2163 | if (yes == 0) { | ||
2164 | if (unknown == 0) { | ||
2165 | sstate->dot_solved[i] = TRUE; | ||
2166 | } else if (unknown == 1) { | ||
2167 | dot_setall(sstate, i, LINE_UNKNOWN, LINE_NO); | ||
2168 | diff = min(diff, DIFF_EASY); | ||
2169 | sstate->dot_solved[i] = TRUE; | ||
2170 | } | ||
2171 | } else if (yes == 1) { | ||
2172 | if (unknown == 0) { | ||
2173 | sstate->solver_status = SOLVER_MISTAKE; | ||
2174 | return DIFF_EASY; | ||
2175 | } else if (unknown == 1) { | ||
2176 | dot_setall(sstate, i, LINE_UNKNOWN, LINE_YES); | ||
2177 | diff = min(diff, DIFF_EASY); | ||
2178 | } | ||
2179 | } else if (yes == 2) { | ||
2180 | if (unknown > 0) { | ||
2181 | dot_setall(sstate, i, LINE_UNKNOWN, LINE_NO); | ||
2182 | diff = min(diff, DIFF_EASY); | ||
2183 | } | ||
2184 | sstate->dot_solved[i] = TRUE; | ||
2185 | } else { | ||
2186 | sstate->solver_status = SOLVER_MISTAKE; | ||
2187 | return DIFF_EASY; | ||
2188 | } | ||
2189 | } | ||
2190 | |||
2191 | check_caches(sstate); | ||
2192 | |||
2193 | return diff; | ||
2194 | } | ||
2195 | |||
2196 | static int dline_deductions(solver_state *sstate) | ||
2197 | { | ||
2198 | game_state *state = sstate->state; | ||
2199 | grid *g = state->game_grid; | ||
2200 | char *dlines = sstate->dlines; | ||
2201 | int i; | ||
2202 | int diff = DIFF_MAX; | ||
2203 | |||
2204 | /* ------ Face deductions ------ */ | ||
2205 | |||
2206 | /* Given a set of dline atmostone/atleastone constraints, need to figure | ||
2207 | * out if we can deduce any further info. For more general faces than | ||
2208 | * squares, this turns out to be a tricky problem. | ||
2209 | * The approach taken here is to define (per face) NxN matrices: | ||
2210 | * "maxs" and "mins". | ||
2211 | * The entries maxs(j,k) and mins(j,k) define the upper and lower limits | ||
2212 | * for the possible number of edges that are YES between positions j and k | ||
2213 | * going clockwise around the face. Can think of j and k as marking dots | ||
2214 | * around the face (recall the labelling scheme: edge0 joins dot0 to dot1, | ||
2215 | * edge1 joins dot1 to dot2 etc). | ||
2216 | * Trivially, mins(j,j) = maxs(j,j) = 0, and we don't even bother storing | ||
2217 | * these. mins(j,j+1) and maxs(j,j+1) are determined by whether edge{j} | ||
2218 | * is YES, NO or UNKNOWN. mins(j,j+2) and maxs(j,j+2) are related to | ||
2219 | * the dline atmostone/atleastone status for edges j and j+1. | ||
2220 | * | ||
2221 | * Then we calculate the remaining entries recursively. We definitely | ||
2222 | * know that | ||
2223 | * mins(j,k) >= { mins(j,u) + mins(u,k) } for any u between j and k. | ||
2224 | * This is because any valid placement of YESs between j and k must give | ||
2225 | * a valid placement between j and u, and also between u and k. | ||
2226 | * I believe it's sufficient to use just the two values of u: | ||
2227 | * j+1 and j+2. Seems to work well in practice - the bounds we compute | ||
2228 | * are rigorous, even if they might not be best-possible. | ||
2229 | * | ||
2230 | * Once we have maxs and mins calculated, we can make inferences about | ||
2231 | * each dline{j,j+1} by looking at the possible complementary edge-counts | ||
2232 | * mins(j+2,j) and maxs(j+2,j) and comparing these with the face clue. | ||
2233 | * As well as dlines, we can make similar inferences about single edges. | ||
2234 | * For example, consider a pentagon with clue 3, and we know at most one | ||
2235 | * of (edge0, edge1) is YES, and at most one of (edge2, edge3) is YES. | ||
2236 | * We could then deduce edge4 is YES, because maxs(0,4) would be 2, so | ||
2237 | * that final edge would have to be YES to make the count up to 3. | ||
2238 | */ | ||
2239 | |||
2240 | /* Much quicker to allocate arrays on the stack than the heap, so | ||
2241 | * define the largest possible face size, and base our array allocations | ||
2242 | * on that. We check this with an assertion, in case someone decides to | ||
2243 | * make a grid which has larger faces than this. Note, this algorithm | ||
2244 | * could get quite expensive if there are many large faces. */ | ||
2245 | #define MAX_FACE_SIZE 12 | ||
2246 | |||
2247 | for (i = 0; i < g->num_faces; i++) { | ||
2248 | int maxs[MAX_FACE_SIZE][MAX_FACE_SIZE]; | ||
2249 | int mins[MAX_FACE_SIZE][MAX_FACE_SIZE]; | ||
2250 | grid_face *f = g->faces + i; | ||
2251 | int N = f->order; | ||
2252 | int j,m; | ||
2253 | int clue = state->clues[i]; | ||
2254 | assert(N <= MAX_FACE_SIZE); | ||
2255 | if (sstate->face_solved[i]) | ||
2256 | continue; | ||
2257 | if (clue < 0) continue; | ||
2258 | |||
2259 | /* Calculate the (j,j+1) entries */ | ||
2260 | for (j = 0; j < N; j++) { | ||
2261 | int edge_index = f->edges[j] - g->edges; | ||
2262 | int dline_index; | ||
2263 | enum line_state line1 = state->lines[edge_index]; | ||
2264 | enum line_state line2; | ||
2265 | int tmp; | ||
2266 | int k = j + 1; | ||
2267 | if (k >= N) k = 0; | ||
2268 | maxs[j][k] = (line1 == LINE_NO) ? 0 : 1; | ||
2269 | mins[j][k] = (line1 == LINE_YES) ? 1 : 0; | ||
2270 | /* Calculate the (j,j+2) entries */ | ||
2271 | dline_index = dline_index_from_face(g, f, k); | ||
2272 | edge_index = f->edges[k] - g->edges; | ||
2273 | line2 = state->lines[edge_index]; | ||
2274 | k++; | ||
2275 | if (k >= N) k = 0; | ||
2276 | |||
2277 | /* max */ | ||
2278 | tmp = 2; | ||
2279 | if (line1 == LINE_NO) tmp--; | ||
2280 | if (line2 == LINE_NO) tmp--; | ||
2281 | if (tmp == 2 && is_atmostone(dlines, dline_index)) | ||
2282 | tmp = 1; | ||
2283 | maxs[j][k] = tmp; | ||
2284 | |||
2285 | /* min */ | ||
2286 | tmp = 0; | ||
2287 | if (line1 == LINE_YES) tmp++; | ||
2288 | if (line2 == LINE_YES) tmp++; | ||
2289 | if (tmp == 0 && is_atleastone(dlines, dline_index)) | ||
2290 | tmp = 1; | ||
2291 | mins[j][k] = tmp; | ||
2292 | } | ||
2293 | |||
2294 | /* Calculate the (j,j+m) entries for m between 3 and N-1 */ | ||
2295 | for (m = 3; m < N; m++) { | ||
2296 | for (j = 0; j < N; j++) { | ||
2297 | int k = j + m; | ||
2298 | int u = j + 1; | ||
2299 | int v = j + 2; | ||
2300 | int tmp; | ||
2301 | if (k >= N) k -= N; | ||
2302 | if (u >= N) u -= N; | ||
2303 | if (v >= N) v -= N; | ||
2304 | maxs[j][k] = maxs[j][u] + maxs[u][k]; | ||
2305 | mins[j][k] = mins[j][u] + mins[u][k]; | ||
2306 | tmp = maxs[j][v] + maxs[v][k]; | ||
2307 | maxs[j][k] = min(maxs[j][k], tmp); | ||
2308 | tmp = mins[j][v] + mins[v][k]; | ||
2309 | mins[j][k] = max(mins[j][k], tmp); | ||
2310 | } | ||
2311 | } | ||
2312 | |||
2313 | /* See if we can make any deductions */ | ||
2314 | for (j = 0; j < N; j++) { | ||
2315 | int k; | ||
2316 | grid_edge *e = f->edges[j]; | ||
2317 | int line_index = e - g->edges; | ||
2318 | int dline_index; | ||
2319 | |||
2320 | if (state->lines[line_index] != LINE_UNKNOWN) | ||
2321 | continue; | ||
2322 | k = j + 1; | ||
2323 | if (k >= N) k = 0; | ||
2324 | |||
2325 | /* minimum YESs in the complement of this edge */ | ||
2326 | if (mins[k][j] > clue) { | ||
2327 | sstate->solver_status = SOLVER_MISTAKE; | ||
2328 | return DIFF_EASY; | ||
2329 | } | ||
2330 | if (mins[k][j] == clue) { | ||
2331 | /* setting this edge to YES would make at least | ||
2332 | * (clue+1) edges - contradiction */ | ||
2333 | solver_set_line(sstate, line_index, LINE_NO); | ||
2334 | diff = min(diff, DIFF_EASY); | ||
2335 | } | ||
2336 | if (maxs[k][j] < clue - 1) { | ||
2337 | sstate->solver_status = SOLVER_MISTAKE; | ||
2338 | return DIFF_EASY; | ||
2339 | } | ||
2340 | if (maxs[k][j] == clue - 1) { | ||
2341 | /* Only way to satisfy the clue is to set edge{j} as YES */ | ||
2342 | solver_set_line(sstate, line_index, LINE_YES); | ||
2343 | diff = min(diff, DIFF_EASY); | ||
2344 | } | ||
2345 | |||
2346 | /* More advanced deduction that allows propagation along diagonal | ||
2347 | * chains of faces connected by dots, for example, 3-2-...-2-3 | ||
2348 | * in square grids. */ | ||
2349 | if (sstate->diff >= DIFF_TRICKY) { | ||
2350 | /* Now see if we can make dline deduction for edges{j,j+1} */ | ||
2351 | e = f->edges[k]; | ||
2352 | if (state->lines[e - g->edges] != LINE_UNKNOWN) | ||
2353 | /* Only worth doing this for an UNKNOWN,UNKNOWN pair. | ||
2354 | * Dlines where one of the edges is known, are handled in the | ||
2355 | * dot-deductions */ | ||
2356 | continue; | ||
2357 | |||
2358 | dline_index = dline_index_from_face(g, f, k); | ||
2359 | k++; | ||
2360 | if (k >= N) k = 0; | ||
2361 | |||
2362 | /* minimum YESs in the complement of this dline */ | ||
2363 | if (mins[k][j] > clue - 2) { | ||
2364 | /* Adding 2 YESs would break the clue */ | ||
2365 | if (set_atmostone(dlines, dline_index)) | ||
2366 | diff = min(diff, DIFF_NORMAL); | ||
2367 | } | ||
2368 | /* maximum YESs in the complement of this dline */ | ||
2369 | if (maxs[k][j] < clue) { | ||
2370 | /* Adding 2 NOs would mean not enough YESs */ | ||
2371 | if (set_atleastone(dlines, dline_index)) | ||
2372 | diff = min(diff, DIFF_NORMAL); | ||
2373 | } | ||
2374 | } | ||
2375 | } | ||
2376 | } | ||
2377 | |||
2378 | if (diff < DIFF_NORMAL) | ||
2379 | return diff; | ||
2380 | |||
2381 | /* ------ Dot deductions ------ */ | ||
2382 | |||
2383 | for (i = 0; i < g->num_dots; i++) { | ||
2384 | grid_dot *d = g->dots + i; | ||
2385 | int N = d->order; | ||
2386 | int yes, no, unknown; | ||
2387 | int j; | ||
2388 | if (sstate->dot_solved[i]) | ||
2389 | continue; | ||
2390 | yes = sstate->dot_yes_count[i]; | ||
2391 | no = sstate->dot_no_count[i]; | ||
2392 | unknown = N - yes - no; | ||
2393 | |||
2394 | for (j = 0; j < N; j++) { | ||
2395 | int k; | ||
2396 | int dline_index; | ||
2397 | int line1_index, line2_index; | ||
2398 | enum line_state line1, line2; | ||
2399 | k = j + 1; | ||
2400 | if (k >= N) k = 0; | ||
2401 | dline_index = dline_index_from_dot(g, d, j); | ||
2402 | line1_index = d->edges[j] - g->edges; | ||
2403 | line2_index = d->edges[k] - g->edges; | ||
2404 | line1 = state->lines[line1_index]; | ||
2405 | line2 = state->lines[line2_index]; | ||
2406 | |||
2407 | /* Infer dline state from line state */ | ||
2408 | if (line1 == LINE_NO || line2 == LINE_NO) { | ||
2409 | if (set_atmostone(dlines, dline_index)) | ||
2410 | diff = min(diff, DIFF_NORMAL); | ||
2411 | } | ||
2412 | if (line1 == LINE_YES || line2 == LINE_YES) { | ||
2413 | if (set_atleastone(dlines, dline_index)) | ||
2414 | diff = min(diff, DIFF_NORMAL); | ||
2415 | } | ||
2416 | /* Infer line state from dline state */ | ||
2417 | if (is_atmostone(dlines, dline_index)) { | ||
2418 | if (line1 == LINE_YES && line2 == LINE_UNKNOWN) { | ||
2419 | solver_set_line(sstate, line2_index, LINE_NO); | ||
2420 | diff = min(diff, DIFF_EASY); | ||
2421 | } | ||
2422 | if (line2 == LINE_YES && line1 == LINE_UNKNOWN) { | ||
2423 | solver_set_line(sstate, line1_index, LINE_NO); | ||
2424 | diff = min(diff, DIFF_EASY); | ||
2425 | } | ||
2426 | } | ||
2427 | if (is_atleastone(dlines, dline_index)) { | ||
2428 | if (line1 == LINE_NO && line2 == LINE_UNKNOWN) { | ||
2429 | solver_set_line(sstate, line2_index, LINE_YES); | ||
2430 | diff = min(diff, DIFF_EASY); | ||
2431 | } | ||
2432 | if (line2 == LINE_NO && line1 == LINE_UNKNOWN) { | ||
2433 | solver_set_line(sstate, line1_index, LINE_YES); | ||
2434 | diff = min(diff, DIFF_EASY); | ||
2435 | } | ||
2436 | } | ||
2437 | /* Deductions that depend on the numbers of lines. | ||
2438 | * Only bother if both lines are UNKNOWN, otherwise the | ||
2439 | * easy-mode solver (or deductions above) would have taken | ||
2440 | * care of it. */ | ||
2441 | if (line1 != LINE_UNKNOWN || line2 != LINE_UNKNOWN) | ||
2442 | continue; | ||
2443 | |||
2444 | if (yes == 0 && unknown == 2) { | ||
2445 | /* Both these unknowns must be identical. If we know | ||
2446 | * atmostone or atleastone, we can make progress. */ | ||
2447 | if (is_atmostone(dlines, dline_index)) { | ||
2448 | solver_set_line(sstate, line1_index, LINE_NO); | ||
2449 | solver_set_line(sstate, line2_index, LINE_NO); | ||
2450 | diff = min(diff, DIFF_EASY); | ||
2451 | } | ||
2452 | if (is_atleastone(dlines, dline_index)) { | ||
2453 | solver_set_line(sstate, line1_index, LINE_YES); | ||
2454 | solver_set_line(sstate, line2_index, LINE_YES); | ||
2455 | diff = min(diff, DIFF_EASY); | ||
2456 | } | ||
2457 | } | ||
2458 | if (yes == 1) { | ||
2459 | if (set_atmostone(dlines, dline_index)) | ||
2460 | diff = min(diff, DIFF_NORMAL); | ||
2461 | if (unknown == 2) { | ||
2462 | if (set_atleastone(dlines, dline_index)) | ||
2463 | diff = min(diff, DIFF_NORMAL); | ||
2464 | } | ||
2465 | } | ||
2466 | |||
2467 | /* More advanced deduction that allows propagation along diagonal | ||
2468 | * chains of faces connected by dots, for example: 3-2-...-2-3 | ||
2469 | * in square grids. */ | ||
2470 | if (sstate->diff >= DIFF_TRICKY) { | ||
2471 | /* If we have atleastone set for this dline, infer | ||
2472 | * atmostone for each "opposite" dline (that is, each | ||
2473 | * dline without edges in common with this one). | ||
2474 | * Again, this test is only worth doing if both these | ||
2475 | * lines are UNKNOWN. For if one of these lines were YES, | ||
2476 | * the (yes == 1) test above would kick in instead. */ | ||
2477 | if (is_atleastone(dlines, dline_index)) { | ||
2478 | int opp; | ||
2479 | for (opp = 0; opp < N; opp++) { | ||
2480 | int opp_dline_index; | ||
2481 | if (opp == j || opp == j+1 || opp == j-1) | ||
2482 | continue; | ||
2483 | if (j == 0 && opp == N-1) | ||
2484 | continue; | ||
2485 | if (j == N-1 && opp == 0) | ||
2486 | continue; | ||
2487 | opp_dline_index = dline_index_from_dot(g, d, opp); | ||
2488 | if (set_atmostone(dlines, opp_dline_index)) | ||
2489 | diff = min(diff, DIFF_NORMAL); | ||
2490 | } | ||
2491 | if (yes == 0 && is_atmostone(dlines, dline_index)) { | ||
2492 | /* This dline has *exactly* one YES and there are no | ||
2493 | * other YESs. This allows more deductions. */ | ||
2494 | if (unknown == 3) { | ||
2495 | /* Third unknown must be YES */ | ||
2496 | for (opp = 0; opp < N; opp++) { | ||
2497 | int opp_index; | ||
2498 | if (opp == j || opp == k) | ||
2499 | continue; | ||
2500 | opp_index = d->edges[opp] - g->edges; | ||
2501 | if (state->lines[opp_index] == LINE_UNKNOWN) { | ||
2502 | solver_set_line(sstate, opp_index, | ||
2503 | LINE_YES); | ||
2504 | diff = min(diff, DIFF_EASY); | ||
2505 | } | ||
2506 | } | ||
2507 | } else if (unknown == 4) { | ||
2508 | /* Exactly one of opposite UNKNOWNS is YES. We've | ||
2509 | * already set atmostone, so set atleastone as | ||
2510 | * well. | ||
2511 | */ | ||
2512 | if (dline_set_opp_atleastone(sstate, d, j)) | ||
2513 | diff = min(diff, DIFF_NORMAL); | ||
2514 | } | ||
2515 | } | ||
2516 | } | ||
2517 | } | ||
2518 | } | ||
2519 | } | ||
2520 | return diff; | ||
2521 | } | ||
2522 | |||
2523 | static int linedsf_deductions(solver_state *sstate) | ||
2524 | { | ||
2525 | game_state *state = sstate->state; | ||
2526 | grid *g = state->game_grid; | ||
2527 | char *dlines = sstate->dlines; | ||
2528 | int i; | ||
2529 | int diff = DIFF_MAX; | ||
2530 | int diff_tmp; | ||
2531 | |||
2532 | /* ------ Face deductions ------ */ | ||
2533 | |||
2534 | /* A fully-general linedsf deduction seems overly complicated | ||
2535 | * (I suspect the problem is NP-complete, though in practice it might just | ||
2536 | * be doable because faces are limited in size). | ||
2537 | * For simplicity, we only consider *pairs* of LINE_UNKNOWNS that are | ||
2538 | * known to be identical. If setting them both to YES (or NO) would break | ||
2539 | * the clue, set them to NO (or YES). */ | ||
2540 | |||
2541 | for (i = 0; i < g->num_faces; i++) { | ||
2542 | int N, yes, no, unknown; | ||
2543 | int clue; | ||
2544 | |||
2545 | if (sstate->face_solved[i]) | ||
2546 | continue; | ||
2547 | clue = state->clues[i]; | ||
2548 | if (clue < 0) | ||
2549 | continue; | ||
2550 | |||
2551 | N = g->faces[i].order; | ||
2552 | yes = sstate->face_yes_count[i]; | ||
2553 | if (yes + 1 == clue) { | ||
2554 | if (face_setall_identical(sstate, i, LINE_NO)) | ||
2555 | diff = min(diff, DIFF_EASY); | ||
2556 | } | ||
2557 | no = sstate->face_no_count[i]; | ||
2558 | if (no + 1 == N - clue) { | ||
2559 | if (face_setall_identical(sstate, i, LINE_YES)) | ||
2560 | diff = min(diff, DIFF_EASY); | ||
2561 | } | ||
2562 | |||
2563 | /* Reload YES count, it might have changed */ | ||
2564 | yes = sstate->face_yes_count[i]; | ||
2565 | unknown = N - no - yes; | ||
2566 | |||
2567 | /* Deductions with small number of LINE_UNKNOWNs, based on overall | ||
2568 | * parity of lines. */ | ||
2569 | diff_tmp = parity_deductions(sstate, g->faces[i].edges, | ||
2570 | (clue - yes) % 2, unknown); | ||
2571 | diff = min(diff, diff_tmp); | ||
2572 | } | ||
2573 | |||
2574 | /* ------ Dot deductions ------ */ | ||
2575 | for (i = 0; i < g->num_dots; i++) { | ||
2576 | grid_dot *d = g->dots + i; | ||
2577 | int N = d->order; | ||
2578 | int j; | ||
2579 | int yes, no, unknown; | ||
2580 | /* Go through dlines, and do any dline<->linedsf deductions wherever | ||
2581 | * we find two UNKNOWNS. */ | ||
2582 | for (j = 0; j < N; j++) { | ||
2583 | int dline_index = dline_index_from_dot(g, d, j); | ||
2584 | int line1_index; | ||
2585 | int line2_index; | ||
2586 | int can1, can2, inv1, inv2; | ||
2587 | int j2; | ||
2588 | line1_index = d->edges[j] - g->edges; | ||
2589 | if (state->lines[line1_index] != LINE_UNKNOWN) | ||
2590 | continue; | ||
2591 | j2 = j + 1; | ||
2592 | if (j2 == N) j2 = 0; | ||
2593 | line2_index = d->edges[j2] - g->edges; | ||
2594 | if (state->lines[line2_index] != LINE_UNKNOWN) | ||
2595 | continue; | ||
2596 | /* Infer dline flags from linedsf */ | ||
2597 | can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1); | ||
2598 | can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2); | ||
2599 | if (can1 == can2 && inv1 != inv2) { | ||
2600 | /* These are opposites, so set dline atmostone/atleastone */ | ||
2601 | if (set_atmostone(dlines, dline_index)) | ||
2602 | diff = min(diff, DIFF_NORMAL); | ||
2603 | if (set_atleastone(dlines, dline_index)) | ||
2604 | diff = min(diff, DIFF_NORMAL); | ||
2605 | continue; | ||
2606 | } | ||
2607 | /* Infer linedsf from dline flags */ | ||
2608 | if (is_atmostone(dlines, dline_index) | ||
2609 | && is_atleastone(dlines, dline_index)) { | ||
2610 | if (merge_lines(sstate, line1_index, line2_index, 1)) | ||
2611 | diff = min(diff, DIFF_HARD); | ||
2612 | } | ||
2613 | } | ||
2614 | |||
2615 | /* Deductions with small number of LINE_UNKNOWNs, based on overall | ||
2616 | * parity of lines. */ | ||
2617 | yes = sstate->dot_yes_count[i]; | ||
2618 | no = sstate->dot_no_count[i]; | ||
2619 | unknown = N - yes - no; | ||
2620 | diff_tmp = parity_deductions(sstate, d->edges, | ||
2621 | yes % 2, unknown); | ||
2622 | diff = min(diff, diff_tmp); | ||
2623 | } | ||
2624 | |||
2625 | /* ------ Edge dsf deductions ------ */ | ||
2626 | |||
2627 | /* If the state of a line is known, deduce the state of its canonical line | ||
2628 | * too, and vice versa. */ | ||
2629 | for (i = 0; i < g->num_edges; i++) { | ||
2630 | int can, inv; | ||
2631 | enum line_state s; | ||
2632 | can = edsf_canonify(sstate->linedsf, i, &inv); | ||
2633 | if (can == i) | ||
2634 | continue; | ||
2635 | s = sstate->state->lines[can]; | ||
2636 | if (s != LINE_UNKNOWN) { | ||
2637 | if (solver_set_line(sstate, i, inv ? OPP(s) : s)) | ||
2638 | diff = min(diff, DIFF_EASY); | ||
2639 | } else { | ||
2640 | s = sstate->state->lines[i]; | ||
2641 | if (s != LINE_UNKNOWN) { | ||
2642 | if (solver_set_line(sstate, can, inv ? OPP(s) : s)) | ||
2643 | diff = min(diff, DIFF_EASY); | ||
2644 | } | ||
2645 | } | ||
2646 | } | ||
2647 | |||
2648 | return diff; | ||
2649 | } | ||
2650 | |||
2651 | static int loop_deductions(solver_state *sstate) | ||
2652 | { | ||
2653 | int edgecount = 0, clues = 0, satclues = 0, sm1clues = 0; | ||
2654 | game_state *state = sstate->state; | ||
2655 | grid *g = state->game_grid; | ||
2656 | int shortest_chainlen = g->num_dots; | ||
2657 | int loop_found = FALSE; | ||
2658 | int dots_connected; | ||
2659 | int progress = FALSE; | ||
2660 | int i; | ||
2661 | |||
2662 | /* | ||
2663 | * Go through the grid and update for all the new edges. | ||
2664 | * Since merge_dots() is idempotent, the simplest way to | ||
2665 | * do this is just to update for _all_ the edges. | ||
2666 | * Also, while we're here, we count the edges. | ||
2667 | */ | ||
2668 | for (i = 0; i < g->num_edges; i++) { | ||
2669 | if (state->lines[i] == LINE_YES) { | ||
2670 | loop_found |= merge_dots(sstate, i); | ||
2671 | edgecount++; | ||
2672 | } | ||
2673 | } | ||
2674 | |||
2675 | /* | ||
2676 | * Count the clues, count the satisfied clues, and count the | ||
2677 | * satisfied-minus-one clues. | ||
2678 | */ | ||
2679 | for (i = 0; i < g->num_faces; i++) { | ||
2680 | int c = state->clues[i]; | ||
2681 | if (c >= 0) { | ||
2682 | int o = sstate->face_yes_count[i]; | ||
2683 | if (o == c) | ||
2684 | satclues++; | ||
2685 | else if (o == c-1) | ||
2686 | sm1clues++; | ||
2687 | clues++; | ||
2688 | } | ||
2689 | } | ||
2690 | |||
2691 | for (i = 0; i < g->num_dots; ++i) { | ||
2692 | dots_connected = | ||
2693 | sstate->looplen[dsf_canonify(sstate->dotdsf, i)]; | ||
2694 | if (dots_connected > 1) | ||
2695 | shortest_chainlen = min(shortest_chainlen, dots_connected); | ||
2696 | } | ||
2697 | |||
2698 | assert(sstate->solver_status == SOLVER_INCOMPLETE); | ||
2699 | |||
2700 | if (satclues == clues && shortest_chainlen == edgecount) { | ||
2701 | sstate->solver_status = SOLVER_SOLVED; | ||
2702 | /* This discovery clearly counts as progress, even if we haven't | ||
2703 | * just added any lines or anything */ | ||
2704 | progress = TRUE; | ||
2705 | goto finished_loop_deductionsing; | ||
2706 | } | ||
2707 | |||
2708 | /* | ||
2709 | * Now go through looking for LINE_UNKNOWN edges which | ||
2710 | * connect two dots that are already in the same | ||
2711 | * equivalence class. If we find one, test to see if the | ||
2712 | * loop it would create is a solution. | ||
2713 | */ | ||
2714 | for (i = 0; i < g->num_edges; i++) { | ||
2715 | grid_edge *e = g->edges + i; | ||
2716 | int d1 = e->dot1 - g->dots; | ||
2717 | int d2 = e->dot2 - g->dots; | ||
2718 | int eqclass, val; | ||
2719 | if (state->lines[i] != LINE_UNKNOWN) | ||
2720 | continue; | ||
2721 | |||
2722 | eqclass = dsf_canonify(sstate->dotdsf, d1); | ||
2723 | if (eqclass != dsf_canonify(sstate->dotdsf, d2)) | ||
2724 | continue; | ||
2725 | |||
2726 | val = LINE_NO; /* loop is bad until proven otherwise */ | ||
2727 | |||
2728 | /* | ||
2729 | * This edge would form a loop. Next | ||
2730 | * question: how long would the loop be? | ||
2731 | * Would it equal the total number of edges | ||
2732 | * (plus the one we'd be adding if we added | ||
2733 | * it)? | ||
2734 | */ | ||
2735 | if (sstate->looplen[eqclass] == edgecount + 1) { | ||
2736 | int sm1_nearby; | ||
2737 | |||
2738 | /* | ||
2739 | * This edge would form a loop which | ||
2740 | * took in all the edges in the entire | ||
2741 | * grid. So now we need to work out | ||
2742 | * whether it would be a valid solution | ||
2743 | * to the puzzle, which means we have to | ||
2744 | * check if it satisfies all the clues. | ||
2745 | * This means that every clue must be | ||
2746 | * either satisfied or satisfied-minus- | ||
2747 | * 1, and also that the number of | ||
2748 | * satisfied-minus-1 clues must be at | ||
2749 | * most two and they must lie on either | ||
2750 | * side of this edge. | ||
2751 | */ | ||
2752 | sm1_nearby = 0; | ||
2753 | if (e->face1) { | ||
2754 | int f = e->face1 - g->faces; | ||
2755 | int c = state->clues[f]; | ||
2756 | if (c >= 0 && sstate->face_yes_count[f] == c - 1) | ||
2757 | sm1_nearby++; | ||
2758 | } | ||
2759 | if (e->face2) { | ||
2760 | int f = e->face2 - g->faces; | ||
2761 | int c = state->clues[f]; | ||
2762 | if (c >= 0 && sstate->face_yes_count[f] == c - 1) | ||
2763 | sm1_nearby++; | ||
2764 | } | ||
2765 | if (sm1clues == sm1_nearby && | ||
2766 | sm1clues + satclues == clues) { | ||
2767 | val = LINE_YES; /* loop is good! */ | ||
2768 | } | ||
2769 | } | ||
2770 | |||
2771 | /* | ||
2772 | * Right. Now we know that adding this edge | ||
2773 | * would form a loop, and we know whether | ||
2774 | * that loop would be a viable solution or | ||
2775 | * not. | ||
2776 | * | ||
2777 | * If adding this edge produces a solution, | ||
2778 | * then we know we've found _a_ solution but | ||
2779 | * we don't know that it's _the_ solution - | ||
2780 | * if it were provably the solution then | ||
2781 | * we'd have deduced this edge some time ago | ||
2782 | * without the need to do loop detection. So | ||
2783 | * in this state we return SOLVER_AMBIGUOUS, | ||
2784 | * which has the effect that hitting Solve | ||
2785 | * on a user-provided puzzle will fill in a | ||
2786 | * solution but using the solver to | ||
2787 | * construct new puzzles won't consider this | ||
2788 | * a reasonable deduction for the user to | ||
2789 | * make. | ||
2790 | */ | ||
2791 | progress = solver_set_line(sstate, i, val); | ||
2792 | assert(progress == TRUE); | ||
2793 | if (val == LINE_YES) { | ||
2794 | sstate->solver_status = SOLVER_AMBIGUOUS; | ||
2795 | goto finished_loop_deductionsing; | ||
2796 | } | ||
2797 | } | ||
2798 | |||
2799 | finished_loop_deductionsing: | ||
2800 | return progress ? DIFF_EASY : DIFF_MAX; | ||
2801 | } | ||
2802 | |||
2803 | /* This will return a dynamically allocated solver_state containing the (more) | ||
2804 | * solved grid */ | ||
2805 | static solver_state *solve_game_rec(const solver_state *sstate_start) | ||
2806 | { | ||
2807 | solver_state *sstate; | ||
2808 | |||
2809 | /* Index of the solver we should call next. */ | ||
2810 | int i = 0; | ||
2811 | |||
2812 | /* As a speed-optimisation, we avoid re-running solvers that we know | ||
2813 | * won't make any progress. This happens when a high-difficulty | ||
2814 | * solver makes a deduction that can only help other high-difficulty | ||
2815 | * solvers. | ||
2816 | * For example: if a new 'dline' flag is set by dline_deductions, the | ||
2817 | * trivial_deductions solver cannot do anything with this information. | ||
2818 | * If we've already run the trivial_deductions solver (because it's | ||
2819 | * earlier in the list), there's no point running it again. | ||
2820 | * | ||
2821 | * Therefore: if a solver is earlier in the list than "threshold_index", | ||
2822 | * we don't bother running it if it's difficulty level is less than | ||
2823 | * "threshold_diff". | ||
2824 | */ | ||
2825 | int threshold_diff = 0; | ||
2826 | int threshold_index = 0; | ||
2827 | |||
2828 | sstate = dup_solver_state(sstate_start); | ||
2829 | |||
2830 | check_caches(sstate); | ||
2831 | |||
2832 | while (i < NUM_SOLVERS) { | ||
2833 | if (sstate->solver_status == SOLVER_MISTAKE) | ||
2834 | return sstate; | ||
2835 | if (sstate->solver_status == SOLVER_SOLVED || | ||
2836 | sstate->solver_status == SOLVER_AMBIGUOUS) { | ||
2837 | /* solver finished */ | ||
2838 | break; | ||
2839 | } | ||
2840 | |||
2841 | if ((solver_diffs[i] >= threshold_diff || i >= threshold_index) | ||
2842 | && solver_diffs[i] <= sstate->diff) { | ||
2843 | /* current_solver is eligible, so use it */ | ||
2844 | int next_diff = solver_fns[i](sstate); | ||
2845 | if (next_diff != DIFF_MAX) { | ||
2846 | /* solver made progress, so use new thresholds and | ||
2847 | * start again at top of list. */ | ||
2848 | threshold_diff = next_diff; | ||
2849 | threshold_index = i; | ||
2850 | i = 0; | ||
2851 | continue; | ||
2852 | } | ||
2853 | } | ||
2854 | /* current_solver is ineligible, or failed to make progress, so | ||
2855 | * go to the next solver in the list */ | ||
2856 | i++; | ||
2857 | } | ||
2858 | |||
2859 | if (sstate->solver_status == SOLVER_SOLVED || | ||
2860 | sstate->solver_status == SOLVER_AMBIGUOUS) { | ||
2861 | /* s/LINE_UNKNOWN/LINE_NO/g */ | ||
2862 | array_setall(sstate->state->lines, LINE_UNKNOWN, LINE_NO, | ||
2863 | sstate->state->game_grid->num_edges); | ||
2864 | return sstate; | ||
2865 | } | ||
2866 | |||
2867 | return sstate; | ||
2868 | } | ||
2869 | |||
2870 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
2871 | const char *aux, char **error) | ||
2872 | { | ||
2873 | char *soln = NULL; | ||
2874 | solver_state *sstate, *new_sstate; | ||
2875 | |||
2876 | sstate = new_solver_state(state, DIFF_MAX); | ||
2877 | new_sstate = solve_game_rec(sstate); | ||
2878 | |||
2879 | if (new_sstate->solver_status == SOLVER_SOLVED) { | ||
2880 | soln = encode_solve_move(new_sstate->state); | ||
2881 | } else if (new_sstate->solver_status == SOLVER_AMBIGUOUS) { | ||
2882 | soln = encode_solve_move(new_sstate->state); | ||
2883 | /**error = "Solver found ambiguous solutions"; */ | ||
2884 | } else { | ||
2885 | soln = encode_solve_move(new_sstate->state); | ||
2886 | /**error = "Solver failed"; */ | ||
2887 | } | ||
2888 | |||
2889 | free_solver_state(new_sstate); | ||
2890 | free_solver_state(sstate); | ||
2891 | |||
2892 | return soln; | ||
2893 | } | ||
2894 | |||
2895 | /* ---------------------------------------------------------------------- | ||
2896 | * Drawing and mouse-handling | ||
2897 | */ | ||
2898 | |||
2899 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
2900 | const game_drawstate *ds, | ||
2901 | int x, int y, int button) | ||
2902 | { | ||
2903 | grid *g = state->game_grid; | ||
2904 | grid_edge *e; | ||
2905 | int i; | ||
2906 | char *ret, buf[80]; | ||
2907 | char button_char = ' '; | ||
2908 | enum line_state old_state; | ||
2909 | |||
2910 | button &= ~MOD_MASK; | ||
2911 | |||
2912 | /* Convert mouse-click (x,y) to grid coordinates */ | ||
2913 | x -= BORDER(ds->tilesize); | ||
2914 | y -= BORDER(ds->tilesize); | ||
2915 | x = x * g->tilesize / ds->tilesize; | ||
2916 | y = y * g->tilesize / ds->tilesize; | ||
2917 | x += g->lowest_x; | ||
2918 | y += g->lowest_y; | ||
2919 | |||
2920 | e = grid_nearest_edge(g, x, y); | ||
2921 | if (e == NULL) | ||
2922 | return NULL; | ||
2923 | |||
2924 | i = e - g->edges; | ||
2925 | |||
2926 | /* I think it's only possible to play this game with mouse clicks, sorry */ | ||
2927 | /* Maybe will add mouse drag support some time */ | ||
2928 | old_state = state->lines[i]; | ||
2929 | |||
2930 | switch (button) { | ||
2931 | case LEFT_BUTTON: | ||
2932 | switch (old_state) { | ||
2933 | case LINE_UNKNOWN: | ||
2934 | button_char = 'y'; | ||
2935 | break; | ||
2936 | case LINE_YES: | ||
2937 | #ifdef STYLUS_BASED | ||
2938 | button_char = 'n'; | ||
2939 | break; | ||
2940 | #endif | ||
2941 | case LINE_NO: | ||
2942 | button_char = 'u'; | ||
2943 | break; | ||
2944 | } | ||
2945 | break; | ||
2946 | case MIDDLE_BUTTON: | ||
2947 | button_char = 'u'; | ||
2948 | break; | ||
2949 | case RIGHT_BUTTON: | ||
2950 | switch (old_state) { | ||
2951 | case LINE_UNKNOWN: | ||
2952 | button_char = 'n'; | ||
2953 | break; | ||
2954 | case LINE_NO: | ||
2955 | #ifdef STYLUS_BASED | ||
2956 | button_char = 'y'; | ||
2957 | break; | ||
2958 | #endif | ||
2959 | case LINE_YES: | ||
2960 | button_char = 'u'; | ||
2961 | break; | ||
2962 | } | ||
2963 | break; | ||
2964 | default: | ||
2965 | return NULL; | ||
2966 | } | ||
2967 | |||
2968 | |||
2969 | sprintf(buf, "%d%c", i, (int)button_char); | ||
2970 | ret = dupstr(buf); | ||
2971 | |||
2972 | return ret; | ||
2973 | } | ||
2974 | |||
2975 | static game_state *execute_move(const game_state *state, const char *move) | ||
2976 | { | ||
2977 | int i; | ||
2978 | game_state *newstate = dup_game(state); | ||
2979 | |||
2980 | if (move[0] == 'S') { | ||
2981 | move++; | ||
2982 | newstate->cheated = TRUE; | ||
2983 | } | ||
2984 | |||
2985 | while (*move) { | ||
2986 | i = atoi(move); | ||
2987 | if (i < 0 || i >= newstate->game_grid->num_edges) | ||
2988 | goto fail; | ||
2989 | move += strspn(move, "1234567890"); | ||
2990 | switch (*(move++)) { | ||
2991 | case 'y': | ||
2992 | newstate->lines[i] = LINE_YES; | ||
2993 | break; | ||
2994 | case 'n': | ||
2995 | newstate->lines[i] = LINE_NO; | ||
2996 | break; | ||
2997 | case 'u': | ||
2998 | newstate->lines[i] = LINE_UNKNOWN; | ||
2999 | break; | ||
3000 | default: | ||
3001 | goto fail; | ||
3002 | } | ||
3003 | } | ||
3004 | |||
3005 | /* | ||
3006 | * Check for completion. | ||
3007 | */ | ||
3008 | if (check_completion(newstate)) | ||
3009 | newstate->solved = TRUE; | ||
3010 | |||
3011 | return newstate; | ||
3012 | |||
3013 | fail: | ||
3014 | free_game(newstate); | ||
3015 | return NULL; | ||
3016 | } | ||
3017 | |||
3018 | /* ---------------------------------------------------------------------- | ||
3019 | * Drawing routines. | ||
3020 | */ | ||
3021 | |||
3022 | /* Convert from grid coordinates to screen coordinates */ | ||
3023 | static void grid_to_screen(const game_drawstate *ds, const grid *g, | ||
3024 | int grid_x, int grid_y, int *x, int *y) | ||
3025 | { | ||
3026 | *x = grid_x - g->lowest_x; | ||
3027 | *y = grid_y - g->lowest_y; | ||
3028 | *x = *x * ds->tilesize / g->tilesize; | ||
3029 | *y = *y * ds->tilesize / g->tilesize; | ||
3030 | *x += BORDER(ds->tilesize); | ||
3031 | *y += BORDER(ds->tilesize); | ||
3032 | } | ||
3033 | |||
3034 | /* Returns (into x,y) position of centre of face for rendering the text clue. | ||
3035 | */ | ||
3036 | static void face_text_pos(const game_drawstate *ds, const grid *g, | ||
3037 | grid_face *f, int *xret, int *yret) | ||
3038 | { | ||
3039 | int faceindex = f - g->faces; | ||
3040 | |||
3041 | /* | ||
3042 | * Return the cached position for this face, if we've already | ||
3043 | * worked it out. | ||
3044 | */ | ||
3045 | if (ds->textx[faceindex] >= 0) { | ||
3046 | *xret = ds->textx[faceindex]; | ||
3047 | *yret = ds->texty[faceindex]; | ||
3048 | return; | ||
3049 | } | ||
3050 | |||
3051 | /* | ||
3052 | * Otherwise, use the incentre computed by grid.c and convert it | ||
3053 | * to screen coordinates. | ||
3054 | */ | ||
3055 | grid_find_incentre(f); | ||
3056 | grid_to_screen(ds, g, f->ix, f->iy, | ||
3057 | &ds->textx[faceindex], &ds->texty[faceindex]); | ||
3058 | |||
3059 | *xret = ds->textx[faceindex]; | ||
3060 | *yret = ds->texty[faceindex]; | ||
3061 | } | ||
3062 | |||
3063 | static void face_text_bbox(game_drawstate *ds, grid *g, grid_face *f, | ||
3064 | int *x, int *y, int *w, int *h) | ||
3065 | { | ||
3066 | int xx, yy; | ||
3067 | face_text_pos(ds, g, f, &xx, &yy); | ||
3068 | |||
3069 | /* There seems to be a certain amount of trial-and-error involved | ||
3070 | * in working out the correct bounding-box for the text. */ | ||
3071 | |||
3072 | *x = xx - ds->tilesize/4 - 1; | ||
3073 | *y = yy - ds->tilesize/4 - 3; | ||
3074 | *w = ds->tilesize/2 + 2; | ||
3075 | *h = ds->tilesize/2 + 5; | ||
3076 | } | ||
3077 | |||
3078 | static void game_redraw_clue(drawing *dr, game_drawstate *ds, | ||
3079 | const game_state *state, int i) | ||
3080 | { | ||
3081 | grid *g = state->game_grid; | ||
3082 | grid_face *f = g->faces + i; | ||
3083 | int x, y; | ||
3084 | char c[20]; | ||
3085 | |||
3086 | sprintf(c, "%d", state->clues[i]); | ||
3087 | |||
3088 | face_text_pos(ds, g, f, &x, &y); | ||
3089 | draw_text(dr, x, y, | ||
3090 | FONT_VARIABLE, ds->tilesize/2, | ||
3091 | ALIGN_VCENTRE | ALIGN_HCENTRE, | ||
3092 | ds->clue_error[i] ? COL_MISTAKE : | ||
3093 | ds->clue_satisfied[i] ? COL_SATISFIED : COL_FOREGROUND, c); | ||
3094 | } | ||
3095 | |||
3096 | static void edge_bbox(game_drawstate *ds, grid *g, grid_edge *e, | ||
3097 | int *x, int *y, int *w, int *h) | ||
3098 | { | ||
3099 | int x1 = e->dot1->x; | ||
3100 | int y1 = e->dot1->y; | ||
3101 | int x2 = e->dot2->x; | ||
3102 | int y2 = e->dot2->y; | ||
3103 | int xmin, xmax, ymin, ymax; | ||
3104 | |||
3105 | grid_to_screen(ds, g, x1, y1, &x1, &y1); | ||
3106 | grid_to_screen(ds, g, x2, y2, &x2, &y2); | ||
3107 | /* Allow extra margin for dots, and thickness of lines */ | ||
3108 | xmin = min(x1, x2) - 2; | ||
3109 | xmax = max(x1, x2) + 2; | ||
3110 | ymin = min(y1, y2) - 2; | ||
3111 | ymax = max(y1, y2) + 2; | ||
3112 | |||
3113 | *x = xmin; | ||
3114 | *y = ymin; | ||
3115 | *w = xmax - xmin + 1; | ||
3116 | *h = ymax - ymin + 1; | ||
3117 | } | ||
3118 | |||
3119 | static void dot_bbox(game_drawstate *ds, grid *g, grid_dot *d, | ||
3120 | int *x, int *y, int *w, int *h) | ||
3121 | { | ||
3122 | int x1, y1; | ||
3123 | |||
3124 | grid_to_screen(ds, g, d->x, d->y, &x1, &y1); | ||
3125 | |||
3126 | *x = x1 - 2; | ||
3127 | *y = y1 - 2; | ||
3128 | *w = 5; | ||
3129 | *h = 5; | ||
3130 | } | ||
3131 | |||
3132 | static const int loopy_line_redraw_phases[] = { | ||
3133 | COL_FAINT, COL_LINEUNKNOWN, COL_FOREGROUND, COL_HIGHLIGHT, COL_MISTAKE | ||
3134 | }; | ||
3135 | #define NPHASES lenof(loopy_line_redraw_phases) | ||
3136 | |||
3137 | static void game_redraw_line(drawing *dr, game_drawstate *ds, | ||
3138 | const game_state *state, int i, int phase) | ||
3139 | { | ||
3140 | grid *g = state->game_grid; | ||
3141 | grid_edge *e = g->edges + i; | ||
3142 | int x1, x2, y1, y2; | ||
3143 | int line_colour; | ||
3144 | |||
3145 | if (state->line_errors[i]) | ||
3146 | line_colour = COL_MISTAKE; | ||
3147 | else if (state->lines[i] == LINE_UNKNOWN) | ||
3148 | line_colour = COL_LINEUNKNOWN; | ||
3149 | else if (state->lines[i] == LINE_NO) | ||
3150 | line_colour = COL_FAINT; | ||
3151 | else if (ds->flashing) | ||
3152 | line_colour = COL_HIGHLIGHT; | ||
3153 | else | ||
3154 | line_colour = COL_FOREGROUND; | ||
3155 | if (line_colour != loopy_line_redraw_phases[phase]) | ||
3156 | return; | ||
3157 | |||
3158 | /* Convert from grid to screen coordinates */ | ||
3159 | grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1); | ||
3160 | grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2); | ||
3161 | |||
3162 | if (line_colour == COL_FAINT) { | ||
3163 | static int draw_faint_lines = -1; | ||
3164 | if (draw_faint_lines < 0) { | ||
3165 | char *env = getenv("LOOPY_FAINT_LINES"); | ||
3166 | draw_faint_lines = (!env || (env[0] == 'y' || | ||
3167 | env[0] == 'Y')); | ||
3168 | } | ||
3169 | if (draw_faint_lines) | ||
3170 | draw_line(dr, x1, y1, x2, y2, line_colour); | ||
3171 | } else { | ||
3172 | draw_thick_line(dr, 3.0, | ||
3173 | x1 + 0.5, y1 + 0.5, | ||
3174 | x2 + 0.5, y2 + 0.5, | ||
3175 | line_colour); | ||
3176 | } | ||
3177 | } | ||
3178 | |||
3179 | static void game_redraw_dot(drawing *dr, game_drawstate *ds, | ||
3180 | const game_state *state, int i) | ||
3181 | { | ||
3182 | grid *g = state->game_grid; | ||
3183 | grid_dot *d = g->dots + i; | ||
3184 | int x, y; | ||
3185 | |||
3186 | grid_to_screen(ds, g, d->x, d->y, &x, &y); | ||
3187 | draw_circle(dr, x, y, 2, COL_FOREGROUND, COL_FOREGROUND); | ||
3188 | } | ||
3189 | |||
3190 | static int boxes_intersect(int x0, int y0, int w0, int h0, | ||
3191 | int x1, int y1, int w1, int h1) | ||
3192 | { | ||
3193 | /* | ||
3194 | * Two intervals intersect iff neither is wholly on one side of | ||
3195 | * the other. Two boxes intersect iff their horizontal and | ||
3196 | * vertical intervals both intersect. | ||
3197 | */ | ||
3198 | return (x0 < x1+w1 && x1 < x0+w0 && y0 < y1+h1 && y1 < y0+h0); | ||
3199 | } | ||
3200 | |||
3201 | static void game_redraw_in_rect(drawing *dr, game_drawstate *ds, | ||
3202 | const game_state *state, | ||
3203 | int x, int y, int w, int h) | ||
3204 | { | ||
3205 | grid *g = state->game_grid; | ||
3206 | int i, phase; | ||
3207 | int bx, by, bw, bh; | ||
3208 | |||
3209 | clip(dr, x, y, w, h); | ||
3210 | draw_rect(dr, x, y, w, h, COL_BACKGROUND); | ||
3211 | |||
3212 | for (i = 0; i < g->num_faces; i++) { | ||
3213 | if (state->clues[i] >= 0) { | ||
3214 | face_text_bbox(ds, g, &g->faces[i], &bx, &by, &bw, &bh); | ||
3215 | if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) | ||
3216 | game_redraw_clue(dr, ds, state, i); | ||
3217 | } | ||
3218 | } | ||
3219 | for (phase = 0; phase < NPHASES; phase++) { | ||
3220 | for (i = 0; i < g->num_edges; i++) { | ||
3221 | edge_bbox(ds, g, &g->edges[i], &bx, &by, &bw, &bh); | ||
3222 | if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) | ||
3223 | game_redraw_line(dr, ds, state, i, phase); | ||
3224 | } | ||
3225 | } | ||
3226 | for (i = 0; i < g->num_dots; i++) { | ||
3227 | dot_bbox(ds, g, &g->dots[i], &bx, &by, &bw, &bh); | ||
3228 | if (boxes_intersect(x, y, w, h, bx, by, bw, bh)) | ||
3229 | game_redraw_dot(dr, ds, state, i); | ||
3230 | } | ||
3231 | |||
3232 | unclip(dr); | ||
3233 | draw_update(dr, x, y, w, h); | ||
3234 | } | ||
3235 | |||
3236 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
3237 | const game_state *oldstate, const game_state *state, | ||
3238 | int dir, const game_ui *ui, | ||
3239 | float animtime, float flashtime) | ||
3240 | { | ||
3241 | #define REDRAW_OBJECTS_LIMIT 16 /* Somewhat arbitrary tradeoff */ | ||
3242 | |||
3243 | grid *g = state->game_grid; | ||
3244 | int border = BORDER(ds->tilesize); | ||
3245 | int i; | ||
3246 | int flash_changed; | ||
3247 | int redraw_everything = FALSE; | ||
3248 | |||
3249 | int edges[REDRAW_OBJECTS_LIMIT], nedges = 0; | ||
3250 | int faces[REDRAW_OBJECTS_LIMIT], nfaces = 0; | ||
3251 | |||
3252 | /* Redrawing is somewhat involved. | ||
3253 | * | ||
3254 | * An update can theoretically affect an arbitrary number of edges | ||
3255 | * (consider, for example, completing or breaking a cycle which doesn't | ||
3256 | * satisfy all the clues -- we'll switch many edges between error and | ||
3257 | * normal states). On the other hand, redrawing the whole grid takes a | ||
3258 | * while, making the game feel sluggish, and many updates are actually | ||
3259 | * quite well localized. | ||
3260 | * | ||
3261 | * This redraw algorithm attempts to cope with both situations gracefully | ||
3262 | * and correctly. For localized changes, we set a clip rectangle, fill | ||
3263 | * it with background, and then redraw (a plausible but conservative | ||
3264 | * guess at) the objects which intersect the rectangle; if several | ||
3265 | * objects need redrawing, we'll do them individually. However, if lots | ||
3266 | * of objects are affected, we'll just redraw everything. | ||
3267 | * | ||
3268 | * The reason for all of this is that it's just not safe to do the redraw | ||
3269 | * piecemeal. If you try to draw an antialiased diagonal line over | ||
3270 | * itself, you get a slightly thicker antialiased diagonal line, which | ||
3271 | * looks rather ugly after a while. | ||
3272 | * | ||
3273 | * So, we take two passes over the grid. The first attempts to work out | ||
3274 | * what needs doing, and the second actually does it. | ||
3275 | */ | ||
3276 | |||
3277 | if (!ds->started) { | ||
3278 | redraw_everything = TRUE; | ||
3279 | /* | ||
3280 | * But we must still go through the upcoming loops, so that we | ||
3281 | * set up stuff in ds correctly for the initial redraw. | ||
3282 | */ | ||
3283 | } | ||
3284 | |||
3285 | /* First, trundle through the faces. */ | ||
3286 | for (i = 0; i < g->num_faces; i++) { | ||
3287 | grid_face *f = g->faces + i; | ||
3288 | int sides = f->order; | ||
3289 | int yes_order, no_order; | ||
3290 | int clue_mistake; | ||
3291 | int clue_satisfied; | ||
3292 | int n = state->clues[i]; | ||
3293 | if (n < 0) | ||
3294 | continue; | ||
3295 | |||
3296 | yes_order = face_order(state, i, LINE_YES); | ||
3297 | if (state->exactly_one_loop) { | ||
3298 | /* | ||
3299 | * Special case: if the set of LINE_YES edges in the grid | ||
3300 | * consists of exactly one loop and nothing else, then we | ||
3301 | * switch to treating LINE_UNKNOWN the same as LINE_NO for | ||
3302 | * purposes of clue checking. | ||
3303 | * | ||
3304 | * This is because some people like to play Loopy without | ||
3305 | * using the right-click, i.e. never setting anything to | ||
3306 | * LINE_NO. Without this special case, if a person playing | ||
3307 | * in that style fills in what they think is a correct | ||
3308 | * solution loop but in fact it has an underfilled clue, | ||
3309 | * then we will display no victory flash and also no error | ||
3310 | * highlight explaining why not. With this special case, | ||
3311 | * we light up underfilled clues at the instant the loop | ||
3312 | * is closed. (Of course, *overfilled* clues are fine | ||
3313 | * either way.) | ||
3314 | * | ||
3315 | * (It might still be considered unfortunate that we can't | ||
3316 | * warn this style of player any earlier, if they make a | ||
3317 | * mistake very near the beginning which doesn't show up | ||
3318 | * until they close the last edge of the loop. One other | ||
3319 | * thing we _could_ do here is to treat any LINE_UNKNOWN | ||
3320 | * as LINE_NO if either of its endpoints has yes-degree 2, | ||
3321 | * reflecting the fact that setting that line to YES would | ||
3322 | * be an obvious error. But I don't think even that could | ||
3323 | * catch _all_ clue errors in a timely manner; I think | ||
3324 | * there are some that won't be displayed until the loop | ||
3325 | * is filled in, even so, and there's no way to avoid that | ||
3326 | * with complete reliability except to switch to being a | ||
3327 | * player who sets things to LINE_NO.) | ||
3328 | */ | ||
3329 | no_order = sides - yes_order; | ||
3330 | } else { | ||
3331 | no_order = face_order(state, i, LINE_NO); | ||
3332 | } | ||
3333 | |||
3334 | clue_mistake = (yes_order > n || no_order > (sides-n)); | ||
3335 | clue_satisfied = (yes_order == n && no_order == (sides-n)); | ||
3336 | |||
3337 | if (clue_mistake != ds->clue_error[i] || | ||
3338 | clue_satisfied != ds->clue_satisfied[i]) { | ||
3339 | ds->clue_error[i] = clue_mistake; | ||
3340 | ds->clue_satisfied[i] = clue_satisfied; | ||
3341 | if (nfaces == REDRAW_OBJECTS_LIMIT) | ||
3342 | redraw_everything = TRUE; | ||
3343 | else | ||
3344 | faces[nfaces++] = i; | ||
3345 | } | ||
3346 | } | ||
3347 | |||
3348 | /* Work out what the flash state needs to be. */ | ||
3349 | if (flashtime > 0 && | ||
3350 | (flashtime <= FLASH_TIME/3 || | ||
3351 | flashtime >= FLASH_TIME*2/3)) { | ||
3352 | flash_changed = !ds->flashing; | ||
3353 | ds->flashing = TRUE; | ||
3354 | } else { | ||
3355 | flash_changed = ds->flashing; | ||
3356 | ds->flashing = FALSE; | ||
3357 | } | ||
3358 | |||
3359 | /* Now, trundle through the edges. */ | ||
3360 | for (i = 0; i < g->num_edges; i++) { | ||
3361 | char new_ds = | ||
3362 | state->line_errors[i] ? DS_LINE_ERROR : state->lines[i]; | ||
3363 | if (new_ds != ds->lines[i] || | ||
3364 | (flash_changed && state->lines[i] == LINE_YES)) { | ||
3365 | ds->lines[i] = new_ds; | ||
3366 | if (nedges == REDRAW_OBJECTS_LIMIT) | ||
3367 | redraw_everything = TRUE; | ||
3368 | else | ||
3369 | edges[nedges++] = i; | ||
3370 | } | ||
3371 | } | ||
3372 | |||
3373 | /* Pass one is now done. Now we do the actual drawing. */ | ||
3374 | if (redraw_everything) { | ||
3375 | int grid_width = g->highest_x - g->lowest_x; | ||
3376 | int grid_height = g->highest_y - g->lowest_y; | ||
3377 | int w = grid_width * ds->tilesize / g->tilesize; | ||
3378 | int h = grid_height * ds->tilesize / g->tilesize; | ||
3379 | |||
3380 | game_redraw_in_rect(dr, ds, state, | ||
3381 | 0, 0, w + 2*border + 1, h + 2*border + 1); | ||
3382 | } else { | ||
3383 | |||
3384 | /* Right. Now we roll up our sleeves. */ | ||
3385 | |||
3386 | for (i = 0; i < nfaces; i++) { | ||
3387 | grid_face *f = g->faces + faces[i]; | ||
3388 | int x, y, w, h; | ||
3389 | |||
3390 | face_text_bbox(ds, g, f, &x, &y, &w, &h); | ||
3391 | game_redraw_in_rect(dr, ds, state, x, y, w, h); | ||
3392 | } | ||
3393 | |||
3394 | for (i = 0; i < nedges; i++) { | ||
3395 | grid_edge *e = g->edges + edges[i]; | ||
3396 | int x, y, w, h; | ||
3397 | |||
3398 | edge_bbox(ds, g, e, &x, &y, &w, &h); | ||
3399 | game_redraw_in_rect(dr, ds, state, x, y, w, h); | ||
3400 | } | ||
3401 | } | ||
3402 | |||
3403 | ds->started = TRUE; | ||
3404 | } | ||
3405 | |||
3406 | static float game_flash_length(const game_state *oldstate, | ||
3407 | const game_state *newstate, int dir, game_ui *ui) | ||
3408 | { | ||
3409 | if (!oldstate->solved && newstate->solved && | ||
3410 | !oldstate->cheated && !newstate->cheated) { | ||
3411 | return FLASH_TIME; | ||
3412 | } | ||
3413 | |||
3414 | return 0.0F; | ||
3415 | } | ||
3416 | |||
3417 | static int game_status(const game_state *state) | ||
3418 | { | ||
3419 | return state->solved ? +1 : 0; | ||
3420 | } | ||
3421 | |||
3422 | static void game_print_size(const game_params *params, float *x, float *y) | ||
3423 | { | ||
3424 | int pw, ph; | ||
3425 | |||
3426 | /* | ||
3427 | * I'll use 7mm "squares" by default. | ||
3428 | */ | ||
3429 | game_compute_size(params, 700, &pw, &ph); | ||
3430 | *x = pw / 100.0F; | ||
3431 | *y = ph / 100.0F; | ||
3432 | } | ||
3433 | |||
3434 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
3435 | { | ||
3436 | int ink = print_mono_colour(dr, 0); | ||
3437 | int i; | ||
3438 | game_drawstate ads, *ds = &ads; | ||
3439 | grid *g = state->game_grid; | ||
3440 | |||
3441 | ds->tilesize = tilesize; | ||
3442 | ds->textx = snewn(g->num_faces, int); | ||
3443 | ds->texty = snewn(g->num_faces, int); | ||
3444 | for (i = 0; i < g->num_faces; i++) | ||
3445 | ds->textx[i] = ds->texty[i] = -1; | ||
3446 | |||
3447 | for (i = 0; i < g->num_dots; i++) { | ||
3448 | int x, y; | ||
3449 | grid_to_screen(ds, g, g->dots[i].x, g->dots[i].y, &x, &y); | ||
3450 | draw_circle(dr, x, y, ds->tilesize / 15, ink, ink); | ||
3451 | } | ||
3452 | |||
3453 | /* | ||
3454 | * Clues. | ||
3455 | */ | ||
3456 | for (i = 0; i < g->num_faces; i++) { | ||
3457 | grid_face *f = g->faces + i; | ||
3458 | int clue = state->clues[i]; | ||
3459 | if (clue >= 0) { | ||
3460 | char c[20]; | ||
3461 | int x, y; | ||
3462 | sprintf(c, "%d", state->clues[i]); | ||
3463 | face_text_pos(ds, g, f, &x, &y); | ||
3464 | draw_text(dr, x, y, | ||
3465 | FONT_VARIABLE, ds->tilesize / 2, | ||
3466 | ALIGN_VCENTRE | ALIGN_HCENTRE, ink, c); | ||
3467 | } | ||
3468 | } | ||
3469 | |||
3470 | /* | ||
3471 | * Lines. | ||
3472 | */ | ||
3473 | for (i = 0; i < g->num_edges; i++) { | ||
3474 | int thickness = (state->lines[i] == LINE_YES) ? 30 : 150; | ||
3475 | grid_edge *e = g->edges + i; | ||
3476 | int x1, y1, x2, y2; | ||
3477 | grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1); | ||
3478 | grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2); | ||
3479 | if (state->lines[i] == LINE_YES) | ||
3480 | { | ||
3481 | /* (dx, dy) points from (x1, y1) to (x2, y2). | ||
3482 | * The line is then "fattened" in a perpendicular | ||
3483 | * direction to create a thin rectangle. */ | ||
3484 | double d = sqrt(SQ((double)x1 - x2) + SQ((double)y1 - y2)); | ||
3485 | double dx = (x2 - x1) / d; | ||
3486 | double dy = (y2 - y1) / d; | ||
3487 | int points[8]; | ||
3488 | |||
3489 | dx = (dx * ds->tilesize) / thickness; | ||
3490 | dy = (dy * ds->tilesize) / thickness; | ||
3491 | points[0] = x1 + (int)dy; | ||
3492 | points[1] = y1 - (int)dx; | ||
3493 | points[2] = x1 - (int)dy; | ||
3494 | points[3] = y1 + (int)dx; | ||
3495 | points[4] = x2 - (int)dy; | ||
3496 | points[5] = y2 + (int)dx; | ||
3497 | points[6] = x2 + (int)dy; | ||
3498 | points[7] = y2 - (int)dx; | ||
3499 | draw_polygon(dr, points, 4, ink, ink); | ||
3500 | } | ||
3501 | else | ||
3502 | { | ||
3503 | /* Draw a dotted line */ | ||
3504 | int divisions = 6; | ||
3505 | int j; | ||
3506 | for (j = 1; j < divisions; j++) { | ||
3507 | /* Weighted average */ | ||
3508 | int x = (x1 * (divisions -j) + x2 * j) / divisions; | ||
3509 | int y = (y1 * (divisions -j) + y2 * j) / divisions; | ||
3510 | draw_circle(dr, x, y, ds->tilesize / thickness, ink, ink); | ||
3511 | } | ||
3512 | } | ||
3513 | } | ||
3514 | |||
3515 | sfree(ds->textx); | ||
3516 | sfree(ds->texty); | ||
3517 | } | ||
3518 | |||
3519 | #ifdef COMBINED | ||
3520 | #define thegame loopy | ||
3521 | #endif | ||
3522 | |||
3523 | const struct game thegame = { | ||
3524 | "Loopy", "games.loopy", "loopy", | ||
3525 | default_params, | ||
3526 | game_fetch_preset, | ||
3527 | decode_params, | ||
3528 | encode_params, | ||
3529 | free_params, | ||
3530 | dup_params, | ||
3531 | TRUE, game_configure, custom_params, | ||
3532 | validate_params, | ||
3533 | new_game_desc, | ||
3534 | validate_desc, | ||
3535 | new_game, | ||
3536 | dup_game, | ||
3537 | free_game, | ||
3538 | 1, solve_game, | ||
3539 | TRUE, game_can_format_as_text_now, game_text_format, | ||
3540 | new_ui, | ||
3541 | free_ui, | ||
3542 | encode_ui, | ||
3543 | decode_ui, | ||
3544 | game_changed_state, | ||
3545 | interpret_move, | ||
3546 | execute_move, | ||
3547 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
3548 | game_colours, | ||
3549 | game_new_drawstate, | ||
3550 | game_free_drawstate, | ||
3551 | game_redraw, | ||
3552 | game_anim_length, | ||
3553 | game_flash_length, | ||
3554 | game_status, | ||
3555 | TRUE, FALSE, game_print_size, game_print, | ||
3556 | FALSE /* wants_statusbar */, | ||
3557 | FALSE, game_timing_state, | ||
3558 | 0, /* mouse_priorities */ | ||
3559 | }; | ||
3560 | |||
3561 | #ifdef STANDALONE_SOLVER | ||
3562 | |||
3563 | /* | ||
3564 | * Half-hearted standalone solver. It can't output the solution to | ||
3565 | * anything but a square puzzle, and it can't log the deductions | ||
3566 | * it makes either. But it can solve square puzzles, and more | ||
3567 | * importantly it can use its solver to grade the difficulty of | ||
3568 | * any puzzle you give it. | ||
3569 | */ | ||
3570 | |||
3571 | #include <stdarg.h> | ||
3572 | |||
3573 | int main(int argc, char **argv) | ||
3574 | { | ||
3575 | game_params *p; | ||
3576 | game_state *s; | ||
3577 | char *id = NULL, *desc, *err; | ||
3578 | int grade = FALSE; | ||
3579 | int ret, diff; | ||
3580 | #if 0 /* verbose solver not supported here (yet) */ | ||
3581 | int really_verbose = FALSE; | ||
3582 | #endif | ||
3583 | |||
3584 | while (--argc > 0) { | ||
3585 | char *p = *++argv; | ||
3586 | #if 0 /* verbose solver not supported here (yet) */ | ||
3587 | if (!strcmp(p, "-v")) { | ||
3588 | really_verbose = TRUE; | ||
3589 | } else | ||
3590 | #endif | ||
3591 | if (!strcmp(p, "-g")) { | ||
3592 | grade = TRUE; | ||
3593 | } else if (*p == '-') { | ||
3594 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
3595 | return 1; | ||
3596 | } else { | ||
3597 | id = p; | ||
3598 | } | ||
3599 | } | ||
3600 | |||
3601 | if (!id) { | ||
3602 | fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]); | ||
3603 | return 1; | ||
3604 | } | ||
3605 | |||
3606 | desc = strchr(id, ':'); | ||
3607 | if (!desc) { | ||
3608 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
3609 | return 1; | ||
3610 | } | ||
3611 | *desc++ = '\0'; | ||
3612 | |||
3613 | p = default_params(); | ||
3614 | decode_params(p, id); | ||
3615 | err = validate_desc(p, desc); | ||
3616 | if (err) { | ||
3617 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
3618 | return 1; | ||
3619 | } | ||
3620 | s = new_game(NULL, p, desc); | ||
3621 | |||
3622 | /* | ||
3623 | * When solving an Easy puzzle, we don't want to bother the | ||
3624 | * user with Hard-level deductions. For this reason, we grade | ||
3625 | * the puzzle internally before doing anything else. | ||
3626 | */ | ||
3627 | ret = -1; /* placate optimiser */ | ||
3628 | for (diff = 0; diff < DIFF_MAX; diff++) { | ||
3629 | solver_state *sstate_new; | ||
3630 | solver_state *sstate = new_solver_state((game_state *)s, diff); | ||
3631 | |||
3632 | sstate_new = solve_game_rec(sstate); | ||
3633 | |||
3634 | if (sstate_new->solver_status == SOLVER_MISTAKE) | ||
3635 | ret = 0; | ||
3636 | else if (sstate_new->solver_status == SOLVER_SOLVED) | ||
3637 | ret = 1; | ||
3638 | else | ||
3639 | ret = 2; | ||
3640 | |||
3641 | free_solver_state(sstate_new); | ||
3642 | free_solver_state(sstate); | ||
3643 | |||
3644 | if (ret < 2) | ||
3645 | break; | ||
3646 | } | ||
3647 | |||
3648 | if (diff == DIFF_MAX) { | ||
3649 | if (grade) | ||
3650 | printf("Difficulty rating: harder than Hard, or ambiguous\n"); | ||
3651 | else | ||
3652 | printf("Unable to find a unique solution\n"); | ||
3653 | } else { | ||
3654 | if (grade) { | ||
3655 | if (ret == 0) | ||
3656 | printf("Difficulty rating: impossible (no solution exists)\n"); | ||
3657 | else if (ret == 1) | ||
3658 | printf("Difficulty rating: %s\n", diffnames[diff]); | ||
3659 | } else { | ||
3660 | solver_state *sstate_new; | ||
3661 | solver_state *sstate = new_solver_state((game_state *)s, diff); | ||
3662 | |||
3663 | /* If we supported a verbose solver, we'd set verbosity here */ | ||
3664 | |||
3665 | sstate_new = solve_game_rec(sstate); | ||
3666 | |||
3667 | if (sstate_new->solver_status == SOLVER_MISTAKE) | ||
3668 | printf("Puzzle is inconsistent\n"); | ||
3669 | else { | ||
3670 | assert(sstate_new->solver_status == SOLVER_SOLVED); | ||
3671 | if (s->grid_type == 0) { | ||
3672 | fputs(game_text_format(sstate_new->state), stdout); | ||
3673 | } else { | ||
3674 | printf("Unable to output non-square grids\n"); | ||
3675 | } | ||
3676 | } | ||
3677 | |||
3678 | free_solver_state(sstate_new); | ||
3679 | free_solver_state(sstate); | ||
3680 | } | ||
3681 | } | ||
3682 | |||
3683 | return 0; | ||
3684 | } | ||
3685 | |||
3686 | #endif | ||
3687 | |||
3688 | /* vim: set shiftwidth=4 tabstop=8: */ | ||