From c0f63b88e536d161a4508c918f805fbc497b75c9 Mon Sep 17 00:00:00 2001 From: simon Date: Mon, 23 Jan 2012 19:12:12 +0000 Subject: [PATCH] Add comments suggesting some solver upgrades to Light Up (perhaps for a new sub-recursive difficulty level?), inspired by a user emailing in the game ID 18x10:gBc1b2g2e2d1b2c2h2e3c2dBd1g1bBb2b1fBbBb1bBgBd2dBi1h1c2b1dBe2bBdBb3cBg which I was able to solve without backtracking by the use of these techniques. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@9388 cda61777-01e9-0310-a592-d414129be87e --- lightup.c | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) diff --git a/lightup.c b/lightup.c index 47b49b2..8f09263 100644 --- a/lightup.c +++ b/lightup.c @@ -1,5 +1,45 @@ /* * lightup.c: Implementation of the Nikoli game 'Light Up'. + * + * Possible future solver enhancements: + * + * - In a situation where two clues are diagonally adjacent, you can + * deduce bounds on the number of lights shared between them. For + * instance, suppose a 3 clue is diagonally adjacent to a 1 clue: + * of the two squares adjacent to both clues, at least one must be + * a light (or the 3 would be unsatisfiable) and yet at most one + * must be a light (or the 1 would be overcommitted), so in fact + * _exactly_ one must be a light, and hence the other two squares + * adjacent to the 3 must also be lights and the other two adjacent + * to the 1 must not. Likewise if the 3 is replaced with a 2 but + * one of its other two squares is known not to be a light, and so + * on. + * + * - In a situation where two clues are orthogonally separated (not + * necessarily directly adjacent), you may be able to deduce + * something about the squares that align with each other. For + * instance, suppose two clues are vertically adjacent. Consider + * the pair of squares A,B horizontally adjacent to the top clue, + * and the pair C,D horizontally adjacent to the bottom clue. + * Assuming no intervening obstacles, A and C align with each other + * and hence at most one of them can be a light, and B and D + * likewise, so we must have at most two lights between the four + * squares. So if the clues indicate that there are at _least_ two + * lights in those four squares because the top clue requires at + * least one of AB to be a light and the bottom one requires at + * least one of CD, then we can in fact deduce that there are + * _exactly_ two lights between the four squares, and fill in the + * other squares adjacent to each clue accordingly. For instance, + * if both clues are 3s, then we instantly deduce that all four of + * the squares _vertically_ adjacent to the two clues must be + * lights. (For that to happen, of course, there'd also have to be + * a black square in between the clues, so the two inner lights + * don't light each other.) + * + * - I haven't thought it through carefully, but there's always the + * possibility that both of the above deductions are special cases + * of some more general pattern which can be made computationally + * feasible... */ #include -- 2.11.0