2 * lightup.c: Implementation of the Nikoli game 'Light Up'.
4 * Possible future solver enhancements:
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
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.)
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
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
59 #if defined STANDALONE_SOLVER
60 #define SOLVER_DIAGNOSTICS
63 #define debug(x) printf x
64 #elif defined SOLVER_DIAGNOSTICS
68 /* --- Constants, structure definitions, etc. --- */
70 #define PREFERRED_TILE_SIZE 32
71 #define TILE_SIZE (ds->tilesize)
72 #define BORDER (TILE_SIZE / 2)
73 #define TILE_RADIUS (ds->crad)
75 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
76 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
78 #define FLASH_TIME 0.30F
83 COL_BLACK, /* black */
84 COL_LIGHT, /* white */
91 enum { SYMM_NONE, SYMM_REF2, SYMM_ROT2, SYMM_REF4, SYMM_ROT4, SYMM_MAX };
97 int blackpc; /* %age of black squares */
99 int difficulty; /* 0 to DIFFCOUNT */
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 */
108 /* flags for non-black squares */
109 #define F_IMPOSSIBLE 8 /* can't put a light here */
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;
123 #define GRID(gs,grid,x,y) (gs->grid[(y)*((gs)->w) + (x)])
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. */
131 int minx, maxx, miny, maxy;
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 { \
141 for (lx = (lld)->minx; lx <= (lld)->maxx; lx++) { \
142 if (lx == (lld)->ox) continue; \
146 for (ly = (lld)->miny; ly <= (lld)->maxy; ly++) { \
147 if (!(lld)->include_origin && ly == (lld)->oy) continue; \
154 struct { int x, y; unsigned int f; } points[4];
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,
163 assert(ox >= 0 && ox < state->w && oy >= 0 && oy < state->h);
165 #define ADDPOINT(cond,nx,ny) do {\
167 s->points[s->npoints].x = (nx); \
168 s->points[s->npoints].y = (ny); \
169 s->points[s->npoints].f = 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);
178 /* --- Game parameter functions --- */
180 #define DEFAULT_PRESET 0
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 },
189 { 12, 12, 20, SYMM_ROT2, 0 },
190 { 12, 12, 20, SYMM_ROT2, 1 },
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 }
199 static game_params *default_params(void)
201 game_params *ret = snew(game_params);
202 *ret = lightup_presets[DEFAULT_PRESET];
207 static int game_fetch_preset(int i, char **name, game_params **params)
212 if (i < 0 || i >= lenof(lightup_presets))
215 ret = default_params();
216 *ret = lightup_presets[i];
219 sprintf(buf, "%dx%d %s",
221 ret->difficulty == 2 ? "hard" :
222 ret->difficulty == 1 ? "tricky" : "easy");
228 static void free_params(game_params *params)
233 static game_params *dup_params(const game_params *params)
235 game_params *ret = snew(game_params);
236 *ret = *params; /* structure copy */
240 #define EATNUM(x) do { \
241 (x) = atoi(string); \
242 while (*string && isdigit((unsigned char)*string)) string++; \
245 static void decode_params(game_params *params, char const *string)
248 if (*string == 'x') {
252 if (*string == 'b') {
254 EATNUM(params->blackpc);
256 if (*string == 's') {
258 EATNUM(params->symm);
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;
265 params->difficulty = 0;
266 /* cope with old params */
267 if (*string == 'r') {
268 params->difficulty = 2;
271 if (*string == 'd') {
273 EATNUM(params->difficulty);
277 static char *encode_params(const game_params *params, int full)
282 sprintf(buf, "%dx%db%ds%dd%d",
283 params->w, params->h, params->blackpc,
287 sprintf(buf, "%dx%d", params->w, params->h);
292 static config_item *game_configure(const game_params *params)
297 ret = snewn(6, config_item);
299 ret[0].name = "Width";
300 ret[0].type = C_STRING;
301 sprintf(buf, "%d", params->w);
302 ret[0].u.string.sval = dupstr(buf);
304 ret[1].name = "Height";
305 ret[1].type = C_STRING;
306 sprintf(buf, "%d", params->h);
307 ret[1].u.string.sval = dupstr(buf);
309 ret[2].name = "%age of black squares";
310 ret[2].type = C_STRING;
311 sprintf(buf, "%d", params->blackpc);
312 ret[2].u.string.sval = dupstr(buf);
314 ret[3].name = "Symmetry";
315 ret[3].type = C_CHOICES;
316 ret[3].u.choices.choicenames = ":None"
317 ":2-way mirror:2-way rotational"
318 ":4-way mirror:4-way rotational";
319 ret[3].u.choices.selected = params->symm;
321 ret[4].name = "Difficulty";
322 ret[4].type = C_CHOICES;
323 ret[4].u.choices.choicenames = ":Easy:Tricky:Hard";
324 ret[4].u.choices.selected = params->difficulty;
332 static game_params *custom_params(const config_item *cfg)
334 game_params *ret = snew(game_params);
336 ret->w = atoi(cfg[0].u.string.sval);
337 ret->h = atoi(cfg[1].u.string.sval);
338 ret->blackpc = atoi(cfg[2].u.string.sval);
339 ret->symm = cfg[3].u.choices.selected;
340 ret->difficulty = cfg[4].u.choices.selected;
345 static char *validate_params(const game_params *params, int full)
347 if (params->w < 2 || params->h < 2)
348 return "Width and height must be at least 2";
350 if (params->blackpc < 5 || params->blackpc > 100)
351 return "Percentage of black squares must be between 5% and 100%";
352 if (params->w != params->h) {
353 if (params->symm == SYMM_ROT4)
354 return "4-fold symmetry is only available with square grids";
356 if (params->symm < 0 || params->symm >= SYMM_MAX)
357 return "Unknown symmetry type";
358 if (params->difficulty < 0 || params->difficulty > DIFFCOUNT)
359 return "Unknown difficulty level";
364 /* --- Game state construction/freeing helper functions --- */
366 static game_state *new_state(const game_params *params)
368 game_state *ret = snew(game_state);
372 ret->lights = snewn(ret->w * ret->h, int);
374 memset(ret->lights, 0, ret->w * ret->h * sizeof(int));
375 ret->flags = snewn(ret->w * ret->h, unsigned int);
376 memset(ret->flags, 0, ret->w * ret->h * sizeof(unsigned int));
377 ret->completed = ret->used_solve = 0;
381 static game_state *dup_game(const game_state *state)
383 game_state *ret = snew(game_state);
388 ret->lights = snewn(ret->w * ret->h, int);
389 memcpy(ret->lights, state->lights, ret->w * ret->h * sizeof(int));
390 ret->nlights = state->nlights;
392 ret->flags = snewn(ret->w * ret->h, unsigned int);
393 memcpy(ret->flags, state->flags, ret->w * ret->h * sizeof(unsigned int));
395 ret->completed = state->completed;
396 ret->used_solve = state->used_solve;
401 static void free_game(game_state *state)
403 sfree(state->lights);
408 static void debug_state(game_state *state)
413 for (y = 0; y < state->h; y++) {
414 for (x = 0; x < state->w; x++) {
416 if (GRID(state, flags, x, y) & F_BLACK) {
417 if (GRID(state, flags, x, y) & F_NUMBERED)
418 c = GRID(state, lights, x, y) + '0';
422 if (GRID(state, flags, x, y) & F_LIGHT)
424 else if (GRID(state, flags, x, y) & F_IMPOSSIBLE)
427 debug(("%c", (int)c));
430 for (x = 0; x < state->w; x++) {
431 if (GRID(state, flags, x, y) & F_BLACK)
434 c = (GRID(state, flags, x, y) & F_LIGHT) ? 'A' : 'a';
435 c += GRID(state, lights, x, y);
437 debug(("%c", (int)c));
443 /* --- Game completion test routines. --- */
445 /* These are split up because occasionally functions are only
446 * interested in one particular aspect. */
448 /* Returns non-zero if all grid spaces are lit. */
449 static int grid_lit(game_state *state)
453 for (x = 0; x < state->w; x++) {
454 for (y = 0; y < state->h; y++) {
455 if (GRID(state,flags,x,y) & F_BLACK) continue;
456 if (GRID(state,lights,x,y) == 0)
463 /* Returns non-zero if any lights are lit by other lights. */
464 static int grid_overlap(game_state *state)
468 for (x = 0; x < state->w; x++) {
469 for (y = 0; y < state->h; y++) {
470 if (!(GRID(state, flags, x, y) & F_LIGHT)) continue;
471 if (GRID(state, lights, x, y) > 1)
478 static int number_wrong(const game_state *state, int x, int y)
481 int i, n, empty, lights = GRID(state, lights, x, y);
484 * This function computes the display hint for a number: we
485 * turn the number red if it is definitely wrong. This means
488 * (a) it has too many lights around it, or
489 * (b) it would have too few lights around it even if all the
490 * plausible squares (not black, lit or F_IMPOSSIBLE) were
491 * filled with lights.
494 assert(GRID(state, flags, x, y) & F_NUMBERED);
495 get_surrounds(state, x, y, &s);
498 for (i = 0; i < s.npoints; i++) {
499 if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT) {
503 if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_BLACK)
505 if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_IMPOSSIBLE)
507 if (GRID(state,lights,s.points[i].x,s.points[i].y))
511 return (n > lights || (n + empty < lights));
514 static int number_correct(game_state *state, int x, int y)
517 int n = 0, i, lights = GRID(state, lights, x, y);
519 assert(GRID(state, flags, x, y) & F_NUMBERED);
520 get_surrounds(state, x, y, &s);
521 for (i = 0; i < s.npoints; i++) {
522 if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT)
525 return (n == lights) ? 1 : 0;
528 /* Returns non-zero if any numbers add up incorrectly. */
529 static int grid_addsup(game_state *state)
533 for (x = 0; x < state->w; x++) {
534 for (y = 0; y < state->h; y++) {
535 if (!(GRID(state, flags, x, y) & F_NUMBERED)) continue;
536 if (!number_correct(state, x, y)) return 0;
542 static int grid_correct(game_state *state)
544 if (grid_lit(state) &&
545 !grid_overlap(state) &&
546 grid_addsup(state)) return 1;
550 /* --- Board initial setup (blacks, lights, numbers) --- */
552 static void clean_board(game_state *state, int leave_blacks)
555 for (x = 0; x < state->w; x++) {
556 for (y = 0; y < state->h; y++) {
558 GRID(state, flags, x, y) &= F_BLACK;
560 GRID(state, flags, x, y) = 0;
561 GRID(state, lights, x, y) = 0;
567 static void set_blacks(game_state *state, const game_params *params,
570 int x, y, degree = 0, rotate = 0, nblack;
572 int wodd = (state->w % 2) ? 1 : 0;
573 int hodd = (state->h % 2) ? 1 : 0;
576 switch (params->symm) {
577 case SYMM_NONE: degree = 1; rotate = 0; break;
578 case SYMM_ROT2: degree = 2; rotate = 1; break;
579 case SYMM_REF2: degree = 2; rotate = 0; break;
580 case SYMM_ROT4: degree = 4; rotate = 1; break;
581 case SYMM_REF4: degree = 4; rotate = 0; break;
582 default: assert(!"Unknown symmetry type");
584 if (params->symm == SYMM_ROT4 && (state->h != state->w))
585 assert(!"4-fold symmetry unavailable without square grid");
590 if (!rotate) rw += wodd; /* ... but see below. */
592 } else if (degree == 2) {
601 /* clear, then randomise, required region. */
602 clean_board(state, 0);
603 nblack = (rw * rh * params->blackpc) / 100;
604 for (i = 0; i < nblack; i++) {
606 x = random_upto(rs,rw);
607 y = random_upto(rs,rh);
608 } while (GRID(state,flags,x,y) & F_BLACK);
609 GRID(state, flags, x, y) |= F_BLACK;
612 /* Copy required region. */
613 if (params->symm == SYMM_NONE) return;
615 for (x = 0; x < rw; x++) {
616 for (y = 0; y < rh; y++) {
620 xs[1] = state->w - 1 - (rotate ? y : x);
621 ys[1] = rotate ? x : y;
622 xs[2] = rotate ? (state->w - 1 - x) : x;
623 ys[2] = state->h - 1 - y;
624 xs[3] = rotate ? y : (state->w - 1 - x);
625 ys[3] = state->h - 1 - (rotate ? x : y);
629 xs[1] = rotate ? (state->w - 1 - x) : x;
630 ys[1] = state->h - 1 - y;
632 for (i = 1; i < degree; i++) {
633 GRID(state, flags, xs[i], ys[i]) =
634 GRID(state, flags, xs[0], ys[0]);
638 /* SYMM_ROT4 misses the middle square above; fix that here. */
639 if (degree == 4 && rotate && wodd &&
640 (random_upto(rs,100) <= (unsigned int)params->blackpc))
642 state->w/2 + wodd - 1, state->h/2 + hodd - 1) |= F_BLACK;
644 #ifdef SOLVER_DIAGNOSTICS
645 if (verbose) debug_state(state);
649 /* Fills in (does not allocate) a ll_data with all the tiles that would
650 * be illuminated by a light at point (ox,oy). If origin=1 then the
651 * origin is included in this list. */
652 static void list_lights(game_state *state, int ox, int oy, int origin,
657 lld->ox = lld->minx = lld->maxx = ox;
658 lld->oy = lld->miny = lld->maxy = oy;
659 lld->include_origin = origin;
662 for (x = ox-1; x >= 0; x--) {
663 if (GRID(state, flags, x, y) & F_BLACK) break;
664 if (x < lld->minx) lld->minx = x;
666 for (x = ox+1; x < state->w; x++) {
667 if (GRID(state, flags, x, y) & F_BLACK) break;
668 if (x > lld->maxx) lld->maxx = x;
672 for (y = oy-1; y >= 0; y--) {
673 if (GRID(state, flags, x, y) & F_BLACK) break;
674 if (y < lld->miny) lld->miny = y;
676 for (y = oy+1; y < state->h; y++) {
677 if (GRID(state, flags, x, y) & F_BLACK) break;
678 if (y > lld->maxy) lld->maxy = y;
682 /* Makes sure a light is the given state, editing the lights table to suit the
683 * new state if necessary. */
684 static void set_light(game_state *state, int ox, int oy, int on)
689 assert(!(GRID(state,flags,ox,oy) & F_BLACK));
691 if (!on && GRID(state,flags,ox,oy) & F_LIGHT) {
693 GRID(state,flags,ox,oy) &= ~F_LIGHT;
695 } else if (on && !(GRID(state,flags,ox,oy) & F_LIGHT)) {
697 GRID(state,flags,ox,oy) |= F_LIGHT;
702 list_lights(state,ox,oy,1,&lld);
703 FOREACHLIT(&lld, GRID(state,lights,lx,ly) += diff; );
707 /* Returns 1 if removing a light at (x,y) would cause a square to go dark. */
708 static int check_dark(game_state *state, int x, int y)
712 list_lights(state, x, y, 1, &lld);
713 FOREACHLIT(&lld, if (GRID(state,lights,lx,ly) == 1) { return 1; } );
717 /* Sets up an initial random correct position (i.e. every
718 * space lit, and no lights lit by other lights) by filling the
719 * grid with lights and then removing lights one by one at random. */
720 static void place_lights(game_state *state, random_state *rs)
722 int i, x, y, n, *numindices, wh = state->w*state->h;
725 numindices = snewn(wh, int);
726 for (i = 0; i < wh; i++) numindices[i] = i;
727 shuffle(numindices, wh, sizeof(*numindices), rs);
729 /* Place a light on all grid squares without lights. */
730 for (x = 0; x < state->w; x++) {
731 for (y = 0; y < state->h; y++) {
732 GRID(state, flags, x, y) &= ~F_MARK; /* we use this later. */
733 if (GRID(state, flags, x, y) & F_BLACK) continue;
734 set_light(state, x, y, 1);
738 for (i = 0; i < wh; i++) {
739 y = numindices[i] / state->w;
740 x = numindices[i] % state->w;
741 if (!(GRID(state, flags, x, y) & F_LIGHT)) continue;
742 if (GRID(state, flags, x, y) & F_MARK) continue;
743 list_lights(state, x, y, 0, &lld);
745 /* If we're not lighting any lights ourself, don't remove anything. */
747 FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += 1; } );
748 if (n == 0) continue; /* [1] */
750 /* Check whether removing lights we're lighting would cause anything
753 FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += check_dark(state,lx,ly); } );
755 /* No, it wouldn't, so we can remove them all. */
756 FOREACHLIT(&lld, set_light(state,lx,ly, 0); );
757 GRID(state,flags,x,y) |= F_MARK;
760 if (!grid_overlap(state)) {
762 return; /* we're done. */
764 assert(grid_lit(state));
766 /* could get here if the line at [1] continue'd out of the loop. */
767 if (grid_overlap(state)) {
769 assert(!"place_lights failed to resolve overlapping lights!");
774 /* Fills in all black squares with numbers of adjacent lights. */
775 static void place_numbers(game_state *state)
780 for (x = 0; x < state->w; x++) {
781 for (y = 0; y < state->h; y++) {
782 if (!(GRID(state,flags,x,y) & F_BLACK)) continue;
783 get_surrounds(state, x, y, &s);
785 for (i = 0; i < s.npoints; i++) {
786 if (GRID(state,flags,s.points[i].x, s.points[i].y) & F_LIGHT)
789 GRID(state,flags,x,y) |= F_NUMBERED;
790 GRID(state,lights,x,y) = n;
795 /* --- Actual solver, with helper subroutines. --- */
797 static void tsl_callback(game_state *state,
798 int lx, int ly, int *x, int *y, int *n)
800 if (GRID(state,flags,lx,ly) & F_IMPOSSIBLE) return;
801 if (GRID(state,lights,lx,ly) > 0) return;
802 *x = lx; *y = ly; (*n)++;
805 static int try_solve_light(game_state *state, int ox, int oy,
806 unsigned int flags, int lights)
809 int sx = 0, sy = 0, n = 0;
811 if (lights > 0) return 0;
812 if (flags & F_BLACK) return 0;
814 /* We have an unlit square; count how many ways there are left to
815 * place a light that lights us (including this square); if only
816 * one, we must put a light there. Squares that could light us
817 * are, of course, the same as the squares we would light... */
818 list_lights(state, ox, oy, 1, &lld);
819 FOREACHLIT(&lld, { tsl_callback(state, lx, ly, &sx, &sy, &n); });
821 set_light(state, sx, sy, 1);
822 #ifdef SOLVER_DIAGNOSTICS
823 debug(("(%d,%d) can only be lit from (%d,%d); setting to LIGHT\n",
825 if (verbose) debug_state(state);
833 static int could_place_light(unsigned int flags, int lights)
835 if (flags & (F_BLACK | F_IMPOSSIBLE)) return 0;
836 return (lights > 0) ? 0 : 1;
839 static int could_place_light_xy(game_state *state, int x, int y)
841 int lights = GRID(state,lights,x,y);
842 unsigned int flags = GRID(state,flags,x,y);
843 return (could_place_light(flags, lights)) ? 1 : 0;
846 /* For a given number square, determine whether we have enough info
847 * to unambiguously place its lights. */
848 static int try_solve_number(game_state *state, int nx, int ny,
849 unsigned int nflags, int nlights)
852 int x, y, nl, ns, i, ret = 0, lights;
855 if (!(nflags & F_NUMBERED)) return 0;
857 get_surrounds(state,nx,ny,&s);
860 /* nl is no. of lights we need to place, ns is no. of spaces we
861 * have to place them in. Try and narrow these down, and mark
862 * points we can ignore later. */
863 for (i = 0; i < s.npoints; i++) {
864 x = s.points[i].x; y = s.points[i].y;
865 flags = GRID(state,flags,x,y);
866 lights = GRID(state,lights,x,y);
867 if (flags & F_LIGHT) {
868 /* light here already; one less light for one less place. */
870 s.points[i].f |= F_MARK;
871 } else if (!could_place_light(flags, lights)) {
873 s.points[i].f |= F_MARK;
876 if (ns == 0) return 0; /* nowhere to put anything. */
878 /* we have placed all lights we need to around here; all remaining
879 * surrounds are therefore IMPOSSIBLE. */
880 GRID(state,flags,nx,ny) |= F_NUMBERUSED;
881 for (i = 0; i < s.npoints; i++) {
882 if (!(s.points[i].f & F_MARK)) {
883 GRID(state,flags,s.points[i].x,s.points[i].y) |= F_IMPOSSIBLE;
887 #ifdef SOLVER_DIAGNOSTICS
888 printf("Clue at (%d,%d) full; setting unlit to IMPOSSIBLE.\n",
890 if (verbose) debug_state(state);
892 } else if (nl == ns) {
893 /* we have as many lights to place as spaces; fill them all. */
894 GRID(state,flags,nx,ny) |= F_NUMBERUSED;
895 for (i = 0; i < s.npoints; i++) {
896 if (!(s.points[i].f & F_MARK)) {
897 set_light(state, s.points[i].x,s.points[i].y, 1);
901 #ifdef SOLVER_DIAGNOSTICS
902 printf("Clue at (%d,%d) trivial; setting unlit to LIGHT.\n",
904 if (verbose) debug_state(state);
915 #define SCRATCHSZ (state->w+state->h)
917 /* New solver algorithm: overlapping sets can add IMPOSSIBLE flags.
918 * Algorithm thanks to Simon:
920 * (a) Any square where you can place a light has a set of squares
921 * which would become non-lights as a result. (This includes
922 * squares lit by the first square, and can also include squares
923 * adjacent to the same clue square if the new light is the last
924 * one around that clue.) Call this MAKESDARK(x,y) with (x,y) being
925 * the square you place a light.
927 * (b) Any unlit square has a set of squares on which you could place
928 * a light to illuminate it. (Possibly including itself, of
929 * course.) This set of squares has the property that _at least
930 * one_ of them must contain a light. Sets of this type also arise
931 * from clue squares. Call this MAKESLIGHT(x,y), again with (x,y)
932 * the square you would place a light.
934 * (c) If there exists (dx,dy) and (lx,ly) such that MAKESDARK(dx,dy) is
935 * a superset of MAKESLIGHT(lx,ly), this implies that placing a light at
936 * (dx,dy) would either leave no remaining way to illuminate a certain
937 * square, or would leave no remaining way to fulfill a certain clue
938 * (at lx,ly). In either case, a light can be ruled out at that position.
940 * So, we construct all possible MAKESLIGHT sets, both from unlit squares
941 * and clue squares, and then we look for plausible MAKESDARK sets that include
942 * our (lx,ly) to see if we can find a (dx,dy) to rule out. By the time we have
943 * constructed the MAKESLIGHT set we don't care about (lx,ly), just the set
946 * Once we have such a set, Simon came up with a Cunning Plan to find
947 * the most sensible MAKESDARK candidate:
949 * (a) for each square S in your set X, find all the squares which _would_
950 * rule it out. That means any square which would light S, plus
951 * any square adjacent to the same clue square as S (provided
952 * that clue square has only one remaining light to be placed).
953 * It's not hard to make this list. Don't do anything with this
954 * data at the moment except _count_ the squares.
956 * (b) Find the square S_min in the original set which has the
957 * _smallest_ number of other squares which would rule it out.
959 * (c) Find all the squares that rule out S_min (it's probably
960 * better to recompute this than to have stored it during step
961 * (a), since the CPU requirement is modest but the storage
962 * cost would get ugly.) For each of these squares, see if it
963 * rules out everything else in the set X. Any which does can
964 * be marked as not-a-light.
968 typedef void (*trl_cb)(game_state *state, int dx, int dy,
969 struct setscratch *scratch, int n, void *ctx);
971 static void try_rule_out(game_state *state, int x, int y,
972 struct setscratch *scratch, int n,
973 trl_cb cb, void *ctx);
975 static void trl_callback_search(game_state *state, int dx, int dy,
976 struct setscratch *scratch, int n, void *ignored)
980 #ifdef SOLVER_DIAGNOSTICS
981 if (verbose) debug(("discount cb: light at (%d,%d)\n", dx, dy));
984 for (i = 0; i < n; i++) {
985 if (dx == scratch[i].x && dy == scratch[i].y) {
992 static void trl_callback_discount(game_state *state, int dx, int dy,
993 struct setscratch *scratch, int n, void *ctx)
995 int *didsth = (int *)ctx;
998 if (GRID(state,flags,dx,dy) & F_IMPOSSIBLE) {
999 #ifdef SOLVER_DIAGNOSTICS
1000 debug(("Square at (%d,%d) already impossible.\n", dx,dy));
1005 /* Check whether a light at (dx,dy) rules out everything
1006 * in scratch, and mark (dx,dy) as IMPOSSIBLE if it does.
1007 * We can use try_rule_out for this as well, as the set of
1008 * squares which would rule out (x,y) is the same as the
1009 * set of squares which (x,y) would rule out. */
1011 #ifdef SOLVER_DIAGNOSTICS
1012 if (verbose) debug(("Checking whether light at (%d,%d) rules out everything in scratch.\n", dx, dy));
1015 for (i = 0; i < n; i++)
1017 try_rule_out(state, dx, dy, scratch, n, trl_callback_search, NULL);
1018 for (i = 0; i < n; i++) {
1019 if (scratch[i].n == 0) return;
1021 /* The light ruled out everything in scratch. Yay. */
1022 GRID(state,flags,dx,dy) |= F_IMPOSSIBLE;
1023 #ifdef SOLVER_DIAGNOSTICS
1024 debug(("Set reduction discounted square at (%d,%d):\n", dx,dy));
1025 if (verbose) debug_state(state);
1031 static void trl_callback_incn(game_state *state, int dx, int dy,
1032 struct setscratch *scratch, int n, void *ctx)
1034 struct setscratch *s = (struct setscratch *)ctx;
1038 static void try_rule_out(game_state *state, int x, int y,
1039 struct setscratch *scratch, int n,
1040 trl_cb cb, void *ctx)
1042 /* XXX Find all the squares which would rule out (x,y); anything
1043 * that would light it as well as squares adjacent to same clues
1044 * as X assuming that clue only has one remaining light.
1045 * Call the callback with each square. */
1048 int i, j, curr_lights, tot_lights;
1050 /* Find all squares that would rule out a light at (x,y) and call trl_cb
1051 * with them: anything that would light (x,y)... */
1053 list_lights(state, x, y, 0, &lld);
1054 FOREACHLIT(&lld, { if (could_place_light_xy(state, lx, ly)) { cb(state, lx, ly, scratch, n, ctx); } });
1056 /* ... as well as any empty space (that isn't x,y) next to any clue square
1057 * next to (x,y) that only has one light left to place. */
1059 get_surrounds(state, x, y, &s);
1060 for (i = 0; i < s.npoints; i++) {
1061 if (!(GRID(state,flags,s.points[i].x,s.points[i].y) & F_NUMBERED))
1063 /* we have an adjacent clue square; find /its/ surrounds
1064 * and count the remaining lights it needs. */
1065 get_surrounds(state,s.points[i].x,s.points[i].y,&ss);
1067 for (j = 0; j < ss.npoints; j++) {
1068 if (GRID(state,flags,ss.points[j].x,ss.points[j].y) & F_LIGHT)
1071 tot_lights = GRID(state, lights, s.points[i].x, s.points[i].y);
1072 /* We have a clue with tot_lights to fill, and curr_lights currently
1073 * around it. If adding a light at (x,y) fills up the clue (i.e.
1074 * curr_lights + 1 = tot_lights) then we need to discount all other
1075 * unlit squares around the clue. */
1076 if ((curr_lights + 1) == tot_lights) {
1077 for (j = 0; j < ss.npoints; j++) {
1078 int lx = ss.points[j].x, ly = ss.points[j].y;
1079 if (lx == x && ly == y) continue;
1080 if (could_place_light_xy(state, lx, ly))
1081 cb(state, lx, ly, scratch, n, ctx);
1087 #ifdef SOLVER_DIAGNOSTICS
1088 static void debug_scratch(const char *msg, struct setscratch *scratch, int n)
1091 debug(("%s scratch (%d elements):\n", msg, n));
1092 for (i = 0; i < n; i++) {
1093 debug((" (%d,%d) n%d\n", scratch[i].x, scratch[i].y, scratch[i].n));
1098 static int discount_set(game_state *state,
1099 struct setscratch *scratch, int n)
1101 int i, besti, bestn, didsth = 0;
1103 #ifdef SOLVER_DIAGNOSTICS
1104 if (verbose > 1) debug_scratch("discount_set", scratch, n);
1106 if (n == 0) return 0;
1108 for (i = 0; i < n; i++) {
1109 try_rule_out(state, scratch[i].x, scratch[i].y, scratch, n,
1110 trl_callback_incn, (void*)&(scratch[i]));
1112 #ifdef SOLVER_DIAGNOSTICS
1113 if (verbose > 1) debug_scratch("discount_set after count", scratch, n);
1116 besti = -1; bestn = SCRATCHSZ;
1117 for (i = 0; i < n; i++) {
1118 if (scratch[i].n < bestn) {
1119 bestn = scratch[i].n;
1123 #ifdef SOLVER_DIAGNOSTICS
1124 if (verbose > 1) debug(("best square (%d,%d) with n%d.\n",
1125 scratch[besti].x, scratch[besti].y, scratch[besti].n));
1127 try_rule_out(state, scratch[besti].x, scratch[besti].y, scratch, n,
1128 trl_callback_discount, (void*)&didsth);
1129 #ifdef SOLVER_DIAGNOSTICS
1130 if (didsth) debug((" [from square (%d,%d)]\n",
1131 scratch[besti].x, scratch[besti].y));
1137 static void discount_clear(game_state *state, struct setscratch *scratch, int *n)
1140 memset(scratch, 0, SCRATCHSZ * sizeof(struct setscratch));
1143 static void unlit_cb(game_state *state, int lx, int ly,
1144 struct setscratch *scratch, int *n)
1146 if (could_place_light_xy(state, lx, ly)) {
1147 scratch[*n].x = lx; scratch[*n].y = ly; (*n)++;
1151 /* Construct a MAKESLIGHT set from an unlit square. */
1152 static int discount_unlit(game_state *state, int x, int y,
1153 struct setscratch *scratch)
1158 #ifdef SOLVER_DIAGNOSTICS
1159 if (verbose) debug(("Trying to discount for unlit square at (%d,%d).\n", x, y));
1160 if (verbose > 1) debug_state(state);
1163 discount_clear(state, scratch, &n);
1165 list_lights(state, x, y, 1, &lld);
1166 FOREACHLIT(&lld, { unlit_cb(state, lx, ly, scratch, &n); });
1167 didsth = discount_set(state, scratch, n);
1168 #ifdef SOLVER_DIAGNOSTICS
1169 if (didsth) debug((" [from unlit square at (%d,%d)].\n", x, y));
1175 /* Construct a series of MAKESLIGHT sets from a clue square.
1176 * for a clue square with N remaining spaces that must contain M lights, every
1177 * subset of size N-M+1 of those N spaces forms such a set.
1180 static int discount_clue(game_state *state, int x, int y,
1181 struct setscratch *scratch)
1183 int slen, m = GRID(state, lights, x, y), n, i, didsth = 0, lights;
1185 surrounds s, sempty;
1188 if (m == 0) return 0;
1190 #ifdef SOLVER_DIAGNOSTICS
1191 if (verbose) debug(("Trying to discount for sets at clue (%d,%d).\n", x, y));
1192 if (verbose > 1) debug_state(state);
1195 /* m is no. of lights still to place; starts off at the clue value
1196 * and decreases when we find a light already down.
1197 * n is no. of spaces left; starts off at 0 and goes up when we find
1198 * a plausible space. */
1200 get_surrounds(state, x, y, &s);
1201 memset(&sempty, 0, sizeof(surrounds));
1202 for (i = 0; i < s.npoints; i++) {
1203 int lx = s.points[i].x, ly = s.points[i].y;
1204 flags = GRID(state,flags,lx,ly);
1205 lights = GRID(state,lights,lx,ly);
1207 if (flags & F_LIGHT) m--;
1209 if (could_place_light(flags, lights)) {
1210 sempty.points[sempty.npoints].x = lx;
1211 sempty.points[sempty.npoints].y = ly;
1215 n = sempty.npoints; /* sempty is now a surrounds of only blank squares. */
1216 if (n == 0) return 0; /* clue is full already. */
1218 if (m < 0 || m > n) return 0; /* become impossible. */
1220 combi = new_combi(n - m + 1, n);
1221 while (next_combi(combi)) {
1222 discount_clear(state, scratch, &slen);
1223 for (i = 0; i < combi->r; i++) {
1224 scratch[slen].x = sempty.points[combi->a[i]].x;
1225 scratch[slen].y = sempty.points[combi->a[i]].y;
1228 if (discount_set(state, scratch, slen)) didsth = 1;
1231 #ifdef SOLVER_DIAGNOSTICS
1232 if (didsth) debug((" [from clue at (%d,%d)].\n", x, y));
1237 #define F_SOLVE_FORCEUNIQUE 1
1238 #define F_SOLVE_DISCOUNTSETS 2
1239 #define F_SOLVE_ALLOWRECURSE 4
1241 static unsigned int flags_from_difficulty(int difficulty)
1243 unsigned int sflags = F_SOLVE_FORCEUNIQUE;
1244 assert(difficulty <= DIFFCOUNT);
1245 if (difficulty >= 1) sflags |= F_SOLVE_DISCOUNTSETS;
1246 if (difficulty >= 2) sflags |= F_SOLVE_ALLOWRECURSE;
1250 #define MAXRECURSE 5
1252 static int solve_sub(game_state *state,
1253 unsigned int solve_flags, int depth,
1257 int x, y, didstuff, ncanplace, lights;
1258 int bestx, besty, n, bestn, copy_soluble, self_soluble, ret, maxrecurse = 0;
1261 struct setscratch *sscratch = NULL;
1263 #ifdef SOLVER_DIAGNOSTICS
1264 printf("solve_sub: depth = %d\n", depth);
1266 if (maxdepth && *maxdepth < depth) *maxdepth = depth;
1267 if (solve_flags & F_SOLVE_ALLOWRECURSE) maxrecurse = MAXRECURSE;
1270 if (grid_overlap(state)) {
1271 /* Our own solver, from scratch, should never cause this to happen
1272 * (assuming a soluble grid). However, if we're trying to solve
1273 * from a half-completed *incorrect* grid this might occur; we
1274 * just return the 'no solutions' code in this case. */
1278 if (grid_correct(state)) { ret = 1; goto done; }
1282 /* These 2 loops, and the functions they call, are the critical loops
1283 * for timing; any optimisations should look here first. */
1284 for (x = 0; x < state->w; x++) {
1285 for (y = 0; y < state->h; y++) {
1286 flags = GRID(state,flags,x,y);
1287 lights = GRID(state,lights,x,y);
1288 ncanplace += could_place_light(flags, lights);
1290 if (try_solve_light(state, x, y, flags, lights)) didstuff = 1;
1291 if (try_solve_number(state, x, y, flags, lights)) didstuff = 1;
1294 if (didstuff) continue;
1296 /* nowhere to put a light, puzzle is unsoluble. */
1300 if (solve_flags & F_SOLVE_DISCOUNTSETS) {
1301 if (!sscratch) sscratch = snewn(SCRATCHSZ, struct setscratch);
1302 /* Try a more cunning (and more involved) way... more details above. */
1303 for (x = 0; x < state->w; x++) {
1304 for (y = 0; y < state->h; y++) {
1305 flags = GRID(state,flags,x,y);
1306 lights = GRID(state,lights,x,y);
1308 if (!(flags & F_BLACK) && lights == 0) {
1309 if (discount_unlit(state, x, y, sscratch)) {
1311 goto reduction_success;
1313 } else if (flags & F_NUMBERED) {
1314 if (discount_clue(state, x, y, sscratch)) {
1316 goto reduction_success;
1323 if (didstuff) continue;
1325 /* We now have to make a guess; we have places to put lights but
1326 * no definite idea about where they can go. */
1327 if (depth >= maxrecurse) {
1328 /* mustn't delve any deeper. */
1329 ret = -1; goto done;
1331 /* Of all the squares that we could place a light, pick the one
1332 * that would light the most currently unlit squares. */
1333 /* This heuristic was just plucked from the air; there may well be
1334 * a more efficient way of choosing a square to flip to minimise
1337 bestx = besty = -1; /* suyb */
1338 for (x = 0; x < state->w; x++) {
1339 for (y = 0; y < state->h; y++) {
1340 flags = GRID(state,flags,x,y);
1341 lights = GRID(state,lights,x,y);
1342 if (!could_place_light(flags, lights)) continue;
1345 list_lights(state, x, y, 1, &lld);
1346 FOREACHLIT(&lld, { if (GRID(state,lights,lx,ly) == 0) n++; });
1348 bestn = n; bestx = x; besty = y;
1353 assert(bestx >= 0 && besty >= 0);
1355 /* Now we've chosen a plausible (x,y), try to solve it once as 'lit'
1356 * and once as 'impossible'; we need to make one copy to do this. */
1358 scopy = dup_game(state);
1359 #ifdef SOLVER_DIAGNOSTICS
1360 debug(("Recursing #1: trying (%d,%d) as IMPOSSIBLE\n", bestx, besty));
1362 GRID(state,flags,bestx,besty) |= F_IMPOSSIBLE;
1363 self_soluble = solve_sub(state, solve_flags, depth+1, maxdepth);
1365 if (!(solve_flags & F_SOLVE_FORCEUNIQUE) && self_soluble > 0) {
1366 /* we didn't care about finding all solutions, and we just
1367 * found one; return with it immediately. */
1373 #ifdef SOLVER_DIAGNOSTICS
1374 debug(("Recursing #2: trying (%d,%d) as LIGHT\n", bestx, besty));
1376 set_light(scopy, bestx, besty, 1);
1377 copy_soluble = solve_sub(scopy, solve_flags, depth+1, maxdepth);
1379 /* If we wanted a unique solution but we hit our recursion limit
1380 * (on either branch) then we have to assume we didn't find possible
1381 * extra solutions, and return 'not soluble'. */
1382 if ((solve_flags & F_SOLVE_FORCEUNIQUE) &&
1383 ((copy_soluble < 0) || (self_soluble < 0))) {
1385 /* Make sure that whether or not it was self or copy (or both) that
1386 * were soluble, that we return a solved state in self. */
1387 } else if (copy_soluble <= 0) {
1388 /* copy wasn't soluble; keep self state and return that result. */
1390 } else if (self_soluble <= 0) {
1391 /* copy solved and we didn't, so copy in copy's (now solved)
1392 * flags and light state. */
1393 memcpy(state->lights, scopy->lights,
1394 scopy->w * scopy->h * sizeof(int));
1395 memcpy(state->flags, scopy->flags,
1396 scopy->w * scopy->h * sizeof(unsigned int));
1399 ret = copy_soluble + self_soluble;
1405 if (sscratch) sfree(sscratch);
1406 #ifdef SOLVER_DIAGNOSTICS
1408 debug(("solve_sub: depth = %d returning, ran out of recursion.\n",
1411 debug(("solve_sub: depth = %d returning, %d solutions.\n",
1417 /* Fills in the (possibly partially-complete) game_state as far as it can,
1418 * returning the number of possible solutions. If it returns >0 then the
1419 * game_state will be in a solved state, but you won't know which one. */
1420 static int dosolve(game_state *state, int solve_flags, int *maxdepth)
1424 for (x = 0; x < state->w; x++) {
1425 for (y = 0; y < state->h; y++) {
1426 GRID(state,flags,x,y) &= ~F_NUMBERUSED;
1429 nsol = solve_sub(state, solve_flags, 0, maxdepth);
1433 static int strip_unused_nums(game_state *state)
1436 for (x = 0; x < state->w; x++) {
1437 for (y = 0; y < state->h; y++) {
1438 if ((GRID(state,flags,x,y) & F_NUMBERED) &&
1439 !(GRID(state,flags,x,y) & F_NUMBERUSED)) {
1440 GRID(state,flags,x,y) &= ~F_NUMBERED;
1441 GRID(state,lights,x,y) = 0;
1446 debug(("Stripped %d unused numbers.\n", n));
1450 static void unplace_lights(game_state *state)
1453 for (x = 0; x < state->w; x++) {
1454 for (y = 0; y < state->h; y++) {
1455 if (GRID(state,flags,x,y) & F_LIGHT)
1456 set_light(state,x,y,0);
1457 GRID(state,flags,x,y) &= ~F_IMPOSSIBLE;
1458 GRID(state,flags,x,y) &= ~F_NUMBERUSED;
1463 static int puzzle_is_good(game_state *state, int difficulty)
1465 int nsol, mdepth = 0;
1466 unsigned int sflags = flags_from_difficulty(difficulty);
1468 unplace_lights(state);
1470 #ifdef SOLVER_DIAGNOSTICS
1471 debug(("Trying to solve with difficulty %d (0x%x):\n",
1472 difficulty, sflags));
1473 if (verbose) debug_state(state);
1476 nsol = dosolve(state, sflags, &mdepth);
1477 /* if we wanted an easy puzzle, make sure we didn't need recursion. */
1478 if (!(sflags & F_SOLVE_ALLOWRECURSE) && mdepth > 0) {
1479 debug(("Ignoring recursive puzzle.\n"));
1483 debug(("%d solutions found.\n", nsol));
1484 if (nsol <= 0) return 0;
1485 if (nsol > 1) return 0;
1489 /* --- New game creation and user input code. --- */
1491 /* The basic algorithm here is to generate the most complex grid possible
1492 * while honouring two restrictions:
1494 * * we require a unique solution, and
1495 * * either we require solubility with no recursion (!params->recurse)
1496 * * or we require some recursion. (params->recurse).
1498 * The solver helpfully keeps track of the numbers it needed to use to
1499 * get its solution, so we use that to remove an initial set of numbers
1500 * and check we still satsify our requirements (on uniqueness and
1501 * non-recursiveness, if applicable; we don't check explicit recursiveness
1504 * Then we try to remove all numbers in a random order, and see if we
1505 * still satisfy requirements (putting them back if we didn't).
1507 * Removing numbers will always, in general terms, make a puzzle require
1508 * more recursion but it may also mean a puzzle becomes non-unique.
1510 * Once we're done, if we wanted a recursive puzzle but the most difficult
1511 * puzzle we could come up with was non-recursive, we give up and try a new
1514 #define MAX_GRIDGEN_TRIES 20
1516 static char *new_game_desc(const game_params *params_in, random_state *rs,
1517 char **aux, int interactive)
1519 game_params params_copy = *params_in; /* structure copy */
1520 game_params *params = ¶ms_copy;
1521 game_state *news = new_state(params), *copys;
1522 int i, j, run, x, y, wh = params->w*params->h, num;
1526 /* Construct a shuffled list of grid positions; we only
1527 * do this once, because if it gets used more than once it'll
1528 * be on a different grid layout. */
1529 numindices = snewn(wh, int);
1530 for (j = 0; j < wh; j++) numindices[j] = j;
1531 shuffle(numindices, wh, sizeof(*numindices), rs);
1534 for (i = 0; i < MAX_GRIDGEN_TRIES; i++) {
1535 set_blacks(news, params, rs); /* also cleans board. */
1537 /* set up lights and then the numbers, and remove the lights */
1538 place_lights(news, rs);
1539 debug(("Generating initial grid.\n"));
1540 place_numbers(news);
1541 if (!puzzle_is_good(news, params->difficulty)) continue;
1543 /* Take a copy, remove numbers we didn't use and check there's
1544 * still a unique solution; if so, use the copy subsequently. */
1545 copys = dup_game(news);
1546 strip_unused_nums(copys);
1547 if (!puzzle_is_good(copys, params->difficulty)) {
1548 debug(("Stripped grid is not good, reverting.\n"));
1555 /* Go through grid removing numbers at random one-by-one and
1556 * trying to solve again; if it ceases to be good put the number back. */
1557 for (j = 0; j < wh; j++) {
1558 y = numindices[j] / params->w;
1559 x = numindices[j] % params->w;
1560 if (!(GRID(news, flags, x, y) & F_NUMBERED)) continue;
1561 num = GRID(news, lights, x, y);
1562 GRID(news, lights, x, y) = 0;
1563 GRID(news, flags, x, y) &= ~F_NUMBERED;
1564 if (!puzzle_is_good(news, params->difficulty)) {
1565 GRID(news, lights, x, y) = num;
1566 GRID(news, flags, x, y) |= F_NUMBERED;
1568 debug(("Removed (%d,%d) still soluble.\n", x, y));
1570 if (params->difficulty > 0) {
1571 /* Was the maximally-difficult puzzle difficult enough?
1572 * Check we can't solve it with a more simplistic solver. */
1573 if (puzzle_is_good(news, params->difficulty-1)) {
1574 debug(("Maximally-hard puzzle still not hard enough, skipping.\n"));
1581 /* Couldn't generate a good puzzle in however many goes. Ramp up the
1582 * %age of black squares (if we didn't already have lots; in which case
1583 * why couldn't we generate a puzzle?) and try again. */
1584 if (params->blackpc < 90) params->blackpc += 5;
1585 debug(("New black layout %d%%.\n", params->blackpc));
1588 /* Game is encoded as a long string one character per square;
1590 * 'B' is a black square with no number
1591 * '0', '1', '2', '3', '4' is a black square with a number. */
1592 ret = snewn((params->w * params->h) + 1, char);
1595 for (y = 0; y < params->h; y++) {
1596 for (x = 0; x < params->w; x++) {
1597 if (GRID(news,flags,x,y) & F_BLACK) {
1599 *p++ = ('a'-1) + run;
1602 if (GRID(news,flags,x,y) & F_NUMBERED)
1603 *p++ = '0' + GRID(news,lights,x,y);
1608 *p++ = ('a'-1) + run;
1616 *p++ = ('a'-1) + run;
1620 assert(p - ret <= params->w * params->h);
1627 static char *validate_desc(const game_params *params, const char *desc)
1630 for (i = 0; i < params->w*params->h; i++) {
1631 if (*desc >= '0' && *desc <= '4')
1633 else if (*desc == 'B')
1635 else if (*desc >= 'a' && *desc <= 'z')
1636 i += *desc - 'a'; /* and the i++ will add another one */
1638 return "Game description shorter than expected";
1640 return "Game description contained unexpected character";
1643 if (*desc || i > params->w*params->h)
1644 return "Game description longer than expected";
1649 static game_state *new_game(midend *me, const game_params *params,
1652 game_state *ret = new_state(params);
1656 for (y = 0; y < params->h; y++) {
1657 for (x = 0; x < params->w; x++) {
1663 if (c >= 'a' && c <= 'z')
1673 case '0': case '1': case '2': case '3': case '4':
1674 GRID(ret,flags,x,y) |= F_NUMBERED;
1675 GRID(ret,lights,x,y) = (c - '0');
1679 GRID(ret,flags,x,y) |= F_BLACK;
1687 assert(!"Malformed desc.");
1692 if (*desc) assert(!"Over-long desc.");
1697 static char *solve_game(const game_state *state, const game_state *currstate,
1698 const char *aux, char **error)
1701 char *move = NULL, buf[80];
1702 int movelen, movesize, x, y, len;
1703 unsigned int oldflags, solvedflags, sflags;
1705 /* We don't care here about non-unique puzzles; if the
1706 * user entered one themself then I doubt they care. */
1708 sflags = F_SOLVE_ALLOWRECURSE | F_SOLVE_DISCOUNTSETS;
1710 /* Try and solve from where we are now (for non-unique
1711 * puzzles this may produce a different answer). */
1712 solved = dup_game(currstate);
1713 if (dosolve(solved, sflags, NULL) > 0) goto solved;
1716 /* That didn't work; try solving from the clean puzzle. */
1717 solved = dup_game(state);
1718 if (dosolve(solved, sflags, NULL) > 0) goto solved;
1719 *error = "Unable to find a solution to this puzzle.";
1724 move = snewn(movesize, char);
1726 move[movelen++] = 'S';
1727 move[movelen] = '\0';
1728 for (x = 0; x < currstate->w; x++) {
1729 for (y = 0; y < currstate->h; y++) {
1731 oldflags = GRID(currstate, flags, x, y);
1732 solvedflags = GRID(solved, flags, x, y);
1733 if ((oldflags & F_LIGHT) != (solvedflags & F_LIGHT))
1734 len = sprintf(buf, ";L%d,%d", x, y);
1735 else if ((oldflags & F_IMPOSSIBLE) != (solvedflags & F_IMPOSSIBLE))
1736 len = sprintf(buf, ";I%d,%d", x, y);
1738 if (movelen + len >= movesize) {
1739 movesize = movelen + len + 256;
1740 move = sresize(move, movesize, char);
1742 strcpy(move + movelen, buf);
1753 static int game_can_format_as_text_now(const game_params *params)
1758 /* 'borrowed' from slant.c, mainly. I could have printed it one
1759 * character per cell (like debug_state) but that comes out tiny.
1760 * 'L' is used for 'light here' because 'O' looks too much like '0'
1761 * (black square with no surrounding lights). */
1762 static char *game_text_format(const game_state *state)
1764 int w = state->w, h = state->h, W = w+1, H = h+1;
1765 int x, y, len, lights;
1769 len = (h+H) * (w+W+1) + 1;
1770 ret = snewn(len, char);
1773 for (y = 0; y < H; y++) {
1774 for (x = 0; x < W; x++) {
1781 for (x = 0; x < W; x++) {
1784 /* actual interesting bit. */
1785 flags = GRID(state, flags, x, y);
1786 lights = GRID(state, lights, x, y);
1787 if (flags & F_BLACK) {
1788 if (flags & F_NUMBERED)
1789 *p++ = '0' + lights;
1793 if (flags & F_LIGHT)
1795 else if (flags & F_IMPOSSIBLE)
1797 else if (lights > 0)
1809 assert(p - ret == len);
1814 int cur_x, cur_y, cur_visible;
1817 static game_ui *new_ui(const game_state *state)
1819 game_ui *ui = snew(game_ui);
1820 ui->cur_x = ui->cur_y = ui->cur_visible = 0;
1824 static void free_ui(game_ui *ui)
1829 static char *encode_ui(const game_ui *ui)
1831 /* nothing to encode. */
1835 static void decode_ui(game_ui *ui, const char *encoding)
1837 /* nothing to decode. */
1840 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1841 const game_state *newstate)
1843 if (newstate->completed)
1844 ui->cur_visible = 0;
1847 #define DF_BLACK 1 /* black square */
1848 #define DF_NUMBERED 2 /* black square with number */
1849 #define DF_LIT 4 /* display (white) square lit up */
1850 #define DF_LIGHT 8 /* display light in square */
1851 #define DF_OVERLAP 16 /* display light as overlapped */
1852 #define DF_CURSOR 32 /* display cursor */
1853 #define DF_NUMBERWRONG 64 /* display black numbered square as error. */
1854 #define DF_FLASH 128 /* background flash is on. */
1855 #define DF_IMPOSSIBLE 256 /* display non-light little square */
1857 struct game_drawstate {
1860 unsigned int *flags; /* width * height */
1865 /* Believe it or not, this empty = "" hack is needed to get around a bug in
1866 * the prc-tools gcc when optimisation is turned on; before, it produced:
1867 lightup-sect.c: In function `interpret_move':
1868 lightup-sect.c:1416: internal error--unrecognizable insn:
1869 (insn 582 580 583 (set (reg:SI 134)
1873 static char *interpret_move(const game_state *state, game_ui *ui,
1874 const game_drawstate *ds,
1875 int x, int y, int button)
1877 enum { NONE, FLIP_LIGHT, FLIP_IMPOSSIBLE } action = NONE;
1878 int cx = -1, cy = -1;
1880 char buf[80], *nullret = UI_UPDATE, *empty = UI_UPDATE, c;
1882 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1883 if (ui->cur_visible)
1885 ui->cur_visible = 0;
1888 action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE;
1889 } else if (IS_CURSOR_SELECT(button) ||
1890 button == 'i' || button == 'I' ||
1891 button == ' ' || button == '\r' || button == '\n') {
1892 if (ui->cur_visible) {
1893 /* Only allow cursor-effect operations if the cursor is visible
1894 * (otherwise you have no idea which square it might be affecting) */
1897 action = (button == 'i' || button == 'I' || button == CURSOR_SELECT2) ?
1898 FLIP_IMPOSSIBLE : FLIP_LIGHT;
1900 ui->cur_visible = 1;
1901 } else if (IS_CURSOR_MOVE(button)) {
1902 move_cursor(button, &ui->cur_x, &ui->cur_y, state->w, state->h, 0);
1903 ui->cur_visible = 1;
1910 case FLIP_IMPOSSIBLE:
1911 if (cx < 0 || cy < 0 || cx >= state->w || cy >= state->h)
1913 flags = GRID(state, flags, cx, cy);
1914 if (flags & F_BLACK)
1916 if (action == FLIP_LIGHT) {
1918 if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'I'; else c = 'L';
1920 if (flags & F_IMPOSSIBLE) return nullret;
1925 if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'L'; else c = 'I';
1927 if (flags & F_LIGHT) return nullret;
1931 sprintf(buf, "%c%d,%d", (int)c, cx, cy);
1938 assert(!"Shouldn't get here!");
1943 static game_state *execute_move(const game_state *state, const char *move)
1945 game_state *ret = dup_game(state);
1949 if (!*move) goto badmove;
1954 ret->used_solve = TRUE;
1956 } else if (c == 'L' || c == 'I') {
1958 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1959 x < 0 || y < 0 || x >= ret->w || y >= ret->h)
1962 flags = GRID(ret, flags, x, y);
1963 if (flags & F_BLACK) goto badmove;
1965 /* LIGHT and IMPOSSIBLE are mutually exclusive. */
1967 GRID(ret, flags, x, y) &= ~F_IMPOSSIBLE;
1968 set_light(ret, x, y, (flags & F_LIGHT) ? 0 : 1);
1970 set_light(ret, x, y, 0);
1971 GRID(ret, flags, x, y) ^= F_IMPOSSIBLE;
1974 } else goto badmove;
1978 else if (*move) goto badmove;
1980 if (grid_correct(ret)) ret->completed = 1;
1988 /* ----------------------------------------------------------------------
1992 /* XXX entirely cloned from fifteen.c; separate out? */
1993 static void game_compute_size(const game_params *params, int tilesize,
1996 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1997 struct { int tilesize; } ads, *ds = &ads;
1998 ads.tilesize = tilesize;
2000 *x = TILE_SIZE * params->w + 2 * BORDER;
2001 *y = TILE_SIZE * params->h + 2 * BORDER;
2004 static void game_set_size(drawing *dr, game_drawstate *ds,
2005 const game_params *params, int tilesize)
2007 ds->tilesize = tilesize;
2008 ds->crad = 3*(tilesize-1)/8;
2011 static float *game_colours(frontend *fe, int *ncolours)
2013 float *ret = snewn(3 * NCOLOURS, float);
2016 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2018 for (i = 0; i < 3; i++) {
2019 ret[COL_BLACK * 3 + i] = 0.0F;
2020 ret[COL_LIGHT * 3 + i] = 1.0F;
2021 ret[COL_CURSOR * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 2.0F;
2022 ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 1.5F;
2026 ret[COL_ERROR * 3 + 0] = 1.0F;
2027 ret[COL_ERROR * 3 + 1] = 0.25F;
2028 ret[COL_ERROR * 3 + 2] = 0.25F;
2030 ret[COL_LIT * 3 + 0] = 1.0F;
2031 ret[COL_LIT * 3 + 1] = 1.0F;
2032 ret[COL_LIT * 3 + 2] = 0.0F;
2034 *ncolours = NCOLOURS;
2038 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2040 struct game_drawstate *ds = snew(struct game_drawstate);
2043 ds->tilesize = ds->crad = 0;
2044 ds->w = state->w; ds->h = state->h;
2046 ds->flags = snewn(ds->w*ds->h, unsigned int);
2047 for (i = 0; i < ds->w*ds->h; i++)
2055 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2061 /* At some stage we should put these into a real options struct.
2062 * Note that tile_redraw has no #ifdeffery; it relies on tile_flags not
2063 * to put those flags in. */
2065 #define HINT_OVERLAPS
2066 #define HINT_NUMBERS
2068 static unsigned int tile_flags(game_drawstate *ds, const game_state *state,
2069 const game_ui *ui, int x, int y, int flashing)
2071 unsigned int flags = GRID(state, flags, x, y);
2072 int lights = GRID(state, lights, x, y);
2073 unsigned int ret = 0;
2075 if (flashing) ret |= DF_FLASH;
2076 if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
2079 if (flags & F_BLACK) {
2081 if (flags & F_NUMBERED) {
2083 if (number_wrong(state, x, y))
2084 ret |= DF_NUMBERWRONG;
2090 if (lights > 0) ret |= DF_LIT;
2092 if (flags & F_LIGHT) {
2094 #ifdef HINT_OVERLAPS
2095 if (lights > 1) ret |= DF_OVERLAP;
2098 if (flags & F_IMPOSSIBLE) ret |= DF_IMPOSSIBLE;
2103 static void tile_redraw(drawing *dr, game_drawstate *ds,
2104 const game_state *state, int x, int y)
2106 unsigned int ds_flags = GRID(ds, flags, x, y);
2107 int dx = COORD(x), dy = COORD(y);
2108 int lit = (ds_flags & DF_FLASH) ? COL_GRID : COL_LIT;
2110 if (ds_flags & DF_BLACK) {
2111 draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_BLACK);
2112 if (ds_flags & DF_NUMBERED) {
2113 int ccol = (ds_flags & DF_NUMBERWRONG) ? COL_ERROR : COL_LIGHT;
2116 /* We know that this won't change over the course of the game
2117 * so it's OK to ignore this when calculating whether or not
2118 * to redraw the tile. */
2119 sprintf(str, "%d", GRID(state, lights, x, y));
2120 draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
2121 FONT_VARIABLE, TILE_SIZE*3/5,
2122 ALIGN_VCENTRE | ALIGN_HCENTRE, ccol, str);
2125 draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE,
2126 (ds_flags & DF_LIT) ? lit : COL_BACKGROUND);
2127 draw_rect_outline(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_GRID);
2128 if (ds_flags & DF_LIGHT) {
2129 int lcol = (ds_flags & DF_OVERLAP) ? COL_ERROR : COL_LIGHT;
2130 draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, TILE_RADIUS,
2132 } else if ((ds_flags & DF_IMPOSSIBLE)) {
2133 static int draw_blobs_when_lit = -1;
2134 if (draw_blobs_when_lit < 0) {
2135 char *env = getenv("LIGHTUP_LIT_BLOBS");
2136 draw_blobs_when_lit = (!env || (env[0] == 'y' ||
2139 if (!(ds_flags & DF_LIT) || draw_blobs_when_lit) {
2140 int rlen = TILE_SIZE / 4;
2141 draw_rect(dr, dx + TILE_SIZE/2 - rlen/2,
2142 dy + TILE_SIZE/2 - rlen/2,
2143 rlen, rlen, COL_BLACK);
2148 if (ds_flags & DF_CURSOR) {
2149 int coff = TILE_SIZE/8;
2150 draw_rect_outline(dr, dx + coff, dy + coff,
2151 TILE_SIZE - coff*2, TILE_SIZE - coff*2, COL_CURSOR);
2154 draw_update(dr, dx, dy, TILE_SIZE, TILE_SIZE);
2157 static void game_redraw(drawing *dr, game_drawstate *ds,
2158 const game_state *oldstate, const game_state *state,
2159 int dir, const game_ui *ui,
2160 float animtime, float flashtime)
2162 int flashing = FALSE;
2165 if (flashtime) flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
2169 TILE_SIZE * ds->w + 2 * BORDER,
2170 TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND);
2172 draw_rect_outline(dr, COORD(0)-1, COORD(0)-1,
2173 TILE_SIZE * ds->w + 2,
2174 TILE_SIZE * ds->h + 2,
2177 draw_update(dr, 0, 0,
2178 TILE_SIZE * ds->w + 2 * BORDER,
2179 TILE_SIZE * ds->h + 2 * BORDER);
2183 for (x = 0; x < ds->w; x++) {
2184 for (y = 0; y < ds->h; y++) {
2185 unsigned int ds_flags = tile_flags(ds, state, ui, x, y, flashing);
2186 if (ds_flags != GRID(ds, flags, x, y)) {
2187 GRID(ds, flags, x, y) = ds_flags;
2188 tile_redraw(dr, ds, state, x, y);
2194 static float game_anim_length(const game_state *oldstate,
2195 const game_state *newstate, int dir, game_ui *ui)
2200 static float game_flash_length(const game_state *oldstate,
2201 const game_state *newstate, int dir, game_ui *ui)
2203 if (!oldstate->completed && newstate->completed &&
2204 !oldstate->used_solve && !newstate->used_solve)
2209 static int game_status(const game_state *state)
2211 return state->completed ? +1 : 0;
2214 static int game_timing_state(const game_state *state, game_ui *ui)
2219 static void game_print_size(const game_params *params, float *x, float *y)
2224 * I'll use 6mm squares by default.
2226 game_compute_size(params, 600, &pw, &ph);
2231 static void game_print(drawing *dr, const game_state *state, int tilesize)
2233 int w = state->w, h = state->h;
2234 int ink = print_mono_colour(dr, 0);
2235 int paper = print_mono_colour(dr, 1);
2238 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2239 game_drawstate ads, *ds = &ads;
2240 game_set_size(dr, ds, NULL, tilesize);
2245 print_line_width(dr, TILE_SIZE / 16);
2246 draw_rect_outline(dr, COORD(0), COORD(0),
2247 TILE_SIZE * w, TILE_SIZE * h, ink);
2252 print_line_width(dr, TILE_SIZE / 24);
2253 for (x = 1; x < w; x++)
2254 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink);
2255 for (y = 1; y < h; y++)
2256 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink);
2261 for (y = 0; y < h; y++)
2262 for (x = 0; x < w; x++) {
2263 unsigned int ds_flags = tile_flags(ds, state, NULL, x, y, FALSE);
2264 int dx = COORD(x), dy = COORD(y);
2265 if (ds_flags & DF_BLACK) {
2266 draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, ink);
2267 if (ds_flags & DF_NUMBERED) {
2269 sprintf(str, "%d", GRID(state, lights, x, y));
2270 draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
2271 FONT_VARIABLE, TILE_SIZE*3/5,
2272 ALIGN_VCENTRE | ALIGN_HCENTRE, paper, str);
2274 } else if (ds_flags & DF_LIGHT) {
2275 draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
2276 TILE_RADIUS, -1, ink);
2282 #define thegame lightup
2285 const struct game thegame = {
2286 "Light Up", "games.lightup", "lightup",
2288 game_fetch_preset, NULL,
2293 TRUE, game_configure, custom_params,
2301 TRUE, game_can_format_as_text_now, game_text_format,
2309 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2312 game_free_drawstate,
2317 TRUE, FALSE, game_print_size, game_print,
2318 FALSE, /* wants_statusbar */
2319 FALSE, game_timing_state,
2323 #ifdef STANDALONE_SOLVER
2325 int main(int argc, char **argv)
2329 char *id = NULL, *desc, *err, *result;
2330 int nsol, diff, really_verbose = 0;
2331 unsigned int sflags;
2333 while (--argc > 0) {
2335 if (!strcmp(p, "-v")) {
2337 } else if (*p == '-') {
2338 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2346 fprintf(stderr, "usage: %s [-v] <game_id>\n", argv[0]);
2350 desc = strchr(id, ':');
2352 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2357 p = default_params();
2358 decode_params(p, id);
2359 err = validate_desc(p, desc);
2361 fprintf(stderr, "%s: %s\n", argv[0], err);
2364 s = new_game(NULL, p, desc);
2366 /* Run the solvers easiest to hardest until we find one that
2367 * can solve our puzzle. If it's soluble we know that the
2368 * hardest (recursive) solver will always find the solution. */
2370 for (diff = 0; diff <= DIFFCOUNT; diff++) {
2371 printf("\nSolving with difficulty %d.\n", diff);
2372 sflags = flags_from_difficulty(diff);
2374 nsol = dosolve(s, sflags, NULL);
2375 if (nsol == 1) break;
2380 printf("Puzzle has no solution.\n");
2381 } else if (nsol < 0) {
2382 printf("Unable to find a unique solution.\n");
2383 } else if (nsol > 1) {
2384 printf("Puzzle has multiple solutions.\n");
2386 verbose = really_verbose;
2388 printf("Puzzle has difficulty %d: solving...\n", diff);
2389 dosolve(s, sflags, NULL); /* sflags from last successful solve */
2390 result = game_text_format(s);
2391 printf("%s", result);
2400 /* vim: set shiftwidth=4 tabstop=8: */