diff options
Diffstat (limited to 'apps/plugins/puzzles/src/pearl.c')
-rw-r--r-- | apps/plugins/puzzles/src/pearl.c | 2770 |
1 files changed, 2770 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/pearl.c b/apps/plugins/puzzles/src/pearl.c new file mode 100644 index 0000000000..c6c305f3f2 --- /dev/null +++ b/apps/plugins/puzzles/src/pearl.c | |||
@@ -0,0 +1,2770 @@ | |||
1 | /* | ||
2 | * pearl.c: Nikoli's `Masyu' puzzle. | ||
3 | */ | ||
4 | |||
5 | /* | ||
6 | * TODO: | ||
7 | * | ||
8 | * - The current keyboard cursor mechanism works well on ordinary PC | ||
9 | * keyboards, but for platforms with only arrow keys and a select | ||
10 | * button or two, we may at some point need a simpler one which can | ||
11 | * handle 'x' markings without needing shift keys. For instance, a | ||
12 | * cursor with twice the grid resolution, so that it can range | ||
13 | * across face centres, edge centres and vertices; 'clicks' on face | ||
14 | * centres begin a drag as currently, clicks on edges toggle | ||
15 | * markings, and clicks on vertices are ignored (but it would be | ||
16 | * too confusing not to let the cursor rest on them). But I'm | ||
17 | * pretty sure that would be less pleasant to play on a full | ||
18 | * keyboard, so probably a #ifdef would be the thing. | ||
19 | * | ||
20 | * - Generation is still pretty slow, due to difficulty coming up in | ||
21 | * the first place with a loop that makes a soluble puzzle even | ||
22 | * with all possible clues filled in. | ||
23 | * + A possible alternative strategy to further tuning of the | ||
24 | * existing loop generator would be to throw the entire | ||
25 | * mechanism out and instead write a different generator from | ||
26 | * scratch which evolves the solution along with the puzzle: | ||
27 | * place a few clues, nail down a bit of the loop, place another | ||
28 | * clue, nail down some more, etc. However, I don't have a | ||
29 | * detailed plan for any such mechanism, so it may be a pipe | ||
30 | * dream. | ||
31 | */ | ||
32 | |||
33 | #include <stdio.h> | ||
34 | #include <stdlib.h> | ||
35 | #include <string.h> | ||
36 | #include <assert.h> | ||
37 | #include <ctype.h> | ||
38 | #include <math.h> | ||
39 | |||
40 | #include "puzzles.h" | ||
41 | #include "grid.h" | ||
42 | #include "loopgen.h" | ||
43 | |||
44 | #define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0) | ||
45 | |||
46 | #define NOCLUE 0 | ||
47 | #define CORNER 1 | ||
48 | #define STRAIGHT 2 | ||
49 | |||
50 | #define R 1 | ||
51 | #define U 2 | ||
52 | #define L 4 | ||
53 | #define D 8 | ||
54 | |||
55 | #define DX(d) ( ((d)==R) - ((d)==L) ) | ||
56 | #define DY(d) ( ((d)==D) - ((d)==U) ) | ||
57 | |||
58 | #define F(d) (((d << 2) | (d >> 2)) & 0xF) | ||
59 | #define C(d) (((d << 3) | (d >> 1)) & 0xF) | ||
60 | #define A(d) (((d << 1) | (d >> 3)) & 0xF) | ||
61 | |||
62 | #define LR (L | R) | ||
63 | #define RL (R | L) | ||
64 | #define UD (U | D) | ||
65 | #define DU (D | U) | ||
66 | #define LU (L | U) | ||
67 | #define UL (U | L) | ||
68 | #define LD (L | D) | ||
69 | #define DL (D | L) | ||
70 | #define RU (R | U) | ||
71 | #define UR (U | R) | ||
72 | #define RD (R | D) | ||
73 | #define DR (D | R) | ||
74 | #define BLANK 0 | ||
75 | #define UNKNOWN 15 | ||
76 | |||
77 | #define bLR (1 << LR) | ||
78 | #define bRL (1 << RL) | ||
79 | #define bUD (1 << UD) | ||
80 | #define bDU (1 << DU) | ||
81 | #define bLU (1 << LU) | ||
82 | #define bUL (1 << UL) | ||
83 | #define bLD (1 << LD) | ||
84 | #define bDL (1 << DL) | ||
85 | #define bRU (1 << RU) | ||
86 | #define bUR (1 << UR) | ||
87 | #define bRD (1 << RD) | ||
88 | #define bDR (1 << DR) | ||
89 | #define bBLANK (1 << BLANK) | ||
90 | |||
91 | enum { | ||
92 | COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT, | ||
93 | COL_CURSOR_BACKGROUND = COL_LOWLIGHT, | ||
94 | COL_BLACK, COL_WHITE, | ||
95 | COL_ERROR, COL_GRID, COL_FLASH, | ||
96 | COL_DRAGON, COL_DRAGOFF, | ||
97 | NCOLOURS | ||
98 | }; | ||
99 | |||
100 | /* Macro ickery copied from slant.c */ | ||
101 | #define DIFFLIST(A) \ | ||
102 | A(EASY,Easy,e) \ | ||
103 | A(TRICKY,Tricky,t) | ||
104 | #define ENUM(upper,title,lower) DIFF_ ## upper, | ||
105 | #define TITLE(upper,title,lower) #title, | ||
106 | #define ENCODE(upper,title,lower) #lower | ||
107 | #define CONFIG(upper,title,lower) ":" #title | ||
108 | enum { DIFFLIST(ENUM) DIFFCOUNT }; | ||
109 | static char const *const pearl_diffnames[] = { DIFFLIST(TITLE) "(count)" }; | ||
110 | static char const pearl_diffchars[] = DIFFLIST(ENCODE); | ||
111 | #define DIFFCONFIG DIFFLIST(CONFIG) | ||
112 | |||
113 | struct game_params { | ||
114 | int w, h; | ||
115 | int difficulty; | ||
116 | int nosolve; /* XXX remove me! */ | ||
117 | }; | ||
118 | |||
119 | struct shared_state { | ||
120 | int w, h, sz; | ||
121 | char *clues; /* size w*h */ | ||
122 | int refcnt; | ||
123 | }; | ||
124 | |||
125 | #define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->shared->w && \ | ||
126 | (gy) >= 0 && (gy) < (state)->shared->h) | ||
127 | struct game_state { | ||
128 | struct shared_state *shared; | ||
129 | char *lines; /* size w*h: lines placed */ | ||
130 | char *errors; /* size w*h: errors detected */ | ||
131 | char *marks; /* size w*h: 'no line here' marks placed. */ | ||
132 | int completed, used_solve; | ||
133 | }; | ||
134 | |||
135 | #define DEFAULT_PRESET 3 | ||
136 | |||
137 | static const struct game_params pearl_presets[] = { | ||
138 | {6, 6, DIFF_EASY}, | ||
139 | {6, 6, DIFF_TRICKY}, | ||
140 | {8, 8, DIFF_EASY}, | ||
141 | {8, 8, DIFF_TRICKY}, | ||
142 | {10, 10, DIFF_EASY}, | ||
143 | {10, 10, DIFF_TRICKY}, | ||
144 | {12, 8, DIFF_EASY}, | ||
145 | {12, 8, DIFF_TRICKY}, | ||
146 | }; | ||
147 | |||
148 | static game_params *default_params(void) | ||
149 | { | ||
150 | game_params *ret = snew(game_params); | ||
151 | |||
152 | *ret = pearl_presets[DEFAULT_PRESET]; | ||
153 | ret->nosolve = FALSE; | ||
154 | |||
155 | return ret; | ||
156 | } | ||
157 | |||
158 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
159 | { | ||
160 | game_params *ret; | ||
161 | char buf[64]; | ||
162 | |||
163 | if (i < 0 || i >= lenof(pearl_presets)) return FALSE; | ||
164 | |||
165 | ret = default_params(); | ||
166 | *ret = pearl_presets[i]; /* struct copy */ | ||
167 | *params = ret; | ||
168 | |||
169 | sprintf(buf, "%dx%d %s", | ||
170 | pearl_presets[i].w, pearl_presets[i].h, | ||
171 | pearl_diffnames[pearl_presets[i].difficulty]); | ||
172 | *name = dupstr(buf); | ||
173 | |||
174 | return TRUE; | ||
175 | } | ||
176 | |||
177 | static void free_params(game_params *params) | ||
178 | { | ||
179 | sfree(params); | ||
180 | } | ||
181 | |||
182 | static game_params *dup_params(const game_params *params) | ||
183 | { | ||
184 | game_params *ret = snew(game_params); | ||
185 | *ret = *params; /* structure copy */ | ||
186 | return ret; | ||
187 | } | ||
188 | |||
189 | static void decode_params(game_params *ret, char const *string) | ||
190 | { | ||
191 | ret->w = ret->h = atoi(string); | ||
192 | while (*string && isdigit((unsigned char) *string)) ++string; | ||
193 | if (*string == 'x') { | ||
194 | string++; | ||
195 | ret->h = atoi(string); | ||
196 | while (*string && isdigit((unsigned char)*string)) string++; | ||
197 | } | ||
198 | |||
199 | ret->difficulty = DIFF_EASY; | ||
200 | if (*string == 'd') { | ||
201 | int i; | ||
202 | string++; | ||
203 | for (i = 0; i < DIFFCOUNT; i++) | ||
204 | if (*string == pearl_diffchars[i]) | ||
205 | ret->difficulty = i; | ||
206 | if (*string) string++; | ||
207 | } | ||
208 | |||
209 | ret->nosolve = FALSE; | ||
210 | if (*string == 'n') { | ||
211 | ret->nosolve = TRUE; | ||
212 | string++; | ||
213 | } | ||
214 | } | ||
215 | |||
216 | static char *encode_params(const game_params *params, int full) | ||
217 | { | ||
218 | char buf[256]; | ||
219 | sprintf(buf, "%dx%d", params->w, params->h); | ||
220 | if (full) | ||
221 | sprintf(buf + strlen(buf), "d%c%s", | ||
222 | pearl_diffchars[params->difficulty], | ||
223 | params->nosolve ? "n" : ""); | ||
224 | return dupstr(buf); | ||
225 | } | ||
226 | |||
227 | static config_item *game_configure(const game_params *params) | ||
228 | { | ||
229 | config_item *ret; | ||
230 | char buf[64]; | ||
231 | |||
232 | ret = snewn(5, config_item); | ||
233 | |||
234 | ret[0].name = "Width"; | ||
235 | ret[0].type = C_STRING; | ||
236 | sprintf(buf, "%d", params->w); | ||
237 | ret[0].sval = dupstr(buf); | ||
238 | ret[0].ival = 0; | ||
239 | |||
240 | ret[1].name = "Height"; | ||
241 | ret[1].type = C_STRING; | ||
242 | sprintf(buf, "%d", params->h); | ||
243 | ret[1].sval = dupstr(buf); | ||
244 | ret[1].ival = 0; | ||
245 | |||
246 | ret[2].name = "Difficulty"; | ||
247 | ret[2].type = C_CHOICES; | ||
248 | ret[2].sval = DIFFCONFIG; | ||
249 | ret[2].ival = params->difficulty; | ||
250 | |||
251 | ret[3].name = "Allow unsoluble"; | ||
252 | ret[3].type = C_BOOLEAN; | ||
253 | ret[3].sval = NULL; | ||
254 | ret[3].ival = params->nosolve; | ||
255 | |||
256 | ret[4].name = NULL; | ||
257 | ret[4].type = C_END; | ||
258 | ret[4].sval = NULL; | ||
259 | ret[4].ival = 0; | ||
260 | |||
261 | return ret; | ||
262 | } | ||
263 | |||
264 | static game_params *custom_params(const config_item *cfg) | ||
265 | { | ||
266 | game_params *ret = snew(game_params); | ||
267 | |||
268 | ret->w = atoi(cfg[0].sval); | ||
269 | ret->h = atoi(cfg[1].sval); | ||
270 | ret->difficulty = cfg[2].ival; | ||
271 | ret->nosolve = cfg[3].ival; | ||
272 | |||
273 | return ret; | ||
274 | } | ||
275 | |||
276 | static char *validate_params(const game_params *params, int full) | ||
277 | { | ||
278 | if (params->w < 5) return "Width must be at least five"; | ||
279 | if (params->h < 5) return "Height must be at least five"; | ||
280 | if (params->difficulty < 0 || params->difficulty >= DIFFCOUNT) | ||
281 | return "Unknown difficulty level"; | ||
282 | |||
283 | return NULL; | ||
284 | } | ||
285 | |||
286 | /* ---------------------------------------------------------------------- | ||
287 | * Solver. | ||
288 | */ | ||
289 | |||
290 | int pearl_solve(int w, int h, char *clues, char *result, | ||
291 | int difficulty, int partial) | ||
292 | { | ||
293 | int W = 2*w+1, H = 2*h+1; | ||
294 | short *workspace; | ||
295 | int *dsf, *dsfsize; | ||
296 | int x, y, b, d; | ||
297 | int ret = -1; | ||
298 | |||
299 | /* | ||
300 | * workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature | ||
301 | * of the square (x,y), as a logical OR of bitfields. | ||
302 | * | ||
303 | * workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates | ||
304 | * whether the horizontal edge between (x,y) and (x+1,y) is | ||
305 | * connected (1), disconnected (2) or unknown (3). | ||
306 | * | ||
307 | * workspace[(2*y+1)*W+(2*x)], indicates the same about the | ||
308 | * vertical edge between (x,y) and (x,y+1). | ||
309 | * | ||
310 | * Initially, every square is considered capable of being in | ||
311 | * any of the seven possible states (two straights, four | ||
312 | * corners and empty), except those corresponding to clue | ||
313 | * squares which are more restricted. | ||
314 | * | ||
315 | * Initially, all edges are unknown, except the ones around the | ||
316 | * grid border which are known to be disconnected. | ||
317 | */ | ||
318 | workspace = snewn(W*H, short); | ||
319 | for (x = 0; x < W*H; x++) | ||
320 | workspace[x] = 0; | ||
321 | /* Square states */ | ||
322 | for (y = 0; y < h; y++) | ||
323 | for (x = 0; x < w; x++) | ||
324 | switch (clues[y*w+x]) { | ||
325 | case CORNER: | ||
326 | workspace[(2*y+1)*W+(2*x+1)] = bLU|bLD|bRU|bRD; | ||
327 | break; | ||
328 | case STRAIGHT: | ||
329 | workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD; | ||
330 | break; | ||
331 | default: | ||
332 | workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD|bLU|bLD|bRU|bRD|bBLANK; | ||
333 | break; | ||
334 | } | ||
335 | /* Horizontal edges */ | ||
336 | for (y = 0; y <= h; y++) | ||
337 | for (x = 0; x < w; x++) | ||
338 | workspace[(2*y)*W+(2*x+1)] = (y==0 || y==h ? 2 : 3); | ||
339 | /* Vertical edges */ | ||
340 | for (y = 0; y < h; y++) | ||
341 | for (x = 0; x <= w; x++) | ||
342 | workspace[(2*y+1)*W+(2*x)] = (x==0 || x==w ? 2 : 3); | ||
343 | |||
344 | /* | ||
345 | * We maintain a dsf of connected squares, together with a | ||
346 | * count of the size of each equivalence class. | ||
347 | */ | ||
348 | dsf = snewn(w*h, int); | ||
349 | dsfsize = snewn(w*h, int); | ||
350 | |||
351 | /* | ||
352 | * Now repeatedly try to find something we can do. | ||
353 | */ | ||
354 | while (1) { | ||
355 | int done_something = FALSE; | ||
356 | |||
357 | #ifdef SOLVER_DIAGNOSTICS | ||
358 | for (y = 0; y < H; y++) { | ||
359 | for (x = 0; x < W; x++) | ||
360 | printf("%*x", (x&1) ? 5 : 2, workspace[y*W+x]); | ||
361 | printf("\n"); | ||
362 | } | ||
363 | #endif | ||
364 | |||
365 | /* | ||
366 | * Go through the square state words, and discard any | ||
367 | * square state which is inconsistent with known facts | ||
368 | * about the edges around the square. | ||
369 | */ | ||
370 | for (y = 0; y < h; y++) | ||
371 | for (x = 0; x < w; x++) { | ||
372 | for (b = 0; b < 0xD; b++) | ||
373 | if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) { | ||
374 | /* | ||
375 | * If any edge of this square is known to | ||
376 | * be connected when state b would require | ||
377 | * it disconnected, or vice versa, discard | ||
378 | * the state. | ||
379 | */ | ||
380 | for (d = 1; d <= 8; d += d) { | ||
381 | int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d); | ||
382 | if (workspace[ey*W+ex] == | ||
383 | ((b & d) ? 2 : 1)) { | ||
384 | workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<b); | ||
385 | #ifdef SOLVER_DIAGNOSTICS | ||
386 | printf("edge (%d,%d)-(%d,%d) rules out state" | ||
387 | " %d for square (%d,%d)\n", | ||
388 | ex/2, ey/2, (ex+1)/2, (ey+1)/2, | ||
389 | b, x, y); | ||
390 | #endif | ||
391 | done_something = TRUE; | ||
392 | break; | ||
393 | } | ||
394 | } | ||
395 | } | ||
396 | |||
397 | /* | ||
398 | * Consistency check: each square must have at | ||
399 | * least one state left! | ||
400 | */ | ||
401 | if (!workspace[(2*y+1)*W+(2*x+1)]) { | ||
402 | #ifdef SOLVER_DIAGNOSTICS | ||
403 | printf("edge check at (%d,%d): inconsistency\n", x, y); | ||
404 | #endif | ||
405 | ret = 0; | ||
406 | goto cleanup; | ||
407 | } | ||
408 | } | ||
409 | |||
410 | /* | ||
411 | * Now go through the states array again, and nail down any | ||
412 | * unknown edge if one of its neighbouring squares makes it | ||
413 | * known. | ||
414 | */ | ||
415 | for (y = 0; y < h; y++) | ||
416 | for (x = 0; x < w; x++) { | ||
417 | int edgeor = 0, edgeand = 15; | ||
418 | |||
419 | for (b = 0; b < 0xD; b++) | ||
420 | if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) { | ||
421 | edgeor |= b; | ||
422 | edgeand &= b; | ||
423 | } | ||
424 | |||
425 | /* | ||
426 | * Now any bit clear in edgeor marks a disconnected | ||
427 | * edge, and any bit set in edgeand marks a | ||
428 | * connected edge. | ||
429 | */ | ||
430 | |||
431 | /* First check consistency: neither bit is both! */ | ||
432 | if (edgeand & ~edgeor) { | ||
433 | #ifdef SOLVER_DIAGNOSTICS | ||
434 | printf("square check at (%d,%d): inconsistency\n", x, y); | ||
435 | #endif | ||
436 | ret = 0; | ||
437 | goto cleanup; | ||
438 | } | ||
439 | |||
440 | for (d = 1; d <= 8; d += d) { | ||
441 | int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d); | ||
442 | |||
443 | if (!(edgeor & d) && workspace[ey*W+ex] == 3) { | ||
444 | workspace[ey*W+ex] = 2; | ||
445 | done_something = TRUE; | ||
446 | #ifdef SOLVER_DIAGNOSTICS | ||
447 | printf("possible states of square (%d,%d) force edge" | ||
448 | " (%d,%d)-(%d,%d) to be disconnected\n", | ||
449 | x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2); | ||
450 | #endif | ||
451 | } else if ((edgeand & d) && workspace[ey*W+ex] == 3) { | ||
452 | workspace[ey*W+ex] = 1; | ||
453 | done_something = TRUE; | ||
454 | #ifdef SOLVER_DIAGNOSTICS | ||
455 | printf("possible states of square (%d,%d) force edge" | ||
456 | " (%d,%d)-(%d,%d) to be connected\n", | ||
457 | x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2); | ||
458 | #endif | ||
459 | } | ||
460 | } | ||
461 | } | ||
462 | |||
463 | if (done_something) | ||
464 | continue; | ||
465 | |||
466 | /* | ||
467 | * Now for longer-range clue-based deductions (using the | ||
468 | * rules that a corner clue must connect to two straight | ||
469 | * squares, and a straight clue must connect to at least | ||
470 | * one corner square). | ||
471 | */ | ||
472 | for (y = 0; y < h; y++) | ||
473 | for (x = 0; x < w; x++) | ||
474 | switch (clues[y*w+x]) { | ||
475 | case CORNER: | ||
476 | for (d = 1; d <= 8; d += d) { | ||
477 | int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d); | ||
478 | int fx = ex + DX(d), fy = ey + DY(d); | ||
479 | int type = d | F(d); | ||
480 | |||
481 | if (workspace[ey*W+ex] == 1) { | ||
482 | /* | ||
483 | * If a corner clue is connected on any | ||
484 | * edge, then we can immediately nail | ||
485 | * down the square beyond that edge as | ||
486 | * being a straight in the appropriate | ||
487 | * direction. | ||
488 | */ | ||
489 | if (workspace[fy*W+fx] != (1<<type)) { | ||
490 | workspace[fy*W+fx] = (1<<type); | ||
491 | done_something = TRUE; | ||
492 | #ifdef SOLVER_DIAGNOSTICS | ||
493 | printf("corner clue at (%d,%d) forces square " | ||
494 | "(%d,%d) into state %d\n", x, y, | ||
495 | fx/2, fy/2, type); | ||
496 | #endif | ||
497 | |||
498 | } | ||
499 | } else if (workspace[ey*W+ex] == 3) { | ||
500 | /* | ||
501 | * Conversely, if a corner clue is | ||
502 | * separated by an unknown edge from a | ||
503 | * square which _cannot_ be a straight | ||
504 | * in the appropriate direction, we can | ||
505 | * mark that edge as disconnected. | ||
506 | */ | ||
507 | if (!(workspace[fy*W+fx] & (1<<type))) { | ||
508 | workspace[ey*W+ex] = 2; | ||
509 | done_something = TRUE; | ||
510 | #ifdef SOLVER_DIAGNOSTICS | ||
511 | printf("corner clue at (%d,%d), plus square " | ||
512 | "(%d,%d) not being state %d, " | ||
513 | "disconnects edge (%d,%d)-(%d,%d)\n", | ||
514 | x, y, fx/2, fy/2, type, | ||
515 | ex/2, ey/2, (ex+1)/2, (ey+1)/2); | ||
516 | #endif | ||
517 | |||
518 | } | ||
519 | } | ||
520 | } | ||
521 | |||
522 | break; | ||
523 | case STRAIGHT: | ||
524 | /* | ||
525 | * If a straight clue is between two squares | ||
526 | * neither of which is capable of being a | ||
527 | * corner connected to it, then the straight | ||
528 | * clue cannot point in that direction. | ||
529 | */ | ||
530 | for (d = 1; d <= 2; d += d) { | ||
531 | int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d); | ||
532 | int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d); | ||
533 | int type = d | F(d); | ||
534 | |||
535 | if (!(workspace[(2*y+1)*W+(2*x+1)] & (1<<type))) | ||
536 | continue; | ||
537 | |||
538 | if (!(workspace[fy*W+fx] & ((1<<(F(d)|A(d))) | | ||
539 | (1<<(F(d)|C(d))))) && | ||
540 | !(workspace[gy*W+gx] & ((1<<( d |A(d))) | | ||
541 | (1<<( d |C(d)))))) { | ||
542 | workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<type); | ||
543 | done_something = TRUE; | ||
544 | #ifdef SOLVER_DIAGNOSTICS | ||
545 | printf("straight clue at (%d,%d) cannot corner at " | ||
546 | "(%d,%d) or (%d,%d) so is not state %d\n", | ||
547 | x, y, fx/2, fy/2, gx/2, gy/2, type); | ||
548 | #endif | ||
549 | } | ||
550 | |||
551 | } | ||
552 | |||
553 | /* | ||
554 | * If a straight clue with known direction is | ||
555 | * connected on one side to a known straight, | ||
556 | * then on the other side it must be a corner. | ||
557 | */ | ||
558 | for (d = 1; d <= 8; d += d) { | ||
559 | int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d); | ||
560 | int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d); | ||
561 | int type = d | F(d); | ||
562 | |||
563 | if (workspace[(2*y+1)*W+(2*x+1)] != (1<<type)) | ||
564 | continue; | ||
565 | |||
566 | if (!(workspace[fy*W+fx] &~ (bLR|bUD)) && | ||
567 | (workspace[gy*W+gx] &~ (bLU|bLD|bRU|bRD))) { | ||
568 | workspace[gy*W+gx] &= (bLU|bLD|bRU|bRD); | ||
569 | done_something = TRUE; | ||
570 | #ifdef SOLVER_DIAGNOSTICS | ||
571 | printf("straight clue at (%d,%d) connecting to " | ||
572 | "straight at (%d,%d) makes (%d,%d) a " | ||
573 | "corner\n", x, y, fx/2, fy/2, gx/2, gy/2); | ||
574 | #endif | ||
575 | } | ||
576 | |||
577 | } | ||
578 | break; | ||
579 | } | ||
580 | |||
581 | if (done_something) | ||
582 | continue; | ||
583 | |||
584 | /* | ||
585 | * Now detect shortcut loops. | ||
586 | */ | ||
587 | |||
588 | { | ||
589 | int nonblanks, loopclass; | ||
590 | |||
591 | dsf_init(dsf, w*h); | ||
592 | for (x = 0; x < w*h; x++) | ||
593 | dsfsize[x] = 1; | ||
594 | |||
595 | /* | ||
596 | * First go through the edge entries and update the dsf | ||
597 | * of which squares are connected to which others. We | ||
598 | * also track the number of squares in each equivalence | ||
599 | * class, and count the overall number of | ||
600 | * known-non-blank squares. | ||
601 | * | ||
602 | * In the process of doing this, we must notice if a | ||
603 | * loop has already been formed. If it has, we blank | ||
604 | * out any square which isn't part of that loop | ||
605 | * (failing a consistency check if any such square does | ||
606 | * not have BLANK as one of its remaining options) and | ||
607 | * exit the deduction loop with success. | ||
608 | */ | ||
609 | nonblanks = 0; | ||
610 | loopclass = -1; | ||
611 | for (y = 1; y < H-1; y++) | ||
612 | for (x = 1; x < W-1; x++) | ||
613 | if ((y ^ x) & 1) { | ||
614 | /* | ||
615 | * (x,y) are the workspace coordinates of | ||
616 | * an edge field. Compute the normal-space | ||
617 | * coordinates of the squares it connects. | ||
618 | */ | ||
619 | int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax; | ||
620 | int bx = x/2, by = y/2, bc = by*w+bx; | ||
621 | |||
622 | /* | ||
623 | * If the edge is connected, do the dsf | ||
624 | * thing. | ||
625 | */ | ||
626 | if (workspace[y*W+x] == 1) { | ||
627 | int ae, be; | ||
628 | |||
629 | ae = dsf_canonify(dsf, ac); | ||
630 | be = dsf_canonify(dsf, bc); | ||
631 | |||
632 | if (ae == be) { | ||
633 | /* | ||
634 | * We have a loop! | ||
635 | */ | ||
636 | if (loopclass != -1) { | ||
637 | /* | ||
638 | * In fact, we have two | ||
639 | * separate loops, which is | ||
640 | * doom. | ||
641 | */ | ||
642 | #ifdef SOLVER_DIAGNOSTICS | ||
643 | printf("two loops found in grid!\n"); | ||
644 | #endif | ||
645 | ret = 0; | ||
646 | goto cleanup; | ||
647 | } | ||
648 | loopclass = ae; | ||
649 | } else { | ||
650 | /* | ||
651 | * Merge the two equivalence | ||
652 | * classes. | ||
653 | */ | ||
654 | int size = dsfsize[ae] + dsfsize[be]; | ||
655 | dsf_merge(dsf, ac, bc); | ||
656 | ae = dsf_canonify(dsf, ac); | ||
657 | dsfsize[ae] = size; | ||
658 | } | ||
659 | } | ||
660 | } else if ((y & x) & 1) { | ||
661 | /* | ||
662 | * (x,y) are the workspace coordinates of a | ||
663 | * square field. If the square is | ||
664 | * definitely not blank, count it. | ||
665 | */ | ||
666 | if (!(workspace[y*W+x] & bBLANK)) | ||
667 | nonblanks++; | ||
668 | } | ||
669 | |||
670 | /* | ||
671 | * If we discovered an existing loop above, we must now | ||
672 | * blank every square not part of it, and exit the main | ||
673 | * deduction loop. | ||
674 | */ | ||
675 | if (loopclass != -1) { | ||
676 | #ifdef SOLVER_DIAGNOSTICS | ||
677 | printf("loop found in grid!\n"); | ||
678 | #endif | ||
679 | for (y = 0; y < h; y++) | ||
680 | for (x = 0; x < w; x++) | ||
681 | if (dsf_canonify(dsf, y*w+x) != loopclass) { | ||
682 | if (workspace[(y*2+1)*W+(x*2+1)] & bBLANK) { | ||
683 | workspace[(y*2+1)*W+(x*2+1)] = bBLANK; | ||
684 | } else { | ||
685 | /* | ||
686 | * This square is not part of the | ||
687 | * loop, but is known non-blank. We | ||
688 | * have goofed. | ||
689 | */ | ||
690 | #ifdef SOLVER_DIAGNOSTICS | ||
691 | printf("non-blank square (%d,%d) found outside" | ||
692 | " loop!\n", x, y); | ||
693 | #endif | ||
694 | ret = 0; | ||
695 | goto cleanup; | ||
696 | } | ||
697 | } | ||
698 | /* | ||
699 | * And we're done. | ||
700 | */ | ||
701 | ret = 1; | ||
702 | break; | ||
703 | } | ||
704 | |||
705 | /* Further deductions are considered 'tricky'. */ | ||
706 | if (difficulty == DIFF_EASY) goto done_deductions; | ||
707 | |||
708 | /* | ||
709 | * Now go through the workspace again and mark any edge | ||
710 | * which would cause a shortcut loop (i.e. would | ||
711 | * connect together two squares in the same equivalence | ||
712 | * class, and that equivalence class does not contain | ||
713 | * _all_ the known-non-blank squares currently in the | ||
714 | * grid) as disconnected. Also, mark any _square state_ | ||
715 | * which would cause a shortcut loop as disconnected. | ||
716 | */ | ||
717 | for (y = 1; y < H-1; y++) | ||
718 | for (x = 1; x < W-1; x++) | ||
719 | if ((y ^ x) & 1) { | ||
720 | /* | ||
721 | * (x,y) are the workspace coordinates of | ||
722 | * an edge field. Compute the normal-space | ||
723 | * coordinates of the squares it connects. | ||
724 | */ | ||
725 | int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax; | ||
726 | int bx = x/2, by = y/2, bc = by*w+bx; | ||
727 | |||
728 | /* | ||
729 | * If the edge is currently unknown, and | ||
730 | * sits between two squares in the same | ||
731 | * equivalence class, and the size of that | ||
732 | * class is less than nonblanks, then | ||
733 | * connecting this edge would be a shortcut | ||
734 | * loop and so we must not do so. | ||
735 | */ | ||
736 | if (workspace[y*W+x] == 3) { | ||
737 | int ae, be; | ||
738 | |||
739 | ae = dsf_canonify(dsf, ac); | ||
740 | be = dsf_canonify(dsf, bc); | ||
741 | |||
742 | if (ae == be) { | ||
743 | /* | ||
744 | * We have a loop. Is it a shortcut? | ||
745 | */ | ||
746 | if (dsfsize[ae] < nonblanks) { | ||
747 | /* | ||
748 | * Yes! Mark this edge disconnected. | ||
749 | */ | ||
750 | workspace[y*W+x] = 2; | ||
751 | done_something = TRUE; | ||
752 | #ifdef SOLVER_DIAGNOSTICS | ||
753 | printf("edge (%d,%d)-(%d,%d) would create" | ||
754 | " a shortcut loop, hence must be" | ||
755 | " disconnected\n", x/2, y/2, | ||
756 | (x+1)/2, (y+1)/2); | ||
757 | #endif | ||
758 | } | ||
759 | } | ||
760 | } | ||
761 | } else if ((y & x) & 1) { | ||
762 | /* | ||
763 | * (x,y) are the workspace coordinates of a | ||
764 | * square field. Go through its possible | ||
765 | * (non-blank) states and see if any gives | ||
766 | * rise to a shortcut loop. | ||
767 | * | ||
768 | * This is slightly fiddly, because we have | ||
769 | * to check whether this square is already | ||
770 | * part of the same equivalence class as | ||
771 | * the things it's joining. | ||
772 | */ | ||
773 | int ae = dsf_canonify(dsf, (y/2)*w+(x/2)); | ||
774 | |||
775 | for (b = 2; b < 0xD; b++) | ||
776 | if (workspace[y*W+x] & (1<<b)) { | ||
777 | /* | ||
778 | * Find the equivalence classes of | ||
779 | * the two squares this one would | ||
780 | * connect if it were in this | ||
781 | * state. | ||
782 | */ | ||
783 | int e = -1; | ||
784 | |||
785 | for (d = 1; d <= 8; d += d) if (b & d) { | ||
786 | int xx = x/2 + DX(d), yy = y/2 + DY(d); | ||
787 | int ee = dsf_canonify(dsf, yy*w+xx); | ||
788 | |||
789 | if (e == -1) | ||
790 | ee = e; | ||
791 | else if (e != ee) | ||
792 | e = -2; | ||
793 | } | ||
794 | |||
795 | if (e >= 0) { | ||
796 | /* | ||
797 | * This square state would form | ||
798 | * a loop on equivalence class | ||
799 | * e. Measure the size of that | ||
800 | * loop, and see if it's a | ||
801 | * shortcut. | ||
802 | */ | ||
803 | int loopsize = dsfsize[e]; | ||
804 | if (e != ae) | ||
805 | loopsize++;/* add the square itself */ | ||
806 | if (loopsize < nonblanks) { | ||
807 | /* | ||
808 | * It is! Mark this square | ||
809 | * state invalid. | ||
810 | */ | ||
811 | workspace[y*W+x] &= ~(1<<b); | ||
812 | done_something = TRUE; | ||
813 | #ifdef SOLVER_DIAGNOSTICS | ||
814 | printf("square (%d,%d) would create a " | ||
815 | "shortcut loop in state %d, " | ||
816 | "hence cannot be\n", | ||
817 | x/2, y/2, b); | ||
818 | #endif | ||
819 | } | ||
820 | } | ||
821 | } | ||
822 | } | ||
823 | } | ||
824 | |||
825 | done_deductions: | ||
826 | |||
827 | if (done_something) | ||
828 | continue; | ||
829 | |||
830 | /* | ||
831 | * If we reach here, there is nothing left we can do. | ||
832 | * Return 2 for ambiguous puzzle. | ||
833 | */ | ||
834 | ret = 2; | ||
835 | break; | ||
836 | } | ||
837 | |||
838 | cleanup: | ||
839 | |||
840 | /* | ||
841 | * If ret = 1 then we've successfully achieved a solution. This | ||
842 | * means that we expect every square to be nailed down to | ||
843 | * exactly one possibility. If this is the case, or if the caller | ||
844 | * asked for a partial solution anyway, transcribe those | ||
845 | * possibilities into the result array. | ||
846 | */ | ||
847 | if (ret == 1 || partial) { | ||
848 | for (y = 0; y < h; y++) { | ||
849 | for (x = 0; x < w; x++) { | ||
850 | for (b = 0; b < 0xD; b++) | ||
851 | if (workspace[(2*y+1)*W+(2*x+1)] == (1<<b)) { | ||
852 | result[y*w+x] = b; | ||
853 | break; | ||
854 | } | ||
855 | if (ret == 1) assert(b < 0xD); /* we should have had a break by now */ | ||
856 | } | ||
857 | } | ||
858 | } | ||
859 | |||
860 | sfree(dsfsize); | ||
861 | sfree(dsf); | ||
862 | sfree(workspace); | ||
863 | assert(ret >= 0); | ||
864 | return ret; | ||
865 | } | ||
866 | |||
867 | /* ---------------------------------------------------------------------- | ||
868 | * Loop generator. | ||
869 | */ | ||
870 | |||
871 | /* | ||
872 | * We use the loop generator code from loopy, hard-coding to a square | ||
873 | * grid of the appropriate size. Knowing the grid layout and the tile | ||
874 | * size we can shrink that to our small grid and then make our line | ||
875 | * layout from the face colour info. | ||
876 | * | ||
877 | * We provide a bias function to the loop generator which tries to | ||
878 | * bias in favour of loops with more scope for Pearl black clues. This | ||
879 | * seems to improve the success rate of the puzzle generator, in that | ||
880 | * such loops have a better chance of being soluble with all valid | ||
881 | * clues put in. | ||
882 | */ | ||
883 | |||
884 | struct pearl_loopgen_bias_ctx { | ||
885 | /* | ||
886 | * Our bias function counts the number of 'black clue' corners | ||
887 | * (i.e. corners adjacent to two straights) in both the | ||
888 | * BLACK/nonBLACK and WHITE/nonWHITE boundaries. In order to do | ||
889 | * this, we must: | ||
890 | * | ||
891 | * - track the edges that are part of each of those loops | ||
892 | * - track the types of vertex in each loop (corner, straight, | ||
893 | * none) | ||
894 | * - track the current black-clue status of each vertex in each | ||
895 | * loop. | ||
896 | * | ||
897 | * Each of these chunks of data is updated incrementally from the | ||
898 | * previous one, to avoid slowdown due to the bias function | ||
899 | * rescanning the whole grid every time it's called. | ||
900 | * | ||
901 | * So we need a lot of separate arrays, plus a tdq for each one, | ||
902 | * and we must repeat it all twice for the BLACK and WHITE | ||
903 | * boundaries. | ||
904 | */ | ||
905 | struct pearl_loopgen_bias_ctx_boundary { | ||
906 | int colour; /* FACE_WHITE or FACE_BLACK */ | ||
907 | |||
908 | char *edges; /* is each edge part of the loop? */ | ||
909 | tdq *edges_todo; | ||
910 | |||
911 | char *vertextypes; /* bits 0-3 == outgoing edge bitmap; | ||
912 | * bit 4 set iff corner clue. | ||
913 | * Hence, 0 means non-vertex; | ||
914 | * nonzero but bit 4 zero = straight. */ | ||
915 | int *neighbour[2]; /* indices of neighbour vertices in loop */ | ||
916 | tdq *vertextypes_todo; | ||
917 | |||
918 | char *blackclues; /* is each vertex a black clue site? */ | ||
919 | tdq *blackclues_todo; | ||
920 | } boundaries[2]; /* boundaries[0]=WHITE, [1]=BLACK */ | ||
921 | |||
922 | char *faces; /* remember last-seen colour of each face */ | ||
923 | tdq *faces_todo; | ||
924 | |||
925 | int score; | ||
926 | |||
927 | grid *g; | ||
928 | }; | ||
929 | int pearl_loopgen_bias(void *vctx, char *board, int face) | ||
930 | { | ||
931 | struct pearl_loopgen_bias_ctx *ctx = (struct pearl_loopgen_bias_ctx *)vctx; | ||
932 | grid *g = ctx->g; | ||
933 | int oldface, newface; | ||
934 | int i, j, k; | ||
935 | |||
936 | tdq_add(ctx->faces_todo, face); | ||
937 | while ((j = tdq_remove(ctx->faces_todo)) >= 0) { | ||
938 | oldface = ctx->faces[j]; | ||
939 | ctx->faces[j] = newface = board[j]; | ||
940 | for (i = 0; i < 2; i++) { | ||
941 | struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i]; | ||
942 | int c = b->colour; | ||
943 | |||
944 | /* | ||
945 | * If the face has changed either from or to colour c, we need | ||
946 | * to reprocess the edges for this boundary. | ||
947 | */ | ||
948 | if (oldface == c || newface == c) { | ||
949 | grid_face *f = &g->faces[face]; | ||
950 | for (k = 0; k < f->order; k++) | ||
951 | tdq_add(b->edges_todo, f->edges[k] - g->edges); | ||
952 | } | ||
953 | } | ||
954 | } | ||
955 | |||
956 | for (i = 0; i < 2; i++) { | ||
957 | struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i]; | ||
958 | int c = b->colour; | ||
959 | |||
960 | /* | ||
961 | * Go through the to-do list of edges. For each edge, decide | ||
962 | * anew whether it's part of this boundary or not. Any edge | ||
963 | * that changes state has to have both its endpoints put on | ||
964 | * the vertextypes_todo list. | ||
965 | */ | ||
966 | while ((j = tdq_remove(b->edges_todo)) >= 0) { | ||
967 | grid_edge *e = &g->edges[j]; | ||
968 | int fc1 = e->face1 ? board[e->face1 - g->faces] : FACE_BLACK; | ||
969 | int fc2 = e->face2 ? board[e->face2 - g->faces] : FACE_BLACK; | ||
970 | int oldedge = b->edges[j]; | ||
971 | int newedge = (fc1==c) ^ (fc2==c); | ||
972 | if (oldedge != newedge) { | ||
973 | b->edges[j] = newedge; | ||
974 | tdq_add(b->vertextypes_todo, e->dot1 - g->dots); | ||
975 | tdq_add(b->vertextypes_todo, e->dot2 - g->dots); | ||
976 | } | ||
977 | } | ||
978 | |||
979 | /* | ||
980 | * Go through the to-do list of vertices whose types need | ||
981 | * refreshing. For each one, decide whether it's a corner, a | ||
982 | * straight, or a vertex not in the loop, and in the former | ||
983 | * two cases also work out the indices of its neighbour | ||
984 | * vertices along the loop. Any vertex that changes state must | ||
985 | * be put back on the to-do list for deciding if it's a black | ||
986 | * clue site, and so must its two new neighbours _and_ its two | ||
987 | * old neighbours. | ||
988 | */ | ||
989 | while ((j = tdq_remove(b->vertextypes_todo)) >= 0) { | ||
990 | grid_dot *d = &g->dots[j]; | ||
991 | int neighbours[2], type = 0, n = 0; | ||
992 | |||
993 | for (k = 0; k < d->order; k++) { | ||
994 | grid_edge *e = d->edges[k]; | ||
995 | grid_dot *d2 = (e->dot1 == d ? e->dot2 : e->dot1); | ||
996 | /* dir == 0,1,2,3 for an edge going L,U,R,D */ | ||
997 | int dir = (d->y == d2->y) + 2*(d->x+d->y > d2->x+d2->y); | ||
998 | int ei = e - g->edges; | ||
999 | if (b->edges[ei]) { | ||
1000 | type |= 1 << dir; | ||
1001 | neighbours[n] = d2 - g->dots; | ||
1002 | n++; | ||
1003 | } | ||
1004 | } | ||
1005 | |||
1006 | /* | ||
1007 | * Decide if it's a corner, and set the corner flag if so. | ||
1008 | */ | ||
1009 | if (type != 0 && type != 0x5 && type != 0xA) | ||
1010 | type |= 0x10; | ||
1011 | |||
1012 | if (type != b->vertextypes[j]) { | ||
1013 | /* | ||
1014 | * Recompute old neighbours, if any. | ||
1015 | */ | ||
1016 | if (b->vertextypes[j]) { | ||
1017 | tdq_add(b->blackclues_todo, b->neighbour[0][j]); | ||
1018 | tdq_add(b->blackclues_todo, b->neighbour[1][j]); | ||
1019 | } | ||
1020 | /* | ||
1021 | * Recompute this vertex. | ||
1022 | */ | ||
1023 | tdq_add(b->blackclues_todo, j); | ||
1024 | b->vertextypes[j] = type; | ||
1025 | /* | ||
1026 | * Recompute new neighbours, if any. | ||
1027 | */ | ||
1028 | if (b->vertextypes[j]) { | ||
1029 | b->neighbour[0][j] = neighbours[0]; | ||
1030 | b->neighbour[1][j] = neighbours[1]; | ||
1031 | tdq_add(b->blackclues_todo, b->neighbour[0][j]); | ||
1032 | tdq_add(b->blackclues_todo, b->neighbour[1][j]); | ||
1033 | } | ||
1034 | } | ||
1035 | } | ||
1036 | |||
1037 | /* | ||
1038 | * Go through the list of vertices which we must check to see | ||
1039 | * if they're black clue sites. Each one is a black clue site | ||
1040 | * iff it is a corner and its loop neighbours are non-corners. | ||
1041 | * Adjust the running total of black clues we've counted. | ||
1042 | */ | ||
1043 | while ((j = tdq_remove(b->blackclues_todo)) >= 0) { | ||
1044 | ctx->score -= b->blackclues[j]; | ||
1045 | b->blackclues[j] = ((b->vertextypes[j] & 0x10) && | ||
1046 | !((b->vertextypes[b->neighbour[0][j]] | | ||
1047 | b->vertextypes[b->neighbour[1][j]]) | ||
1048 | & 0x10)); | ||
1049 | ctx->score += b->blackclues[j]; | ||
1050 | } | ||
1051 | } | ||
1052 | |||
1053 | return ctx->score; | ||
1054 | } | ||
1055 | |||
1056 | void pearl_loopgen(int w, int h, char *lines, random_state *rs) | ||
1057 | { | ||
1058 | grid *g = grid_new(GRID_SQUARE, w-1, h-1, NULL); | ||
1059 | char *board = snewn(g->num_faces, char); | ||
1060 | int i, s = g->tilesize; | ||
1061 | struct pearl_loopgen_bias_ctx biasctx; | ||
1062 | |||
1063 | memset(lines, 0, w*h); | ||
1064 | |||
1065 | /* | ||
1066 | * Initialise the context for the bias function. Initially we fill | ||
1067 | * all the to-do lists, so that the first call will scan | ||
1068 | * everything; thereafter the lists stay empty so we make | ||
1069 | * incremental changes. | ||
1070 | */ | ||
1071 | biasctx.g = g; | ||
1072 | biasctx.faces = snewn(g->num_faces, char); | ||
1073 | biasctx.faces_todo = tdq_new(g->num_faces); | ||
1074 | tdq_fill(biasctx.faces_todo); | ||
1075 | biasctx.score = 0; | ||
1076 | memset(biasctx.faces, FACE_GREY, g->num_faces); | ||
1077 | for (i = 0; i < 2; i++) { | ||
1078 | biasctx.boundaries[i].edges = snewn(g->num_edges, char); | ||
1079 | memset(biasctx.boundaries[i].edges, 0, g->num_edges); | ||
1080 | biasctx.boundaries[i].edges_todo = tdq_new(g->num_edges); | ||
1081 | tdq_fill(biasctx.boundaries[i].edges_todo); | ||
1082 | biasctx.boundaries[i].vertextypes = snewn(g->num_dots, char); | ||
1083 | memset(biasctx.boundaries[i].vertextypes, 0, g->num_dots); | ||
1084 | biasctx.boundaries[i].neighbour[0] = snewn(g->num_dots, int); | ||
1085 | biasctx.boundaries[i].neighbour[1] = snewn(g->num_dots, int); | ||
1086 | biasctx.boundaries[i].vertextypes_todo = tdq_new(g->num_dots); | ||
1087 | tdq_fill(biasctx.boundaries[i].vertextypes_todo); | ||
1088 | biasctx.boundaries[i].blackclues = snewn(g->num_dots, char); | ||
1089 | memset(biasctx.boundaries[i].blackclues, 0, g->num_dots); | ||
1090 | biasctx.boundaries[i].blackclues_todo = tdq_new(g->num_dots); | ||
1091 | tdq_fill(biasctx.boundaries[i].blackclues_todo); | ||
1092 | } | ||
1093 | biasctx.boundaries[0].colour = FACE_WHITE; | ||
1094 | biasctx.boundaries[1].colour = FACE_BLACK; | ||
1095 | generate_loop(g, board, rs, pearl_loopgen_bias, &biasctx); | ||
1096 | sfree(biasctx.faces); | ||
1097 | tdq_free(biasctx.faces_todo); | ||
1098 | for (i = 0; i < 2; i++) { | ||
1099 | sfree(biasctx.boundaries[i].edges); | ||
1100 | tdq_free(biasctx.boundaries[i].edges_todo); | ||
1101 | sfree(biasctx.boundaries[i].vertextypes); | ||
1102 | sfree(biasctx.boundaries[i].neighbour[0]); | ||
1103 | sfree(biasctx.boundaries[i].neighbour[1]); | ||
1104 | tdq_free(biasctx.boundaries[i].vertextypes_todo); | ||
1105 | sfree(biasctx.boundaries[i].blackclues); | ||
1106 | tdq_free(biasctx.boundaries[i].blackclues_todo); | ||
1107 | } | ||
1108 | |||
1109 | for (i = 0; i < g->num_edges; i++) { | ||
1110 | grid_edge *e = g->edges + i; | ||
1111 | enum face_colour c1 = FACE_COLOUR(e->face1); | ||
1112 | enum face_colour c2 = FACE_COLOUR(e->face2); | ||
1113 | assert(c1 != FACE_GREY); | ||
1114 | assert(c2 != FACE_GREY); | ||
1115 | if (c1 != c2) { | ||
1116 | /* This grid edge is on the loop: lay line along it */ | ||
1117 | int x1 = e->dot1->x/s, y1 = e->dot1->y/s; | ||
1118 | int x2 = e->dot2->x/s, y2 = e->dot2->y/s; | ||
1119 | |||
1120 | /* (x1,y1) and (x2,y2) are now in our grid coords (0-w,0-h). */ | ||
1121 | if (x1 == x2) { | ||
1122 | if (y1 > y2) SWAP(y1,y2); | ||
1123 | |||
1124 | assert(y1+1 == y2); | ||
1125 | lines[y1*w+x1] |= D; | ||
1126 | lines[y2*w+x1] |= U; | ||
1127 | } else if (y1 == y2) { | ||
1128 | if (x1 > x2) SWAP(x1,x2); | ||
1129 | |||
1130 | assert(x1+1 == x2); | ||
1131 | lines[y1*w+x1] |= R; | ||
1132 | lines[y1*w+x2] |= L; | ||
1133 | } else | ||
1134 | assert(!"grid with diagonal coords?!"); | ||
1135 | } | ||
1136 | } | ||
1137 | |||
1138 | grid_free(g); | ||
1139 | sfree(board); | ||
1140 | |||
1141 | #if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS | ||
1142 | printf("as returned:\n"); | ||
1143 | for (y = 0; y < h; y++) { | ||
1144 | for (x = 0; x < w; x++) { | ||
1145 | int type = lines[y*w+x]; | ||
1146 | char s[5], *p = s; | ||
1147 | if (type & L) *p++ = 'L'; | ||
1148 | if (type & R) *p++ = 'R'; | ||
1149 | if (type & U) *p++ = 'U'; | ||
1150 | if (type & D) *p++ = 'D'; | ||
1151 | *p = '\0'; | ||
1152 | printf("%3s", s); | ||
1153 | } | ||
1154 | printf("\n"); | ||
1155 | } | ||
1156 | printf("\n"); | ||
1157 | #endif | ||
1158 | } | ||
1159 | |||
1160 | static int new_clues(const game_params *params, random_state *rs, | ||
1161 | char *clues, char *grid) | ||
1162 | { | ||
1163 | int w = params->w, h = params->h, diff = params->difficulty; | ||
1164 | int ngen = 0, x, y, d, ret, i; | ||
1165 | |||
1166 | |||
1167 | /* | ||
1168 | * Difficulty exception: 5x5 Tricky is not generable (the | ||
1169 | * generator will spin forever trying) and so we fudge it to Easy. | ||
1170 | */ | ||
1171 | if (w == 5 && h == 5 && diff > DIFF_EASY) | ||
1172 | diff = DIFF_EASY; | ||
1173 | |||
1174 | while (1) { | ||
1175 | ngen++; | ||
1176 | pearl_loopgen(w, h, grid, rs); | ||
1177 | |||
1178 | #ifdef GENERATION_DIAGNOSTICS | ||
1179 | printf("grid array:\n"); | ||
1180 | for (y = 0; y < h; y++) { | ||
1181 | for (x = 0; x < w; x++) { | ||
1182 | int type = grid[y*w+x]; | ||
1183 | char s[5], *p = s; | ||
1184 | if (type & L) *p++ = 'L'; | ||
1185 | if (type & R) *p++ = 'R'; | ||
1186 | if (type & U) *p++ = 'U'; | ||
1187 | if (type & D) *p++ = 'D'; | ||
1188 | *p = '\0'; | ||
1189 | printf("%2s ", s); | ||
1190 | } | ||
1191 | printf("\n"); | ||
1192 | } | ||
1193 | printf("\n"); | ||
1194 | #endif | ||
1195 | |||
1196 | /* | ||
1197 | * Set up the maximal clue array. | ||
1198 | */ | ||
1199 | for (y = 0; y < h; y++) | ||
1200 | for (x = 0; x < w; x++) { | ||
1201 | int type = grid[y*w+x]; | ||
1202 | |||
1203 | clues[y*w+x] = NOCLUE; | ||
1204 | |||
1205 | if ((bLR|bUD) & (1 << type)) { | ||
1206 | /* | ||
1207 | * This is a straight; see if it's a viable | ||
1208 | * candidate for a straight clue. It qualifies if | ||
1209 | * at least one of the squares it connects to is a | ||
1210 | * corner. | ||
1211 | */ | ||
1212 | for (d = 1; d <= 8; d += d) if (type & d) { | ||
1213 | int xx = x + DX(d), yy = y + DY(d); | ||
1214 | assert(xx >= 0 && xx < w && yy >= 0 && yy < h); | ||
1215 | if ((bLU|bLD|bRU|bRD) & (1 << grid[yy*w+xx])) | ||
1216 | break; | ||
1217 | } | ||
1218 | if (d <= 8) /* we found one */ | ||
1219 | clues[y*w+x] = STRAIGHT; | ||
1220 | } else if ((bLU|bLD|bRU|bRD) & (1 << type)) { | ||
1221 | /* | ||
1222 | * This is a corner; see if it's a viable candidate | ||
1223 | * for a corner clue. It qualifies if all the | ||
1224 | * squares it connects to are straights. | ||
1225 | */ | ||
1226 | for (d = 1; d <= 8; d += d) if (type & d) { | ||
1227 | int xx = x + DX(d), yy = y + DY(d); | ||
1228 | assert(xx >= 0 && xx < w && yy >= 0 && yy < h); | ||
1229 | if (!((bLR|bUD) & (1 << grid[yy*w+xx]))) | ||
1230 | break; | ||
1231 | } | ||
1232 | if (d > 8) /* we didn't find a counterexample */ | ||
1233 | clues[y*w+x] = CORNER; | ||
1234 | } | ||
1235 | } | ||
1236 | |||
1237 | #ifdef GENERATION_DIAGNOSTICS | ||
1238 | printf("clue array:\n"); | ||
1239 | for (y = 0; y < h; y++) { | ||
1240 | for (x = 0; x < w; x++) { | ||
1241 | printf("%c", " *O"[(unsigned char)clues[y*w+x]]); | ||
1242 | } | ||
1243 | printf("\n"); | ||
1244 | } | ||
1245 | printf("\n"); | ||
1246 | #endif | ||
1247 | |||
1248 | if (!params->nosolve) { | ||
1249 | int *cluespace, *straights, *corners; | ||
1250 | int nstraights, ncorners, nstraightpos, ncornerpos; | ||
1251 | |||
1252 | /* | ||
1253 | * See if we can solve the puzzle just like this. | ||
1254 | */ | ||
1255 | ret = pearl_solve(w, h, clues, grid, diff, FALSE); | ||
1256 | assert(ret > 0); /* shouldn't be inconsistent! */ | ||
1257 | if (ret != 1) | ||
1258 | continue; /* go round and try again */ | ||
1259 | |||
1260 | /* | ||
1261 | * Check this puzzle isn't too easy. | ||
1262 | */ | ||
1263 | if (diff > DIFF_EASY) { | ||
1264 | ret = pearl_solve(w, h, clues, grid, diff-1, FALSE); | ||
1265 | assert(ret > 0); | ||
1266 | if (ret == 1) | ||
1267 | continue; /* too easy: try again */ | ||
1268 | } | ||
1269 | |||
1270 | /* | ||
1271 | * Now shuffle the grid points and gradually remove the | ||
1272 | * clues to find a minimal set which still leaves the | ||
1273 | * puzzle soluble. | ||
1274 | * | ||
1275 | * We preferentially attempt to remove whichever type of | ||
1276 | * clue is currently most numerous, to combat a general | ||
1277 | * tendency of plain random generation to bias in favour | ||
1278 | * of many white clues and few black. | ||
1279 | * | ||
1280 | * 'nstraights' and 'ncorners' count the number of clues | ||
1281 | * of each type currently remaining in the grid; | ||
1282 | * 'nstraightpos' and 'ncornerpos' count the clues of each | ||
1283 | * type we have left to try to remove. (Clues which we | ||
1284 | * have tried and failed to remove are counted by the | ||
1285 | * former but not the latter.) | ||
1286 | */ | ||
1287 | cluespace = snewn(w*h, int); | ||
1288 | straights = cluespace; | ||
1289 | nstraightpos = 0; | ||
1290 | for (i = 0; i < w*h; i++) | ||
1291 | if (clues[i] == STRAIGHT) | ||
1292 | straights[nstraightpos++] = i; | ||
1293 | corners = straights + nstraightpos; | ||
1294 | ncornerpos = 0; | ||
1295 | for (i = 0; i < w*h; i++) | ||
1296 | if (clues[i] == STRAIGHT) | ||
1297 | corners[ncornerpos++] = i; | ||
1298 | nstraights = nstraightpos; | ||
1299 | ncorners = ncornerpos; | ||
1300 | |||
1301 | shuffle(straights, nstraightpos, sizeof(*straights), rs); | ||
1302 | shuffle(corners, ncornerpos, sizeof(*corners), rs); | ||
1303 | while (nstraightpos > 0 || ncornerpos > 0) { | ||
1304 | int cluepos; | ||
1305 | int clue; | ||
1306 | |||
1307 | /* | ||
1308 | * Decide which clue to try to remove next. If both | ||
1309 | * types are available, we choose whichever kind is | ||
1310 | * currently overrepresented; otherwise we take | ||
1311 | * whatever we can get. | ||
1312 | */ | ||
1313 | if (nstraightpos > 0 && ncornerpos > 0) { | ||
1314 | if (nstraights >= ncorners) | ||
1315 | cluepos = straights[--nstraightpos]; | ||
1316 | else | ||
1317 | cluepos = straights[--ncornerpos]; | ||
1318 | } else { | ||
1319 | if (nstraightpos > 0) | ||
1320 | cluepos = straights[--nstraightpos]; | ||
1321 | else | ||
1322 | cluepos = straights[--ncornerpos]; | ||
1323 | } | ||
1324 | |||
1325 | y = cluepos / w; | ||
1326 | x = cluepos % w; | ||
1327 | |||
1328 | clue = clues[y*w+x]; | ||
1329 | clues[y*w+x] = 0; /* try removing this clue */ | ||
1330 | |||
1331 | ret = pearl_solve(w, h, clues, grid, diff, FALSE); | ||
1332 | assert(ret > 0); | ||
1333 | if (ret != 1) | ||
1334 | clues[y*w+x] = clue; /* oops, put it back again */ | ||
1335 | } | ||
1336 | sfree(cluespace); | ||
1337 | } | ||
1338 | |||
1339 | #ifdef FINISHED_PUZZLE | ||
1340 | printf("clue array:\n"); | ||
1341 | for (y = 0; y < h; y++) { | ||
1342 | for (x = 0; x < w; x++) { | ||
1343 | printf("%c", " *O"[(unsigned char)clues[y*w+x]]); | ||
1344 | } | ||
1345 | printf("\n"); | ||
1346 | } | ||
1347 | printf("\n"); | ||
1348 | #endif | ||
1349 | |||
1350 | break; /* got it */ | ||
1351 | } | ||
1352 | |||
1353 | debug(("%d %dx%d loops before finished puzzle.\n", ngen, w, h)); | ||
1354 | |||
1355 | return ngen; | ||
1356 | } | ||
1357 | |||
1358 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
1359 | char **aux, int interactive) | ||
1360 | { | ||
1361 | char *grid, *clues; | ||
1362 | char *desc; | ||
1363 | int w = params->w, h = params->h, i, j; | ||
1364 | |||
1365 | grid = snewn(w*h, char); | ||
1366 | clues = snewn(w*h, char); | ||
1367 | |||
1368 | new_clues(params, rs, clues, grid); | ||
1369 | |||
1370 | desc = snewn(w * h + 1, char); | ||
1371 | for (i = j = 0; i < w*h; i++) { | ||
1372 | if (clues[i] == NOCLUE && j > 0 && | ||
1373 | desc[j-1] >= 'a' && desc[j-1] < 'z') | ||
1374 | desc[j-1]++; | ||
1375 | else if (clues[i] == NOCLUE) | ||
1376 | desc[j++] = 'a'; | ||
1377 | else if (clues[i] == CORNER) | ||
1378 | desc[j++] = 'B'; | ||
1379 | else if (clues[i] == STRAIGHT) | ||
1380 | desc[j++] = 'W'; | ||
1381 | } | ||
1382 | desc[j] = '\0'; | ||
1383 | |||
1384 | *aux = snewn(w*h+1, char); | ||
1385 | for (i = 0; i < w*h; i++) | ||
1386 | (*aux)[i] = (grid[i] < 10) ? (grid[i] + '0') : (grid[i] + 'A' - 10); | ||
1387 | (*aux)[w*h] = '\0'; | ||
1388 | |||
1389 | sfree(grid); | ||
1390 | sfree(clues); | ||
1391 | |||
1392 | return desc; | ||
1393 | } | ||
1394 | |||
1395 | static char *validate_desc(const game_params *params, const char *desc) | ||
1396 | { | ||
1397 | int i, sizesofar; | ||
1398 | const int totalsize = params->w * params->h; | ||
1399 | |||
1400 | sizesofar = 0; | ||
1401 | for (i = 0; desc[i]; i++) { | ||
1402 | if (desc[i] >= 'a' && desc[i] <= 'z') | ||
1403 | sizesofar += desc[i] - 'a' + 1; | ||
1404 | else if (desc[i] == 'B' || desc[i] == 'W') | ||
1405 | sizesofar++; | ||
1406 | else | ||
1407 | return "unrecognised character in string"; | ||
1408 | } | ||
1409 | |||
1410 | if (sizesofar > totalsize) | ||
1411 | return "string too long"; | ||
1412 | else if (sizesofar < totalsize) | ||
1413 | return "string too short"; | ||
1414 | |||
1415 | return NULL; | ||
1416 | } | ||
1417 | |||
1418 | static game_state *new_game(midend *me, const game_params *params, | ||
1419 | const char *desc) | ||
1420 | { | ||
1421 | game_state *state = snew(game_state); | ||
1422 | int i, j, sz = params->w*params->h; | ||
1423 | |||
1424 | state->completed = state->used_solve = FALSE; | ||
1425 | state->shared = snew(struct shared_state); | ||
1426 | |||
1427 | state->shared->w = params->w; | ||
1428 | state->shared->h = params->h; | ||
1429 | state->shared->sz = sz; | ||
1430 | state->shared->refcnt = 1; | ||
1431 | state->shared->clues = snewn(sz, char); | ||
1432 | for (i = j = 0; desc[i]; i++) { | ||
1433 | assert(j < sz); | ||
1434 | if (desc[i] >= 'a' && desc[i] <= 'z') { | ||
1435 | int n = desc[i] - 'a' + 1; | ||
1436 | assert(j + n <= sz); | ||
1437 | while (n-- > 0) | ||
1438 | state->shared->clues[j++] = NOCLUE; | ||
1439 | } else if (desc[i] == 'B') { | ||
1440 | state->shared->clues[j++] = CORNER; | ||
1441 | } else if (desc[i] == 'W') { | ||
1442 | state->shared->clues[j++] = STRAIGHT; | ||
1443 | } | ||
1444 | } | ||
1445 | |||
1446 | state->lines = snewn(sz, char); | ||
1447 | state->errors = snewn(sz, char); | ||
1448 | state->marks = snewn(sz, char); | ||
1449 | for (i = 0; i < sz; i++) | ||
1450 | state->lines[i] = state->errors[i] = state->marks[i] = BLANK; | ||
1451 | |||
1452 | return state; | ||
1453 | } | ||
1454 | |||
1455 | static game_state *dup_game(const game_state *state) | ||
1456 | { | ||
1457 | game_state *ret = snew(game_state); | ||
1458 | int sz = state->shared->sz, i; | ||
1459 | |||
1460 | ret->shared = state->shared; | ||
1461 | ret->completed = state->completed; | ||
1462 | ret->used_solve = state->used_solve; | ||
1463 | ++ret->shared->refcnt; | ||
1464 | |||
1465 | ret->lines = snewn(sz, char); | ||
1466 | ret->errors = snewn(sz, char); | ||
1467 | ret->marks = snewn(sz, char); | ||
1468 | for (i = 0; i < sz; i++) { | ||
1469 | ret->lines[i] = state->lines[i]; | ||
1470 | ret->errors[i] = state->errors[i]; | ||
1471 | ret->marks[i] = state->marks[i]; | ||
1472 | } | ||
1473 | |||
1474 | return ret; | ||
1475 | } | ||
1476 | |||
1477 | static void free_game(game_state *state) | ||
1478 | { | ||
1479 | assert(state); | ||
1480 | if (--state->shared->refcnt == 0) { | ||
1481 | sfree(state->shared->clues); | ||
1482 | sfree(state->shared); | ||
1483 | } | ||
1484 | sfree(state->lines); | ||
1485 | sfree(state->errors); | ||
1486 | sfree(state->marks); | ||
1487 | sfree(state); | ||
1488 | } | ||
1489 | |||
1490 | static char nbits[16] = { 0, 1, 1, 2, | ||
1491 | 1, 2, 2, 3, | ||
1492 | 1, 2, 2, 3, | ||
1493 | 2, 3, 3, 4 }; | ||
1494 | #define NBITS(l) ( ((l) < 0 || (l) > 15) ? 4 : nbits[l] ) | ||
1495 | |||
1496 | #define ERROR_CLUE 16 | ||
1497 | |||
1498 | static void dsf_update_completion(game_state *state, int ax, int ay, char dir, | ||
1499 | int *dsf) | ||
1500 | { | ||
1501 | int w = state->shared->w /*, h = state->shared->h */; | ||
1502 | int ac = ay*w+ax, bx, by, bc; | ||
1503 | |||
1504 | if (!(state->lines[ac] & dir)) return; /* no link */ | ||
1505 | bx = ax + DX(dir); by = ay + DY(dir); | ||
1506 | |||
1507 | assert(INGRID(state, bx, by)); /* should not have a link off grid */ | ||
1508 | |||
1509 | bc = by*w+bx; | ||
1510 | assert(state->lines[bc] & F(dir)); /* should have reciprocal link */ | ||
1511 | if (!(state->lines[bc] & F(dir))) return; | ||
1512 | |||
1513 | dsf_merge(dsf, ac, bc); | ||
1514 | } | ||
1515 | |||
1516 | static void check_completion(game_state *state, int mark) | ||
1517 | { | ||
1518 | int w = state->shared->w, h = state->shared->h, x, y, i, d; | ||
1519 | int had_error = FALSE; | ||
1520 | int *dsf, *component_state; | ||
1521 | int nsilly, nloop, npath, largest_comp, largest_size, total_pathsize; | ||
1522 | enum { COMP_NONE, COMP_LOOP, COMP_PATH, COMP_SILLY, COMP_EMPTY }; | ||
1523 | |||
1524 | if (mark) { | ||
1525 | for (i = 0; i < w*h; i++) { | ||
1526 | state->errors[i] = 0; | ||
1527 | } | ||
1528 | } | ||
1529 | |||
1530 | #define ERROR(x,y,e) do { had_error = TRUE; if (mark) state->errors[(y)*w+(x)] |= (e); } while(0) | ||
1531 | |||
1532 | /* | ||
1533 | * Analyse the solution into loops, paths and stranger things. | ||
1534 | * Basic strategy here is all the same as in Loopy - see the big | ||
1535 | * comment in loopy.c's check_completion() - and for exactly the | ||
1536 | * same reasons, since Loopy and Pearl have basically the same | ||
1537 | * form of expected solution. | ||
1538 | */ | ||
1539 | dsf = snew_dsf(w*h); | ||
1540 | |||
1541 | /* Build the dsf. */ | ||
1542 | for (x = 0; x < w; x++) { | ||
1543 | for (y = 0; y < h; y++) { | ||
1544 | dsf_update_completion(state, x, y, R, dsf); | ||
1545 | dsf_update_completion(state, x, y, D, dsf); | ||
1546 | } | ||
1547 | } | ||
1548 | |||
1549 | /* Initialise a state variable for each connected component. */ | ||
1550 | component_state = snewn(w*h, int); | ||
1551 | for (i = 0; i < w*h; i++) { | ||
1552 | if (dsf_canonify(dsf, i) == i) | ||
1553 | component_state[i] = COMP_LOOP; | ||
1554 | else | ||
1555 | component_state[i] = COMP_NONE; | ||
1556 | } | ||
1557 | |||
1558 | /* | ||
1559 | * Classify components, and mark errors where a square has more | ||
1560 | * than two line segments. | ||
1561 | */ | ||
1562 | for (x = 0; x < w; x++) { | ||
1563 | for (y = 0; y < h; y++) { | ||
1564 | int type = state->lines[y*w+x]; | ||
1565 | int degree = NBITS(type); | ||
1566 | int comp = dsf_canonify(dsf, y*w+x); | ||
1567 | if (degree > 2) { | ||
1568 | ERROR(x,y,type); | ||
1569 | component_state[comp] = COMP_SILLY; | ||
1570 | } else if (degree == 0) { | ||
1571 | component_state[comp] = COMP_EMPTY; | ||
1572 | } else if (degree == 1) { | ||
1573 | if (component_state[comp] != COMP_SILLY) | ||
1574 | component_state[comp] = COMP_PATH; | ||
1575 | } | ||
1576 | } | ||
1577 | } | ||
1578 | |||
1579 | /* Count the components, and find the largest sensible one. */ | ||
1580 | nsilly = nloop = npath = 0; | ||
1581 | total_pathsize = 0; | ||
1582 | largest_comp = largest_size = -1; | ||
1583 | for (i = 0; i < w*h; i++) { | ||
1584 | if (component_state[i] == COMP_SILLY) { | ||
1585 | nsilly++; | ||
1586 | } else if (component_state[i] == COMP_PATH) { | ||
1587 | total_pathsize += dsf_size(dsf, i); | ||
1588 | npath = 1; | ||
1589 | } else if (component_state[i] == COMP_LOOP) { | ||
1590 | int this_size; | ||
1591 | |||
1592 | nloop++; | ||
1593 | |||
1594 | if ((this_size = dsf_size(dsf, i)) > largest_size) { | ||
1595 | largest_comp = i; | ||
1596 | largest_size = this_size; | ||
1597 | } | ||
1598 | } | ||
1599 | } | ||
1600 | if (largest_size < total_pathsize) { | ||
1601 | largest_comp = -1; /* means the paths */ | ||
1602 | largest_size = total_pathsize; | ||
1603 | } | ||
1604 | |||
1605 | if (nloop > 0 && nloop + npath > 1) { | ||
1606 | /* | ||
1607 | * If there are at least two sensible components including at | ||
1608 | * least one loop, highlight every sensible component that is | ||
1609 | * not the largest one. | ||
1610 | */ | ||
1611 | for (i = 0; i < w*h; i++) { | ||
1612 | int comp = dsf_canonify(dsf, i); | ||
1613 | if ((component_state[comp] == COMP_PATH && | ||
1614 | -1 != largest_comp) || | ||
1615 | (component_state[comp] == COMP_LOOP && | ||
1616 | comp != largest_comp)) | ||
1617 | ERROR(i%w, i/w, state->lines[i]); | ||
1618 | } | ||
1619 | } | ||
1620 | |||
1621 | /* Now we've finished with the dsf and component states. The only | ||
1622 | * thing we'll need to remember later on is whether all edges were | ||
1623 | * part of a single loop, for which our counter variables | ||
1624 | * nsilly,nloop,npath are enough. */ | ||
1625 | sfree(component_state); | ||
1626 | sfree(dsf); | ||
1627 | |||
1628 | /* | ||
1629 | * Check that no clues are contradicted. This code is similar to | ||
1630 | * the code that sets up the maximal clue array for any given | ||
1631 | * loop. | ||
1632 | */ | ||
1633 | for (x = 0; x < w; x++) { | ||
1634 | for (y = 0; y < h; y++) { | ||
1635 | int type = state->lines[y*w+x]; | ||
1636 | if (state->shared->clues[y*w+x] == CORNER) { | ||
1637 | /* Supposed to be a corner: will find a contradiction if | ||
1638 | * it actually contains a straight line, or if it touches any | ||
1639 | * corners. */ | ||
1640 | if ((bLR|bUD) & (1 << type)) { | ||
1641 | ERROR(x,y,ERROR_CLUE); /* actually straight */ | ||
1642 | } | ||
1643 | for (d = 1; d <= 8; d += d) if (type & d) { | ||
1644 | int xx = x + DX(d), yy = y + DY(d); | ||
1645 | if (!INGRID(state, xx, yy)) { | ||
1646 | ERROR(x,y,d); /* leads off grid */ | ||
1647 | } else { | ||
1648 | if ((bLU|bLD|bRU|bRD) & (1 << state->lines[yy*w+xx])) { | ||
1649 | ERROR(x,y,ERROR_CLUE); /* touches corner */ | ||
1650 | } | ||
1651 | } | ||
1652 | } | ||
1653 | } else if (state->shared->clues[y*w+x] == STRAIGHT) { | ||
1654 | /* Supposed to be straight: will find a contradiction if | ||
1655 | * it actually contains a corner, or if it only touches | ||
1656 | * straight lines. */ | ||
1657 | if ((bLU|bLD|bRU|bRD) & (1 << type)) { | ||
1658 | ERROR(x,y,ERROR_CLUE); /* actually a corner */ | ||
1659 | } | ||
1660 | i = 0; | ||
1661 | for (d = 1; d <= 8; d += d) if (type & d) { | ||
1662 | int xx = x + DX(d), yy = y + DY(d); | ||
1663 | if (!INGRID(state, xx, yy)) { | ||
1664 | ERROR(x,y,d); /* leads off grid */ | ||
1665 | } else { | ||
1666 | if ((bLR|bUD) & (1 << state->lines[yy*w+xx])) | ||
1667 | i++; /* a straight */ | ||
1668 | } | ||
1669 | } | ||
1670 | if (i >= 2 && NBITS(type) >= 2) { | ||
1671 | ERROR(x,y,ERROR_CLUE); /* everything touched is straight */ | ||
1672 | } | ||
1673 | } | ||
1674 | } | ||
1675 | } | ||
1676 | |||
1677 | if (nloop == 1 && nsilly == 0 && npath == 0) { | ||
1678 | /* | ||
1679 | * If there's exactly one loop (so that the puzzle is at least | ||
1680 | * potentially complete), we need to ensure it hasn't left any | ||
1681 | * clue out completely. | ||
1682 | */ | ||
1683 | for (x = 0; x < w; x++) { | ||
1684 | for (y = 0; y < h; y++) { | ||
1685 | if (state->lines[y*w+x] == BLANK) { | ||
1686 | if (state->shared->clues[y*w+x] != NOCLUE) { | ||
1687 | /* the loop doesn't include this clue square! */ | ||
1688 | ERROR(x, y, ERROR_CLUE); | ||
1689 | } | ||
1690 | } | ||
1691 | } | ||
1692 | } | ||
1693 | |||
1694 | /* | ||
1695 | * But if not, then we're done! | ||
1696 | */ | ||
1697 | if (!had_error) | ||
1698 | state->completed = TRUE; | ||
1699 | } | ||
1700 | } | ||
1701 | |||
1702 | /* completion check: | ||
1703 | * | ||
1704 | * - no clues must be contradicted (highlight clue itself in error if so) | ||
1705 | * - if there is a closed loop it must include every line segment laid | ||
1706 | * - if there's a smaller closed loop then highlight whole loop as error | ||
1707 | * - no square must have more than 2 lines radiating from centre point | ||
1708 | * (highlight all lines in that square as error if so) | ||
1709 | */ | ||
1710 | |||
1711 | static char *solve_for_diff(game_state *state, char *old_lines, char *new_lines) | ||
1712 | { | ||
1713 | int w = state->shared->w, h = state->shared->h, i; | ||
1714 | char *move = snewn(w*h*40, char), *p = move; | ||
1715 | |||
1716 | *p++ = 'S'; | ||
1717 | for (i = 0; i < w*h; i++) { | ||
1718 | if (old_lines[i] != new_lines[i]) { | ||
1719 | p += sprintf(p, ";R%d,%d,%d", new_lines[i], i%w, i/w); | ||
1720 | } | ||
1721 | } | ||
1722 | *p++ = '\0'; | ||
1723 | move = sresize(move, p - move, char); | ||
1724 | |||
1725 | return move; | ||
1726 | } | ||
1727 | |||
1728 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1729 | const char *aux, char **error) | ||
1730 | { | ||
1731 | game_state *solved = dup_game(state); | ||
1732 | int i, ret, sz = state->shared->sz; | ||
1733 | char *move; | ||
1734 | |||
1735 | if (aux) { | ||
1736 | for (i = 0; i < sz; i++) { | ||
1737 | if (aux[i] >= '0' && aux[i] <= '9') | ||
1738 | solved->lines[i] = aux[i] - '0'; | ||
1739 | else if (aux[i] >= 'A' && aux[i] <= 'F') | ||
1740 | solved->lines[i] = aux[i] - 'A' + 10; | ||
1741 | else { | ||
1742 | *error = "invalid char in aux"; | ||
1743 | move = NULL; | ||
1744 | goto done; | ||
1745 | } | ||
1746 | } | ||
1747 | ret = 1; | ||
1748 | } else { | ||
1749 | /* Try to solve with present (half-solved) state first: if there's no | ||
1750 | * solution from there go back to original state. */ | ||
1751 | ret = pearl_solve(currstate->shared->w, currstate->shared->h, | ||
1752 | currstate->shared->clues, solved->lines, | ||
1753 | DIFFCOUNT, FALSE); | ||
1754 | if (ret < 1) | ||
1755 | ret = pearl_solve(state->shared->w, state->shared->h, | ||
1756 | state->shared->clues, solved->lines, | ||
1757 | DIFFCOUNT, FALSE); | ||
1758 | |||
1759 | } | ||
1760 | |||
1761 | if (ret < 1) { | ||
1762 | *error = "Unable to find solution"; | ||
1763 | move = NULL; | ||
1764 | } else { | ||
1765 | move = solve_for_diff(solved, currstate->lines, solved->lines); | ||
1766 | } | ||
1767 | |||
1768 | done: | ||
1769 | free_game(solved); | ||
1770 | return move; | ||
1771 | } | ||
1772 | |||
1773 | static int game_can_format_as_text_now(const game_params *params) | ||
1774 | { | ||
1775 | return TRUE; | ||
1776 | } | ||
1777 | |||
1778 | static char *game_text_format(const game_state *state) | ||
1779 | { | ||
1780 | int w = state->shared->w, h = state->shared->h, cw = 4, ch = 2; | ||
1781 | int gw = cw*(w-1) + 2, gh = ch*(h-1) + 1, len = gw * gh, r, c, j; | ||
1782 | char *board = snewn(len + 1, char); | ||
1783 | |||
1784 | assert(board); | ||
1785 | memset(board, ' ', len); | ||
1786 | |||
1787 | for (r = 0; r < h; ++r) { | ||
1788 | for (c = 0; c < w; ++c) { | ||
1789 | int i = r*w + c, cell = r*ch*gw + c*cw; | ||
1790 | board[cell] = "+BW"[(unsigned char)state->shared->clues[i]]; | ||
1791 | if (c < w - 1 && (state->lines[i] & R || state->lines[i+1] & L)) | ||
1792 | memset(board + cell + 1, '-', cw - 1); | ||
1793 | if (r < h - 1 && (state->lines[i] & D || state->lines[i+w] & U)) | ||
1794 | for (j = 1; j < ch; ++j) board[cell + j*gw] = '|'; | ||
1795 | if (c < w - 1 && (state->marks[i] & R || state->marks[i+1] & L)) | ||
1796 | board[cell + cw/2] = 'x'; | ||
1797 | if (r < h - 1 && (state->marks[i] & D || state->marks[i+w] & U)) | ||
1798 | board[cell + (ch/2 * gw)] = 'x'; | ||
1799 | } | ||
1800 | |||
1801 | for (j = 0; j < (r == h - 1 ? 1 : ch); ++j) | ||
1802 | board[r*ch*gw + (gw - 1) + j*gw] = '\n'; | ||
1803 | } | ||
1804 | |||
1805 | board[len] = '\0'; | ||
1806 | return board; | ||
1807 | } | ||
1808 | |||
1809 | struct game_ui { | ||
1810 | int *dragcoords; /* list of (y*w+x) coords in drag so far */ | ||
1811 | int ndragcoords; /* number of entries in dragcoords. | ||
1812 | * 0 = click but no drag yet. -1 = no drag at all */ | ||
1813 | int clickx, clicky; /* pixel position of initial click */ | ||
1814 | |||
1815 | int curx, cury; /* grid position of keyboard cursor */ | ||
1816 | int cursor_active; /* TRUE iff cursor is shown */ | ||
1817 | }; | ||
1818 | |||
1819 | static game_ui *new_ui(const game_state *state) | ||
1820 | { | ||
1821 | game_ui *ui = snew(game_ui); | ||
1822 | int sz = state->shared->sz; | ||
1823 | |||
1824 | ui->ndragcoords = -1; | ||
1825 | ui->dragcoords = snewn(sz, int); | ||
1826 | ui->cursor_active = FALSE; | ||
1827 | ui->curx = ui->cury = 0; | ||
1828 | |||
1829 | return ui; | ||
1830 | } | ||
1831 | |||
1832 | static void free_ui(game_ui *ui) | ||
1833 | { | ||
1834 | sfree(ui->dragcoords); | ||
1835 | sfree(ui); | ||
1836 | } | ||
1837 | |||
1838 | static char *encode_ui(const game_ui *ui) | ||
1839 | { | ||
1840 | return NULL; | ||
1841 | } | ||
1842 | |||
1843 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1844 | { | ||
1845 | } | ||
1846 | |||
1847 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1848 | const game_state *newstate) | ||
1849 | { | ||
1850 | } | ||
1851 | |||
1852 | #define PREFERRED_TILE_SIZE 31 | ||
1853 | #define HALFSZ (ds->halfsz) | ||
1854 | #define TILE_SIZE (ds->halfsz*2 + 1) | ||
1855 | |||
1856 | #define BORDER ((get_gui_style() == GUI_LOOPY) ? (TILE_SIZE/8) : (TILE_SIZE/2)) | ||
1857 | |||
1858 | #define BORDER_WIDTH (max(TILE_SIZE / 32, 1)) | ||
1859 | |||
1860 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) | ||
1861 | #define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 ) | ||
1862 | #define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) ) | ||
1863 | |||
1864 | #define DS_ESHIFT 4 /* R/U/L/D shift, for error flags */ | ||
1865 | #define DS_DSHIFT 8 /* R/U/L/D shift, for drag-in-progress flags */ | ||
1866 | #define DS_MSHIFT 12 /* shift for no-line mark */ | ||
1867 | |||
1868 | #define DS_ERROR_CLUE (1 << 20) | ||
1869 | #define DS_FLASH (1 << 21) | ||
1870 | #define DS_CURSOR (1 << 22) | ||
1871 | |||
1872 | enum { GUI_MASYU, GUI_LOOPY }; | ||
1873 | |||
1874 | static int get_gui_style(void) | ||
1875 | { | ||
1876 | static int gui_style = -1; | ||
1877 | |||
1878 | if (gui_style == -1) { | ||
1879 | char *env = getenv("PEARL_GUI_LOOPY"); | ||
1880 | if (env && (env[0] == 'y' || env[0] == 'Y')) | ||
1881 | gui_style = GUI_LOOPY; | ||
1882 | else | ||
1883 | gui_style = GUI_MASYU; | ||
1884 | } | ||
1885 | return gui_style; | ||
1886 | } | ||
1887 | |||
1888 | struct game_drawstate { | ||
1889 | int halfsz; | ||
1890 | int started; | ||
1891 | |||
1892 | int w, h, sz; | ||
1893 | unsigned int *lflags; /* size w*h */ | ||
1894 | |||
1895 | char *draglines; /* size w*h; lines flipped by current drag */ | ||
1896 | }; | ||
1897 | |||
1898 | static void update_ui_drag(const game_state *state, game_ui *ui, | ||
1899 | int gx, int gy) | ||
1900 | { | ||
1901 | int /* sz = state->shared->sz, */ w = state->shared->w; | ||
1902 | int i, ox, oy, pos; | ||
1903 | int lastpos; | ||
1904 | |||
1905 | if (!INGRID(state, gx, gy)) | ||
1906 | return; /* square is outside grid */ | ||
1907 | |||
1908 | if (ui->ndragcoords < 0) | ||
1909 | return; /* drag not in progress anyway */ | ||
1910 | |||
1911 | pos = gy * w + gx; | ||
1912 | |||
1913 | lastpos = ui->dragcoords[ui->ndragcoords > 0 ? ui->ndragcoords-1 : 0]; | ||
1914 | if (pos == lastpos) | ||
1915 | return; /* same square as last visited one */ | ||
1916 | |||
1917 | /* Drag confirmed, if it wasn't already. */ | ||
1918 | if (ui->ndragcoords == 0) | ||
1919 | ui->ndragcoords = 1; | ||
1920 | |||
1921 | /* | ||
1922 | * Dragging the mouse into a square that's already been visited by | ||
1923 | * the drag path so far has the effect of truncating the path back | ||
1924 | * to that square, so a player can back out part of an uncommitted | ||
1925 | * drag without having to let go of the mouse. | ||
1926 | */ | ||
1927 | for (i = 0; i < ui->ndragcoords; i++) | ||
1928 | if (pos == ui->dragcoords[i]) { | ||
1929 | ui->ndragcoords = i+1; | ||
1930 | return; | ||
1931 | } | ||
1932 | |||
1933 | /* | ||
1934 | * Otherwise, dragging the mouse into a square that's a rook-move | ||
1935 | * away from the last one on the path extends the path. | ||
1936 | */ | ||
1937 | oy = ui->dragcoords[ui->ndragcoords-1] / w; | ||
1938 | ox = ui->dragcoords[ui->ndragcoords-1] % w; | ||
1939 | if (ox == gx || oy == gy) { | ||
1940 | int dx = (gx < ox ? -1 : gx > ox ? +1 : 0); | ||
1941 | int dy = (gy < oy ? -1 : gy > oy ? +1 : 0); | ||
1942 | int dir = (dy>0 ? D : dy<0 ? U : dx>0 ? R : L); | ||
1943 | while (ox != gx || oy != gy) { | ||
1944 | /* | ||
1945 | * If the drag attempts to cross a 'no line here' mark, | ||
1946 | * stop there. We physically don't allow the user to drag | ||
1947 | * over those marks. | ||
1948 | */ | ||
1949 | if (state->marks[oy*w+ox] & dir) | ||
1950 | break; | ||
1951 | ox += dx; | ||
1952 | oy += dy; | ||
1953 | ui->dragcoords[ui->ndragcoords++] = oy * w + ox; | ||
1954 | } | ||
1955 | } | ||
1956 | |||
1957 | /* | ||
1958 | * Failing that, we do nothing at all: if the user has dragged | ||
1959 | * diagonally across the board, they'll just have to return the | ||
1960 | * mouse to the last known position and do whatever they meant to | ||
1961 | * do again, more slowly and clearly. | ||
1962 | */ | ||
1963 | } | ||
1964 | |||
1965 | /* | ||
1966 | * Routine shared between interpret_move and game_redraw to work out | ||
1967 | * the intended effect of a drag path on the grid. | ||
1968 | * | ||
1969 | * Call it in a loop, like this: | ||
1970 | * | ||
1971 | * int clearing = TRUE; | ||
1972 | * for (i = 0; i < ui->ndragcoords - 1; i++) { | ||
1973 | * int sx, sy, dx, dy, dir, oldstate, newstate; | ||
1974 | * interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy, | ||
1975 | * &dir, &oldstate, &newstate); | ||
1976 | * | ||
1977 | * [do whatever is needed to handle the fact that the drag | ||
1978 | * wants the edge from sx,sy to dx,dy (heading in direction | ||
1979 | * 'dir' at the sx,sy end) to be changed from state oldstate | ||
1980 | * to state newstate, each of which equals either 0 or dir] | ||
1981 | * } | ||
1982 | */ | ||
1983 | static void interpret_ui_drag(const game_state *state, const game_ui *ui, | ||
1984 | int *clearing, int i, int *sx, int *sy, | ||
1985 | int *dx, int *dy, int *dir, | ||
1986 | int *oldstate, int *newstate) | ||
1987 | { | ||
1988 | int w = state->shared->w; | ||
1989 | int sp = ui->dragcoords[i], dp = ui->dragcoords[i+1]; | ||
1990 | *sy = sp/w; | ||
1991 | *sx = sp%w; | ||
1992 | *dy = dp/w; | ||
1993 | *dx = dp%w; | ||
1994 | *dir = (*dy>*sy ? D : *dy<*sy ? U : *dx>*sx ? R : L); | ||
1995 | *oldstate = state->lines[sp] & *dir; | ||
1996 | if (*oldstate) { | ||
1997 | /* | ||
1998 | * The edge we've dragged over was previously | ||
1999 | * present. Set it to absent, unless we've already | ||
2000 | * stopped doing that. | ||
2001 | */ | ||
2002 | *newstate = *clearing ? 0 : *dir; | ||
2003 | } else { | ||
2004 | /* | ||
2005 | * The edge we've dragged over was previously | ||
2006 | * absent. Set it to present, and cancel the | ||
2007 | * 'clearing' flag so that all subsequent edges in | ||
2008 | * the drag are set rather than cleared. | ||
2009 | */ | ||
2010 | *newstate = *dir; | ||
2011 | *clearing = FALSE; | ||
2012 | } | ||
2013 | } | ||
2014 | |||
2015 | static char *mark_in_direction(const game_state *state, int x, int y, int dir, | ||
2016 | int primary, char *buf) | ||
2017 | { | ||
2018 | int w = state->shared->w /*, h = state->shared->h, sz = state->shared->sz */; | ||
2019 | int x2 = x + DX(dir); | ||
2020 | int y2 = y + DY(dir); | ||
2021 | int dir2 = F(dir); | ||
2022 | |||
2023 | char ch = primary ? 'F' : 'M', *other; | ||
2024 | |||
2025 | if (!INGRID(state, x, y) || !INGRID(state, x2, y2)) return ""; | ||
2026 | |||
2027 | /* disallow laying a mark over a line, or vice versa. */ | ||
2028 | other = primary ? state->marks : state->lines; | ||
2029 | if (other[y*w+x] & dir || other[y2*w+x2] & dir2) return ""; | ||
2030 | |||
2031 | sprintf(buf, "%c%d,%d,%d;%c%d,%d,%d", ch, dir, x, y, ch, dir2, x2, y2); | ||
2032 | return dupstr(buf); | ||
2033 | } | ||
2034 | |||
2035 | #define KEY_DIRECTION(btn) (\ | ||
2036 | (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\ | ||
2037 | (btn) == CURSOR_LEFT ? L : R) | ||
2038 | |||
2039 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
2040 | const game_drawstate *ds, | ||
2041 | int x, int y, int button) | ||
2042 | { | ||
2043 | int w = state->shared->w, h = state->shared->h /*, sz = state->shared->sz */; | ||
2044 | int gx = FROMCOORD(x), gy = FROMCOORD(y), i; | ||
2045 | int release = FALSE; | ||
2046 | char tmpbuf[80]; | ||
2047 | |||
2048 | int shift = button & MOD_SHFT, control = button & MOD_CTRL; | ||
2049 | button &= ~MOD_MASK; | ||
2050 | |||
2051 | if (IS_MOUSE_DOWN(button)) { | ||
2052 | ui->cursor_active = FALSE; | ||
2053 | |||
2054 | if (!INGRID(state, gx, gy)) { | ||
2055 | ui->ndragcoords = -1; | ||
2056 | return NULL; | ||
2057 | } | ||
2058 | |||
2059 | ui->clickx = x; ui->clicky = y; | ||
2060 | ui->dragcoords[0] = gy * w + gx; | ||
2061 | ui->ndragcoords = 0; /* will be 1 once drag is confirmed */ | ||
2062 | |||
2063 | return ""; | ||
2064 | } | ||
2065 | |||
2066 | if (button == LEFT_DRAG && ui->ndragcoords >= 0) { | ||
2067 | update_ui_drag(state, ui, gx, gy); | ||
2068 | return ""; | ||
2069 | } | ||
2070 | |||
2071 | if (IS_MOUSE_RELEASE(button)) release = TRUE; | ||
2072 | |||
2073 | if (IS_CURSOR_MOVE(button)) { | ||
2074 | if (!ui->cursor_active) { | ||
2075 | ui->cursor_active = TRUE; | ||
2076 | } else if (control | shift) { | ||
2077 | char *move; | ||
2078 | if (ui->ndragcoords > 0) return NULL; | ||
2079 | ui->ndragcoords = -1; | ||
2080 | move = mark_in_direction(state, ui->curx, ui->cury, | ||
2081 | KEY_DIRECTION(button), control, tmpbuf); | ||
2082 | if (control && !shift && *move) | ||
2083 | move_cursor(button, &ui->curx, &ui->cury, w, h, FALSE); | ||
2084 | return move; | ||
2085 | } else { | ||
2086 | move_cursor(button, &ui->curx, &ui->cury, w, h, FALSE); | ||
2087 | if (ui->ndragcoords >= 0) | ||
2088 | update_ui_drag(state, ui, ui->curx, ui->cury); | ||
2089 | } | ||
2090 | return ""; | ||
2091 | } | ||
2092 | |||
2093 | if (IS_CURSOR_SELECT(button)) { | ||
2094 | if (!ui->cursor_active) { | ||
2095 | ui->cursor_active = TRUE; | ||
2096 | return ""; | ||
2097 | } else if (button == CURSOR_SELECT) { | ||
2098 | if (ui->ndragcoords == -1) { | ||
2099 | ui->ndragcoords = 0; | ||
2100 | ui->dragcoords[0] = ui->cury * w + ui->curx; | ||
2101 | ui->clickx = CENTERED_COORD(ui->curx); | ||
2102 | ui->clicky = CENTERED_COORD(ui->cury); | ||
2103 | return ""; | ||
2104 | } else release = TRUE; | ||
2105 | } else if (button == CURSOR_SELECT2 && ui->ndragcoords >= 0) { | ||
2106 | ui->ndragcoords = -1; | ||
2107 | return ""; | ||
2108 | } | ||
2109 | } | ||
2110 | |||
2111 | if (button == 27 || button == '\b') { | ||
2112 | ui->ndragcoords = -1; | ||
2113 | return ""; | ||
2114 | } | ||
2115 | |||
2116 | if (release) { | ||
2117 | if (ui->ndragcoords > 0) { | ||
2118 | /* End of a drag: process the cached line data. */ | ||
2119 | int buflen = 0, bufsize = 256, tmplen; | ||
2120 | char *buf = NULL; | ||
2121 | const char *sep = ""; | ||
2122 | int clearing = TRUE; | ||
2123 | |||
2124 | for (i = 0; i < ui->ndragcoords - 1; i++) { | ||
2125 | int sx, sy, dx, dy, dir, oldstate, newstate; | ||
2126 | interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy, | ||
2127 | &dir, &oldstate, &newstate); | ||
2128 | |||
2129 | if (oldstate != newstate) { | ||
2130 | if (!buf) buf = snewn(bufsize, char); | ||
2131 | tmplen = sprintf(tmpbuf, "%sF%d,%d,%d;F%d,%d,%d", sep, | ||
2132 | dir, sx, sy, F(dir), dx, dy); | ||
2133 | if (buflen + tmplen >= bufsize) { | ||
2134 | bufsize = (buflen + tmplen) * 5 / 4 + 256; | ||
2135 | buf = sresize(buf, bufsize, char); | ||
2136 | } | ||
2137 | strcpy(buf + buflen, tmpbuf); | ||
2138 | buflen += tmplen; | ||
2139 | sep = ";"; | ||
2140 | } | ||
2141 | } | ||
2142 | |||
2143 | ui->ndragcoords = -1; | ||
2144 | |||
2145 | return buf ? buf : ""; | ||
2146 | } else if (ui->ndragcoords == 0) { | ||
2147 | /* Click (or tiny drag). Work out which edge we were | ||
2148 | * closest to. */ | ||
2149 | int cx, cy; | ||
2150 | |||
2151 | ui->ndragcoords = -1; | ||
2152 | |||
2153 | /* | ||
2154 | * We process clicks based on the mouse-down location, | ||
2155 | * because that's more natural for a user to carefully | ||
2156 | * control than the mouse-up. | ||
2157 | */ | ||
2158 | x = ui->clickx; | ||
2159 | y = ui->clicky; | ||
2160 | |||
2161 | gx = FROMCOORD(x); | ||
2162 | gy = FROMCOORD(y); | ||
2163 | cx = CENTERED_COORD(gx); | ||
2164 | cy = CENTERED_COORD(gy); | ||
2165 | |||
2166 | if (!INGRID(state, gx, gy)) return ""; | ||
2167 | |||
2168 | if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) { | ||
2169 | /* TODO closer to centre of grid: process as a cell click not an edge click. */ | ||
2170 | |||
2171 | return ""; | ||
2172 | } else { | ||
2173 | int direction; | ||
2174 | if (abs(x-cx) < abs(y-cy)) { | ||
2175 | /* Closest to top/bottom edge. */ | ||
2176 | direction = (y < cy) ? U : D; | ||
2177 | } else { | ||
2178 | /* Closest to left/right edge. */ | ||
2179 | direction = (x < cx) ? L : R; | ||
2180 | } | ||
2181 | return mark_in_direction(state, gx, gy, direction, | ||
2182 | (button == LEFT_RELEASE), tmpbuf); | ||
2183 | } | ||
2184 | } | ||
2185 | } | ||
2186 | |||
2187 | if (button == 'H' || button == 'h') | ||
2188 | return dupstr("H"); | ||
2189 | |||
2190 | return NULL; | ||
2191 | } | ||
2192 | |||
2193 | static game_state *execute_move(const game_state *state, const char *move) | ||
2194 | { | ||
2195 | int w = state->shared->w, h = state->shared->h; | ||
2196 | char c; | ||
2197 | int x, y, l, n; | ||
2198 | game_state *ret = dup_game(state); | ||
2199 | |||
2200 | debug(("move: %s\n", move)); | ||
2201 | |||
2202 | while (*move) { | ||
2203 | c = *move; | ||
2204 | if (c == 'S') { | ||
2205 | ret->used_solve = TRUE; | ||
2206 | move++; | ||
2207 | } else if (c == 'L' || c == 'N' || c == 'R' || c == 'F' || c == 'M') { | ||
2208 | /* 'line' or 'noline' or 'replace' or 'flip' or 'mark' */ | ||
2209 | move++; | ||
2210 | if (sscanf(move, "%d,%d,%d%n", &l, &x, &y, &n) != 3) | ||
2211 | goto badmove; | ||
2212 | if (!INGRID(state, x, y)) goto badmove; | ||
2213 | if (l < 0 || l > 15) goto badmove; | ||
2214 | |||
2215 | if (c == 'L') | ||
2216 | ret->lines[y*w + x] |= (char)l; | ||
2217 | else if (c == 'N') | ||
2218 | ret->lines[y*w + x] &= ~((char)l); | ||
2219 | else if (c == 'R') { | ||
2220 | ret->lines[y*w + x] = (char)l; | ||
2221 | ret->marks[y*w + x] &= ~((char)l); /* erase marks too */ | ||
2222 | } else if (c == 'F') | ||
2223 | ret->lines[y*w + x] ^= (char)l; | ||
2224 | else if (c == 'M') | ||
2225 | ret->marks[y*w + x] ^= (char)l; | ||
2226 | |||
2227 | /* | ||
2228 | * If we ended up trying to lay a line _over_ a mark, | ||
2229 | * that's a failed move: interpret_move() should have | ||
2230 | * ensured we never received a move string like that in | ||
2231 | * the first place. | ||
2232 | */ | ||
2233 | if ((ret->lines[y*w + x] & (char)l) && | ||
2234 | (ret->marks[y*w + x] & (char)l)) | ||
2235 | goto badmove; | ||
2236 | |||
2237 | move += n; | ||
2238 | } else if (strcmp(move, "H") == 0) { | ||
2239 | pearl_solve(ret->shared->w, ret->shared->h, | ||
2240 | ret->shared->clues, ret->lines, DIFFCOUNT, TRUE); | ||
2241 | for (n = 0; n < w*h; n++) | ||
2242 | ret->marks[n] &= ~ret->lines[n]; /* erase marks too */ | ||
2243 | move++; | ||
2244 | } else { | ||
2245 | goto badmove; | ||
2246 | } | ||
2247 | if (*move == ';') | ||
2248 | move++; | ||
2249 | else if (*move) | ||
2250 | goto badmove; | ||
2251 | } | ||
2252 | |||
2253 | check_completion(ret, TRUE); | ||
2254 | |||
2255 | return ret; | ||
2256 | |||
2257 | badmove: | ||
2258 | free_game(ret); | ||
2259 | return NULL; | ||
2260 | } | ||
2261 | |||
2262 | /* ---------------------------------------------------------------------- | ||
2263 | * Drawing routines. | ||
2264 | */ | ||
2265 | |||
2266 | #define FLASH_TIME 0.5F | ||
2267 | |||
2268 | static void game_compute_size(const game_params *params, int tilesize, | ||
2269 | int *x, int *y) | ||
2270 | { | ||
2271 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2272 | struct { int halfsz; } ads, *ds = &ads; | ||
2273 | ads.halfsz = (tilesize-1)/2; | ||
2274 | |||
2275 | *x = (params->w) * TILE_SIZE + 2 * BORDER; | ||
2276 | *y = (params->h) * TILE_SIZE + 2 * BORDER; | ||
2277 | } | ||
2278 | |||
2279 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
2280 | const game_params *params, int tilesize) | ||
2281 | { | ||
2282 | ds->halfsz = (tilesize-1)/2; | ||
2283 | } | ||
2284 | |||
2285 | static float *game_colours(frontend *fe, int *ncolours) | ||
2286 | { | ||
2287 | float *ret = snewn(3 * NCOLOURS, float); | ||
2288 | int i; | ||
2289 | |||
2290 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); | ||
2291 | |||
2292 | for (i = 0; i < 3; i++) { | ||
2293 | ret[COL_BLACK * 3 + i] = 0.0F; | ||
2294 | ret[COL_WHITE * 3 + i] = 1.0F; | ||
2295 | ret[COL_GRID * 3 + i] = 0.4F; | ||
2296 | } | ||
2297 | |||
2298 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
2299 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
2300 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
2301 | |||
2302 | ret[COL_DRAGON * 3 + 0] = 0.0F; | ||
2303 | ret[COL_DRAGON * 3 + 1] = 0.0F; | ||
2304 | ret[COL_DRAGON * 3 + 2] = 1.0F; | ||
2305 | |||
2306 | ret[COL_DRAGOFF * 3 + 0] = 0.8F; | ||
2307 | ret[COL_DRAGOFF * 3 + 1] = 0.8F; | ||
2308 | ret[COL_DRAGOFF * 3 + 2] = 1.0F; | ||
2309 | |||
2310 | ret[COL_FLASH * 3 + 0] = 1.0F; | ||
2311 | ret[COL_FLASH * 3 + 1] = 1.0F; | ||
2312 | ret[COL_FLASH * 3 + 2] = 1.0F; | ||
2313 | |||
2314 | *ncolours = NCOLOURS; | ||
2315 | |||
2316 | return ret; | ||
2317 | } | ||
2318 | |||
2319 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
2320 | { | ||
2321 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
2322 | int i; | ||
2323 | |||
2324 | ds->halfsz = 0; | ||
2325 | ds->started = FALSE; | ||
2326 | |||
2327 | ds->w = state->shared->w; | ||
2328 | ds->h = state->shared->h; | ||
2329 | ds->sz = state->shared->sz; | ||
2330 | ds->lflags = snewn(ds->sz, unsigned int); | ||
2331 | for (i = 0; i < ds->sz; i++) | ||
2332 | ds->lflags[i] = 0; | ||
2333 | |||
2334 | ds->draglines = snewn(ds->sz, char); | ||
2335 | |||
2336 | return ds; | ||
2337 | } | ||
2338 | |||
2339 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
2340 | { | ||
2341 | sfree(ds->draglines); | ||
2342 | sfree(ds->lflags); | ||
2343 | sfree(ds); | ||
2344 | } | ||
2345 | |||
2346 | static void draw_lines_specific(drawing *dr, game_drawstate *ds, | ||
2347 | int x, int y, unsigned int lflags, | ||
2348 | unsigned int shift, int c) | ||
2349 | { | ||
2350 | int ox = COORD(x), oy = COORD(y); | ||
2351 | int t2 = HALFSZ, t16 = HALFSZ/4; | ||
2352 | int cx = ox + t2, cy = oy + t2; | ||
2353 | int d; | ||
2354 | |||
2355 | /* Draw each of the four directions, where laid (or error, or drag, etc.) */ | ||
2356 | for (d = 1; d < 16; d *= 2) { | ||
2357 | int xoff = t2 * DX(d), yoff = t2 * DY(d); | ||
2358 | int xnudge = abs(t16 * DX(C(d))), ynudge = abs(t16 * DY(C(d))); | ||
2359 | |||
2360 | if ((lflags >> shift) & d) { | ||
2361 | int lx = cx + ((xoff < 0) ? xoff : 0) - xnudge; | ||
2362 | int ly = cy + ((yoff < 0) ? yoff : 0) - ynudge; | ||
2363 | |||
2364 | if (c == COL_DRAGOFF && !(lflags & d)) | ||
2365 | continue; | ||
2366 | if (c == COL_DRAGON && (lflags & d)) | ||
2367 | continue; | ||
2368 | |||
2369 | draw_rect(dr, lx, ly, | ||
2370 | abs(xoff)+2*xnudge+1, | ||
2371 | abs(yoff)+2*ynudge+1, c); | ||
2372 | /* end cap */ | ||
2373 | draw_rect(dr, cx - t16, cy - t16, 2*t16+1, 2*t16+1, c); | ||
2374 | } | ||
2375 | } | ||
2376 | } | ||
2377 | |||
2378 | static void draw_square(drawing *dr, game_drawstate *ds, const game_ui *ui, | ||
2379 | int x, int y, unsigned int lflags, char clue) | ||
2380 | { | ||
2381 | int ox = COORD(x), oy = COORD(y); | ||
2382 | int t2 = HALFSZ, t16 = HALFSZ/4; | ||
2383 | int cx = ox + t2, cy = oy + t2; | ||
2384 | int d; | ||
2385 | |||
2386 | assert(dr); | ||
2387 | |||
2388 | /* Clip to the grid square. */ | ||
2389 | clip(dr, ox, oy, TILE_SIZE, TILE_SIZE); | ||
2390 | |||
2391 | /* Clear the square. */ | ||
2392 | draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, | ||
2393 | (lflags & DS_CURSOR) ? | ||
2394 | COL_CURSOR_BACKGROUND : COL_BACKGROUND); | ||
2395 | |||
2396 | |||
2397 | if (get_gui_style() == GUI_LOOPY) { | ||
2398 | /* Draw small dot, underneath any lines. */ | ||
2399 | draw_circle(dr, cx, cy, t16, COL_GRID, COL_GRID); | ||
2400 | } else { | ||
2401 | /* Draw outline of grid square */ | ||
2402 | draw_line(dr, ox, oy, COORD(x+1), oy, COL_GRID); | ||
2403 | draw_line(dr, ox, oy, ox, COORD(y+1), COL_GRID); | ||
2404 | } | ||
2405 | |||
2406 | /* Draw grid: either thin gridlines, or no-line marks. | ||
2407 | * We draw these first because the thick laid lines should be on top. */ | ||
2408 | for (d = 1; d < 16; d *= 2) { | ||
2409 | int xoff = t2 * DX(d), yoff = t2 * DY(d); | ||
2410 | |||
2411 | if ((x == 0 && d == L) || | ||
2412 | (y == 0 && d == U) || | ||
2413 | (x == ds->w-1 && d == R) || | ||
2414 | (y == ds->h-1 && d == D)) | ||
2415 | continue; /* no gridlines out to the border. */ | ||
2416 | |||
2417 | if ((lflags >> DS_MSHIFT) & d) { | ||
2418 | /* either a no-line mark ... */ | ||
2419 | int mx = cx + xoff, my = cy + yoff, msz = t16; | ||
2420 | |||
2421 | draw_line(dr, mx-msz, my-msz, mx+msz, my+msz, COL_BLACK); | ||
2422 | draw_line(dr, mx-msz, my+msz, mx+msz, my-msz, COL_BLACK); | ||
2423 | } else { | ||
2424 | if (get_gui_style() == GUI_LOOPY) { | ||
2425 | /* draw grid lines connecting centre of cells */ | ||
2426 | draw_line(dr, cx, cy, cx+xoff, cy+yoff, COL_GRID); | ||
2427 | } | ||
2428 | } | ||
2429 | } | ||
2430 | |||
2431 | /* Draw each of the four directions, where laid (or error, or drag, etc.) | ||
2432 | * Order is important here, specifically for the eventual colours of the | ||
2433 | * exposed end caps. */ | ||
2434 | draw_lines_specific(dr, ds, x, y, lflags, 0, | ||
2435 | (lflags & DS_FLASH ? COL_FLASH : COL_BLACK)); | ||
2436 | draw_lines_specific(dr, ds, x, y, lflags, DS_ESHIFT, COL_ERROR); | ||
2437 | draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGOFF); | ||
2438 | draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGON); | ||
2439 | |||
2440 | /* Draw a clue, if present */ | ||
2441 | if (clue != NOCLUE) { | ||
2442 | int c = (lflags & DS_FLASH) ? COL_FLASH : | ||
2443 | (clue == STRAIGHT) ? COL_WHITE : COL_BLACK; | ||
2444 | |||
2445 | if (lflags & DS_ERROR_CLUE) /* draw a bigger 'error' clue circle. */ | ||
2446 | draw_circle(dr, cx, cy, TILE_SIZE*3/8, COL_ERROR, COL_ERROR); | ||
2447 | |||
2448 | draw_circle(dr, cx, cy, TILE_SIZE/4, c, COL_BLACK); | ||
2449 | } | ||
2450 | |||
2451 | unclip(dr); | ||
2452 | draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE); | ||
2453 | } | ||
2454 | |||
2455 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
2456 | const game_state *oldstate, const game_state *state, | ||
2457 | int dir, const game_ui *ui, | ||
2458 | float animtime, float flashtime) | ||
2459 | { | ||
2460 | int w = state->shared->w, h = state->shared->h, sz = state->shared->sz; | ||
2461 | int x, y, force = 0, flashing = 0; | ||
2462 | |||
2463 | if (!ds->started) { | ||
2464 | /* | ||
2465 | * The initial contents of the window are not guaranteed and | ||
2466 | * can vary with front ends. To be on the safe side, all games | ||
2467 | * should start by drawing a big background-colour rectangle | ||
2468 | * covering the whole window. | ||
2469 | */ | ||
2470 | draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER, | ||
2471 | COL_BACKGROUND); | ||
2472 | |||
2473 | if (get_gui_style() == GUI_MASYU) { | ||
2474 | /* | ||
2475 | * Smaller black rectangle which is the main grid. | ||
2476 | */ | ||
2477 | draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH, | ||
2478 | w*TILE_SIZE + 2*BORDER_WIDTH + 1, | ||
2479 | h*TILE_SIZE + 2*BORDER_WIDTH + 1, | ||
2480 | COL_GRID); | ||
2481 | } | ||
2482 | |||
2483 | draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER); | ||
2484 | |||
2485 | ds->started = TRUE; | ||
2486 | force = 1; | ||
2487 | } | ||
2488 | |||
2489 | if (flashtime > 0 && | ||
2490 | (flashtime <= FLASH_TIME/3 || | ||
2491 | flashtime >= FLASH_TIME*2/3)) | ||
2492 | flashing = DS_FLASH; | ||
2493 | |||
2494 | memset(ds->draglines, 0, sz); | ||
2495 | if (ui->ndragcoords > 0) { | ||
2496 | int i, clearing = TRUE; | ||
2497 | for (i = 0; i < ui->ndragcoords - 1; i++) { | ||
2498 | int sx, sy, dx, dy, dir, oldstate, newstate; | ||
2499 | interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy, | ||
2500 | &dir, &oldstate, &newstate); | ||
2501 | ds->draglines[sy*w+sx] ^= (oldstate ^ newstate); | ||
2502 | ds->draglines[dy*w+dx] ^= (F(oldstate) ^ F(newstate)); | ||
2503 | } | ||
2504 | } | ||
2505 | |||
2506 | for (x = 0; x < w; x++) { | ||
2507 | for (y = 0; y < h; y++) { | ||
2508 | unsigned int f = (unsigned int)state->lines[y*w+x]; | ||
2509 | unsigned int eline = (unsigned int)(state->errors[y*w+x] & (R|U|L|D)); | ||
2510 | |||
2511 | f |= eline << DS_ESHIFT; | ||
2512 | f |= ((unsigned int)ds->draglines[y*w+x]) << DS_DSHIFT; | ||
2513 | f |= ((unsigned int)state->marks[y*w+x]) << DS_MSHIFT; | ||
2514 | |||
2515 | if (state->errors[y*w+x] & ERROR_CLUE) | ||
2516 | f |= DS_ERROR_CLUE; | ||
2517 | |||
2518 | f |= flashing; | ||
2519 | |||
2520 | if (ui->cursor_active && x == ui->curx && y == ui->cury) | ||
2521 | f |= DS_CURSOR; | ||
2522 | |||
2523 | if (f != ds->lflags[y*w+x] || force) { | ||
2524 | ds->lflags[y*w+x] = f; | ||
2525 | draw_square(dr, ds, ui, x, y, f, state->shared->clues[y*w+x]); | ||
2526 | } | ||
2527 | } | ||
2528 | } | ||
2529 | } | ||
2530 | |||
2531 | static float game_anim_length(const game_state *oldstate, | ||
2532 | const game_state *newstate, int dir, game_ui *ui) | ||
2533 | { | ||
2534 | return 0.0F; | ||
2535 | } | ||
2536 | |||
2537 | static float game_flash_length(const game_state *oldstate, | ||
2538 | const game_state *newstate, int dir, game_ui *ui) | ||
2539 | { | ||
2540 | if (!oldstate->completed && newstate->completed && | ||
2541 | !oldstate->used_solve && !newstate->used_solve) | ||
2542 | return FLASH_TIME; | ||
2543 | else | ||
2544 | return 0.0F; | ||
2545 | } | ||
2546 | |||
2547 | static int game_status(const game_state *state) | ||
2548 | { | ||
2549 | return state->completed ? +1 : 0; | ||
2550 | } | ||
2551 | |||
2552 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
2553 | { | ||
2554 | return TRUE; | ||
2555 | } | ||
2556 | |||
2557 | static void game_print_size(const game_params *params, float *x, float *y) | ||
2558 | { | ||
2559 | int pw, ph; | ||
2560 | |||
2561 | /* | ||
2562 | * I'll use 6mm squares by default. | ||
2563 | */ | ||
2564 | game_compute_size(params, 600, &pw, &ph); | ||
2565 | *x = pw / 100.0F; | ||
2566 | *y = ph / 100.0F; | ||
2567 | } | ||
2568 | |||
2569 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
2570 | { | ||
2571 | int w = state->shared->w, h = state->shared->h, x, y; | ||
2572 | int black = print_mono_colour(dr, 0); | ||
2573 | int white = print_mono_colour(dr, 1); | ||
2574 | |||
2575 | /* No GUI_LOOPY here: only use the familiar masyu style. */ | ||
2576 | |||
2577 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2578 | game_drawstate *ds = game_new_drawstate(dr, state); | ||
2579 | game_set_size(dr, ds, NULL, tilesize); | ||
2580 | |||
2581 | /* Draw grid outlines (black). */ | ||
2582 | for (x = 0; x <= w; x++) | ||
2583 | draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black); | ||
2584 | for (y = 0; y <= h; y++) | ||
2585 | draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black); | ||
2586 | |||
2587 | for (x = 0; x < w; x++) { | ||
2588 | for (y = 0; y < h; y++) { | ||
2589 | int cx = COORD(x) + HALFSZ, cy = COORD(y) + HALFSZ; | ||
2590 | int clue = state->shared->clues[y*w+x]; | ||
2591 | |||
2592 | draw_lines_specific(dr, ds, x, y, state->lines[y*w+x], 0, black); | ||
2593 | |||
2594 | if (clue != NOCLUE) { | ||
2595 | int c = (clue == CORNER) ? black : white; | ||
2596 | draw_circle(dr, cx, cy, TILE_SIZE/4, c, black); | ||
2597 | } | ||
2598 | } | ||
2599 | } | ||
2600 | |||
2601 | game_free_drawstate(dr, ds); | ||
2602 | } | ||
2603 | |||
2604 | #ifdef COMBINED | ||
2605 | #define thegame pearl | ||
2606 | #endif | ||
2607 | |||
2608 | const struct game thegame = { | ||
2609 | "Pearl", "games.pearl", "pearl", | ||
2610 | default_params, | ||
2611 | game_fetch_preset, NULL, | ||
2612 | decode_params, | ||
2613 | encode_params, | ||
2614 | free_params, | ||
2615 | dup_params, | ||
2616 | TRUE, game_configure, custom_params, | ||
2617 | validate_params, | ||
2618 | new_game_desc, | ||
2619 | validate_desc, | ||
2620 | new_game, | ||
2621 | dup_game, | ||
2622 | free_game, | ||
2623 | TRUE, solve_game, | ||
2624 | TRUE, game_can_format_as_text_now, game_text_format, | ||
2625 | new_ui, | ||
2626 | free_ui, | ||
2627 | encode_ui, | ||
2628 | decode_ui, | ||
2629 | game_changed_state, | ||
2630 | interpret_move, | ||
2631 | execute_move, | ||
2632 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
2633 | game_colours, | ||
2634 | game_new_drawstate, | ||
2635 | game_free_drawstate, | ||
2636 | game_redraw, | ||
2637 | game_anim_length, | ||
2638 | game_flash_length, | ||
2639 | game_status, | ||
2640 | TRUE, FALSE, game_print_size, game_print, | ||
2641 | FALSE, /* wants_statusbar */ | ||
2642 | FALSE, game_timing_state, | ||
2643 | 0, /* flags */ | ||
2644 | }; | ||
2645 | |||
2646 | #ifdef STANDALONE_SOLVER | ||
2647 | |||
2648 | #include <time.h> | ||
2649 | #include <stdarg.h> | ||
2650 | |||
2651 | const char *quis = NULL; | ||
2652 | |||
2653 | static void usage(FILE *out) { | ||
2654 | fprintf(out, "usage: %s <params>\n", quis); | ||
2655 | } | ||
2656 | |||
2657 | static void pnum(int n, int ntot, const char *desc) | ||
2658 | { | ||
2659 | printf("%2.1f%% (%d) %s", (double)n*100.0 / (double)ntot, n, desc); | ||
2660 | } | ||
2661 | |||
2662 | static void start_soak(game_params *p, random_state *rs, int nsecs) | ||
2663 | { | ||
2664 | time_t tt_start, tt_now, tt_last; | ||
2665 | int n = 0, nsolved = 0, nimpossible = 0, ret; | ||
2666 | char *grid, *clues; | ||
2667 | |||
2668 | tt_start = tt_last = time(NULL); | ||
2669 | |||
2670 | /* Currently this generates puzzles of any difficulty (trying to solve it | ||
2671 | * on the maximum difficulty level and not checking it's not too easy). */ | ||
2672 | printf("Soak-testing a %dx%d grid (any difficulty)", p->w, p->h); | ||
2673 | if (nsecs > 0) printf(" for %d seconds", nsecs); | ||
2674 | printf(".\n"); | ||
2675 | |||
2676 | p->nosolve = TRUE; | ||
2677 | |||
2678 | grid = snewn(p->w*p->h, char); | ||
2679 | clues = snewn(p->w*p->h, char); | ||
2680 | |||
2681 | while (1) { | ||
2682 | n += new_clues(p, rs, clues, grid); /* should be 1, with nosolve */ | ||
2683 | |||
2684 | ret = pearl_solve(p->w, p->h, clues, grid, DIFF_TRICKY, FALSE); | ||
2685 | if (ret <= 0) nimpossible++; | ||
2686 | if (ret == 1) nsolved++; | ||
2687 | |||
2688 | tt_now = time(NULL); | ||
2689 | if (tt_now > tt_last) { | ||
2690 | tt_last = tt_now; | ||
2691 | |||
2692 | printf("%d total, %3.1f/s, ", | ||
2693 | n, (double)n / ((double)tt_now - tt_start)); | ||
2694 | pnum(nsolved, n, "solved"); printf(", "); | ||
2695 | printf("%3.1f/s", (double)nsolved / ((double)tt_now - tt_start)); | ||
2696 | if (nimpossible > 0) | ||
2697 | pnum(nimpossible, n, "impossible"); | ||
2698 | printf("\n"); | ||
2699 | } | ||
2700 | if (nsecs > 0 && (tt_now - tt_start) > nsecs) { | ||
2701 | printf("\n"); | ||
2702 | break; | ||
2703 | } | ||
2704 | } | ||
2705 | |||
2706 | sfree(grid); | ||
2707 | sfree(clues); | ||
2708 | } | ||
2709 | |||
2710 | int main(int argc, const char *argv[]) | ||
2711 | { | ||
2712 | game_params *p = NULL; | ||
2713 | random_state *rs = NULL; | ||
2714 | time_t seed = time(NULL); | ||
2715 | char *id = NULL, *err; | ||
2716 | |||
2717 | setvbuf(stdout, NULL, _IONBF, 0); | ||
2718 | |||
2719 | quis = argv[0]; | ||
2720 | |||
2721 | while (--argc > 0) { | ||
2722 | char *p = (char*)(*++argv); | ||
2723 | if (!strcmp(p, "-e") || !strcmp(p, "--seed")) { | ||
2724 | seed = atoi(*++argv); | ||
2725 | argc--; | ||
2726 | } else if (*p == '-') { | ||
2727 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
2728 | usage(stderr); | ||
2729 | exit(1); | ||
2730 | } else { | ||
2731 | id = p; | ||
2732 | } | ||
2733 | } | ||
2734 | |||
2735 | rs = random_new((void*)&seed, sizeof(time_t)); | ||
2736 | p = default_params(); | ||
2737 | |||
2738 | if (id) { | ||
2739 | if (strchr(id, ':')) { | ||
2740 | fprintf(stderr, "soak takes params only.\n"); | ||
2741 | goto done; | ||
2742 | } | ||
2743 | |||
2744 | decode_params(p, id); | ||
2745 | err = validate_params(p, 1); | ||
2746 | if (err) { | ||
2747 | fprintf(stderr, "%s: %s", argv[0], err); | ||
2748 | goto done; | ||
2749 | } | ||
2750 | |||
2751 | start_soak(p, rs, 0); /* run forever */ | ||
2752 | } else { | ||
2753 | int i; | ||
2754 | |||
2755 | for (i = 5; i <= 12; i++) { | ||
2756 | p->w = p->h = i; | ||
2757 | start_soak(p, rs, 5); | ||
2758 | } | ||
2759 | } | ||
2760 | |||
2761 | done: | ||
2762 | free_params(p); | ||
2763 | random_free(rs); | ||
2764 | |||
2765 | return 0; | ||
2766 | } | ||
2767 | |||
2768 | #endif | ||
2769 | |||
2770 | /* vim: set shiftwidth=4 tabstop=8: */ | ||