2
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
added
removed
lightup.c
