diff options
author | Franklin Wei <git@fwei.tk> | 2017-04-29 18:21:56 -0400 |
---|---|---|
committer | Franklin Wei <git@fwei.tk> | 2017-04-29 18:24:42 -0400 |
commit | 881746789a489fad85aae8317555f73dbe261556 (patch) | |
tree | cec2946362c4698c8db3c10f3242ef546c2c22dd /apps/plugins/puzzles/src/lightup.c | |
parent | 03dd4b92be7dcd5c8ab06da3810887060e06abd5 (diff) | |
download | rockbox-881746789a489fad85aae8317555f73dbe261556.tar.gz rockbox-881746789a489fad85aae8317555f73dbe261556.zip |
puzzles: refactor and resync with upstream
This brings puzzles up-to-date with upstream revision
2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made
by me, including cursor-only Untangle and some compilation fixes
remain. Upstream code has been moved to its separate subdirectory and
future syncs can be done by simply copying over the new sources.
Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804
Diffstat (limited to 'apps/plugins/puzzles/src/lightup.c')
-rw-r--r-- | apps/plugins/puzzles/src/lightup.c | 2405 |
1 files changed, 2405 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/lightup.c b/apps/plugins/puzzles/src/lightup.c new file mode 100644 index 0000000000..4dd46c8392 --- /dev/null +++ b/apps/plugins/puzzles/src/lightup.c | |||
@@ -0,0 +1,2405 @@ | |||
1 | /* | ||
2 | * lightup.c: Implementation of the Nikoli game 'Light Up'. | ||
3 | * | ||
4 | * Possible future solver enhancements: | ||
5 | * | ||
6 | * - In a situation where two clues are diagonally adjacent, you can | ||
7 | * deduce bounds on the number of lights shared between them. For | ||
8 | * instance, suppose a 3 clue is diagonally adjacent to a 1 clue: | ||
9 | * of the two squares adjacent to both clues, at least one must be | ||
10 | * a light (or the 3 would be unsatisfiable) and yet at most one | ||
11 | * must be a light (or the 1 would be overcommitted), so in fact | ||
12 | * _exactly_ one must be a light, and hence the other two squares | ||
13 | * adjacent to the 3 must also be lights and the other two adjacent | ||
14 | * to the 1 must not. Likewise if the 3 is replaced with a 2 but | ||
15 | * one of its other two squares is known not to be a light, and so | ||
16 | * on. | ||
17 | * | ||
18 | * - In a situation where two clues are orthogonally separated (not | ||
19 | * necessarily directly adjacent), you may be able to deduce | ||
20 | * something about the squares that align with each other. For | ||
21 | * instance, suppose two clues are vertically adjacent. Consider | ||
22 | * the pair of squares A,B horizontally adjacent to the top clue, | ||
23 | * and the pair C,D horizontally adjacent to the bottom clue. | ||
24 | * Assuming no intervening obstacles, A and C align with each other | ||
25 | * and hence at most one of them can be a light, and B and D | ||
26 | * likewise, so we must have at most two lights between the four | ||
27 | * squares. So if the clues indicate that there are at _least_ two | ||
28 | * lights in those four squares because the top clue requires at | ||
29 | * least one of AB to be a light and the bottom one requires at | ||
30 | * least one of CD, then we can in fact deduce that there are | ||
31 | * _exactly_ two lights between the four squares, and fill in the | ||
32 | * other squares adjacent to each clue accordingly. For instance, | ||
33 | * if both clues are 3s, then we instantly deduce that all four of | ||
34 | * the squares _vertically_ adjacent to the two clues must be | ||
35 | * lights. (For that to happen, of course, there'd also have to be | ||
36 | * a black square in between the clues, so the two inner lights | ||
37 | * don't light each other.) | ||
38 | * | ||
39 | * - I haven't thought it through carefully, but there's always the | ||
40 | * possibility that both of the above deductions are special cases | ||
41 | * of some more general pattern which can be made computationally | ||
42 | * feasible... | ||
43 | */ | ||
44 | |||
45 | #include <stdio.h> | ||
46 | #include <stdlib.h> | ||
47 | #include <string.h> | ||
48 | #include <assert.h> | ||
49 | #include <ctype.h> | ||
50 | #include <math.h> | ||
51 | |||
52 | #include "puzzles.h" | ||
53 | |||
54 | /* | ||
55 | * In standalone solver mode, `verbose' is a variable which can be | ||
56 | * set by command-line option; in debugging mode it's simply always | ||
57 | * true. | ||
58 | */ | ||
59 | #if defined STANDALONE_SOLVER | ||
60 | #define SOLVER_DIAGNOSTICS | ||
61 | int verbose = 0; | ||
62 | #undef debug | ||
63 | #define debug(x) printf x | ||
64 | #elif defined SOLVER_DIAGNOSTICS | ||
65 | #define verbose 2 | ||
66 | #endif | ||
67 | |||
68 | /* --- Constants, structure definitions, etc. --- */ | ||
69 | |||
70 | #define PREFERRED_TILE_SIZE 32 | ||
71 | #define TILE_SIZE (ds->tilesize) | ||
72 | #define BORDER (TILE_SIZE / 2) | ||
73 | #define TILE_RADIUS (ds->crad) | ||
74 | |||
75 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) | ||
76 | #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) | ||
77 | |||
78 | #define FLASH_TIME 0.30F | ||
79 | |||
80 | enum { | ||
81 | COL_BACKGROUND, | ||
82 | COL_GRID, | ||
83 | COL_BLACK, /* black */ | ||
84 | COL_LIGHT, /* white */ | ||
85 | COL_LIT, /* yellow */ | ||
86 | COL_ERROR, /* red */ | ||
87 | COL_CURSOR, | ||
88 | NCOLOURS | ||
89 | }; | ||
90 | |||
91 | enum { SYMM_NONE, SYMM_REF2, SYMM_ROT2, SYMM_REF4, SYMM_ROT4, SYMM_MAX }; | ||
92 | |||
93 | #define DIFFCOUNT 2 | ||
94 | |||
95 | struct game_params { | ||
96 | int w, h; | ||
97 | int blackpc; /* %age of black squares */ | ||
98 | int symm; | ||
99 | int difficulty; /* 0 to DIFFCOUNT */ | ||
100 | }; | ||
101 | |||
102 | #define F_BLACK 1 | ||
103 | |||
104 | /* flags for black squares */ | ||
105 | #define F_NUMBERED 2 /* it has a number attached */ | ||
106 | #define F_NUMBERUSED 4 /* this number was useful for solving */ | ||
107 | |||
108 | /* flags for non-black squares */ | ||
109 | #define F_IMPOSSIBLE 8 /* can't put a light here */ | ||
110 | #define F_LIGHT 16 | ||
111 | |||
112 | #define F_MARK 32 | ||
113 | |||
114 | struct game_state { | ||
115 | int w, h, nlights; | ||
116 | int *lights; /* For black squares, (optionally) the number | ||
117 | of surrounding lights. For non-black squares, | ||
118 | the number of times it's lit. size h*w*/ | ||
119 | unsigned int *flags; /* size h*w */ | ||
120 | int completed, used_solve; | ||
121 | }; | ||
122 | |||
123 | #define GRID(gs,grid,x,y) (gs->grid[(y)*((gs)->w) + (x)]) | ||
124 | |||
125 | /* A ll_data holds information about which lights would be lit by | ||
126 | * a particular grid location's light (or conversely, which locations | ||
127 | * could light a specific other location). */ | ||
128 | /* most things should consider this struct opaque. */ | ||
129 | typedef struct { | ||
130 | int ox,oy; | ||
131 | int minx, maxx, miny, maxy; | ||
132 | int include_origin; | ||
133 | } ll_data; | ||
134 | |||
135 | /* Macro that executes 'block' once per light in lld, including | ||
136 | * the origin if include_origin is specified. 'block' can use | ||
137 | * lx and ly as the coords. */ | ||
138 | #define FOREACHLIT(lld,block) do { \ | ||
139 | int lx,ly; \ | ||
140 | ly = (lld)->oy; \ | ||
141 | for (lx = (lld)->minx; lx <= (lld)->maxx; lx++) { \ | ||
142 | if (lx == (lld)->ox) continue; \ | ||
143 | block \ | ||
144 | } \ | ||
145 | lx = (lld)->ox; \ | ||
146 | for (ly = (lld)->miny; ly <= (lld)->maxy; ly++) { \ | ||
147 | if (!(lld)->include_origin && ly == (lld)->oy) continue; \ | ||
148 | block \ | ||
149 | } \ | ||
150 | } while(0) | ||
151 | |||
152 | |||
153 | typedef struct { | ||
154 | struct { int x, y; unsigned int f; } points[4]; | ||
155 | int npoints; | ||
156 | } surrounds; | ||
157 | |||
158 | /* Fills in (doesn't allocate) a surrounds structure with the grid locations | ||
159 | * around a given square, taking account of the edges. */ | ||
160 | static void get_surrounds(const game_state *state, int ox, int oy, | ||
161 | surrounds *s) | ||
162 | { | ||
163 | assert(ox >= 0 && ox < state->w && oy >= 0 && oy < state->h); | ||
164 | s->npoints = 0; | ||
165 | #define ADDPOINT(cond,nx,ny) do {\ | ||
166 | if (cond) { \ | ||
167 | s->points[s->npoints].x = (nx); \ | ||
168 | s->points[s->npoints].y = (ny); \ | ||
169 | s->points[s->npoints].f = 0; \ | ||
170 | s->npoints++; \ | ||
171 | } } while(0) | ||
172 | ADDPOINT(ox > 0, ox-1, oy); | ||
173 | ADDPOINT(ox < (state->w-1), ox+1, oy); | ||
174 | ADDPOINT(oy > 0, ox, oy-1); | ||
175 | ADDPOINT(oy < (state->h-1), ox, oy+1); | ||
176 | } | ||
177 | |||
178 | /* --- Game parameter functions --- */ | ||
179 | |||
180 | #define DEFAULT_PRESET 0 | ||
181 | |||
182 | const struct game_params lightup_presets[] = { | ||
183 | { 7, 7, 20, SYMM_ROT4, 0 }, | ||
184 | { 7, 7, 20, SYMM_ROT4, 1 }, | ||
185 | { 7, 7, 20, SYMM_ROT4, 2 }, | ||
186 | { 10, 10, 20, SYMM_ROT2, 0 }, | ||
187 | { 10, 10, 20, SYMM_ROT2, 1 }, | ||
188 | #ifdef SLOW_SYSTEM | ||
189 | { 12, 12, 20, SYMM_ROT2, 0 }, | ||
190 | { 12, 12, 20, SYMM_ROT2, 1 }, | ||
191 | #else | ||
192 | { 10, 10, 20, SYMM_ROT2, 2 }, | ||
193 | { 14, 14, 20, SYMM_ROT2, 0 }, | ||
194 | { 14, 14, 20, SYMM_ROT2, 1 }, | ||
195 | { 14, 14, 20, SYMM_ROT2, 2 } | ||
196 | #endif | ||
197 | }; | ||
198 | |||
199 | static game_params *default_params(void) | ||
200 | { | ||
201 | game_params *ret = snew(game_params); | ||
202 | *ret = lightup_presets[DEFAULT_PRESET]; | ||
203 | |||
204 | return ret; | ||
205 | } | ||
206 | |||
207 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
208 | { | ||
209 | game_params *ret; | ||
210 | char buf[80]; | ||
211 | |||
212 | if (i < 0 || i >= lenof(lightup_presets)) | ||
213 | return FALSE; | ||
214 | |||
215 | ret = default_params(); | ||
216 | *ret = lightup_presets[i]; | ||
217 | *params = ret; | ||
218 | |||
219 | sprintf(buf, "%dx%d %s", | ||
220 | ret->w, ret->h, | ||
221 | ret->difficulty == 2 ? "hard" : | ||
222 | ret->difficulty == 1 ? "tricky" : "easy"); | ||
223 | *name = dupstr(buf); | ||
224 | |||
225 | return TRUE; | ||
226 | } | ||
227 | |||
228 | static void free_params(game_params *params) | ||
229 | { | ||
230 | sfree(params); | ||
231 | } | ||
232 | |||
233 | static game_params *dup_params(const game_params *params) | ||
234 | { | ||
235 | game_params *ret = snew(game_params); | ||
236 | *ret = *params; /* structure copy */ | ||
237 | return ret; | ||
238 | } | ||
239 | |||
240 | #define EATNUM(x) do { \ | ||
241 | (x) = atoi(string); \ | ||
242 | while (*string && isdigit((unsigned char)*string)) string++; \ | ||
243 | } while(0) | ||
244 | |||
245 | static void decode_params(game_params *params, char const *string) | ||
246 | { | ||
247 | EATNUM(params->w); | ||
248 | if (*string == 'x') { | ||
249 | string++; | ||
250 | EATNUM(params->h); | ||
251 | } | ||
252 | if (*string == 'b') { | ||
253 | string++; | ||
254 | EATNUM(params->blackpc); | ||
255 | } | ||
256 | if (*string == 's') { | ||
257 | string++; | ||
258 | EATNUM(params->symm); | ||
259 | } else { | ||
260 | /* cope with user input such as '18x10' by ensuring symmetry | ||
261 | * is not selected by default to be incompatible with dimensions */ | ||
262 | if (params->symm == SYMM_ROT4 && params->w != params->h) | ||
263 | params->symm = SYMM_ROT2; | ||
264 | } | ||
265 | params->difficulty = 0; | ||
266 | /* cope with old params */ | ||
267 | if (*string == 'r') { | ||
268 | params->difficulty = 2; | ||
269 | string++; | ||
270 | } | ||
271 | if (*string == 'd') { | ||
272 | string++; | ||
273 | EATNUM(params->difficulty); | ||
274 | } | ||
275 | } | ||
276 | |||
277 | static char *encode_params(const game_params *params, int full) | ||
278 | { | ||
279 | char buf[80]; | ||
280 | |||
281 | if (full) { | ||
282 | sprintf(buf, "%dx%db%ds%dd%d", | ||
283 | params->w, params->h, params->blackpc, | ||
284 | params->symm, | ||
285 | params->difficulty); | ||
286 | } else { | ||
287 | sprintf(buf, "%dx%d", params->w, params->h); | ||
288 | } | ||
289 | return dupstr(buf); | ||
290 | } | ||
291 | |||
292 | static config_item *game_configure(const game_params *params) | ||
293 | { | ||
294 | config_item *ret; | ||
295 | char buf[80]; | ||
296 | |||
297 | ret = snewn(6, config_item); | ||
298 | |||
299 | ret[0].name = "Width"; | ||
300 | ret[0].type = C_STRING; | ||
301 | sprintf(buf, "%d", params->w); | ||
302 | ret[0].sval = dupstr(buf); | ||
303 | ret[0].ival = 0; | ||
304 | |||
305 | ret[1].name = "Height"; | ||
306 | ret[1].type = C_STRING; | ||
307 | sprintf(buf, "%d", params->h); | ||
308 | ret[1].sval = dupstr(buf); | ||
309 | ret[1].ival = 0; | ||
310 | |||
311 | ret[2].name = "%age of black squares"; | ||
312 | ret[2].type = C_STRING; | ||
313 | sprintf(buf, "%d", params->blackpc); | ||
314 | ret[2].sval = dupstr(buf); | ||
315 | ret[2].ival = 0; | ||
316 | |||
317 | ret[3].name = "Symmetry"; | ||
318 | ret[3].type = C_CHOICES; | ||
319 | ret[3].sval = ":None" | ||
320 | ":2-way mirror:2-way rotational" | ||
321 | ":4-way mirror:4-way rotational"; | ||
322 | ret[3].ival = params->symm; | ||
323 | |||
324 | ret[4].name = "Difficulty"; | ||
325 | ret[4].type = C_CHOICES; | ||
326 | ret[4].sval = ":Easy:Tricky:Hard"; | ||
327 | ret[4].ival = params->difficulty; | ||
328 | |||
329 | ret[5].name = NULL; | ||
330 | ret[5].type = C_END; | ||
331 | ret[5].sval = NULL; | ||
332 | ret[5].ival = 0; | ||
333 | |||
334 | return ret; | ||
335 | } | ||
336 | |||
337 | static game_params *custom_params(const config_item *cfg) | ||
338 | { | ||
339 | game_params *ret = snew(game_params); | ||
340 | |||
341 | ret->w = atoi(cfg[0].sval); | ||
342 | ret->h = atoi(cfg[1].sval); | ||
343 | ret->blackpc = atoi(cfg[2].sval); | ||
344 | ret->symm = cfg[3].ival; | ||
345 | ret->difficulty = cfg[4].ival; | ||
346 | |||
347 | return ret; | ||
348 | } | ||
349 | |||
350 | static char *validate_params(const game_params *params, int full) | ||
351 | { | ||
352 | if (params->w < 2 || params->h < 2) | ||
353 | return "Width and height must be at least 2"; | ||
354 | if (full) { | ||
355 | if (params->blackpc < 5 || params->blackpc > 100) | ||
356 | return "Percentage of black squares must be between 5% and 100%"; | ||
357 | if (params->w != params->h) { | ||
358 | if (params->symm == SYMM_ROT4) | ||
359 | return "4-fold symmetry is only available with square grids"; | ||
360 | } | ||
361 | if (params->symm < 0 || params->symm >= SYMM_MAX) | ||
362 | return "Unknown symmetry type"; | ||
363 | if (params->difficulty < 0 || params->difficulty > DIFFCOUNT) | ||
364 | return "Unknown difficulty level"; | ||
365 | } | ||
366 | return NULL; | ||
367 | } | ||
368 | |||
369 | /* --- Game state construction/freeing helper functions --- */ | ||
370 | |||
371 | static game_state *new_state(const game_params *params) | ||
372 | { | ||
373 | game_state *ret = snew(game_state); | ||
374 | |||
375 | ret->w = params->w; | ||
376 | ret->h = params->h; | ||
377 | ret->lights = snewn(ret->w * ret->h, int); | ||
378 | ret->nlights = 0; | ||
379 | memset(ret->lights, 0, ret->w * ret->h * sizeof(int)); | ||
380 | ret->flags = snewn(ret->w * ret->h, unsigned int); | ||
381 | memset(ret->flags, 0, ret->w * ret->h * sizeof(unsigned int)); | ||
382 | ret->completed = ret->used_solve = 0; | ||
383 | return ret; | ||
384 | } | ||
385 | |||
386 | static game_state *dup_game(const game_state *state) | ||
387 | { | ||
388 | game_state *ret = snew(game_state); | ||
389 | |||
390 | ret->w = state->w; | ||
391 | ret->h = state->h; | ||
392 | |||
393 | ret->lights = snewn(ret->w * ret->h, int); | ||
394 | memcpy(ret->lights, state->lights, ret->w * ret->h * sizeof(int)); | ||
395 | ret->nlights = state->nlights; | ||
396 | |||
397 | ret->flags = snewn(ret->w * ret->h, unsigned int); | ||
398 | memcpy(ret->flags, state->flags, ret->w * ret->h * sizeof(unsigned int)); | ||
399 | |||
400 | ret->completed = state->completed; | ||
401 | ret->used_solve = state->used_solve; | ||
402 | |||
403 | return ret; | ||
404 | } | ||
405 | |||
406 | static void free_game(game_state *state) | ||
407 | { | ||
408 | sfree(state->lights); | ||
409 | sfree(state->flags); | ||
410 | sfree(state); | ||
411 | } | ||
412 | |||
413 | static void debug_state(game_state *state) | ||
414 | { | ||
415 | int x, y; | ||
416 | char c = '?'; | ||
417 | |||
418 | for (y = 0; y < state->h; y++) { | ||
419 | for (x = 0; x < state->w; x++) { | ||
420 | c = '.'; | ||
421 | if (GRID(state, flags, x, y) & F_BLACK) { | ||
422 | if (GRID(state, flags, x, y) & F_NUMBERED) | ||
423 | c = GRID(state, lights, x, y) + '0'; | ||
424 | else | ||
425 | c = '#'; | ||
426 | } else { | ||
427 | if (GRID(state, flags, x, y) & F_LIGHT) | ||
428 | c = 'O'; | ||
429 | else if (GRID(state, flags, x, y) & F_IMPOSSIBLE) | ||
430 | c = 'X'; | ||
431 | } | ||
432 | debug(("%c", (int)c)); | ||
433 | } | ||
434 | debug((" ")); | ||
435 | for (x = 0; x < state->w; x++) { | ||
436 | if (GRID(state, flags, x, y) & F_BLACK) | ||
437 | c = '#'; | ||
438 | else { | ||
439 | c = (GRID(state, flags, x, y) & F_LIGHT) ? 'A' : 'a'; | ||
440 | c += GRID(state, lights, x, y); | ||
441 | } | ||
442 | debug(("%c", (int)c)); | ||
443 | } | ||
444 | debug(("\n")); | ||
445 | } | ||
446 | } | ||
447 | |||
448 | /* --- Game completion test routines. --- */ | ||
449 | |||
450 | /* These are split up because occasionally functions are only | ||
451 | * interested in one particular aspect. */ | ||
452 | |||
453 | /* Returns non-zero if all grid spaces are lit. */ | ||
454 | static int grid_lit(game_state *state) | ||
455 | { | ||
456 | int x, y; | ||
457 | |||
458 | for (x = 0; x < state->w; x++) { | ||
459 | for (y = 0; y < state->h; y++) { | ||
460 | if (GRID(state,flags,x,y) & F_BLACK) continue; | ||
461 | if (GRID(state,lights,x,y) == 0) | ||
462 | return 0; | ||
463 | } | ||
464 | } | ||
465 | return 1; | ||
466 | } | ||
467 | |||
468 | /* Returns non-zero if any lights are lit by other lights. */ | ||
469 | static int grid_overlap(game_state *state) | ||
470 | { | ||
471 | int x, y; | ||
472 | |||
473 | for (x = 0; x < state->w; x++) { | ||
474 | for (y = 0; y < state->h; y++) { | ||
475 | if (!(GRID(state, flags, x, y) & F_LIGHT)) continue; | ||
476 | if (GRID(state, lights, x, y) > 1) | ||
477 | return 1; | ||
478 | } | ||
479 | } | ||
480 | return 0; | ||
481 | } | ||
482 | |||
483 | static int number_wrong(const game_state *state, int x, int y) | ||
484 | { | ||
485 | surrounds s; | ||
486 | int i, n, empty, lights = GRID(state, lights, x, y); | ||
487 | |||
488 | /* | ||
489 | * This function computes the display hint for a number: we | ||
490 | * turn the number red if it is definitely wrong. This means | ||
491 | * that either | ||
492 | * | ||
493 | * (a) it has too many lights around it, or | ||
494 | * (b) it would have too few lights around it even if all the | ||
495 | * plausible squares (not black, lit or F_IMPOSSIBLE) were | ||
496 | * filled with lights. | ||
497 | */ | ||
498 | |||
499 | assert(GRID(state, flags, x, y) & F_NUMBERED); | ||
500 | get_surrounds(state, x, y, &s); | ||
501 | |||
502 | empty = n = 0; | ||
503 | for (i = 0; i < s.npoints; i++) { | ||
504 | if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT) { | ||
505 | n++; | ||
506 | continue; | ||
507 | } | ||
508 | if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_BLACK) | ||
509 | continue; | ||
510 | if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_IMPOSSIBLE) | ||
511 | continue; | ||
512 | if (GRID(state,lights,s.points[i].x,s.points[i].y)) | ||
513 | continue; | ||
514 | empty++; | ||
515 | } | ||
516 | return (n > lights || (n + empty < lights)); | ||
517 | } | ||
518 | |||
519 | static int number_correct(game_state *state, int x, int y) | ||
520 | { | ||
521 | surrounds s; | ||
522 | int n = 0, i, lights = GRID(state, lights, x, y); | ||
523 | |||
524 | assert(GRID(state, flags, x, y) & F_NUMBERED); | ||
525 | get_surrounds(state, x, y, &s); | ||
526 | for (i = 0; i < s.npoints; i++) { | ||
527 | if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT) | ||
528 | n++; | ||
529 | } | ||
530 | return (n == lights) ? 1 : 0; | ||
531 | } | ||
532 | |||
533 | /* Returns non-zero if any numbers add up incorrectly. */ | ||
534 | static int grid_addsup(game_state *state) | ||
535 | { | ||
536 | int x, y; | ||
537 | |||
538 | for (x = 0; x < state->w; x++) { | ||
539 | for (y = 0; y < state->h; y++) { | ||
540 | if (!(GRID(state, flags, x, y) & F_NUMBERED)) continue; | ||
541 | if (!number_correct(state, x, y)) return 0; | ||
542 | } | ||
543 | } | ||
544 | return 1; | ||
545 | } | ||
546 | |||
547 | static int grid_correct(game_state *state) | ||
548 | { | ||
549 | if (grid_lit(state) && | ||
550 | !grid_overlap(state) && | ||
551 | grid_addsup(state)) return 1; | ||
552 | return 0; | ||
553 | } | ||
554 | |||
555 | /* --- Board initial setup (blacks, lights, numbers) --- */ | ||
556 | |||
557 | static void clean_board(game_state *state, int leave_blacks) | ||
558 | { | ||
559 | int x,y; | ||
560 | for (x = 0; x < state->w; x++) { | ||
561 | for (y = 0; y < state->h; y++) { | ||
562 | if (leave_blacks) | ||
563 | GRID(state, flags, x, y) &= F_BLACK; | ||
564 | else | ||
565 | GRID(state, flags, x, y) = 0; | ||
566 | GRID(state, lights, x, y) = 0; | ||
567 | } | ||
568 | } | ||
569 | state->nlights = 0; | ||
570 | } | ||
571 | |||
572 | static void set_blacks(game_state *state, const game_params *params, | ||
573 | random_state *rs) | ||
574 | { | ||
575 | int x, y, degree = 0, rotate = 0, nblack; | ||
576 | int rh, rw, i; | ||
577 | int wodd = (state->w % 2) ? 1 : 0; | ||
578 | int hodd = (state->h % 2) ? 1 : 0; | ||
579 | int xs[4], ys[4]; | ||
580 | |||
581 | switch (params->symm) { | ||
582 | case SYMM_NONE: degree = 1; rotate = 0; break; | ||
583 | case SYMM_ROT2: degree = 2; rotate = 1; break; | ||
584 | case SYMM_REF2: degree = 2; rotate = 0; break; | ||
585 | case SYMM_ROT4: degree = 4; rotate = 1; break; | ||
586 | case SYMM_REF4: degree = 4; rotate = 0; break; | ||
587 | default: assert(!"Unknown symmetry type"); | ||
588 | } | ||
589 | if (params->symm == SYMM_ROT4 && (state->h != state->w)) | ||
590 | assert(!"4-fold symmetry unavailable without square grid"); | ||
591 | |||
592 | if (degree == 4) { | ||
593 | rw = state->w/2; | ||
594 | rh = state->h/2; | ||
595 | if (!rotate) rw += wodd; /* ... but see below. */ | ||
596 | rh += hodd; | ||
597 | } else if (degree == 2) { | ||
598 | rw = state->w; | ||
599 | rh = state->h/2; | ||
600 | rh += hodd; | ||
601 | } else { | ||
602 | rw = state->w; | ||
603 | rh = state->h; | ||
604 | } | ||
605 | |||
606 | /* clear, then randomise, required region. */ | ||
607 | clean_board(state, 0); | ||
608 | nblack = (rw * rh * params->blackpc) / 100; | ||
609 | for (i = 0; i < nblack; i++) { | ||
610 | do { | ||
611 | x = random_upto(rs,rw); | ||
612 | y = random_upto(rs,rh); | ||
613 | } while (GRID(state,flags,x,y) & F_BLACK); | ||
614 | GRID(state, flags, x, y) |= F_BLACK; | ||
615 | } | ||
616 | |||
617 | /* Copy required region. */ | ||
618 | if (params->symm == SYMM_NONE) return; | ||
619 | |||
620 | for (x = 0; x < rw; x++) { | ||
621 | for (y = 0; y < rh; y++) { | ||
622 | if (degree == 4) { | ||
623 | xs[0] = x; | ||
624 | ys[0] = y; | ||
625 | xs[1] = state->w - 1 - (rotate ? y : x); | ||
626 | ys[1] = rotate ? x : y; | ||
627 | xs[2] = rotate ? (state->w - 1 - x) : x; | ||
628 | ys[2] = state->h - 1 - y; | ||
629 | xs[3] = rotate ? y : (state->w - 1 - x); | ||
630 | ys[3] = state->h - 1 - (rotate ? x : y); | ||
631 | } else { | ||
632 | xs[0] = x; | ||
633 | ys[0] = y; | ||
634 | xs[1] = rotate ? (state->w - 1 - x) : x; | ||
635 | ys[1] = state->h - 1 - y; | ||
636 | } | ||
637 | for (i = 1; i < degree; i++) { | ||
638 | GRID(state, flags, xs[i], ys[i]) = | ||
639 | GRID(state, flags, xs[0], ys[0]); | ||
640 | } | ||
641 | } | ||
642 | } | ||
643 | /* SYMM_ROT4 misses the middle square above; fix that here. */ | ||
644 | if (degree == 4 && rotate && wodd && | ||
645 | (random_upto(rs,100) <= (unsigned int)params->blackpc)) | ||
646 | GRID(state,flags, | ||
647 | state->w/2 + wodd - 1, state->h/2 + hodd - 1) |= F_BLACK; | ||
648 | |||
649 | #ifdef SOLVER_DIAGNOSTICS | ||
650 | if (verbose) debug_state(state); | ||
651 | #endif | ||
652 | } | ||
653 | |||
654 | /* Fills in (does not allocate) a ll_data with all the tiles that would | ||
655 | * be illuminated by a light at point (ox,oy). If origin=1 then the | ||
656 | * origin is included in this list. */ | ||
657 | static void list_lights(game_state *state, int ox, int oy, int origin, | ||
658 | ll_data *lld) | ||
659 | { | ||
660 | int x,y; | ||
661 | |||
662 | lld->ox = lld->minx = lld->maxx = ox; | ||
663 | lld->oy = lld->miny = lld->maxy = oy; | ||
664 | lld->include_origin = origin; | ||
665 | |||
666 | y = oy; | ||
667 | for (x = ox-1; x >= 0; x--) { | ||
668 | if (GRID(state, flags, x, y) & F_BLACK) break; | ||
669 | if (x < lld->minx) lld->minx = x; | ||
670 | } | ||
671 | for (x = ox+1; x < state->w; x++) { | ||
672 | if (GRID(state, flags, x, y) & F_BLACK) break; | ||
673 | if (x > lld->maxx) lld->maxx = x; | ||
674 | } | ||
675 | |||
676 | x = ox; | ||
677 | for (y = oy-1; y >= 0; y--) { | ||
678 | if (GRID(state, flags, x, y) & F_BLACK) break; | ||
679 | if (y < lld->miny) lld->miny = y; | ||
680 | } | ||
681 | for (y = oy+1; y < state->h; y++) { | ||
682 | if (GRID(state, flags, x, y) & F_BLACK) break; | ||
683 | if (y > lld->maxy) lld->maxy = y; | ||
684 | } | ||
685 | } | ||
686 | |||
687 | /* Makes sure a light is the given state, editing the lights table to suit the | ||
688 | * new state if necessary. */ | ||
689 | static void set_light(game_state *state, int ox, int oy, int on) | ||
690 | { | ||
691 | ll_data lld; | ||
692 | int diff = 0; | ||
693 | |||
694 | assert(!(GRID(state,flags,ox,oy) & F_BLACK)); | ||
695 | |||
696 | if (!on && GRID(state,flags,ox,oy) & F_LIGHT) { | ||
697 | diff = -1; | ||
698 | GRID(state,flags,ox,oy) &= ~F_LIGHT; | ||
699 | state->nlights--; | ||
700 | } else if (on && !(GRID(state,flags,ox,oy) & F_LIGHT)) { | ||
701 | diff = 1; | ||
702 | GRID(state,flags,ox,oy) |= F_LIGHT; | ||
703 | state->nlights++; | ||
704 | } | ||
705 | |||
706 | if (diff != 0) { | ||
707 | list_lights(state,ox,oy,1,&lld); | ||
708 | FOREACHLIT(&lld, GRID(state,lights,lx,ly) += diff; ); | ||
709 | } | ||
710 | } | ||
711 | |||
712 | /* Returns 1 if removing a light at (x,y) would cause a square to go dark. */ | ||
713 | static int check_dark(game_state *state, int x, int y) | ||
714 | { | ||
715 | ll_data lld; | ||
716 | |||
717 | list_lights(state, x, y, 1, &lld); | ||
718 | FOREACHLIT(&lld, if (GRID(state,lights,lx,ly) == 1) { return 1; } ); | ||
719 | return 0; | ||
720 | } | ||
721 | |||
722 | /* Sets up an initial random correct position (i.e. every | ||
723 | * space lit, and no lights lit by other lights) by filling the | ||
724 | * grid with lights and then removing lights one by one at random. */ | ||
725 | static void place_lights(game_state *state, random_state *rs) | ||
726 | { | ||
727 | int i, x, y, n, *numindices, wh = state->w*state->h; | ||
728 | ll_data lld; | ||
729 | |||
730 | numindices = snewn(wh, int); | ||
731 | for (i = 0; i < wh; i++) numindices[i] = i; | ||
732 | shuffle(numindices, wh, sizeof(*numindices), rs); | ||
733 | |||
734 | /* Place a light on all grid squares without lights. */ | ||
735 | for (x = 0; x < state->w; x++) { | ||
736 | for (y = 0; y < state->h; y++) { | ||
737 | GRID(state, flags, x, y) &= ~F_MARK; /* we use this later. */ | ||
738 | if (GRID(state, flags, x, y) & F_BLACK) continue; | ||
739 | set_light(state, x, y, 1); | ||
740 | } | ||
741 | } | ||
742 | |||
743 | for (i = 0; i < wh; i++) { | ||
744 | y = numindices[i] / state->w; | ||
745 | x = numindices[i] % state->w; | ||
746 | if (!(GRID(state, flags, x, y) & F_LIGHT)) continue; | ||
747 | if (GRID(state, flags, x, y) & F_MARK) continue; | ||
748 | list_lights(state, x, y, 0, &lld); | ||
749 | |||
750 | /* If we're not lighting any lights ourself, don't remove anything. */ | ||
751 | n = 0; | ||
752 | FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += 1; } ); | ||
753 | if (n == 0) continue; /* [1] */ | ||
754 | |||
755 | /* Check whether removing lights we're lighting would cause anything | ||
756 | * to go dark. */ | ||
757 | n = 0; | ||
758 | FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += check_dark(state,lx,ly); } ); | ||
759 | if (n == 0) { | ||
760 | /* No, it wouldn't, so we can remove them all. */ | ||
761 | FOREACHLIT(&lld, set_light(state,lx,ly, 0); ); | ||
762 | GRID(state,flags,x,y) |= F_MARK; | ||
763 | } | ||
764 | |||
765 | if (!grid_overlap(state)) { | ||
766 | sfree(numindices); | ||
767 | return; /* we're done. */ | ||
768 | } | ||
769 | assert(grid_lit(state)); | ||
770 | } | ||
771 | /* could get here if the line at [1] continue'd out of the loop. */ | ||
772 | if (grid_overlap(state)) { | ||
773 | debug_state(state); | ||
774 | assert(!"place_lights failed to resolve overlapping lights!"); | ||
775 | } | ||
776 | sfree(numindices); | ||
777 | } | ||
778 | |||
779 | /* Fills in all black squares with numbers of adjacent lights. */ | ||
780 | static void place_numbers(game_state *state) | ||
781 | { | ||
782 | int x, y, i, n; | ||
783 | surrounds s; | ||
784 | |||
785 | for (x = 0; x < state->w; x++) { | ||
786 | for (y = 0; y < state->h; y++) { | ||
787 | if (!(GRID(state,flags,x,y) & F_BLACK)) continue; | ||
788 | get_surrounds(state, x, y, &s); | ||
789 | n = 0; | ||
790 | for (i = 0; i < s.npoints; i++) { | ||
791 | if (GRID(state,flags,s.points[i].x, s.points[i].y) & F_LIGHT) | ||
792 | n++; | ||
793 | } | ||
794 | GRID(state,flags,x,y) |= F_NUMBERED; | ||
795 | GRID(state,lights,x,y) = n; | ||
796 | } | ||
797 | } | ||
798 | } | ||
799 | |||
800 | /* --- Actual solver, with helper subroutines. --- */ | ||
801 | |||
802 | static void tsl_callback(game_state *state, | ||
803 | int lx, int ly, int *x, int *y, int *n) | ||
804 | { | ||
805 | if (GRID(state,flags,lx,ly) & F_IMPOSSIBLE) return; | ||
806 | if (GRID(state,lights,lx,ly) > 0) return; | ||
807 | *x = lx; *y = ly; (*n)++; | ||
808 | } | ||
809 | |||
810 | static int try_solve_light(game_state *state, int ox, int oy, | ||
811 | unsigned int flags, int lights) | ||
812 | { | ||
813 | ll_data lld; | ||
814 | int sx = 0, sy = 0, n = 0; | ||
815 | |||
816 | if (lights > 0) return 0; | ||
817 | if (flags & F_BLACK) return 0; | ||
818 | |||
819 | /* We have an unlit square; count how many ways there are left to | ||
820 | * place a light that lights us (including this square); if only | ||
821 | * one, we must put a light there. Squares that could light us | ||
822 | * are, of course, the same as the squares we would light... */ | ||
823 | list_lights(state, ox, oy, 1, &lld); | ||
824 | FOREACHLIT(&lld, { tsl_callback(state, lx, ly, &sx, &sy, &n); }); | ||
825 | if (n == 1) { | ||
826 | set_light(state, sx, sy, 1); | ||
827 | #ifdef SOLVER_DIAGNOSTICS | ||
828 | debug(("(%d,%d) can only be lit from (%d,%d); setting to LIGHT\n", | ||
829 | ox,oy,sx,sy)); | ||
830 | if (verbose) debug_state(state); | ||
831 | #endif | ||
832 | return 1; | ||
833 | } | ||
834 | |||
835 | return 0; | ||
836 | } | ||
837 | |||
838 | static int could_place_light(unsigned int flags, int lights) | ||
839 | { | ||
840 | if (flags & (F_BLACK | F_IMPOSSIBLE)) return 0; | ||
841 | return (lights > 0) ? 0 : 1; | ||
842 | } | ||
843 | |||
844 | static int could_place_light_xy(game_state *state, int x, int y) | ||
845 | { | ||
846 | int lights = GRID(state,lights,x,y); | ||
847 | unsigned int flags = GRID(state,flags,x,y); | ||
848 | return (could_place_light(flags, lights)) ? 1 : 0; | ||
849 | } | ||
850 | |||
851 | /* For a given number square, determine whether we have enough info | ||
852 | * to unambiguously place its lights. */ | ||
853 | static int try_solve_number(game_state *state, int nx, int ny, | ||
854 | unsigned int nflags, int nlights) | ||
855 | { | ||
856 | surrounds s; | ||
857 | int x, y, nl, ns, i, ret = 0, lights; | ||
858 | unsigned int flags; | ||
859 | |||
860 | if (!(nflags & F_NUMBERED)) return 0; | ||
861 | nl = nlights; | ||
862 | get_surrounds(state,nx,ny,&s); | ||
863 | ns = s.npoints; | ||
864 | |||
865 | /* nl is no. of lights we need to place, ns is no. of spaces we | ||
866 | * have to place them in. Try and narrow these down, and mark | ||
867 | * points we can ignore later. */ | ||
868 | for (i = 0; i < s.npoints; i++) { | ||
869 | x = s.points[i].x; y = s.points[i].y; | ||
870 | flags = GRID(state,flags,x,y); | ||
871 | lights = GRID(state,lights,x,y); | ||
872 | if (flags & F_LIGHT) { | ||
873 | /* light here already; one less light for one less place. */ | ||
874 | nl--; ns--; | ||
875 | s.points[i].f |= F_MARK; | ||
876 | } else if (!could_place_light(flags, lights)) { | ||
877 | ns--; | ||
878 | s.points[i].f |= F_MARK; | ||
879 | } | ||
880 | } | ||
881 | if (ns == 0) return 0; /* nowhere to put anything. */ | ||
882 | if (nl == 0) { | ||
883 | /* we have placed all lights we need to around here; all remaining | ||
884 | * surrounds are therefore IMPOSSIBLE. */ | ||
885 | GRID(state,flags,nx,ny) |= F_NUMBERUSED; | ||
886 | for (i = 0; i < s.npoints; i++) { | ||
887 | if (!(s.points[i].f & F_MARK)) { | ||
888 | GRID(state,flags,s.points[i].x,s.points[i].y) |= F_IMPOSSIBLE; | ||
889 | ret = 1; | ||
890 | } | ||
891 | } | ||
892 | #ifdef SOLVER_DIAGNOSTICS | ||
893 | printf("Clue at (%d,%d) full; setting unlit to IMPOSSIBLE.\n", | ||
894 | nx,ny); | ||
895 | if (verbose) debug_state(state); | ||
896 | #endif | ||
897 | } else if (nl == ns) { | ||
898 | /* we have as many lights to place as spaces; fill them all. */ | ||
899 | GRID(state,flags,nx,ny) |= F_NUMBERUSED; | ||
900 | for (i = 0; i < s.npoints; i++) { | ||
901 | if (!(s.points[i].f & F_MARK)) { | ||
902 | set_light(state, s.points[i].x,s.points[i].y, 1); | ||
903 | ret = 1; | ||
904 | } | ||
905 | } | ||
906 | #ifdef SOLVER_DIAGNOSTICS | ||
907 | printf("Clue at (%d,%d) trivial; setting unlit to LIGHT.\n", | ||
908 | nx,ny); | ||
909 | if (verbose) debug_state(state); | ||
910 | #endif | ||
911 | } | ||
912 | return ret; | ||
913 | } | ||
914 | |||
915 | struct setscratch { | ||
916 | int x, y; | ||
917 | int n; | ||
918 | }; | ||
919 | |||
920 | #define SCRATCHSZ (state->w+state->h) | ||
921 | |||
922 | /* New solver algorithm: overlapping sets can add IMPOSSIBLE flags. | ||
923 | * Algorithm thanks to Simon: | ||
924 | * | ||
925 | * (a) Any square where you can place a light has a set of squares | ||
926 | * which would become non-lights as a result. (This includes | ||
927 | * squares lit by the first square, and can also include squares | ||
928 | * adjacent to the same clue square if the new light is the last | ||
929 | * one around that clue.) Call this MAKESDARK(x,y) with (x,y) being | ||
930 | * the square you place a light. | ||
931 | |||
932 | * (b) Any unlit square has a set of squares on which you could place | ||
933 | * a light to illuminate it. (Possibly including itself, of | ||
934 | * course.) This set of squares has the property that _at least | ||
935 | * one_ of them must contain a light. Sets of this type also arise | ||
936 | * from clue squares. Call this MAKESLIGHT(x,y), again with (x,y) | ||
937 | * the square you would place a light. | ||
938 | |||
939 | * (c) If there exists (dx,dy) and (lx,ly) such that MAKESDARK(dx,dy) is | ||
940 | * a superset of MAKESLIGHT(lx,ly), this implies that placing a light at | ||
941 | * (dx,dy) would either leave no remaining way to illuminate a certain | ||
942 | * square, or would leave no remaining way to fulfill a certain clue | ||
943 | * (at lx,ly). In either case, a light can be ruled out at that position. | ||
944 | * | ||
945 | * So, we construct all possible MAKESLIGHT sets, both from unlit squares | ||
946 | * and clue squares, and then we look for plausible MAKESDARK sets that include | ||
947 | * our (lx,ly) to see if we can find a (dx,dy) to rule out. By the time we have | ||
948 | * constructed the MAKESLIGHT set we don't care about (lx,ly), just the set | ||
949 | * members. | ||
950 | * | ||
951 | * Once we have such a set, Simon came up with a Cunning Plan to find | ||
952 | * the most sensible MAKESDARK candidate: | ||
953 | * | ||
954 | * (a) for each square S in your set X, find all the squares which _would_ | ||
955 | * rule it out. That means any square which would light S, plus | ||
956 | * any square adjacent to the same clue square as S (provided | ||
957 | * that clue square has only one remaining light to be placed). | ||
958 | * It's not hard to make this list. Don't do anything with this | ||
959 | * data at the moment except _count_ the squares. | ||
960 | |||
961 | * (b) Find the square S_min in the original set which has the | ||
962 | * _smallest_ number of other squares which would rule it out. | ||
963 | |||
964 | * (c) Find all the squares that rule out S_min (it's probably | ||
965 | * better to recompute this than to have stored it during step | ||
966 | * (a), since the CPU requirement is modest but the storage | ||
967 | * cost would get ugly.) For each of these squares, see if it | ||
968 | * rules out everything else in the set X. Any which does can | ||
969 | * be marked as not-a-light. | ||
970 | * | ||
971 | */ | ||
972 | |||
973 | typedef void (*trl_cb)(game_state *state, int dx, int dy, | ||
974 | struct setscratch *scratch, int n, void *ctx); | ||
975 | |||
976 | static void try_rule_out(game_state *state, int x, int y, | ||
977 | struct setscratch *scratch, int n, | ||
978 | trl_cb cb, void *ctx); | ||
979 | |||
980 | static void trl_callback_search(game_state *state, int dx, int dy, | ||
981 | struct setscratch *scratch, int n, void *ignored) | ||
982 | { | ||
983 | int i; | ||
984 | |||
985 | #ifdef SOLVER_DIAGNOSTICS | ||
986 | if (verbose) debug(("discount cb: light at (%d,%d)\n", dx, dy)); | ||
987 | #endif | ||
988 | |||
989 | for (i = 0; i < n; i++) { | ||
990 | if (dx == scratch[i].x && dy == scratch[i].y) { | ||
991 | scratch[i].n = 1; | ||
992 | return; | ||
993 | } | ||
994 | } | ||
995 | } | ||
996 | |||
997 | static void trl_callback_discount(game_state *state, int dx, int dy, | ||
998 | struct setscratch *scratch, int n, void *ctx) | ||
999 | { | ||
1000 | int *didsth = (int *)ctx; | ||
1001 | int i; | ||
1002 | |||
1003 | if (GRID(state,flags,dx,dy) & F_IMPOSSIBLE) { | ||
1004 | #ifdef SOLVER_DIAGNOSTICS | ||
1005 | debug(("Square at (%d,%d) already impossible.\n", dx,dy)); | ||
1006 | #endif | ||
1007 | return; | ||
1008 | } | ||
1009 | |||
1010 | /* Check whether a light at (dx,dy) rules out everything | ||
1011 | * in scratch, and mark (dx,dy) as IMPOSSIBLE if it does. | ||
1012 | * We can use try_rule_out for this as well, as the set of | ||
1013 | * squares which would rule out (x,y) is the same as the | ||
1014 | * set of squares which (x,y) would rule out. */ | ||
1015 | |||
1016 | #ifdef SOLVER_DIAGNOSTICS | ||
1017 | if (verbose) debug(("Checking whether light at (%d,%d) rules out everything in scratch.\n", dx, dy)); | ||
1018 | #endif | ||
1019 | |||
1020 | for (i = 0; i < n; i++) | ||
1021 | scratch[i].n = 0; | ||
1022 | try_rule_out(state, dx, dy, scratch, n, trl_callback_search, NULL); | ||
1023 | for (i = 0; i < n; i++) { | ||
1024 | if (scratch[i].n == 0) return; | ||
1025 | } | ||
1026 | /* The light ruled out everything in scratch. Yay. */ | ||
1027 | GRID(state,flags,dx,dy) |= F_IMPOSSIBLE; | ||
1028 | #ifdef SOLVER_DIAGNOSTICS | ||
1029 | debug(("Set reduction discounted square at (%d,%d):\n", dx,dy)); | ||
1030 | if (verbose) debug_state(state); | ||
1031 | #endif | ||
1032 | |||
1033 | *didsth = 1; | ||
1034 | } | ||
1035 | |||
1036 | static void trl_callback_incn(game_state *state, int dx, int dy, | ||
1037 | struct setscratch *scratch, int n, void *ctx) | ||
1038 | { | ||
1039 | struct setscratch *s = (struct setscratch *)ctx; | ||
1040 | s->n++; | ||
1041 | } | ||
1042 | |||
1043 | static void try_rule_out(game_state *state, int x, int y, | ||
1044 | struct setscratch *scratch, int n, | ||
1045 | trl_cb cb, void *ctx) | ||
1046 | { | ||
1047 | /* XXX Find all the squares which would rule out (x,y); anything | ||
1048 | * that would light it as well as squares adjacent to same clues | ||
1049 | * as X assuming that clue only has one remaining light. | ||
1050 | * Call the callback with each square. */ | ||
1051 | ll_data lld; | ||
1052 | surrounds s, ss; | ||
1053 | int i, j, curr_lights, tot_lights; | ||
1054 | |||
1055 | /* Find all squares that would rule out a light at (x,y) and call trl_cb | ||
1056 | * with them: anything that would light (x,y)... */ | ||
1057 | |||
1058 | list_lights(state, x, y, 0, &lld); | ||
1059 | FOREACHLIT(&lld, { if (could_place_light_xy(state, lx, ly)) { cb(state, lx, ly, scratch, n, ctx); } }); | ||
1060 | |||
1061 | /* ... as well as any empty space (that isn't x,y) next to any clue square | ||
1062 | * next to (x,y) that only has one light left to place. */ | ||
1063 | |||
1064 | get_surrounds(state, x, y, &s); | ||
1065 | for (i = 0; i < s.npoints; i++) { | ||
1066 | if (!(GRID(state,flags,s.points[i].x,s.points[i].y) & F_NUMBERED)) | ||
1067 | continue; | ||
1068 | /* we have an adjacent clue square; find /its/ surrounds | ||
1069 | * and count the remaining lights it needs. */ | ||
1070 | get_surrounds(state,s.points[i].x,s.points[i].y,&ss); | ||
1071 | curr_lights = 0; | ||
1072 | for (j = 0; j < ss.npoints; j++) { | ||
1073 | if (GRID(state,flags,ss.points[j].x,ss.points[j].y) & F_LIGHT) | ||
1074 | curr_lights++; | ||
1075 | } | ||
1076 | tot_lights = GRID(state, lights, s.points[i].x, s.points[i].y); | ||
1077 | /* We have a clue with tot_lights to fill, and curr_lights currently | ||
1078 | * around it. If adding a light at (x,y) fills up the clue (i.e. | ||
1079 | * curr_lights + 1 = tot_lights) then we need to discount all other | ||
1080 | * unlit squares around the clue. */ | ||
1081 | if ((curr_lights + 1) == tot_lights) { | ||
1082 | for (j = 0; j < ss.npoints; j++) { | ||
1083 | int lx = ss.points[j].x, ly = ss.points[j].y; | ||
1084 | if (lx == x && ly == y) continue; | ||
1085 | if (could_place_light_xy(state, lx, ly)) | ||
1086 | cb(state, lx, ly, scratch, n, ctx); | ||
1087 | } | ||
1088 | } | ||
1089 | } | ||
1090 | } | ||
1091 | |||
1092 | #ifdef SOLVER_DIAGNOSTICS | ||
1093 | static void debug_scratch(const char *msg, struct setscratch *scratch, int n) | ||
1094 | { | ||
1095 | int i; | ||
1096 | debug(("%s scratch (%d elements):\n", msg, n)); | ||
1097 | for (i = 0; i < n; i++) { | ||
1098 | debug((" (%d,%d) n%d\n", scratch[i].x, scratch[i].y, scratch[i].n)); | ||
1099 | } | ||
1100 | } | ||
1101 | #endif | ||
1102 | |||
1103 | static int discount_set(game_state *state, | ||
1104 | struct setscratch *scratch, int n) | ||
1105 | { | ||
1106 | int i, besti, bestn, didsth = 0; | ||
1107 | |||
1108 | #ifdef SOLVER_DIAGNOSTICS | ||
1109 | if (verbose > 1) debug_scratch("discount_set", scratch, n); | ||
1110 | #endif | ||
1111 | if (n == 0) return 0; | ||
1112 | |||
1113 | for (i = 0; i < n; i++) { | ||
1114 | try_rule_out(state, scratch[i].x, scratch[i].y, scratch, n, | ||
1115 | trl_callback_incn, (void*)&(scratch[i])); | ||
1116 | } | ||
1117 | #ifdef SOLVER_DIAGNOSTICS | ||
1118 | if (verbose > 1) debug_scratch("discount_set after count", scratch, n); | ||
1119 | #endif | ||
1120 | |||
1121 | besti = -1; bestn = SCRATCHSZ; | ||
1122 | for (i = 0; i < n; i++) { | ||
1123 | if (scratch[i].n < bestn) { | ||
1124 | bestn = scratch[i].n; | ||
1125 | besti = i; | ||
1126 | } | ||
1127 | } | ||
1128 | #ifdef SOLVER_DIAGNOSTICS | ||
1129 | if (verbose > 1) debug(("best square (%d,%d) with n%d.\n", | ||
1130 | scratch[besti].x, scratch[besti].y, scratch[besti].n)); | ||
1131 | #endif | ||
1132 | try_rule_out(state, scratch[besti].x, scratch[besti].y, scratch, n, | ||
1133 | trl_callback_discount, (void*)&didsth); | ||
1134 | #ifdef SOLVER_DIAGNOSTICS | ||
1135 | if (didsth) debug((" [from square (%d,%d)]\n", | ||
1136 | scratch[besti].x, scratch[besti].y)); | ||
1137 | #endif | ||
1138 | |||
1139 | return didsth; | ||
1140 | } | ||
1141 | |||
1142 | static void discount_clear(game_state *state, struct setscratch *scratch, int *n) | ||
1143 | { | ||
1144 | *n = 0; | ||
1145 | memset(scratch, 0, SCRATCHSZ * sizeof(struct setscratch)); | ||
1146 | } | ||
1147 | |||
1148 | static void unlit_cb(game_state *state, int lx, int ly, | ||
1149 | struct setscratch *scratch, int *n) | ||
1150 | { | ||
1151 | if (could_place_light_xy(state, lx, ly)) { | ||
1152 | scratch[*n].x = lx; scratch[*n].y = ly; (*n)++; | ||
1153 | } | ||
1154 | } | ||
1155 | |||
1156 | /* Construct a MAKESLIGHT set from an unlit square. */ | ||
1157 | static int discount_unlit(game_state *state, int x, int y, | ||
1158 | struct setscratch *scratch) | ||
1159 | { | ||
1160 | ll_data lld; | ||
1161 | int n, didsth; | ||
1162 | |||
1163 | #ifdef SOLVER_DIAGNOSTICS | ||
1164 | if (verbose) debug(("Trying to discount for unlit square at (%d,%d).\n", x, y)); | ||
1165 | if (verbose > 1) debug_state(state); | ||
1166 | #endif | ||
1167 | |||
1168 | discount_clear(state, scratch, &n); | ||
1169 | |||
1170 | list_lights(state, x, y, 1, &lld); | ||
1171 | FOREACHLIT(&lld, { unlit_cb(state, lx, ly, scratch, &n); }); | ||
1172 | didsth = discount_set(state, scratch, n); | ||
1173 | #ifdef SOLVER_DIAGNOSTICS | ||
1174 | if (didsth) debug((" [from unlit square at (%d,%d)].\n", x, y)); | ||
1175 | #endif | ||
1176 | return didsth; | ||
1177 | |||
1178 | } | ||
1179 | |||
1180 | /* Construct a series of MAKESLIGHT sets from a clue square. | ||
1181 | * for a clue square with N remaining spaces that must contain M lights, every | ||
1182 | * subset of size N-M+1 of those N spaces forms such a set. | ||
1183 | */ | ||
1184 | |||
1185 | static int discount_clue(game_state *state, int x, int y, | ||
1186 | struct setscratch *scratch) | ||
1187 | { | ||
1188 | int slen, m = GRID(state, lights, x, y), n, i, didsth = 0, lights; | ||
1189 | unsigned int flags; | ||
1190 | surrounds s, sempty; | ||
1191 | combi_ctx *combi; | ||
1192 | |||
1193 | if (m == 0) return 0; | ||
1194 | |||
1195 | #ifdef SOLVER_DIAGNOSTICS | ||
1196 | if (verbose) debug(("Trying to discount for sets at clue (%d,%d).\n", x, y)); | ||
1197 | if (verbose > 1) debug_state(state); | ||
1198 | #endif | ||
1199 | |||
1200 | /* m is no. of lights still to place; starts off at the clue value | ||
1201 | * and decreases when we find a light already down. | ||
1202 | * n is no. of spaces left; starts off at 0 and goes up when we find | ||
1203 | * a plausible space. */ | ||
1204 | |||
1205 | get_surrounds(state, x, y, &s); | ||
1206 | memset(&sempty, 0, sizeof(surrounds)); | ||
1207 | for (i = 0; i < s.npoints; i++) { | ||
1208 | int lx = s.points[i].x, ly = s.points[i].y; | ||
1209 | flags = GRID(state,flags,lx,ly); | ||
1210 | lights = GRID(state,lights,lx,ly); | ||
1211 | |||
1212 | if (flags & F_LIGHT) m--; | ||
1213 | |||
1214 | if (could_place_light(flags, lights)) { | ||
1215 | sempty.points[sempty.npoints].x = lx; | ||
1216 | sempty.points[sempty.npoints].y = ly; | ||
1217 | sempty.npoints++; | ||
1218 | } | ||
1219 | } | ||
1220 | n = sempty.npoints; /* sempty is now a surrounds of only blank squares. */ | ||
1221 | if (n == 0) return 0; /* clue is full already. */ | ||
1222 | |||
1223 | if (m < 0 || m > n) return 0; /* become impossible. */ | ||
1224 | |||
1225 | combi = new_combi(n - m + 1, n); | ||
1226 | while (next_combi(combi)) { | ||
1227 | discount_clear(state, scratch, &slen); | ||
1228 | for (i = 0; i < combi->r; i++) { | ||
1229 | scratch[slen].x = sempty.points[combi->a[i]].x; | ||
1230 | scratch[slen].y = sempty.points[combi->a[i]].y; | ||
1231 | slen++; | ||
1232 | } | ||
1233 | if (discount_set(state, scratch, slen)) didsth = 1; | ||
1234 | } | ||
1235 | free_combi(combi); | ||
1236 | #ifdef SOLVER_DIAGNOSTICS | ||
1237 | if (didsth) debug((" [from clue at (%d,%d)].\n", x, y)); | ||
1238 | #endif | ||
1239 | return didsth; | ||
1240 | } | ||
1241 | |||
1242 | #define F_SOLVE_FORCEUNIQUE 1 | ||
1243 | #define F_SOLVE_DISCOUNTSETS 2 | ||
1244 | #define F_SOLVE_ALLOWRECURSE 4 | ||
1245 | |||
1246 | static unsigned int flags_from_difficulty(int difficulty) | ||
1247 | { | ||
1248 | unsigned int sflags = F_SOLVE_FORCEUNIQUE; | ||
1249 | assert(difficulty <= DIFFCOUNT); | ||
1250 | if (difficulty >= 1) sflags |= F_SOLVE_DISCOUNTSETS; | ||
1251 | if (difficulty >= 2) sflags |= F_SOLVE_ALLOWRECURSE; | ||
1252 | return sflags; | ||
1253 | } | ||
1254 | |||
1255 | #define MAXRECURSE 5 | ||
1256 | |||
1257 | static int solve_sub(game_state *state, | ||
1258 | unsigned int solve_flags, int depth, | ||
1259 | int *maxdepth) | ||
1260 | { | ||
1261 | unsigned int flags; | ||
1262 | int x, y, didstuff, ncanplace, lights; | ||
1263 | int bestx, besty, n, bestn, copy_soluble, self_soluble, ret, maxrecurse = 0; | ||
1264 | game_state *scopy; | ||
1265 | ll_data lld; | ||
1266 | struct setscratch *sscratch = NULL; | ||
1267 | |||
1268 | #ifdef SOLVER_DIAGNOSTICS | ||
1269 | printf("solve_sub: depth = %d\n", depth); | ||
1270 | #endif | ||
1271 | if (maxdepth && *maxdepth < depth) *maxdepth = depth; | ||
1272 | if (solve_flags & F_SOLVE_ALLOWRECURSE) maxrecurse = MAXRECURSE; | ||
1273 | |||
1274 | while (1) { | ||
1275 | if (grid_overlap(state)) { | ||
1276 | /* Our own solver, from scratch, should never cause this to happen | ||
1277 | * (assuming a soluble grid). However, if we're trying to solve | ||
1278 | * from a half-completed *incorrect* grid this might occur; we | ||
1279 | * just return the 'no solutions' code in this case. */ | ||
1280 | ret = 0; goto done; | ||
1281 | } | ||
1282 | |||
1283 | if (grid_correct(state)) { ret = 1; goto done; } | ||
1284 | |||
1285 | ncanplace = 0; | ||
1286 | didstuff = 0; | ||
1287 | /* These 2 loops, and the functions they call, are the critical loops | ||
1288 | * for timing; any optimisations should look here first. */ | ||
1289 | for (x = 0; x < state->w; x++) { | ||
1290 | for (y = 0; y < state->h; y++) { | ||
1291 | flags = GRID(state,flags,x,y); | ||
1292 | lights = GRID(state,lights,x,y); | ||
1293 | ncanplace += could_place_light(flags, lights); | ||
1294 | |||
1295 | if (try_solve_light(state, x, y, flags, lights)) didstuff = 1; | ||
1296 | if (try_solve_number(state, x, y, flags, lights)) didstuff = 1; | ||
1297 | } | ||
1298 | } | ||
1299 | if (didstuff) continue; | ||
1300 | if (!ncanplace) { | ||
1301 | /* nowhere to put a light, puzzle is unsoluble. */ | ||
1302 | ret = 0; goto done; | ||
1303 | } | ||
1304 | |||
1305 | if (solve_flags & F_SOLVE_DISCOUNTSETS) { | ||
1306 | if (!sscratch) sscratch = snewn(SCRATCHSZ, struct setscratch); | ||
1307 | /* Try a more cunning (and more involved) way... more details above. */ | ||
1308 | for (x = 0; x < state->w; x++) { | ||
1309 | for (y = 0; y < state->h; y++) { | ||
1310 | flags = GRID(state,flags,x,y); | ||
1311 | lights = GRID(state,lights,x,y); | ||
1312 | |||
1313 | if (!(flags & F_BLACK) && lights == 0) { | ||
1314 | if (discount_unlit(state, x, y, sscratch)) { | ||
1315 | didstuff = 1; | ||
1316 | goto reduction_success; | ||
1317 | } | ||
1318 | } else if (flags & F_NUMBERED) { | ||
1319 | if (discount_clue(state, x, y, sscratch)) { | ||
1320 | didstuff = 1; | ||
1321 | goto reduction_success; | ||
1322 | } | ||
1323 | } | ||
1324 | } | ||
1325 | } | ||
1326 | } | ||
1327 | reduction_success: | ||
1328 | if (didstuff) continue; | ||
1329 | |||
1330 | /* We now have to make a guess; we have places to put lights but | ||
1331 | * no definite idea about where they can go. */ | ||
1332 | if (depth >= maxrecurse) { | ||
1333 | /* mustn't delve any deeper. */ | ||
1334 | ret = -1; goto done; | ||
1335 | } | ||
1336 | /* Of all the squares that we could place a light, pick the one | ||
1337 | * that would light the most currently unlit squares. */ | ||
1338 | /* This heuristic was just plucked from the air; there may well be | ||
1339 | * a more efficient way of choosing a square to flip to minimise | ||
1340 | * recursion. */ | ||
1341 | bestn = 0; | ||
1342 | bestx = besty = -1; /* suyb */ | ||
1343 | for (x = 0; x < state->w; x++) { | ||
1344 | for (y = 0; y < state->h; y++) { | ||
1345 | flags = GRID(state,flags,x,y); | ||
1346 | lights = GRID(state,lights,x,y); | ||
1347 | if (!could_place_light(flags, lights)) continue; | ||
1348 | |||
1349 | n = 0; | ||
1350 | list_lights(state, x, y, 1, &lld); | ||
1351 | FOREACHLIT(&lld, { if (GRID(state,lights,lx,ly) == 0) n++; }); | ||
1352 | if (n > bestn) { | ||
1353 | bestn = n; bestx = x; besty = y; | ||
1354 | } | ||
1355 | } | ||
1356 | } | ||
1357 | assert(bestn > 0); | ||
1358 | assert(bestx >= 0 && besty >= 0); | ||
1359 | |||
1360 | /* Now we've chosen a plausible (x,y), try to solve it once as 'lit' | ||
1361 | * and once as 'impossible'; we need to make one copy to do this. */ | ||
1362 | |||
1363 | scopy = dup_game(state); | ||
1364 | #ifdef SOLVER_DIAGNOSTICS | ||
1365 | debug(("Recursing #1: trying (%d,%d) as IMPOSSIBLE\n", bestx, besty)); | ||
1366 | #endif | ||
1367 | GRID(state,flags,bestx,besty) |= F_IMPOSSIBLE; | ||
1368 | self_soluble = solve_sub(state, solve_flags, depth+1, maxdepth); | ||
1369 | |||
1370 | if (!(solve_flags & F_SOLVE_FORCEUNIQUE) && self_soluble > 0) { | ||
1371 | /* we didn't care about finding all solutions, and we just | ||
1372 | * found one; return with it immediately. */ | ||
1373 | free_game(scopy); | ||
1374 | ret = self_soluble; | ||
1375 | goto done; | ||
1376 | } | ||
1377 | |||
1378 | #ifdef SOLVER_DIAGNOSTICS | ||
1379 | debug(("Recursing #2: trying (%d,%d) as LIGHT\n", bestx, besty)); | ||
1380 | #endif | ||
1381 | set_light(scopy, bestx, besty, 1); | ||
1382 | copy_soluble = solve_sub(scopy, solve_flags, depth+1, maxdepth); | ||
1383 | |||
1384 | /* If we wanted a unique solution but we hit our recursion limit | ||
1385 | * (on either branch) then we have to assume we didn't find possible | ||
1386 | * extra solutions, and return 'not soluble'. */ | ||
1387 | if ((solve_flags & F_SOLVE_FORCEUNIQUE) && | ||
1388 | ((copy_soluble < 0) || (self_soluble < 0))) { | ||
1389 | ret = -1; | ||
1390 | /* Make sure that whether or not it was self or copy (or both) that | ||
1391 | * were soluble, that we return a solved state in self. */ | ||
1392 | } else if (copy_soluble <= 0) { | ||
1393 | /* copy wasn't soluble; keep self state and return that result. */ | ||
1394 | ret = self_soluble; | ||
1395 | } else if (self_soluble <= 0) { | ||
1396 | /* copy solved and we didn't, so copy in copy's (now solved) | ||
1397 | * flags and light state. */ | ||
1398 | memcpy(state->lights, scopy->lights, | ||
1399 | scopy->w * scopy->h * sizeof(int)); | ||
1400 | memcpy(state->flags, scopy->flags, | ||
1401 | scopy->w * scopy->h * sizeof(unsigned int)); | ||
1402 | ret = copy_soluble; | ||
1403 | } else { | ||
1404 | ret = copy_soluble + self_soluble; | ||
1405 | } | ||
1406 | free_game(scopy); | ||
1407 | goto done; | ||
1408 | } | ||
1409 | done: | ||
1410 | if (sscratch) sfree(sscratch); | ||
1411 | #ifdef SOLVER_DIAGNOSTICS | ||
1412 | if (ret < 0) | ||
1413 | debug(("solve_sub: depth = %d returning, ran out of recursion.\n", | ||
1414 | depth)); | ||
1415 | else | ||
1416 | debug(("solve_sub: depth = %d returning, %d solutions.\n", | ||
1417 | depth, ret)); | ||
1418 | #endif | ||
1419 | return ret; | ||
1420 | } | ||
1421 | |||
1422 | /* Fills in the (possibly partially-complete) game_state as far as it can, | ||
1423 | * returning the number of possible solutions. If it returns >0 then the | ||
1424 | * game_state will be in a solved state, but you won't know which one. */ | ||
1425 | static int dosolve(game_state *state, int solve_flags, int *maxdepth) | ||
1426 | { | ||
1427 | int x, y, nsol; | ||
1428 | |||
1429 | for (x = 0; x < state->w; x++) { | ||
1430 | for (y = 0; y < state->h; y++) { | ||
1431 | GRID(state,flags,x,y) &= ~F_NUMBERUSED; | ||
1432 | } | ||
1433 | } | ||
1434 | nsol = solve_sub(state, solve_flags, 0, maxdepth); | ||
1435 | return nsol; | ||
1436 | } | ||
1437 | |||
1438 | static int strip_unused_nums(game_state *state) | ||
1439 | { | ||
1440 | int x,y,n=0; | ||
1441 | for (x = 0; x < state->w; x++) { | ||
1442 | for (y = 0; y < state->h; y++) { | ||
1443 | if ((GRID(state,flags,x,y) & F_NUMBERED) && | ||
1444 | !(GRID(state,flags,x,y) & F_NUMBERUSED)) { | ||
1445 | GRID(state,flags,x,y) &= ~F_NUMBERED; | ||
1446 | GRID(state,lights,x,y) = 0; | ||
1447 | n++; | ||
1448 | } | ||
1449 | } | ||
1450 | } | ||
1451 | debug(("Stripped %d unused numbers.\n", n)); | ||
1452 | return n; | ||
1453 | } | ||
1454 | |||
1455 | static void unplace_lights(game_state *state) | ||
1456 | { | ||
1457 | int x,y; | ||
1458 | for (x = 0; x < state->w; x++) { | ||
1459 | for (y = 0; y < state->h; y++) { | ||
1460 | if (GRID(state,flags,x,y) & F_LIGHT) | ||
1461 | set_light(state,x,y,0); | ||
1462 | GRID(state,flags,x,y) &= ~F_IMPOSSIBLE; | ||
1463 | GRID(state,flags,x,y) &= ~F_NUMBERUSED; | ||
1464 | } | ||
1465 | } | ||
1466 | } | ||
1467 | |||
1468 | static int puzzle_is_good(game_state *state, int difficulty) | ||
1469 | { | ||
1470 | int nsol, mdepth = 0; | ||
1471 | unsigned int sflags = flags_from_difficulty(difficulty); | ||
1472 | |||
1473 | unplace_lights(state); | ||
1474 | |||
1475 | #ifdef SOLVER_DIAGNOSTICS | ||
1476 | debug(("Trying to solve with difficulty %d (0x%x):\n", | ||
1477 | difficulty, sflags)); | ||
1478 | if (verbose) debug_state(state); | ||
1479 | #endif | ||
1480 | |||
1481 | nsol = dosolve(state, sflags, &mdepth); | ||
1482 | /* if we wanted an easy puzzle, make sure we didn't need recursion. */ | ||
1483 | if (!(sflags & F_SOLVE_ALLOWRECURSE) && mdepth > 0) { | ||
1484 | debug(("Ignoring recursive puzzle.\n")); | ||
1485 | return 0; | ||
1486 | } | ||
1487 | |||
1488 | debug(("%d solutions found.\n", nsol)); | ||
1489 | if (nsol <= 0) return 0; | ||
1490 | if (nsol > 1) return 0; | ||
1491 | return 1; | ||
1492 | } | ||
1493 | |||
1494 | /* --- New game creation and user input code. --- */ | ||
1495 | |||
1496 | /* The basic algorithm here is to generate the most complex grid possible | ||
1497 | * while honouring two restrictions: | ||
1498 | * | ||
1499 | * * we require a unique solution, and | ||
1500 | * * either we require solubility with no recursion (!params->recurse) | ||
1501 | * * or we require some recursion. (params->recurse). | ||
1502 | * | ||
1503 | * The solver helpfully keeps track of the numbers it needed to use to | ||
1504 | * get its solution, so we use that to remove an initial set of numbers | ||
1505 | * and check we still satsify our requirements (on uniqueness and | ||
1506 | * non-recursiveness, if applicable; we don't check explicit recursiveness | ||
1507 | * until the end). | ||
1508 | * | ||
1509 | * Then we try to remove all numbers in a random order, and see if we | ||
1510 | * still satisfy requirements (putting them back if we didn't). | ||
1511 | * | ||
1512 | * Removing numbers will always, in general terms, make a puzzle require | ||
1513 | * more recursion but it may also mean a puzzle becomes non-unique. | ||
1514 | * | ||
1515 | * Once we're done, if we wanted a recursive puzzle but the most difficult | ||
1516 | * puzzle we could come up with was non-recursive, we give up and try a new | ||
1517 | * grid. */ | ||
1518 | |||
1519 | #define MAX_GRIDGEN_TRIES 20 | ||
1520 | |||
1521 | static char *new_game_desc(const game_params *params_in, random_state *rs, | ||
1522 | char **aux, int interactive) | ||
1523 | { | ||
1524 | game_params params_copy = *params_in; /* structure copy */ | ||
1525 | game_params *params = ¶ms_copy; | ||
1526 | game_state *news = new_state(params), *copys; | ||
1527 | int i, j, run, x, y, wh = params->w*params->h, num; | ||
1528 | char *ret, *p; | ||
1529 | int *numindices; | ||
1530 | |||
1531 | /* Construct a shuffled list of grid positions; we only | ||
1532 | * do this once, because if it gets used more than once it'll | ||
1533 | * be on a different grid layout. */ | ||
1534 | numindices = snewn(wh, int); | ||
1535 | for (j = 0; j < wh; j++) numindices[j] = j; | ||
1536 | shuffle(numindices, wh, sizeof(*numindices), rs); | ||
1537 | |||
1538 | while (1) { | ||
1539 | for (i = 0; i < MAX_GRIDGEN_TRIES; i++) { | ||
1540 | set_blacks(news, params, rs); /* also cleans board. */ | ||
1541 | |||
1542 | /* set up lights and then the numbers, and remove the lights */ | ||
1543 | place_lights(news, rs); | ||
1544 | debug(("Generating initial grid.\n")); | ||
1545 | place_numbers(news); | ||
1546 | if (!puzzle_is_good(news, params->difficulty)) continue; | ||
1547 | |||
1548 | /* Take a copy, remove numbers we didn't use and check there's | ||
1549 | * still a unique solution; if so, use the copy subsequently. */ | ||
1550 | copys = dup_game(news); | ||
1551 | strip_unused_nums(copys); | ||
1552 | if (!puzzle_is_good(copys, params->difficulty)) { | ||
1553 | debug(("Stripped grid is not good, reverting.\n")); | ||
1554 | free_game(copys); | ||
1555 | } else { | ||
1556 | free_game(news); | ||
1557 | news = copys; | ||
1558 | } | ||
1559 | |||
1560 | /* Go through grid removing numbers at random one-by-one and | ||
1561 | * trying to solve again; if it ceases to be good put the number back. */ | ||
1562 | for (j = 0; j < wh; j++) { | ||
1563 | y = numindices[j] / params->w; | ||
1564 | x = numindices[j] % params->w; | ||
1565 | if (!(GRID(news, flags, x, y) & F_NUMBERED)) continue; | ||
1566 | num = GRID(news, lights, x, y); | ||
1567 | GRID(news, lights, x, y) = 0; | ||
1568 | GRID(news, flags, x, y) &= ~F_NUMBERED; | ||
1569 | if (!puzzle_is_good(news, params->difficulty)) { | ||
1570 | GRID(news, lights, x, y) = num; | ||
1571 | GRID(news, flags, x, y) |= F_NUMBERED; | ||
1572 | } else | ||
1573 | debug(("Removed (%d,%d) still soluble.\n", x, y)); | ||
1574 | } | ||
1575 | if (params->difficulty > 0) { | ||
1576 | /* Was the maximally-difficult puzzle difficult enough? | ||
1577 | * Check we can't solve it with a more simplistic solver. */ | ||
1578 | if (puzzle_is_good(news, params->difficulty-1)) { | ||
1579 | debug(("Maximally-hard puzzle still not hard enough, skipping.\n")); | ||
1580 | continue; | ||
1581 | } | ||
1582 | } | ||
1583 | |||
1584 | goto goodpuzzle; | ||
1585 | } | ||
1586 | /* Couldn't generate a good puzzle in however many goes. Ramp up the | ||
1587 | * %age of black squares (if we didn't already have lots; in which case | ||
1588 | * why couldn't we generate a puzzle?) and try again. */ | ||
1589 | if (params->blackpc < 90) params->blackpc += 5; | ||
1590 | debug(("New black layout %d%%.\n", params->blackpc)); | ||
1591 | } | ||
1592 | goodpuzzle: | ||
1593 | /* Game is encoded as a long string one character per square; | ||
1594 | * 'S' is a space | ||
1595 | * 'B' is a black square with no number | ||
1596 | * '0', '1', '2', '3', '4' is a black square with a number. */ | ||
1597 | ret = snewn((params->w * params->h) + 1, char); | ||
1598 | p = ret; | ||
1599 | run = 0; | ||
1600 | for (y = 0; y < params->h; y++) { | ||
1601 | for (x = 0; x < params->w; x++) { | ||
1602 | if (GRID(news,flags,x,y) & F_BLACK) { | ||
1603 | if (run) { | ||
1604 | *p++ = ('a'-1) + run; | ||
1605 | run = 0; | ||
1606 | } | ||
1607 | if (GRID(news,flags,x,y) & F_NUMBERED) | ||
1608 | *p++ = '0' + GRID(news,lights,x,y); | ||
1609 | else | ||
1610 | *p++ = 'B'; | ||
1611 | } else { | ||
1612 | if (run == 26) { | ||
1613 | *p++ = ('a'-1) + run; | ||
1614 | run = 0; | ||
1615 | } | ||
1616 | run++; | ||
1617 | } | ||
1618 | } | ||
1619 | } | ||
1620 | if (run) { | ||
1621 | *p++ = ('a'-1) + run; | ||
1622 | run = 0; | ||
1623 | } | ||
1624 | *p = '\0'; | ||
1625 | assert(p - ret <= params->w * params->h); | ||
1626 | free_game(news); | ||
1627 | sfree(numindices); | ||
1628 | |||
1629 | return ret; | ||
1630 | } | ||
1631 | |||
1632 | static char *validate_desc(const game_params *params, const char *desc) | ||
1633 | { | ||
1634 | int i; | ||
1635 | for (i = 0; i < params->w*params->h; i++) { | ||
1636 | if (*desc >= '0' && *desc <= '4') | ||
1637 | /* OK */; | ||
1638 | else if (*desc == 'B') | ||
1639 | /* OK */; | ||
1640 | else if (*desc >= 'a' && *desc <= 'z') | ||
1641 | i += *desc - 'a'; /* and the i++ will add another one */ | ||
1642 | else if (!*desc) | ||
1643 | return "Game description shorter than expected"; | ||
1644 | else | ||
1645 | return "Game description contained unexpected character"; | ||
1646 | desc++; | ||
1647 | } | ||
1648 | if (*desc || i > params->w*params->h) | ||
1649 | return "Game description longer than expected"; | ||
1650 | |||
1651 | return NULL; | ||
1652 | } | ||
1653 | |||
1654 | static game_state *new_game(midend *me, const game_params *params, | ||
1655 | const char *desc) | ||
1656 | { | ||
1657 | game_state *ret = new_state(params); | ||
1658 | int x,y; | ||
1659 | int run = 0; | ||
1660 | |||
1661 | for (y = 0; y < params->h; y++) { | ||
1662 | for (x = 0; x < params->w; x++) { | ||
1663 | char c = '\0'; | ||
1664 | |||
1665 | if (run == 0) { | ||
1666 | c = *desc++; | ||
1667 | assert(c != 'S'); | ||
1668 | if (c >= 'a' && c <= 'z') | ||
1669 | run = c - 'a' + 1; | ||
1670 | } | ||
1671 | |||
1672 | if (run > 0) { | ||
1673 | c = 'S'; | ||
1674 | run--; | ||
1675 | } | ||
1676 | |||
1677 | switch (c) { | ||
1678 | case '0': case '1': case '2': case '3': case '4': | ||
1679 | GRID(ret,flags,x,y) |= F_NUMBERED; | ||
1680 | GRID(ret,lights,x,y) = (c - '0'); | ||
1681 | /* run-on... */ | ||
1682 | |||
1683 | case 'B': | ||
1684 | GRID(ret,flags,x,y) |= F_BLACK; | ||
1685 | break; | ||
1686 | |||
1687 | case 'S': | ||
1688 | /* empty square */ | ||
1689 | break; | ||
1690 | |||
1691 | default: | ||
1692 | assert(!"Malformed desc."); | ||
1693 | break; | ||
1694 | } | ||
1695 | } | ||
1696 | } | ||
1697 | if (*desc) assert(!"Over-long desc."); | ||
1698 | |||
1699 | return ret; | ||
1700 | } | ||
1701 | |||
1702 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1703 | const char *aux, char **error) | ||
1704 | { | ||
1705 | game_state *solved; | ||
1706 | char *move = NULL, buf[80]; | ||
1707 | int movelen, movesize, x, y, len; | ||
1708 | unsigned int oldflags, solvedflags, sflags; | ||
1709 | |||
1710 | /* We don't care here about non-unique puzzles; if the | ||
1711 | * user entered one themself then I doubt they care. */ | ||
1712 | |||
1713 | sflags = F_SOLVE_ALLOWRECURSE | F_SOLVE_DISCOUNTSETS; | ||
1714 | |||
1715 | /* Try and solve from where we are now (for non-unique | ||
1716 | * puzzles this may produce a different answer). */ | ||
1717 | solved = dup_game(currstate); | ||
1718 | if (dosolve(solved, sflags, NULL) > 0) goto solved; | ||
1719 | free_game(solved); | ||
1720 | |||
1721 | /* That didn't work; try solving from the clean puzzle. */ | ||
1722 | solved = dup_game(state); | ||
1723 | if (dosolve(solved, sflags, NULL) > 0) goto solved; | ||
1724 | *error = "Unable to find a solution to this puzzle."; | ||
1725 | goto done; | ||
1726 | |||
1727 | solved: | ||
1728 | movesize = 256; | ||
1729 | move = snewn(movesize, char); | ||
1730 | movelen = 0; | ||
1731 | move[movelen++] = 'S'; | ||
1732 | move[movelen] = '\0'; | ||
1733 | for (x = 0; x < currstate->w; x++) { | ||
1734 | for (y = 0; y < currstate->h; y++) { | ||
1735 | len = 0; | ||
1736 | oldflags = GRID(currstate, flags, x, y); | ||
1737 | solvedflags = GRID(solved, flags, x, y); | ||
1738 | if ((oldflags & F_LIGHT) != (solvedflags & F_LIGHT)) | ||
1739 | len = sprintf(buf, ";L%d,%d", x, y); | ||
1740 | else if ((oldflags & F_IMPOSSIBLE) != (solvedflags & F_IMPOSSIBLE)) | ||
1741 | len = sprintf(buf, ";I%d,%d", x, y); | ||
1742 | if (len) { | ||
1743 | if (movelen + len >= movesize) { | ||
1744 | movesize = movelen + len + 256; | ||
1745 | move = sresize(move, movesize, char); | ||
1746 | } | ||
1747 | strcpy(move + movelen, buf); | ||
1748 | movelen += len; | ||
1749 | } | ||
1750 | } | ||
1751 | } | ||
1752 | |||
1753 | done: | ||
1754 | free_game(solved); | ||
1755 | return move; | ||
1756 | } | ||
1757 | |||
1758 | static int game_can_format_as_text_now(const game_params *params) | ||
1759 | { | ||
1760 | return TRUE; | ||
1761 | } | ||
1762 | |||
1763 | /* 'borrowed' from slant.c, mainly. I could have printed it one | ||
1764 | * character per cell (like debug_state) but that comes out tiny. | ||
1765 | * 'L' is used for 'light here' because 'O' looks too much like '0' | ||
1766 | * (black square with no surrounding lights). */ | ||
1767 | static char *game_text_format(const game_state *state) | ||
1768 | { | ||
1769 | int w = state->w, h = state->h, W = w+1, H = h+1; | ||
1770 | int x, y, len, lights; | ||
1771 | unsigned int flags; | ||
1772 | char *ret, *p; | ||
1773 | |||
1774 | len = (h+H) * (w+W+1) + 1; | ||
1775 | ret = snewn(len, char); | ||
1776 | p = ret; | ||
1777 | |||
1778 | for (y = 0; y < H; y++) { | ||
1779 | for (x = 0; x < W; x++) { | ||
1780 | *p++ = '+'; | ||
1781 | if (x < w) | ||
1782 | *p++ = '-'; | ||
1783 | } | ||
1784 | *p++ = '\n'; | ||
1785 | if (y < h) { | ||
1786 | for (x = 0; x < W; x++) { | ||
1787 | *p++ = '|'; | ||
1788 | if (x < w) { | ||
1789 | /* actual interesting bit. */ | ||
1790 | flags = GRID(state, flags, x, y); | ||
1791 | lights = GRID(state, lights, x, y); | ||
1792 | if (flags & F_BLACK) { | ||
1793 | if (flags & F_NUMBERED) | ||
1794 | *p++ = '0' + lights; | ||
1795 | else | ||
1796 | *p++ = '#'; | ||
1797 | } else { | ||
1798 | if (flags & F_LIGHT) | ||
1799 | *p++ = 'L'; | ||
1800 | else if (flags & F_IMPOSSIBLE) | ||
1801 | *p++ = 'x'; | ||
1802 | else if (lights > 0) | ||
1803 | *p++ = '.'; | ||
1804 | else | ||
1805 | *p++ = ' '; | ||
1806 | } | ||
1807 | } | ||
1808 | } | ||
1809 | *p++ = '\n'; | ||
1810 | } | ||
1811 | } | ||
1812 | *p++ = '\0'; | ||
1813 | |||
1814 | assert(p - ret == len); | ||
1815 | return ret; | ||
1816 | } | ||
1817 | |||
1818 | struct game_ui { | ||
1819 | int cur_x, cur_y, cur_visible; | ||
1820 | }; | ||
1821 | |||
1822 | static game_ui *new_ui(const game_state *state) | ||
1823 | { | ||
1824 | game_ui *ui = snew(game_ui); | ||
1825 | ui->cur_x = ui->cur_y = ui->cur_visible = 0; | ||
1826 | return ui; | ||
1827 | } | ||
1828 | |||
1829 | static void free_ui(game_ui *ui) | ||
1830 | { | ||
1831 | sfree(ui); | ||
1832 | } | ||
1833 | |||
1834 | static char *encode_ui(const game_ui *ui) | ||
1835 | { | ||
1836 | /* nothing to encode. */ | ||
1837 | return NULL; | ||
1838 | } | ||
1839 | |||
1840 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1841 | { | ||
1842 | /* nothing to decode. */ | ||
1843 | } | ||
1844 | |||
1845 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1846 | const game_state *newstate) | ||
1847 | { | ||
1848 | if (newstate->completed) | ||
1849 | ui->cur_visible = 0; | ||
1850 | } | ||
1851 | |||
1852 | #define DF_BLACK 1 /* black square */ | ||
1853 | #define DF_NUMBERED 2 /* black square with number */ | ||
1854 | #define DF_LIT 4 /* display (white) square lit up */ | ||
1855 | #define DF_LIGHT 8 /* display light in square */ | ||
1856 | #define DF_OVERLAP 16 /* display light as overlapped */ | ||
1857 | #define DF_CURSOR 32 /* display cursor */ | ||
1858 | #define DF_NUMBERWRONG 64 /* display black numbered square as error. */ | ||
1859 | #define DF_FLASH 128 /* background flash is on. */ | ||
1860 | #define DF_IMPOSSIBLE 256 /* display non-light little square */ | ||
1861 | |||
1862 | struct game_drawstate { | ||
1863 | int tilesize, crad; | ||
1864 | int w, h; | ||
1865 | unsigned int *flags; /* width * height */ | ||
1866 | int started; | ||
1867 | }; | ||
1868 | |||
1869 | |||
1870 | /* Believe it or not, this empty = "" hack is needed to get around a bug in | ||
1871 | * the prc-tools gcc when optimisation is turned on; before, it produced: | ||
1872 | lightup-sect.c: In function `interpret_move': | ||
1873 | lightup-sect.c:1416: internal error--unrecognizable insn: | ||
1874 | (insn 582 580 583 (set (reg:SI 134) | ||
1875 | (pc)) -1 (nil) | ||
1876 | (nil)) | ||
1877 | */ | ||
1878 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1879 | const game_drawstate *ds, | ||
1880 | int x, int y, int button) | ||
1881 | { | ||
1882 | enum { NONE, FLIP_LIGHT, FLIP_IMPOSSIBLE } action = NONE; | ||
1883 | int cx = -1, cy = -1; | ||
1884 | unsigned int flags; | ||
1885 | char buf[80], *nullret = NULL, *empty = "", c; | ||
1886 | |||
1887 | if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { | ||
1888 | if (ui->cur_visible) | ||
1889 | nullret = empty; | ||
1890 | ui->cur_visible = 0; | ||
1891 | cx = FROMCOORD(x); | ||
1892 | cy = FROMCOORD(y); | ||
1893 | action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE; | ||
1894 | } else if (IS_CURSOR_SELECT(button) || | ||
1895 | button == 'i' || button == 'I' || | ||
1896 | button == ' ' || button == '\r' || button == '\n') { | ||
1897 | if (ui->cur_visible) { | ||
1898 | /* Only allow cursor-effect operations if the cursor is visible | ||
1899 | * (otherwise you have no idea which square it might be affecting) */ | ||
1900 | cx = ui->cur_x; | ||
1901 | cy = ui->cur_y; | ||
1902 | action = (button == 'i' || button == 'I' || button == CURSOR_SELECT2) ? | ||
1903 | FLIP_IMPOSSIBLE : FLIP_LIGHT; | ||
1904 | } | ||
1905 | ui->cur_visible = 1; | ||
1906 | } else if (IS_CURSOR_MOVE(button)) { | ||
1907 | move_cursor(button, &ui->cur_x, &ui->cur_y, state->w, state->h, 0); | ||
1908 | ui->cur_visible = 1; | ||
1909 | nullret = empty; | ||
1910 | } else | ||
1911 | return NULL; | ||
1912 | |||
1913 | switch (action) { | ||
1914 | case FLIP_LIGHT: | ||
1915 | case FLIP_IMPOSSIBLE: | ||
1916 | if (cx < 0 || cy < 0 || cx >= state->w || cy >= state->h) | ||
1917 | return nullret; | ||
1918 | flags = GRID(state, flags, cx, cy); | ||
1919 | if (flags & F_BLACK) | ||
1920 | return nullret; | ||
1921 | if (action == FLIP_LIGHT) { | ||
1922 | #ifdef STYLUS_BASED | ||
1923 | if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'I'; else c = 'L'; | ||
1924 | #else | ||
1925 | if (flags & F_IMPOSSIBLE) return nullret; | ||
1926 | c = 'L'; | ||
1927 | #endif | ||
1928 | } else { | ||
1929 | #ifdef STYLUS_BASED | ||
1930 | if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'L'; else c = 'I'; | ||
1931 | #else | ||
1932 | if (flags & F_LIGHT) return nullret; | ||
1933 | c = 'I'; | ||
1934 | #endif | ||
1935 | } | ||
1936 | sprintf(buf, "%c%d,%d", (int)c, cx, cy); | ||
1937 | break; | ||
1938 | |||
1939 | case NONE: | ||
1940 | return nullret; | ||
1941 | |||
1942 | default: | ||
1943 | assert(!"Shouldn't get here!"); | ||
1944 | } | ||
1945 | return dupstr(buf); | ||
1946 | } | ||
1947 | |||
1948 | static game_state *execute_move(const game_state *state, const char *move) | ||
1949 | { | ||
1950 | game_state *ret = dup_game(state); | ||
1951 | int x, y, n, flags; | ||
1952 | char c; | ||
1953 | |||
1954 | if (!*move) goto badmove; | ||
1955 | |||
1956 | while (*move) { | ||
1957 | c = *move; | ||
1958 | if (c == 'S') { | ||
1959 | ret->used_solve = TRUE; | ||
1960 | move++; | ||
1961 | } else if (c == 'L' || c == 'I') { | ||
1962 | move++; | ||
1963 | if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 || | ||
1964 | x < 0 || y < 0 || x >= ret->w || y >= ret->h) | ||
1965 | goto badmove; | ||
1966 | |||
1967 | flags = GRID(ret, flags, x, y); | ||
1968 | if (flags & F_BLACK) goto badmove; | ||
1969 | |||
1970 | /* LIGHT and IMPOSSIBLE are mutually exclusive. */ | ||
1971 | if (c == 'L') { | ||
1972 | GRID(ret, flags, x, y) &= ~F_IMPOSSIBLE; | ||
1973 | set_light(ret, x, y, (flags & F_LIGHT) ? 0 : 1); | ||
1974 | } else { | ||
1975 | set_light(ret, x, y, 0); | ||
1976 | GRID(ret, flags, x, y) ^= F_IMPOSSIBLE; | ||
1977 | } | ||
1978 | move += n; | ||
1979 | } else goto badmove; | ||
1980 | |||
1981 | if (*move == ';') | ||
1982 | move++; | ||
1983 | else if (*move) goto badmove; | ||
1984 | } | ||
1985 | if (grid_correct(ret)) ret->completed = 1; | ||
1986 | return ret; | ||
1987 | |||
1988 | badmove: | ||
1989 | free_game(ret); | ||
1990 | return NULL; | ||
1991 | } | ||
1992 | |||
1993 | /* ---------------------------------------------------------------------- | ||
1994 | * Drawing routines. | ||
1995 | */ | ||
1996 | |||
1997 | /* XXX entirely cloned from fifteen.c; separate out? */ | ||
1998 | static void game_compute_size(const game_params *params, int tilesize, | ||
1999 | int *x, int *y) | ||
2000 | { | ||
2001 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2002 | struct { int tilesize; } ads, *ds = &ads; | ||
2003 | ads.tilesize = tilesize; | ||
2004 | |||
2005 | *x = TILE_SIZE * params->w + 2 * BORDER; | ||
2006 | *y = TILE_SIZE * params->h + 2 * BORDER; | ||
2007 | } | ||
2008 | |||
2009 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
2010 | const game_params *params, int tilesize) | ||
2011 | { | ||
2012 | ds->tilesize = tilesize; | ||
2013 | ds->crad = 3*(tilesize-1)/8; | ||
2014 | } | ||
2015 | |||
2016 | static float *game_colours(frontend *fe, int *ncolours) | ||
2017 | { | ||
2018 | float *ret = snewn(3 * NCOLOURS, float); | ||
2019 | int i; | ||
2020 | |||
2021 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
2022 | |||
2023 | for (i = 0; i < 3; i++) { | ||
2024 | ret[COL_BLACK * 3 + i] = 0.0F; | ||
2025 | ret[COL_LIGHT * 3 + i] = 1.0F; | ||
2026 | ret[COL_CURSOR * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 2.0F; | ||
2027 | ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 1.5F; | ||
2028 | |||
2029 | } | ||
2030 | |||
2031 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
2032 | ret[COL_ERROR * 3 + 1] = 0.25F; | ||
2033 | ret[COL_ERROR * 3 + 2] = 0.25F; | ||
2034 | |||
2035 | ret[COL_LIT * 3 + 0] = 1.0F; | ||
2036 | ret[COL_LIT * 3 + 1] = 1.0F; | ||
2037 | ret[COL_LIT * 3 + 2] = 0.0F; | ||
2038 | |||
2039 | *ncolours = NCOLOURS; | ||
2040 | return ret; | ||
2041 | } | ||
2042 | |||
2043 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
2044 | { | ||
2045 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
2046 | int i; | ||
2047 | |||
2048 | ds->tilesize = ds->crad = 0; | ||
2049 | ds->w = state->w; ds->h = state->h; | ||
2050 | |||
2051 | ds->flags = snewn(ds->w*ds->h, unsigned int); | ||
2052 | for (i = 0; i < ds->w*ds->h; i++) | ||
2053 | ds->flags[i] = -1; | ||
2054 | |||
2055 | ds->started = 0; | ||
2056 | |||
2057 | return ds; | ||
2058 | } | ||
2059 | |||
2060 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
2061 | { | ||
2062 | sfree(ds->flags); | ||
2063 | sfree(ds); | ||
2064 | } | ||
2065 | |||
2066 | /* At some stage we should put these into a real options struct. | ||
2067 | * Note that tile_redraw has no #ifdeffery; it relies on tile_flags not | ||
2068 | * to put those flags in. */ | ||
2069 | #define HINT_LIGHTS | ||
2070 | #define HINT_OVERLAPS | ||
2071 | #define HINT_NUMBERS | ||
2072 | |||
2073 | static unsigned int tile_flags(game_drawstate *ds, const game_state *state, | ||
2074 | const game_ui *ui, int x, int y, int flashing) | ||
2075 | { | ||
2076 | unsigned int flags = GRID(state, flags, x, y); | ||
2077 | int lights = GRID(state, lights, x, y); | ||
2078 | unsigned int ret = 0; | ||
2079 | |||
2080 | if (flashing) ret |= DF_FLASH; | ||
2081 | if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y) | ||
2082 | ret |= DF_CURSOR; | ||
2083 | |||
2084 | if (flags & F_BLACK) { | ||
2085 | ret |= DF_BLACK; | ||
2086 | if (flags & F_NUMBERED) { | ||
2087 | #ifdef HINT_NUMBERS | ||
2088 | if (number_wrong(state, x, y)) | ||
2089 | ret |= DF_NUMBERWRONG; | ||
2090 | #endif | ||
2091 | ret |= DF_NUMBERED; | ||
2092 | } | ||
2093 | } else { | ||
2094 | #ifdef HINT_LIGHTS | ||
2095 | if (lights > 0) ret |= DF_LIT; | ||
2096 | #endif | ||
2097 | if (flags & F_LIGHT) { | ||
2098 | ret |= DF_LIGHT; | ||
2099 | #ifdef HINT_OVERLAPS | ||
2100 | if (lights > 1) ret |= DF_OVERLAP; | ||
2101 | #endif | ||
2102 | } | ||
2103 | if (flags & F_IMPOSSIBLE) ret |= DF_IMPOSSIBLE; | ||
2104 | } | ||
2105 | return ret; | ||
2106 | } | ||
2107 | |||
2108 | static void tile_redraw(drawing *dr, game_drawstate *ds, | ||
2109 | const game_state *state, int x, int y) | ||
2110 | { | ||
2111 | unsigned int ds_flags = GRID(ds, flags, x, y); | ||
2112 | int dx = COORD(x), dy = COORD(y); | ||
2113 | int lit = (ds_flags & DF_FLASH) ? COL_GRID : COL_LIT; | ||
2114 | |||
2115 | if (ds_flags & DF_BLACK) { | ||
2116 | draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_BLACK); | ||
2117 | if (ds_flags & DF_NUMBERED) { | ||
2118 | int ccol = (ds_flags & DF_NUMBERWRONG) ? COL_ERROR : COL_LIGHT; | ||
2119 | char str[32]; | ||
2120 | |||
2121 | /* We know that this won't change over the course of the game | ||
2122 | * so it's OK to ignore this when calculating whether or not | ||
2123 | * to redraw the tile. */ | ||
2124 | sprintf(str, "%d", GRID(state, lights, x, y)); | ||
2125 | draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, | ||
2126 | FONT_VARIABLE, TILE_SIZE*3/5, | ||
2127 | ALIGN_VCENTRE | ALIGN_HCENTRE, ccol, str); | ||
2128 | } | ||
2129 | } else { | ||
2130 | draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, | ||
2131 | (ds_flags & DF_LIT) ? lit : COL_BACKGROUND); | ||
2132 | draw_rect_outline(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_GRID); | ||
2133 | if (ds_flags & DF_LIGHT) { | ||
2134 | int lcol = (ds_flags & DF_OVERLAP) ? COL_ERROR : COL_LIGHT; | ||
2135 | draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, TILE_RADIUS, | ||
2136 | lcol, COL_BLACK); | ||
2137 | } else if ((ds_flags & DF_IMPOSSIBLE)) { | ||
2138 | static int draw_blobs_when_lit = -1; | ||
2139 | if (draw_blobs_when_lit < 0) { | ||
2140 | char *env = getenv("LIGHTUP_LIT_BLOBS"); | ||
2141 | draw_blobs_when_lit = (!env || (env[0] == 'y' || | ||
2142 | env[0] == 'Y')); | ||
2143 | } | ||
2144 | if (!(ds_flags & DF_LIT) || draw_blobs_when_lit) { | ||
2145 | int rlen = TILE_SIZE / 4; | ||
2146 | draw_rect(dr, dx + TILE_SIZE/2 - rlen/2, | ||
2147 | dy + TILE_SIZE/2 - rlen/2, | ||
2148 | rlen, rlen, COL_BLACK); | ||
2149 | } | ||
2150 | } | ||
2151 | } | ||
2152 | |||
2153 | if (ds_flags & DF_CURSOR) { | ||
2154 | int coff = TILE_SIZE/8; | ||
2155 | draw_rect_outline(dr, dx + coff, dy + coff, | ||
2156 | TILE_SIZE - coff*2, TILE_SIZE - coff*2, COL_CURSOR); | ||
2157 | } | ||
2158 | |||
2159 | draw_update(dr, dx, dy, TILE_SIZE, TILE_SIZE); | ||
2160 | } | ||
2161 | |||
2162 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
2163 | const game_state *oldstate, const game_state *state, | ||
2164 | int dir, const game_ui *ui, | ||
2165 | float animtime, float flashtime) | ||
2166 | { | ||
2167 | int flashing = FALSE; | ||
2168 | int x,y; | ||
2169 | |||
2170 | if (flashtime) flashing = (int)(flashtime * 3 / FLASH_TIME) != 1; | ||
2171 | |||
2172 | if (!ds->started) { | ||
2173 | draw_rect(dr, 0, 0, | ||
2174 | TILE_SIZE * ds->w + 2 * BORDER, | ||
2175 | TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND); | ||
2176 | |||
2177 | draw_rect_outline(dr, COORD(0)-1, COORD(0)-1, | ||
2178 | TILE_SIZE * ds->w + 2, | ||
2179 | TILE_SIZE * ds->h + 2, | ||
2180 | COL_GRID); | ||
2181 | |||
2182 | draw_update(dr, 0, 0, | ||
2183 | TILE_SIZE * ds->w + 2 * BORDER, | ||
2184 | TILE_SIZE * ds->h + 2 * BORDER); | ||
2185 | ds->started = 1; | ||
2186 | } | ||
2187 | |||
2188 | for (x = 0; x < ds->w; x++) { | ||
2189 | for (y = 0; y < ds->h; y++) { | ||
2190 | unsigned int ds_flags = tile_flags(ds, state, ui, x, y, flashing); | ||
2191 | if (ds_flags != GRID(ds, flags, x, y)) { | ||
2192 | GRID(ds, flags, x, y) = ds_flags; | ||
2193 | tile_redraw(dr, ds, state, x, y); | ||
2194 | } | ||
2195 | } | ||
2196 | } | ||
2197 | } | ||
2198 | |||
2199 | static float game_anim_length(const game_state *oldstate, | ||
2200 | const game_state *newstate, int dir, game_ui *ui) | ||
2201 | { | ||
2202 | return 0.0F; | ||
2203 | } | ||
2204 | |||
2205 | static float game_flash_length(const game_state *oldstate, | ||
2206 | const game_state *newstate, int dir, game_ui *ui) | ||
2207 | { | ||
2208 | if (!oldstate->completed && newstate->completed && | ||
2209 | !oldstate->used_solve && !newstate->used_solve) | ||
2210 | return FLASH_TIME; | ||
2211 | return 0.0F; | ||
2212 | } | ||
2213 | |||
2214 | static int game_status(const game_state *state) | ||
2215 | { | ||
2216 | return state->completed ? +1 : 0; | ||
2217 | } | ||
2218 | |||
2219 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
2220 | { | ||
2221 | return TRUE; | ||
2222 | } | ||
2223 | |||
2224 | static void game_print_size(const game_params *params, float *x, float *y) | ||
2225 | { | ||
2226 | int pw, ph; | ||
2227 | |||
2228 | /* | ||
2229 | * I'll use 6mm squares by default. | ||
2230 | */ | ||
2231 | game_compute_size(params, 600, &pw, &ph); | ||
2232 | *x = pw / 100.0F; | ||
2233 | *y = ph / 100.0F; | ||
2234 | } | ||
2235 | |||
2236 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
2237 | { | ||
2238 | int w = state->w, h = state->h; | ||
2239 | int ink = print_mono_colour(dr, 0); | ||
2240 | int paper = print_mono_colour(dr, 1); | ||
2241 | int x, y; | ||
2242 | |||
2243 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2244 | game_drawstate ads, *ds = &ads; | ||
2245 | game_set_size(dr, ds, NULL, tilesize); | ||
2246 | |||
2247 | /* | ||
2248 | * Border. | ||
2249 | */ | ||
2250 | print_line_width(dr, TILE_SIZE / 16); | ||
2251 | draw_rect_outline(dr, COORD(0), COORD(0), | ||
2252 | TILE_SIZE * w, TILE_SIZE * h, ink); | ||
2253 | |||
2254 | /* | ||
2255 | * Grid. | ||
2256 | */ | ||
2257 | print_line_width(dr, TILE_SIZE / 24); | ||
2258 | for (x = 1; x < w; x++) | ||
2259 | draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink); | ||
2260 | for (y = 1; y < h; y++) | ||
2261 | draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink); | ||
2262 | |||
2263 | /* | ||
2264 | * Grid contents. | ||
2265 | */ | ||
2266 | for (y = 0; y < h; y++) | ||
2267 | for (x = 0; x < w; x++) { | ||
2268 | unsigned int ds_flags = tile_flags(ds, state, NULL, x, y, FALSE); | ||
2269 | int dx = COORD(x), dy = COORD(y); | ||
2270 | if (ds_flags & DF_BLACK) { | ||
2271 | draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, ink); | ||
2272 | if (ds_flags & DF_NUMBERED) { | ||
2273 | char str[32]; | ||
2274 | sprintf(str, "%d", GRID(state, lights, x, y)); | ||
2275 | draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, | ||
2276 | FONT_VARIABLE, TILE_SIZE*3/5, | ||
2277 | ALIGN_VCENTRE | ALIGN_HCENTRE, paper, str); | ||
2278 | } | ||
2279 | } else if (ds_flags & DF_LIGHT) { | ||
2280 | draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, | ||
2281 | TILE_RADIUS, -1, ink); | ||
2282 | } | ||
2283 | } | ||
2284 | } | ||
2285 | |||
2286 | #ifdef COMBINED | ||
2287 | #define thegame lightup | ||
2288 | #endif | ||
2289 | |||
2290 | const struct game thegame = { | ||
2291 | "Light Up", "games.lightup", "lightup", | ||
2292 | default_params, | ||
2293 | game_fetch_preset, NULL, | ||
2294 | decode_params, | ||
2295 | encode_params, | ||
2296 | free_params, | ||
2297 | dup_params, | ||
2298 | TRUE, game_configure, custom_params, | ||
2299 | validate_params, | ||
2300 | new_game_desc, | ||
2301 | validate_desc, | ||
2302 | new_game, | ||
2303 | dup_game, | ||
2304 | free_game, | ||
2305 | TRUE, solve_game, | ||
2306 | TRUE, game_can_format_as_text_now, game_text_format, | ||
2307 | new_ui, | ||
2308 | free_ui, | ||
2309 | encode_ui, | ||
2310 | decode_ui, | ||
2311 | game_changed_state, | ||
2312 | interpret_move, | ||
2313 | execute_move, | ||
2314 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
2315 | game_colours, | ||
2316 | game_new_drawstate, | ||
2317 | game_free_drawstate, | ||
2318 | game_redraw, | ||
2319 | game_anim_length, | ||
2320 | game_flash_length, | ||
2321 | game_status, | ||
2322 | TRUE, FALSE, game_print_size, game_print, | ||
2323 | FALSE, /* wants_statusbar */ | ||
2324 | FALSE, game_timing_state, | ||
2325 | 0, /* flags */ | ||
2326 | }; | ||
2327 | |||
2328 | #ifdef STANDALONE_SOLVER | ||
2329 | |||
2330 | int main(int argc, char **argv) | ||
2331 | { | ||
2332 | game_params *p; | ||
2333 | game_state *s; | ||
2334 | char *id = NULL, *desc, *err, *result; | ||
2335 | int nsol, diff, really_verbose = 0; | ||
2336 | unsigned int sflags; | ||
2337 | |||
2338 | while (--argc > 0) { | ||
2339 | char *p = *++argv; | ||
2340 | if (!strcmp(p, "-v")) { | ||
2341 | really_verbose++; | ||
2342 | } else if (*p == '-') { | ||
2343 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
2344 | return 1; | ||
2345 | } else { | ||
2346 | id = p; | ||
2347 | } | ||
2348 | } | ||
2349 | |||
2350 | if (!id) { | ||
2351 | fprintf(stderr, "usage: %s [-v] <game_id>\n", argv[0]); | ||
2352 | return 1; | ||
2353 | } | ||
2354 | |||
2355 | desc = strchr(id, ':'); | ||
2356 | if (!desc) { | ||
2357 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
2358 | return 1; | ||
2359 | } | ||
2360 | *desc++ = '\0'; | ||
2361 | |||
2362 | p = default_params(); | ||
2363 | decode_params(p, id); | ||
2364 | err = validate_desc(p, desc); | ||
2365 | if (err) { | ||
2366 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
2367 | return 1; | ||
2368 | } | ||
2369 | s = new_game(NULL, p, desc); | ||
2370 | |||
2371 | /* Run the solvers easiest to hardest until we find one that | ||
2372 | * can solve our puzzle. If it's soluble we know that the | ||
2373 | * hardest (recursive) solver will always find the solution. */ | ||
2374 | nsol = sflags = 0; | ||
2375 | for (diff = 0; diff <= DIFFCOUNT; diff++) { | ||
2376 | printf("\nSolving with difficulty %d.\n", diff); | ||
2377 | sflags = flags_from_difficulty(diff); | ||
2378 | unplace_lights(s); | ||
2379 | nsol = dosolve(s, sflags, NULL); | ||
2380 | if (nsol == 1) break; | ||
2381 | } | ||
2382 | |||
2383 | printf("\n"); | ||
2384 | if (nsol == 0) { | ||
2385 | printf("Puzzle has no solution.\n"); | ||
2386 | } else if (nsol < 0) { | ||
2387 | printf("Unable to find a unique solution.\n"); | ||
2388 | } else if (nsol > 1) { | ||
2389 | printf("Puzzle has multiple solutions.\n"); | ||
2390 | } else { | ||
2391 | verbose = really_verbose; | ||
2392 | unplace_lights(s); | ||
2393 | printf("Puzzle has difficulty %d: solving...\n", diff); | ||
2394 | dosolve(s, sflags, NULL); /* sflags from last successful solve */ | ||
2395 | result = game_text_format(s); | ||
2396 | printf("%s", result); | ||
2397 | sfree(result); | ||
2398 | } | ||
2399 | |||
2400 | return 0; | ||
2401 | } | ||
2402 | |||
2403 | #endif | ||
2404 | |||
2405 | /* vim: set shiftwidth=4 tabstop=8: */ | ||