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