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(game_state
*state
, int ox
, int oy
, surrounds
*s
)
162 assert(ox
>= 0 && ox
< state
->w
&& oy
>= 0 && oy
< state
->h
);
164 #define ADDPOINT(cond,nx,ny) do {\
166 s->points[s->npoints].x = (nx); \
167 s->points[s->npoints].y = (ny); \
168 s->points[s->npoints].f = 0; \
171 ADDPOINT(ox
> 0, ox
-1, oy
);
172 ADDPOINT(ox
< (state
->w
-1), ox
+1, oy
);
173 ADDPOINT(oy
> 0, ox
, oy
-1);
174 ADDPOINT(oy
< (state
->h
-1), ox
, oy
+1);
177 /* --- Game parameter functions --- */
179 #define DEFAULT_PRESET 0
181 const struct game_params lightup_presets
[] = {
182 { 7, 7, 20, SYMM_ROT4
, 0 },
183 { 7, 7, 20, SYMM_ROT4
, 1 },
184 { 7, 7, 20, SYMM_ROT4
, 2 },
185 { 10, 10, 20, SYMM_ROT2
, 0 },
186 { 10, 10, 20, SYMM_ROT2
, 1 },
188 { 12, 12, 20, SYMM_ROT2
, 0 },
189 { 12, 12, 20, SYMM_ROT2
, 1 },
191 { 10, 10, 20, SYMM_ROT2
, 2 },
192 { 14, 14, 20, SYMM_ROT2
, 0 },
193 { 14, 14, 20, SYMM_ROT2
, 1 },
194 { 14, 14, 20, SYMM_ROT2
, 2 }
198 static game_params
*default_params(void)
200 game_params
*ret
= snew(game_params
);
201 *ret
= lightup_presets
[DEFAULT_PRESET
];
206 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
211 if (i
< 0 || i
>= lenof(lightup_presets
))
214 ret
= default_params();
215 *ret
= lightup_presets
[i
];
218 sprintf(buf
, "%dx%d %s",
220 ret
->difficulty
== 2 ?
"hard" :
221 ret
->difficulty
== 1 ?
"tricky" : "easy");
227 static void free_params(game_params
*params
)
232 static game_params
*dup_params(game_params
*params
)
234 game_params
*ret
= snew(game_params
);
235 *ret
= *params
; /* structure copy */
239 #define EATNUM(x) do { \
240 (x) = atoi(string); \
241 while (*string && isdigit((unsigned char)*string)) string++; \
244 static void decode_params(game_params
*params
, char const *string
)
247 if (*string
== 'x') {
251 if (*string
== 'b') {
253 EATNUM(params
->blackpc
);
255 if (*string
== 's') {
257 EATNUM(params
->symm
);
259 /* cope with user input such as '18x10' by ensuring symmetry
260 * is not selected by default to be incompatible with dimensions */
261 if (params
->symm
== SYMM_ROT4
&& params
->w
!= params
->h
)
262 params
->symm
= SYMM_ROT2
;
264 params
->difficulty
= 0;
265 /* cope with old params */
266 if (*string
== 'r') {
267 params
->difficulty
= 2;
270 if (*string
== 'd') {
272 EATNUM(params
->difficulty
);
276 static char *encode_params(game_params
*params
, int full
)
281 sprintf(buf
, "%dx%db%ds%dd%d",
282 params
->w
, params
->h
, params
->blackpc
,
286 sprintf(buf
, "%dx%d", params
->w
, params
->h
);
291 static config_item
*game_configure(game_params
*params
)
296 ret
= snewn(6, config_item
);
298 ret
[0].name
= "Width";
299 ret
[0].type
= C_STRING
;
300 sprintf(buf
, "%d", params
->w
);
301 ret
[0].sval
= dupstr(buf
);
304 ret
[1].name
= "Height";
305 ret
[1].type
= C_STRING
;
306 sprintf(buf
, "%d", params
->h
);
307 ret
[1].sval
= dupstr(buf
);
310 ret
[2].name
= "%age of black squares";
311 ret
[2].type
= C_STRING
;
312 sprintf(buf
, "%d", params
->blackpc
);
313 ret
[2].sval
= dupstr(buf
);
316 ret
[3].name
= "Symmetry";
317 ret
[3].type
= C_CHOICES
;
318 ret
[3].sval
= ":None"
319 ":2-way mirror:2-way rotational"
320 ":4-way mirror:4-way rotational";
321 ret
[3].ival
= params
->symm
;
323 ret
[4].name
= "Difficulty";
324 ret
[4].type
= C_CHOICES
;
325 ret
[4].sval
= ":Easy:Tricky:Hard";
326 ret
[4].ival
= params
->difficulty
;
336 static game_params
*custom_params(config_item
*cfg
)
338 game_params
*ret
= snew(game_params
);
340 ret
->w
= atoi(cfg
[0].sval
);
341 ret
->h
= atoi(cfg
[1].sval
);
342 ret
->blackpc
= atoi(cfg
[2].sval
);
343 ret
->symm
= cfg
[3].ival
;
344 ret
->difficulty
= cfg
[4].ival
;
349 static char *validate_params(game_params
*params
, int full
)
351 if (params
->w
< 2 || params
->h
< 2)
352 return "Width and height must be at least 2";
354 if (params
->blackpc
< 5 || params
->blackpc
> 100)
355 return "Percentage of black squares must be between 5% and 100%";
356 if (params
->w
!= params
->h
) {
357 if (params
->symm
== SYMM_ROT4
)
358 return "4-fold symmetry is only available with square grids";
360 if (params
->symm
< 0 || params
->symm
>= SYMM_MAX
)
361 return "Unknown symmetry type";
362 if (params
->difficulty
< 0 || params
->difficulty
> DIFFCOUNT
)
363 return "Unknown difficulty level";
368 /* --- Game state construction/freeing helper functions --- */
370 static game_state
*new_state(game_params
*params
)
372 game_state
*ret
= snew(game_state
);
376 ret
->lights
= snewn(ret
->w
* ret
->h
, int);
378 memset(ret
->lights
, 0, ret
->w
* ret
->h
* sizeof(int));
379 ret
->flags
= snewn(ret
->w
* ret
->h
, unsigned int);
380 memset(ret
->flags
, 0, ret
->w
* ret
->h
* sizeof(unsigned int));
381 ret
->completed
= ret
->used_solve
= 0;
385 static game_state
*dup_game(game_state
*state
)
387 game_state
*ret
= snew(game_state
);
392 ret
->lights
= snewn(ret
->w
* ret
->h
, int);
393 memcpy(ret
->lights
, state
->lights
, ret
->w
* ret
->h
* sizeof(int));
394 ret
->nlights
= state
->nlights
;
396 ret
->flags
= snewn(ret
->w
* ret
->h
, unsigned int);
397 memcpy(ret
->flags
, state
->flags
, ret
->w
* ret
->h
* sizeof(unsigned int));
399 ret
->completed
= state
->completed
;
400 ret
->used_solve
= state
->used_solve
;
405 static void free_game(game_state
*state
)
407 sfree(state
->lights
);
412 static void debug_state(game_state
*state
)
417 for (y
= 0; y
< state
->h
; y
++) {
418 for (x
= 0; x
< state
->w
; x
++) {
420 if (GRID(state
, flags
, x
, y
) & F_BLACK
) {
421 if (GRID(state
, flags
, x
, y
) & F_NUMBERED
)
422 c
= GRID(state
, lights
, x
, y
) + '0';
426 if (GRID(state
, flags
, x
, y
) & F_LIGHT
)
428 else if (GRID(state
, flags
, x
, y
) & F_IMPOSSIBLE
)
431 debug(("%c", (int)c
));
434 for (x
= 0; x
< state
->w
; x
++) {
435 if (GRID(state
, flags
, x
, y
) & F_BLACK
)
438 c
= (GRID(state
, flags
, x
, y
) & F_LIGHT
) ?
'A' : 'a';
439 c
+= GRID(state
, lights
, x
, y
);
441 debug(("%c", (int)c
));
447 /* --- Game completion test routines. --- */
449 /* These are split up because occasionally functions are only
450 * interested in one particular aspect. */
452 /* Returns non-zero if all grid spaces are lit. */
453 static int grid_lit(game_state
*state
)
457 for (x
= 0; x
< state
->w
; x
++) {
458 for (y
= 0; y
< state
->h
; y
++) {
459 if (GRID(state
,flags
,x
,y
) & F_BLACK
) continue;
460 if (GRID(state
,lights
,x
,y
) == 0)
467 /* Returns non-zero if any lights are lit by other lights. */
468 static int grid_overlap(game_state
*state
)
472 for (x
= 0; x
< state
->w
; x
++) {
473 for (y
= 0; y
< state
->h
; y
++) {
474 if (!(GRID(state
, flags
, x
, y
) & F_LIGHT
)) continue;
475 if (GRID(state
, lights
, x
, y
) > 1)
482 static int number_wrong(game_state
*state
, int x
, int y
)
485 int i
, n
, empty
, lights
= GRID(state
, lights
, x
, y
);
488 * This function computes the display hint for a number: we
489 * turn the number red if it is definitely wrong. This means
492 * (a) it has too many lights around it, or
493 * (b) it would have too few lights around it even if all the
494 * plausible squares (not black, lit or F_IMPOSSIBLE) were
495 * filled with lights.
498 assert(GRID(state
, flags
, x
, y
) & F_NUMBERED
);
499 get_surrounds(state
, x
, y
, &s
);
502 for (i
= 0; i
< s
.npoints
; i
++) {
503 if (GRID(state
,flags
,s
.points
[i
].x
,s
.points
[i
].y
) & F_LIGHT
) {
507 if (GRID(state
,flags
,s
.points
[i
].x
,s
.points
[i
].y
) & F_BLACK
)
509 if (GRID(state
,flags
,s
.points
[i
].x
,s
.points
[i
].y
) & F_IMPOSSIBLE
)
511 if (GRID(state
,lights
,s
.points
[i
].x
,s
.points
[i
].y
))
515 return (n
> lights
|| (n
+ empty
< lights
));
518 static int number_correct(game_state
*state
, int x
, int y
)
521 int n
= 0, i
, lights
= GRID(state
, lights
, x
, y
);
523 assert(GRID(state
, flags
, x
, y
) & F_NUMBERED
);
524 get_surrounds(state
, x
, y
, &s
);
525 for (i
= 0; i
< s
.npoints
; i
++) {
526 if (GRID(state
,flags
,s
.points
[i
].x
,s
.points
[i
].y
) & F_LIGHT
)
529 return (n
== lights
) ?
1 : 0;
532 /* Returns non-zero if any numbers add up incorrectly. */
533 static int grid_addsup(game_state
*state
)
537 for (x
= 0; x
< state
->w
; x
++) {
538 for (y
= 0; y
< state
->h
; y
++) {
539 if (!(GRID(state
, flags
, x
, y
) & F_NUMBERED
)) continue;
540 if (!number_correct(state
, x
, y
)) return 0;
546 static int grid_correct(game_state
*state
)
548 if (grid_lit(state
) &&
549 !grid_overlap(state
) &&
550 grid_addsup(state
)) return 1;
554 /* --- Board initial setup (blacks, lights, numbers) --- */
556 static void clean_board(game_state
*state
, int leave_blacks
)
559 for (x
= 0; x
< state
->w
; x
++) {
560 for (y
= 0; y
< state
->h
; y
++) {
562 GRID(state
, flags
, x
, y
) &= F_BLACK
;
564 GRID(state
, flags
, x
, y
) = 0;
565 GRID(state
, lights
, x
, y
) = 0;
571 static void set_blacks(game_state
*state
, game_params
*params
, random_state
*rs
)
573 int x
, y
, degree
= 0, rotate
= 0, nblack
;
575 int wodd
= (state
->w
% 2) ?
1 : 0;
576 int hodd
= (state
->h
% 2) ?
1 : 0;
579 switch (params
->symm
) {
580 case SYMM_NONE
: degree
= 1; rotate
= 0; break;
581 case SYMM_ROT2
: degree
= 2; rotate
= 1; break;
582 case SYMM_REF2
: degree
= 2; rotate
= 0; break;
583 case SYMM_ROT4
: degree
= 4; rotate
= 1; break;
584 case SYMM_REF4
: degree
= 4; rotate
= 0; break;
585 default: assert(!"Unknown symmetry type");
587 if (params
->symm
== SYMM_ROT4
&& (state
->h
!= state
->w
))
588 assert(!"4-fold symmetry unavailable without square grid");
593 if (!rotate
) rw
+= wodd
; /* ... but see below. */
595 } else if (degree
== 2) {
604 /* clear, then randomise, required region. */
605 clean_board(state
, 0);
606 nblack
= (rw
* rh
* params
->blackpc
) / 100;
607 for (i
= 0; i
< nblack
; i
++) {
609 x
= random_upto(rs
,rw
);
610 y
= random_upto(rs
,rh
);
611 } while (GRID(state
,flags
,x
,y
) & F_BLACK
);
612 GRID(state
, flags
, x
, y
) |= F_BLACK
;
615 /* Copy required region. */
616 if (params
->symm
== SYMM_NONE
) return;
618 for (x
= 0; x
< rw
; x
++) {
619 for (y
= 0; y
< rh
; y
++) {
623 xs
[1] = state
->w
- 1 - (rotate ? y
: x
);
624 ys
[1] = rotate ? x
: y
;
625 xs
[2] = rotate ?
(state
->w
- 1 - x
) : x
;
626 ys
[2] = state
->h
- 1 - y
;
627 xs
[3] = rotate ? y
: (state
->w
- 1 - x
);
628 ys
[3] = state
->h
- 1 - (rotate ? x
: y
);
632 xs
[1] = rotate ?
(state
->w
- 1 - x
) : x
;
633 ys
[1] = state
->h
- 1 - y
;
635 for (i
= 1; i
< degree
; i
++) {
636 GRID(state
, flags
, xs
[i
], ys
[i
]) =
637 GRID(state
, flags
, xs
[0], ys
[0]);
641 /* SYMM_ROT4 misses the middle square above; fix that here. */
642 if (degree
== 4 && rotate
&& wodd
&&
643 (random_upto(rs
,100) <= (unsigned int)params
->blackpc
))
645 state
->w
/2 + wodd
- 1, state
->h
/2 + hodd
- 1) |= F_BLACK
;
647 #ifdef SOLVER_DIAGNOSTICS
648 if (verbose
) debug_state(state
);
652 /* Fills in (does not allocate) a ll_data with all the tiles that would
653 * be illuminated by a light at point (ox,oy). If origin=1 then the
654 * origin is included in this list. */
655 static void list_lights(game_state
*state
, int ox
, int oy
, int origin
,
660 memset(lld
, 0, sizeof(lld
));
661 lld
->ox
= lld
->minx
= lld
->maxx
= ox
;
662 lld
->oy
= lld
->miny
= lld
->maxy
= oy
;
663 lld
->include_origin
= origin
;
666 for (x
= ox
-1; x
>= 0; x
--) {
667 if (GRID(state
, flags
, x
, y
) & F_BLACK
) break;
668 if (x
< lld
->minx
) lld
->minx
= x
;
670 for (x
= ox
+1; x
< state
->w
; x
++) {
671 if (GRID(state
, flags
, x
, y
) & F_BLACK
) break;
672 if (x
> lld
->maxx
) lld
->maxx
= x
;
676 for (y
= oy
-1; y
>= 0; y
--) {
677 if (GRID(state
, flags
, x
, y
) & F_BLACK
) break;
678 if (y
< lld
->miny
) lld
->miny
= y
;
680 for (y
= oy
+1; y
< state
->h
; y
++) {
681 if (GRID(state
, flags
, x
, y
) & F_BLACK
) break;
682 if (y
> lld
->maxy
) lld
->maxy
= y
;
686 /* Makes sure a light is the given state, editing the lights table to suit the
687 * new state if necessary. */
688 static void set_light(game_state
*state
, int ox
, int oy
, int on
)
693 assert(!(GRID(state
,flags
,ox
,oy
) & F_BLACK
));
695 if (!on
&& GRID(state
,flags
,ox
,oy
) & F_LIGHT
) {
697 GRID(state
,flags
,ox
,oy
) &= ~F_LIGHT
;
699 } else if (on
&& !(GRID(state
,flags
,ox
,oy
) & F_LIGHT
)) {
701 GRID(state
,flags
,ox
,oy
) |= F_LIGHT
;
706 list_lights(state
,ox
,oy
,1,&lld
);
707 FOREACHLIT(&lld
, GRID(state
,lights
,lx
,ly
) += diff
; );
711 /* Returns 1 if removing a light at (x,y) would cause a square to go dark. */
712 static int check_dark(game_state
*state
, int x
, int y
)
716 list_lights(state
, x
, y
, 1, &lld
);
717 FOREACHLIT(&lld
, if (GRID(state
,lights
,lx
,ly
) == 1) { return 1; } );
721 /* Sets up an initial random correct position (i.e. every
722 * space lit, and no lights lit by other lights) by filling the
723 * grid with lights and then removing lights one by one at random. */
724 static void place_lights(game_state
*state
, random_state
*rs
)
726 int i
, x
, y
, n
, *numindices
, wh
= state
->w
*state
->h
;
729 numindices
= snewn(wh
, int);
730 for (i
= 0; i
< wh
; i
++) numindices
[i
] = i
;
731 shuffle(numindices
, wh
, sizeof(*numindices
), rs
);
733 /* Place a light on all grid squares without lights. */
734 for (x
= 0; x
< state
->w
; x
++) {
735 for (y
= 0; y
< state
->h
; y
++) {
736 GRID(state
, flags
, x
, y
) &= ~F_MARK
; /* we use this later. */
737 if (GRID(state
, flags
, x
, y
) & F_BLACK
) continue;
738 set_light(state
, x
, y
, 1);
742 for (i
= 0; i
< wh
; i
++) {
743 y
= numindices
[i
] / state
->w
;
744 x
= numindices
[i
] % state
->w
;
745 if (!(GRID(state
, flags
, x
, y
) & F_LIGHT
)) continue;
746 if (GRID(state
, flags
, x
, y
) & F_MARK
) continue;
747 list_lights(state
, x
, y
, 0, &lld
);
749 /* If we're not lighting any lights ourself, don't remove anything. */
751 FOREACHLIT(&lld
, if (GRID(state
,flags
,lx
,ly
) & F_LIGHT
) { n
+= 1; } );
752 if (n
== 0) continue; /* [1] */
754 /* Check whether removing lights we're lighting would cause anything
757 FOREACHLIT(&lld
, if (GRID(state
,flags
,lx
,ly
) & F_LIGHT
) { n
+= check_dark(state
,lx
,ly
); } );
759 /* No, it wouldn't, so we can remove them all. */
760 FOREACHLIT(&lld
, set_light(state
,lx
,ly
, 0); );
761 GRID(state
,flags
,x
,y
) |= F_MARK
;
764 if (!grid_overlap(state
)) {
766 return; /* we're done. */
768 assert(grid_lit(state
));
770 /* could get here if the line at [1] continue'd out of the loop. */
771 if (grid_overlap(state
)) {
773 assert(!"place_lights failed to resolve overlapping lights!");
778 /* Fills in all black squares with numbers of adjacent lights. */
779 static void place_numbers(game_state
*state
)
784 for (x
= 0; x
< state
->w
; x
++) {
785 for (y
= 0; y
< state
->h
; y
++) {
786 if (!(GRID(state
,flags
,x
,y
) & F_BLACK
)) continue;
787 get_surrounds(state
, x
, y
, &s
);
789 for (i
= 0; i
< s
.npoints
; i
++) {
790 if (GRID(state
,flags
,s
.points
[i
].x
, s
.points
[i
].y
) & F_LIGHT
)
793 GRID(state
,flags
,x
,y
) |= F_NUMBERED
;
794 GRID(state
,lights
,x
,y
) = n
;
799 /* --- Actual solver, with helper subroutines. --- */
801 static void tsl_callback(game_state
*state
,
802 int lx
, int ly
, int *x
, int *y
, int *n
)
804 if (GRID(state
,flags
,lx
,ly
) & F_IMPOSSIBLE
) return;
805 if (GRID(state
,lights
,lx
,ly
) > 0) return;
806 *x
= lx
; *y
= ly
; (*n
)++;
809 static int try_solve_light(game_state
*state
, int ox
, int oy
,
810 unsigned int flags
, int lights
)
813 int sx
= 0, sy
= 0, n
= 0;
815 if (lights
> 0) return 0;
816 if (flags
& F_BLACK
) return 0;
818 /* We have an unlit square; count how many ways there are left to
819 * place a light that lights us (including this square); if only
820 * one, we must put a light there. Squares that could light us
821 * are, of course, the same as the squares we would light... */
822 list_lights(state
, ox
, oy
, 1, &lld
);
823 FOREACHLIT(&lld
, { tsl_callback(state
, lx
, ly
, &sx
, &sy
, &n
); });
825 set_light(state
, sx
, sy
, 1);
826 #ifdef SOLVER_DIAGNOSTICS
827 debug(("(%d,%d) can only be lit from (%d,%d); setting to LIGHT\n",
829 if (verbose
) debug_state(state
);
837 static int could_place_light(unsigned int flags
, int lights
)
839 if (flags
& (F_BLACK
| F_IMPOSSIBLE
)) return 0;
840 return (lights
> 0) ?
0 : 1;
843 static int could_place_light_xy(game_state
*state
, int x
, int y
)
845 int lights
= GRID(state
,lights
,x
,y
);
846 unsigned int flags
= GRID(state
,flags
,x
,y
);
847 return (could_place_light(flags
, lights
)) ?
1 : 0;
850 /* For a given number square, determine whether we have enough info
851 * to unambiguously place its lights. */
852 static int try_solve_number(game_state
*state
, int nx
, int ny
,
853 unsigned int nflags
, int nlights
)
856 int x
, y
, nl
, ns
, i
, ret
= 0, lights
;
859 if (!(nflags
& F_NUMBERED
)) return 0;
861 get_surrounds(state
,nx
,ny
,&s
);
864 /* nl is no. of lights we need to place, ns is no. of spaces we
865 * have to place them in. Try and narrow these down, and mark
866 * points we can ignore later. */
867 for (i
= 0; i
< s
.npoints
; i
++) {
868 x
= s
.points
[i
].x
; y
= s
.points
[i
].y
;
869 flags
= GRID(state
,flags
,x
,y
);
870 lights
= GRID(state
,lights
,x
,y
);
871 if (flags
& F_LIGHT
) {
872 /* light here already; one less light for one less place. */
874 s
.points
[i
].f
|= F_MARK
;
875 } else if (!could_place_light(flags
, lights
)) {
877 s
.points
[i
].f
|= F_MARK
;
880 if (ns
== 0) return 0; /* nowhere to put anything. */
882 /* we have placed all lights we need to around here; all remaining
883 * surrounds are therefore IMPOSSIBLE. */
884 GRID(state
,flags
,nx
,ny
) |= F_NUMBERUSED
;
885 for (i
= 0; i
< s
.npoints
; i
++) {
886 if (!(s
.points
[i
].f
& F_MARK
)) {
887 GRID(state
,flags
,s
.points
[i
].x
,s
.points
[i
].y
) |= F_IMPOSSIBLE
;
891 #ifdef SOLVER_DIAGNOSTICS
892 printf("Clue at (%d,%d) full; setting unlit to IMPOSSIBLE.\n",
894 if (verbose
) debug_state(state
);
896 } else if (nl
== ns
) {
897 /* we have as many lights to place as spaces; fill them all. */
898 GRID(state
,flags
,nx
,ny
) |= F_NUMBERUSED
;
899 for (i
= 0; i
< s
.npoints
; i
++) {
900 if (!(s
.points
[i
].f
& F_MARK
)) {
901 set_light(state
, s
.points
[i
].x
,s
.points
[i
].y
, 1);
905 #ifdef SOLVER_DIAGNOSTICS
906 printf("Clue at (%d,%d) trivial; setting unlit to LIGHT.\n",
908 if (verbose
) debug_state(state
);
919 #define SCRATCHSZ (state->w+state->h)
921 /* New solver algorithm: overlapping sets can add IMPOSSIBLE flags.
922 * Algorithm thanks to Simon:
924 * (a) Any square where you can place a light has a set of squares
925 * which would become non-lights as a result. (This includes
926 * squares lit by the first square, and can also include squares
927 * adjacent to the same clue square if the new light is the last
928 * one around that clue.) Call this MAKESDARK(x,y) with (x,y) being
929 * the square you place a light.
931 * (b) Any unlit square has a set of squares on which you could place
932 * a light to illuminate it. (Possibly including itself, of
933 * course.) This set of squares has the property that _at least
934 * one_ of them must contain a light. Sets of this type also arise
935 * from clue squares. Call this MAKESLIGHT(x,y), again with (x,y)
936 * the square you would place a light.
938 * (c) If there exists (dx,dy) and (lx,ly) such that MAKESDARK(dx,dy) is
939 * a superset of MAKESLIGHT(lx,ly), this implies that placing a light at
940 * (dx,dy) would either leave no remaining way to illuminate a certain
941 * square, or would leave no remaining way to fulfill a certain clue
942 * (at lx,ly). In either case, a light can be ruled out at that position.
944 * So, we construct all possible MAKESLIGHT sets, both from unlit squares
945 * and clue squares, and then we look for plausible MAKESDARK sets that include
946 * our (lx,ly) to see if we can find a (dx,dy) to rule out. By the time we have
947 * constructed the MAKESLIGHT set we don't care about (lx,ly), just the set
950 * Once we have such a set, Simon came up with a Cunning Plan to find
951 * the most sensible MAKESDARK candidate:
953 * (a) for each square S in your set X, find all the squares which _would_
954 * rule it out. That means any square which would light S, plus
955 * any square adjacent to the same clue square as S (provided
956 * that clue square has only one remaining light to be placed).
957 * It's not hard to make this list. Don't do anything with this
958 * data at the moment except _count_ the squares.
960 * (b) Find the square S_min in the original set which has the
961 * _smallest_ number of other squares which would rule it out.
963 * (c) Find all the squares that rule out S_min (it's probably
964 * better to recompute this than to have stored it during step
965 * (a), since the CPU requirement is modest but the storage
966 * cost would get ugly.) For each of these squares, see if it
967 * rules out everything else in the set X. Any which does can
968 * be marked as not-a-light.
972 typedef void (*trl_cb
)(game_state
*state
, int dx
, int dy
,
973 struct setscratch
*scratch
, int n
, void *ctx
);
975 static void try_rule_out(game_state
*state
, int x
, int y
,
976 struct setscratch
*scratch
, int n
,
977 trl_cb cb
, void *ctx
);
979 static void trl_callback_search(game_state
*state
, int dx
, int dy
,
980 struct setscratch
*scratch
, int n
, void *ignored
)
984 #ifdef SOLVER_DIAGNOSTICS
985 if (verbose
) debug(("discount cb: light at (%d,%d)\n", dx
, dy
));
988 for (i
= 0; i
< n
; i
++) {
989 if (dx
== scratch
[i
].x
&& dy
== scratch
[i
].y
) {
996 static void trl_callback_discount(game_state
*state
, int dx
, int dy
,
997 struct setscratch
*scratch
, int n
, void *ctx
)
999 int *didsth
= (int *)ctx
;
1002 if (GRID(state
,flags
,dx
,dy
) & F_IMPOSSIBLE
) {
1003 #ifdef SOLVER_DIAGNOSTICS
1004 debug(("Square at (%d,%d) already impossible.\n", dx
,dy
));
1009 /* Check whether a light at (dx,dy) rules out everything
1010 * in scratch, and mark (dx,dy) as IMPOSSIBLE if it does.
1011 * We can use try_rule_out for this as well, as the set of
1012 * squares which would rule out (x,y) is the same as the
1013 * set of squares which (x,y) would rule out. */
1015 #ifdef SOLVER_DIAGNOSTICS
1016 if (verbose
) debug(("Checking whether light at (%d,%d) rules out everything in scratch.\n", dx
, dy
));
1019 for (i
= 0; i
< n
; i
++)
1021 try_rule_out(state
, dx
, dy
, scratch
, n
, trl_callback_search
, NULL
);
1022 for (i
= 0; i
< n
; i
++) {
1023 if (scratch
[i
].n
== 0) return;
1025 /* The light ruled out everything in scratch. Yay. */
1026 GRID(state
,flags
,dx
,dy
) |= F_IMPOSSIBLE
;
1027 #ifdef SOLVER_DIAGNOSTICS
1028 debug(("Set reduction discounted square at (%d,%d):\n", dx
,dy
));
1029 if (verbose
) debug_state(state
);
1035 static void trl_callback_incn(game_state
*state
, int dx
, int dy
,
1036 struct setscratch
*scratch
, int n
, void *ctx
)
1038 struct setscratch
*s
= (struct setscratch
*)ctx
;
1042 static void try_rule_out(game_state
*state
, int x
, int y
,
1043 struct setscratch
*scratch
, int n
,
1044 trl_cb cb
, void *ctx
)
1046 /* XXX Find all the squares which would rule out (x,y); anything
1047 * that would light it as well as squares adjacent to same clues
1048 * as X assuming that clue only has one remaining light.
1049 * Call the callback with each square. */
1052 int i
, j
, curr_lights
, tot_lights
;
1054 /* Find all squares that would rule out a light at (x,y) and call trl_cb
1055 * with them: anything that would light (x,y)... */
1057 list_lights(state
, x
, y
, 0, &lld
);
1058 FOREACHLIT(&lld
, { if (could_place_light_xy(state
, lx
, ly
)) { cb(state
, lx
, ly
, scratch
, n
, ctx
); } });
1060 /* ... as well as any empty space (that isn't x,y) next to any clue square
1061 * next to (x,y) that only has one light left to place. */
1063 get_surrounds(state
, x
, y
, &s
);
1064 for (i
= 0; i
< s
.npoints
; i
++) {
1065 if (!(GRID(state
,flags
,s
.points
[i
].x
,s
.points
[i
].y
) & F_NUMBERED
))
1067 /* we have an adjacent clue square; find /its/ surrounds
1068 * and count the remaining lights it needs. */
1069 get_surrounds(state
,s
.points
[i
].x
,s
.points
[i
].y
,&ss
);
1071 for (j
= 0; j
< ss
.npoints
; j
++) {
1072 if (GRID(state
,flags
,ss
.points
[j
].x
,ss
.points
[j
].y
) & F_LIGHT
)
1075 tot_lights
= GRID(state
, lights
, s
.points
[i
].x
, s
.points
[i
].y
);
1076 /* We have a clue with tot_lights to fill, and curr_lights currently
1077 * around it. If adding a light at (x,y) fills up the clue (i.e.
1078 * curr_lights + 1 = tot_lights) then we need to discount all other
1079 * unlit squares around the clue. */
1080 if ((curr_lights
+ 1) == tot_lights
) {
1081 for (j
= 0; j
< ss
.npoints
; j
++) {
1082 int lx
= ss
.points
[j
].x
, ly
= ss
.points
[j
].y
;
1083 if (lx
== x
&& ly
== y
) continue;
1084 if (could_place_light_xy(state
, lx
, ly
))
1085 cb(state
, lx
, ly
, scratch
, n
, ctx
);
1091 #ifdef SOLVER_DIAGNOSTICS
1092 static void debug_scratch(const char *msg
, struct setscratch
*scratch
, int n
)
1095 debug(("%s scratch (%d elements):\n", msg
, n
));
1096 for (i
= 0; i
< n
; i
++) {
1097 debug((" (%d,%d) n%d\n", scratch
[i
].x
, scratch
[i
].y
, scratch
[i
].n
));
1102 static int discount_set(game_state
*state
,
1103 struct setscratch
*scratch
, int n
)
1105 int i
, besti
, bestn
, didsth
= 0;
1107 #ifdef SOLVER_DIAGNOSTICS
1108 if (verbose
> 1) debug_scratch("discount_set", scratch
, n
);
1110 if (n
== 0) return 0;
1112 for (i
= 0; i
< n
; i
++) {
1113 try_rule_out(state
, scratch
[i
].x
, scratch
[i
].y
, scratch
, n
,
1114 trl_callback_incn
, (void*)&(scratch
[i
]));
1116 #ifdef SOLVER_DIAGNOSTICS
1117 if (verbose
> 1) debug_scratch("discount_set after count", scratch
, n
);
1120 besti
= -1; bestn
= SCRATCHSZ
;
1121 for (i
= 0; i
< n
; i
++) {
1122 if (scratch
[i
].n
< bestn
) {
1123 bestn
= scratch
[i
].n
;
1127 #ifdef SOLVER_DIAGNOSTICS
1128 if (verbose
> 1) debug(("best square (%d,%d) with n%d.\n",
1129 scratch
[besti
].x
, scratch
[besti
].y
, scratch
[besti
].n
));
1131 try_rule_out(state
, scratch
[besti
].x
, scratch
[besti
].y
, scratch
, n
,
1132 trl_callback_discount
, (void*)&didsth
);
1133 #ifdef SOLVER_DIAGNOSTICS
1134 if (didsth
) debug((" [from square (%d,%d)]\n",
1135 scratch
[besti
].x
, scratch
[besti
].y
));
1141 static void discount_clear(game_state
*state
, struct setscratch
*scratch
, int *n
)
1144 memset(scratch
, 0, SCRATCHSZ
* sizeof(struct setscratch
));
1147 static void unlit_cb(game_state
*state
, int lx
, int ly
,
1148 struct setscratch
*scratch
, int *n
)
1150 if (could_place_light_xy(state
, lx
, ly
)) {
1151 scratch
[*n
].x
= lx
; scratch
[*n
].y
= ly
; (*n
)++;
1155 /* Construct a MAKESLIGHT set from an unlit square. */
1156 static int discount_unlit(game_state
*state
, int x
, int y
,
1157 struct setscratch
*scratch
)
1162 #ifdef SOLVER_DIAGNOSTICS
1163 if (verbose
) debug(("Trying to discount for unlit square at (%d,%d).\n", x
, y
));
1164 if (verbose
> 1) debug_state(state
);
1167 discount_clear(state
, scratch
, &n
);
1169 list_lights(state
, x
, y
, 1, &lld
);
1170 FOREACHLIT(&lld
, { unlit_cb(state
, lx
, ly
, scratch
, &n
); });
1171 didsth
= discount_set(state
, scratch
, n
);
1172 #ifdef SOLVER_DIAGNOSTICS
1173 if (didsth
) debug((" [from unlit square at (%d,%d)].\n", x
, y
));
1179 /* Construct a series of MAKESLIGHT sets from a clue square.
1180 * for a clue square with N remaining spaces that must contain M lights, every
1181 * subset of size N-M+1 of those N spaces forms such a set.
1184 static int discount_clue(game_state
*state
, int x
, int y
,
1185 struct setscratch
*scratch
)
1187 int slen
, m
= GRID(state
, lights
, x
, y
), n
, i
, didsth
= 0, lights
;
1189 surrounds s
, sempty
;
1192 if (m
== 0) return 0;
1194 #ifdef SOLVER_DIAGNOSTICS
1195 if (verbose
) debug(("Trying to discount for sets at clue (%d,%d).\n", x
, y
));
1196 if (verbose
> 1) debug_state(state
);
1199 /* m is no. of lights still to place; starts off at the clue value
1200 * and decreases when we find a light already down.
1201 * n is no. of spaces left; starts off at 0 and goes up when we find
1202 * a plausible space. */
1204 get_surrounds(state
, x
, y
, &s
);
1205 memset(&sempty
, 0, sizeof(surrounds
));
1206 for (i
= 0; i
< s
.npoints
; i
++) {
1207 int lx
= s
.points
[i
].x
, ly
= s
.points
[i
].y
;
1208 flags
= GRID(state
,flags
,lx
,ly
);
1209 lights
= GRID(state
,lights
,lx
,ly
);
1211 if (flags
& F_LIGHT
) m
--;
1213 if (could_place_light(flags
, lights
)) {
1214 sempty
.points
[sempty
.npoints
].x
= lx
;
1215 sempty
.points
[sempty
.npoints
].y
= ly
;
1219 n
= sempty
.npoints
; /* sempty is now a surrounds of only blank squares. */
1220 if (n
== 0) return 0; /* clue is full already. */
1222 if (m
< 0 || m
> n
) return 0; /* become impossible. */
1224 combi
= new_combi(n
- m
+ 1, n
);
1225 while (next_combi(combi
)) {
1226 discount_clear(state
, scratch
, &slen
);
1227 for (i
= 0; i
< combi
->r
; i
++) {
1228 scratch
[slen
].x
= sempty
.points
[combi
->a
[i
]].x
;
1229 scratch
[slen
].y
= sempty
.points
[combi
->a
[i
]].y
;
1232 if (discount_set(state
, scratch
, slen
)) didsth
= 1;
1235 #ifdef SOLVER_DIAGNOSTICS
1236 if (didsth
) debug((" [from clue at (%d,%d)].\n", x
, y
));
1241 #define F_SOLVE_FORCEUNIQUE 1
1242 #define F_SOLVE_DISCOUNTSETS 2
1243 #define F_SOLVE_ALLOWRECURSE 4
1245 static unsigned int flags_from_difficulty(int difficulty
)
1247 unsigned int sflags
= F_SOLVE_FORCEUNIQUE
;
1248 assert(difficulty
<= DIFFCOUNT
);
1249 if (difficulty
>= 1) sflags
|= F_SOLVE_DISCOUNTSETS
;
1250 if (difficulty
>= 2) sflags
|= F_SOLVE_ALLOWRECURSE
;
1254 #define MAXRECURSE 5
1256 static int solve_sub(game_state
*state
,
1257 unsigned int solve_flags
, int depth
,
1261 int x
, y
, didstuff
, ncanplace
, lights
;
1262 int bestx
, besty
, n
, bestn
, copy_soluble
, self_soluble
, ret
, maxrecurse
= 0;
1265 struct setscratch
*sscratch
= NULL
;
1267 #ifdef SOLVER_DIAGNOSTICS
1268 printf("solve_sub: depth = %d\n", depth
);
1270 if (maxdepth
&& *maxdepth
< depth
) *maxdepth
= depth
;
1271 if (solve_flags
& F_SOLVE_ALLOWRECURSE
) maxrecurse
= MAXRECURSE
;
1274 if (grid_overlap(state
)) {
1275 /* Our own solver, from scratch, should never cause this to happen
1276 * (assuming a soluble grid). However, if we're trying to solve
1277 * from a half-completed *incorrect* grid this might occur; we
1278 * just return the 'no solutions' code in this case. */
1282 if (grid_correct(state
)) { ret
= 1; goto done
; }
1286 /* These 2 loops, and the functions they call, are the critical loops
1287 * for timing; any optimisations should look here first. */
1288 for (x
= 0; x
< state
->w
; x
++) {
1289 for (y
= 0; y
< state
->h
; y
++) {
1290 flags
= GRID(state
,flags
,x
,y
);
1291 lights
= GRID(state
,lights
,x
,y
);
1292 ncanplace
+= could_place_light(flags
, lights
);
1294 if (try_solve_light(state
, x
, y
, flags
, lights
)) didstuff
= 1;
1295 if (try_solve_number(state
, x
, y
, flags
, lights
)) didstuff
= 1;
1298 if (didstuff
) continue;
1300 /* nowhere to put a light, puzzle is unsoluble. */
1304 if (solve_flags
& F_SOLVE_DISCOUNTSETS
) {
1305 if (!sscratch
) sscratch
= snewn(SCRATCHSZ
, struct setscratch
);
1306 /* Try a more cunning (and more involved) way... more details above. */
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
);
1312 if (!(flags
& F_BLACK
) && lights
== 0) {
1313 if (discount_unlit(state
, x
, y
, sscratch
)) {
1315 goto reduction_success
;
1317 } else if (flags
& F_NUMBERED
) {
1318 if (discount_clue(state
, x
, y
, sscratch
)) {
1320 goto reduction_success
;
1327 if (didstuff
) continue;
1329 /* We now have to make a guess; we have places to put lights but
1330 * no definite idea about where they can go. */
1331 if (depth
>= maxrecurse
) {
1332 /* mustn't delve any deeper. */
1333 ret
= -1; goto done
;
1335 /* Of all the squares that we could place a light, pick the one
1336 * that would light the most currently unlit squares. */
1337 /* This heuristic was just plucked from the air; there may well be
1338 * a more efficient way of choosing a square to flip to minimise
1341 bestx
= besty
= -1; /* suyb */
1342 for (x
= 0; x
< state
->w
; x
++) {
1343 for (y
= 0; y
< state
->h
; y
++) {
1344 flags
= GRID(state
,flags
,x
,y
);
1345 lights
= GRID(state
,lights
,x
,y
);
1346 if (!could_place_light(flags
, lights
)) continue;
1349 list_lights(state
, x
, y
, 1, &lld
);
1350 FOREACHLIT(&lld
, { if (GRID(state
,lights
,lx
,ly
) == 0) n
++; });
1352 bestn
= n
; bestx
= x
; besty
= y
;
1357 assert(bestx
>= 0 && besty
>= 0);
1359 /* Now we've chosen a plausible (x,y), try to solve it once as 'lit'
1360 * and once as 'impossible'; we need to make one copy to do this. */
1362 scopy
= dup_game(state
);
1363 #ifdef SOLVER_DIAGNOSTICS
1364 debug(("Recursing #1: trying (%d,%d) as IMPOSSIBLE\n", bestx
, besty
));
1366 GRID(state
,flags
,bestx
,besty
) |= F_IMPOSSIBLE
;
1367 self_soluble
= solve_sub(state
, solve_flags
, depth
+1, maxdepth
);
1369 if (!(solve_flags
& F_SOLVE_FORCEUNIQUE
) && self_soluble
> 0) {
1370 /* we didn't care about finding all solutions, and we just
1371 * found one; return with it immediately. */
1377 #ifdef SOLVER_DIAGNOSTICS
1378 debug(("Recursing #2: trying (%d,%d) as LIGHT\n", bestx
, besty
));
1380 set_light(scopy
, bestx
, besty
, 1);
1381 copy_soluble
= solve_sub(scopy
, solve_flags
, depth
+1, maxdepth
);
1383 /* If we wanted a unique solution but we hit our recursion limit
1384 * (on either branch) then we have to assume we didn't find possible
1385 * extra solutions, and return 'not soluble'. */
1386 if ((solve_flags
& F_SOLVE_FORCEUNIQUE
) &&
1387 ((copy_soluble
< 0) || (self_soluble
< 0))) {
1389 /* Make sure that whether or not it was self or copy (or both) that
1390 * were soluble, that we return a solved state in self. */
1391 } else if (copy_soluble
<= 0) {
1392 /* copy wasn't soluble; keep self state and return that result. */
1394 } else if (self_soluble
<= 0) {
1395 /* copy solved and we didn't, so copy in copy's (now solved)
1396 * flags and light state. */
1397 memcpy(state
->lights
, scopy
->lights
,
1398 scopy
->w
* scopy
->h
* sizeof(int));
1399 memcpy(state
->flags
, scopy
->flags
,
1400 scopy
->w
* scopy
->h
* sizeof(unsigned int));
1403 ret
= copy_soluble
+ self_soluble
;
1409 if (sscratch
) sfree(sscratch
);
1410 #ifdef SOLVER_DIAGNOSTICS
1412 debug(("solve_sub: depth = %d returning, ran out of recursion.\n",
1415 debug(("solve_sub: depth = %d returning, %d solutions.\n",
1421 /* Fills in the (possibly partially-complete) game_state as far as it can,
1422 * returning the number of possible solutions. If it returns >0 then the
1423 * game_state will be in a solved state, but you won't know which one. */
1424 static int dosolve(game_state
*state
, int solve_flags
, int *maxdepth
)
1428 for (x
= 0; x
< state
->w
; x
++) {
1429 for (y
= 0; y
< state
->h
; y
++) {
1430 GRID(state
,flags
,x
,y
) &= ~F_NUMBERUSED
;
1433 nsol
= solve_sub(state
, solve_flags
, 0, maxdepth
);
1437 static int strip_unused_nums(game_state
*state
)
1440 for (x
= 0; x
< state
->w
; x
++) {
1441 for (y
= 0; y
< state
->h
; y
++) {
1442 if ((GRID(state
,flags
,x
,y
) & F_NUMBERED
) &&
1443 !(GRID(state
,flags
,x
,y
) & F_NUMBERUSED
)) {
1444 GRID(state
,flags
,x
,y
) &= ~F_NUMBERED
;
1445 GRID(state
,lights
,x
,y
) = 0;
1450 debug(("Stripped %d unused numbers.\n", n
));
1454 static void unplace_lights(game_state
*state
)
1457 for (x
= 0; x
< state
->w
; x
++) {
1458 for (y
= 0; y
< state
->h
; y
++) {
1459 if (GRID(state
,flags
,x
,y
) & F_LIGHT
)
1460 set_light(state
,x
,y
,0);
1461 GRID(state
,flags
,x
,y
) &= ~F_IMPOSSIBLE
;
1462 GRID(state
,flags
,x
,y
) &= ~F_NUMBERUSED
;
1467 static int puzzle_is_good(game_state
*state
, int difficulty
)
1469 int nsol
, mdepth
= 0;
1470 unsigned int sflags
= flags_from_difficulty(difficulty
);
1472 unplace_lights(state
);
1474 #ifdef SOLVER_DIAGNOSTICS
1475 debug(("Trying to solve with difficulty %d (0x%x):\n",
1476 difficulty
, sflags
));
1477 if (verbose
) debug_state(state
);
1480 nsol
= dosolve(state
, sflags
, &mdepth
);
1481 /* if we wanted an easy puzzle, make sure we didn't need recursion. */
1482 if (!(sflags
& F_SOLVE_ALLOWRECURSE
) && mdepth
> 0) {
1483 debug(("Ignoring recursive puzzle.\n"));
1487 debug(("%d solutions found.\n", nsol
));
1488 if (nsol
<= 0) return 0;
1489 if (nsol
> 1) return 0;
1493 /* --- New game creation and user input code. --- */
1495 /* The basic algorithm here is to generate the most complex grid possible
1496 * while honouring two restrictions:
1498 * * we require a unique solution, and
1499 * * either we require solubility with no recursion (!params->recurse)
1500 * * or we require some recursion. (params->recurse).
1502 * The solver helpfully keeps track of the numbers it needed to use to
1503 * get its solution, so we use that to remove an initial set of numbers
1504 * and check we still satsify our requirements (on uniqueness and
1505 * non-recursiveness, if applicable; we don't check explicit recursiveness
1508 * Then we try to remove all numbers in a random order, and see if we
1509 * still satisfy requirements (putting them back if we didn't).
1511 * Removing numbers will always, in general terms, make a puzzle require
1512 * more recursion but it may also mean a puzzle becomes non-unique.
1514 * Once we're done, if we wanted a recursive puzzle but the most difficult
1515 * puzzle we could come up with was non-recursive, we give up and try a new
1518 #define MAX_GRIDGEN_TRIES 20
1520 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1521 char **aux
, int interactive
)
1523 game_state
*news
= new_state(params
), *copys
;
1524 int i
, j
, run
, x
, y
, wh
= params
->w
*params
->h
, num
;
1528 /* Construct a shuffled list of grid positions; we only
1529 * do this once, because if it gets used more than once it'll
1530 * be on a different grid layout. */
1531 numindices
= snewn(wh
, int);
1532 for (j
= 0; j
< wh
; j
++) numindices
[j
] = j
;
1533 shuffle(numindices
, wh
, sizeof(*numindices
), rs
);
1536 for (i
= 0; i
< MAX_GRIDGEN_TRIES
; i
++) {
1537 set_blacks(news
, params
, rs
); /* also cleans board. */
1539 /* set up lights and then the numbers, and remove the lights */
1540 place_lights(news
, rs
);
1541 debug(("Generating initial grid.\n"));
1542 place_numbers(news
);
1543 if (!puzzle_is_good(news
, params
->difficulty
)) continue;
1545 /* Take a copy, remove numbers we didn't use and check there's
1546 * still a unique solution; if so, use the copy subsequently. */
1547 copys
= dup_game(news
);
1548 strip_unused_nums(copys
);
1549 if (!puzzle_is_good(copys
, params
->difficulty
)) {
1550 debug(("Stripped grid is not good, reverting.\n"));
1557 /* Go through grid removing numbers at random one-by-one and
1558 * trying to solve again; if it ceases to be good put the number back. */
1559 for (j
= 0; j
< wh
; j
++) {
1560 y
= numindices
[j
] / params
->w
;
1561 x
= numindices
[j
] % params
->w
;
1562 if (!(GRID(news
, flags
, x
, y
) & F_NUMBERED
)) continue;
1563 num
= GRID(news
, lights
, x
, y
);
1564 GRID(news
, lights
, x
, y
) = 0;
1565 GRID(news
, flags
, x
, y
) &= ~F_NUMBERED
;
1566 if (!puzzle_is_good(news
, params
->difficulty
)) {
1567 GRID(news
, lights
, x
, y
) = num
;
1568 GRID(news
, flags
, x
, y
) |= F_NUMBERED
;
1570 debug(("Removed (%d,%d) still soluble.\n", x
, y
));
1572 if (params
->difficulty
> 0) {
1573 /* Was the maximally-difficult puzzle difficult enough?
1574 * Check we can't solve it with a more simplistic solver. */
1575 if (puzzle_is_good(news
, params
->difficulty
-1)) {
1576 debug(("Maximally-hard puzzle still not hard enough, skipping.\n"));
1583 /* Couldn't generate a good puzzle in however many goes. Ramp up the
1584 * %age of black squares (if we didn't already have lots; in which case
1585 * why couldn't we generate a puzzle?) and try again. */
1586 if (params
->blackpc
< 90) params
->blackpc
+= 5;
1587 debug(("New black layout %d%%.\n", params
->blackpc
));
1590 /* Game is encoded as a long string one character per square;
1592 * 'B' is a black square with no number
1593 * '0', '1', '2', '3', '4' is a black square with a number. */
1594 ret
= snewn((params
->w
* params
->h
) + 1, char);
1597 for (y
= 0; y
< params
->h
; y
++) {
1598 for (x
= 0; x
< params
->w
; x
++) {
1599 if (GRID(news
,flags
,x
,y
) & F_BLACK
) {
1601 *p
++ = ('a'-1) + run
;
1604 if (GRID(news
,flags
,x
,y
) & F_NUMBERED
)
1605 *p
++ = '0' + GRID(news
,lights
,x
,y
);
1610 *p
++ = ('a'-1) + run
;
1618 *p
++ = ('a'-1) + run
;
1622 assert(p
- ret
<= params
->w
* params
->h
);
1629 static char *validate_desc(game_params
*params
, char *desc
)
1632 for (i
= 0; i
< params
->w
*params
->h
; i
++) {
1633 if (*desc
>= '0' && *desc
<= '4')
1635 else if (*desc
== 'B')
1637 else if (*desc
>= 'a' && *desc
<= 'z')
1638 i
+= *desc
- 'a'; /* and the i++ will add another one */
1640 return "Game description shorter than expected";
1642 return "Game description contained unexpected character";
1645 if (*desc
|| i
> params
->w
*params
->h
)
1646 return "Game description longer than expected";
1651 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1653 game_state
*ret
= new_state(params
);
1657 for (y
= 0; y
< params
->h
; y
++) {
1658 for (x
= 0; x
< params
->w
; x
++) {
1664 if (c
>= 'a' && c
<= 'z')
1674 case '0': case '1': case '2': case '3': case '4':
1675 GRID(ret
,flags
,x
,y
) |= F_NUMBERED
;
1676 GRID(ret
,lights
,x
,y
) = (c
- '0');
1680 GRID(ret
,flags
,x
,y
) |= F_BLACK
;
1688 assert(!"Malformed desc.");
1693 if (*desc
) assert(!"Over-long desc.");
1698 static char *solve_game(game_state
*state
, game_state
*currstate
,
1699 char *aux
, char **error
)
1702 char *move
= NULL
, buf
[80];
1703 int movelen
, movesize
, x
, y
, len
;
1704 unsigned int oldflags
, solvedflags
, sflags
;
1706 /* We don't care here about non-unique puzzles; if the
1707 * user entered one themself then I doubt they care. */
1709 sflags
= F_SOLVE_ALLOWRECURSE
| F_SOLVE_DISCOUNTSETS
;
1711 /* Try and solve from where we are now (for non-unique
1712 * puzzles this may produce a different answer). */
1713 solved
= dup_game(currstate
);
1714 if (dosolve(solved
, sflags
, NULL
) > 0) goto solved
;
1717 /* That didn't work; try solving from the clean puzzle. */
1718 solved
= dup_game(state
);
1719 if (dosolve(solved
, sflags
, NULL
) > 0) goto solved
;
1720 *error
= "Unable to find a solution to this puzzle.";
1725 move
= snewn(movesize
, char);
1727 move
[movelen
++] = 'S';
1728 move
[movelen
] = '\0';
1729 for (x
= 0; x
< currstate
->w
; x
++) {
1730 for (y
= 0; y
< currstate
->h
; y
++) {
1732 oldflags
= GRID(currstate
, flags
, x
, y
);
1733 solvedflags
= GRID(solved
, flags
, x
, y
);
1734 if ((oldflags
& F_LIGHT
) != (solvedflags
& F_LIGHT
))
1735 len
= sprintf(buf
, ";L%d,%d", x
, y
);
1736 else if ((oldflags
& F_IMPOSSIBLE
) != (solvedflags
& F_IMPOSSIBLE
))
1737 len
= sprintf(buf
, ";I%d,%d", x
, y
);
1739 if (movelen
+ len
>= movesize
) {
1740 movesize
= movelen
+ len
+ 256;
1741 move
= sresize(move
, movesize
, char);
1743 strcpy(move
+ movelen
, buf
);
1754 static int game_can_format_as_text_now(game_params
*params
)
1759 /* 'borrowed' from slant.c, mainly. I could have printed it one
1760 * character per cell (like debug_state) but that comes out tiny.
1761 * 'L' is used for 'light here' because 'O' looks too much like '0'
1762 * (black square with no surrounding lights). */
1763 static char *game_text_format(game_state
*state
)
1765 int w
= state
->w
, h
= state
->h
, W
= w
+1, H
= h
+1;
1766 int x
, y
, len
, lights
;
1770 len
= (h
+H
) * (w
+W
+1) + 1;
1771 ret
= snewn(len
, char);
1774 for (y
= 0; y
< H
; y
++) {
1775 for (x
= 0; x
< W
; x
++) {
1782 for (x
= 0; x
< W
; x
++) {
1785 /* actual interesting bit. */
1786 flags
= GRID(state
, flags
, x
, y
);
1787 lights
= GRID(state
, lights
, x
, y
);
1788 if (flags
& F_BLACK
) {
1789 if (flags
& F_NUMBERED
)
1790 *p
++ = '0' + lights
;
1794 if (flags
& F_LIGHT
)
1796 else if (flags
& F_IMPOSSIBLE
)
1798 else if (lights
> 0)
1810 assert(p
- ret
== len
);
1815 int cur_x
, cur_y
, cur_visible
;
1818 static game_ui
*new_ui(game_state
*state
)
1820 game_ui
*ui
= snew(game_ui
);
1821 ui
->cur_x
= ui
->cur_y
= ui
->cur_visible
= 0;
1825 static void free_ui(game_ui
*ui
)
1830 static char *encode_ui(game_ui
*ui
)
1832 /* nothing to encode. */
1836 static void decode_ui(game_ui
*ui
, char *encoding
)
1838 /* nothing to decode. */
1841 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1842 game_state
*newstate
)
1844 if (newstate
->completed
)
1845 ui
->cur_visible
= 0;
1848 #define DF_BLACK 1 /* black square */
1849 #define DF_NUMBERED 2 /* black square with number */
1850 #define DF_LIT 4 /* display (white) square lit up */
1851 #define DF_LIGHT 8 /* display light in square */
1852 #define DF_OVERLAP 16 /* display light as overlapped */
1853 #define DF_CURSOR 32 /* display cursor */
1854 #define DF_NUMBERWRONG 64 /* display black numbered square as error. */
1855 #define DF_FLASH 128 /* background flash is on. */
1856 #define DF_IMPOSSIBLE 256 /* display non-light little square */
1858 struct game_drawstate
{
1861 unsigned int *flags
; /* width * height */
1866 /* Believe it or not, this empty = "" hack is needed to get around a bug in
1867 * the prc-tools gcc when optimisation is turned on; before, it produced:
1868 lightup-sect.c: In function `interpret_move':
1869 lightup-sect.c:1416: internal error--unrecognizable insn:
1870 (insn 582 580 583 (set (reg:SI 134)
1874 static char *interpret_move(game_state
*state
, game_ui
*ui
, 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
= NULL
, *empty
= "", 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(game_state
*state
, 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(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 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
, 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
, game_state
*state
, game_ui
*ui
,
2069 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
, game_state
*state
,
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
, game_state
*oldstate
,
2158 game_state
*state
, int dir
, game_ui
*ui
,
2159 float animtime
, float flashtime
)
2161 int flashing
= FALSE
;
2164 if (flashtime
) flashing
= (int)(flashtime
* 3 / FLASH_TIME
) != 1;
2168 TILE_SIZE
* ds
->w
+ 2 * BORDER
,
2169 TILE_SIZE
* ds
->h
+ 2 * BORDER
, COL_BACKGROUND
);
2171 draw_rect_outline(dr
, COORD(0)-1, COORD(0)-1,
2172 TILE_SIZE
* ds
->w
+ 2,
2173 TILE_SIZE
* ds
->h
+ 2,
2176 draw_update(dr
, 0, 0,
2177 TILE_SIZE
* ds
->w
+ 2 * BORDER
,
2178 TILE_SIZE
* ds
->h
+ 2 * BORDER
);
2182 for (x
= 0; x
< ds
->w
; x
++) {
2183 for (y
= 0; y
< ds
->h
; y
++) {
2184 unsigned int ds_flags
= tile_flags(ds
, state
, ui
, x
, y
, flashing
);
2185 if (ds_flags
!= GRID(ds
, flags
, x
, y
)) {
2186 GRID(ds
, flags
, x
, y
) = ds_flags
;
2187 tile_redraw(dr
, ds
, state
, x
, y
);
2193 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2194 int dir
, game_ui
*ui
)
2199 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2200 int dir
, game_ui
*ui
)
2202 if (!oldstate
->completed
&& newstate
->completed
&&
2203 !oldstate
->used_solve
&& !newstate
->used_solve
)
2208 static int game_status(game_state
*state
)
2210 return state
->completed ?
+1 : 0;
2213 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2218 static void game_print_size(game_params
*params
, float *x
, float *y
)
2223 * I'll use 6mm squares by default.
2225 game_compute_size(params
, 600, &pw
, &ph
);
2230 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2232 int w
= state
->w
, h
= state
->h
;
2233 int ink
= print_mono_colour(dr
, 0);
2234 int paper
= print_mono_colour(dr
, 1);
2237 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2238 game_drawstate ads
, *ds
= &ads
;
2239 game_set_size(dr
, ds
, NULL
, tilesize
);
2244 print_line_width(dr
, TILE_SIZE
/ 16);
2245 draw_rect_outline(dr
, COORD(0), COORD(0),
2246 TILE_SIZE
* w
, TILE_SIZE
* h
, ink
);
2251 print_line_width(dr
, TILE_SIZE
/ 24);
2252 for (x
= 1; x
< w
; x
++)
2253 draw_line(dr
, COORD(x
), COORD(0), COORD(x
), COORD(h
), ink
);
2254 for (y
= 1; y
< h
; y
++)
2255 draw_line(dr
, COORD(0), COORD(y
), COORD(w
), COORD(y
), ink
);
2260 for (y
= 0; y
< h
; y
++)
2261 for (x
= 0; x
< w
; x
++) {
2262 unsigned int ds_flags
= tile_flags(ds
, state
, NULL
, x
, y
, FALSE
);
2263 int dx
= COORD(x
), dy
= COORD(y
);
2264 if (ds_flags
& DF_BLACK
) {
2265 draw_rect(dr
, dx
, dy
, TILE_SIZE
, TILE_SIZE
, ink
);
2266 if (ds_flags
& DF_NUMBERED
) {
2268 sprintf(str
, "%d", GRID(state
, lights
, x
, y
));
2269 draw_text(dr
, dx
+ TILE_SIZE
/2, dy
+ TILE_SIZE
/2,
2270 FONT_VARIABLE
, TILE_SIZE
*3/5,
2271 ALIGN_VCENTRE
| ALIGN_HCENTRE
, paper
, str
);
2273 } else if (ds_flags
& DF_LIGHT
) {
2274 draw_circle(dr
, dx
+ TILE_SIZE
/2, dy
+ TILE_SIZE
/2,
2275 TILE_RADIUS
, -1, ink
);
2281 #define thegame lightup
2284 const struct game thegame
= {
2285 "Light Up", "games.lightup", "lightup",
2292 TRUE
, game_configure
, custom_params
,
2300 TRUE
, game_can_format_as_text_now
, game_text_format
,
2308 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
2311 game_free_drawstate
,
2316 TRUE
, FALSE
, game_print_size
, game_print
,
2317 FALSE
, /* wants_statusbar */
2318 FALSE
, game_timing_state
,
2322 #ifdef STANDALONE_SOLVER
2324 int main(int argc
, char **argv
)
2328 char *id
= NULL
, *desc
, *err
, *result
;
2329 int nsol
, diff
, really_verbose
= 0;
2330 unsigned int sflags
;
2332 while (--argc
> 0) {
2334 if (!strcmp(p
, "-v")) {
2336 } else if (*p
== '-') {
2337 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
2345 fprintf(stderr
, "usage: %s [-v] <game_id>\n", argv
[0]);
2349 desc
= strchr(id
, ':');
2351 fprintf(stderr
, "%s: game id expects a colon in it\n", argv
[0]);
2356 p
= default_params();
2357 decode_params(p
, id
);
2358 err
= validate_desc(p
, desc
);
2360 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
2363 s
= new_game(NULL
, p
, desc
);
2365 /* Run the solvers easiest to hardest until we find one that
2366 * can solve our puzzle. If it's soluble we know that the
2367 * hardest (recursive) solver will always find the solution. */
2369 for (diff
= 0; diff
<= DIFFCOUNT
; diff
++) {
2370 printf("\nSolving with difficulty %d.\n", diff
);
2371 sflags
= flags_from_difficulty(diff
);
2373 nsol
= dosolve(s
, sflags
, NULL
);
2374 if (nsol
== 1) break;
2379 printf("Puzzle has no solution.\n");
2380 } else if (nsol
< 0) {
2381 printf("Unable to find a unique solution.\n");
2382 } else if (nsol
> 1) {
2383 printf("Puzzle has multiple solutions.\n");
2385 verbose
= really_verbose
;
2387 printf("Puzzle has difficulty %d: solving...\n", diff
);
2388 dosolve(s
, sflags
, NULL
); /* sflags from last successful solve */
2389 result
= game_text_format(s
);
2390 printf("%s", result
);
2399 /* vim: set shiftwidth=4 tabstop=8: */