{"id":1805,"date":"2014-07-29T14:12:35","date_gmt":"2014-07-29T04:12:35","guid":{"rendered":"http:\/\/www.somethinkodd.com\/oddthinking\/?p=1805"},"modified":"2014-07-29T14:12:35","modified_gmt":"2014-07-29T04:12:35","slug":"light-up-puzzle","status":"publish","type":"post","link":"https:\/\/www.somethinkodd.com\/oddthinking\/2014\/07\/29\/light-up-puzzle\/","title":{"rendered":"Light Up Puzzle"},"content":{"rendered":"

Long-term readers (given the radio silence, do I have any other type?) will remember that I wrote a Puzzle Solving Framework<\/a> to help solve “newspaper” pencil-and-paper puzzles. I’ve been thinking of preparing a presentation about it for a local Python group, so I decided to implement another one.<\/p>\n

Introducing Light Up<\/h2>\n

Light Up<\/a> is an example of such a puzzle. Simon Tatham’s Portable Puzzle Collection includes an online version<\/a> (amongst others).<\/p>\n

Quick Rule Summary<\/h2>\n

The puzzle is presented as a grid of white and black cells. The black cells are pre-set – like in a cross-word. Some black cells are marked with a number from 0 to 4.<\/p>\n

The task is to mark all the white cells as either empty (indicated with a small rectangular dot) or containing a light globe (indicated with a large circle).<\/p>\n

Lights illuminate all white cells squares in their line-of-sight in four directions, until blocked by a black square. <\/p>\n

The constraints are:<\/p>\n

    \n
  1. Lights may not be in direct line-of-sight of other lights.<\/li>\n
  2. All white cells must be illuminated.<\/li>\n
  3. The numbered blocks must be directly adjacent (i.e. four directions) with that many lights.<\/li>\n<\/ol>\n

    Go try some now, before the spoilers.<\/p>\n

    Tactics<\/h2>\n

    Here’s an example screen-shot (from my own program) of an unsolved puzzle.<\/p>\n

    \"Puzzle<\/a><\/p>\n

    Where can we start to solve this puzzle?<\/p>\n

    Tactic A<\/h3>\n

    We can mark the cells around the 0 cell as empty. There can’t be any lights around it.<\/p>\n

    More generally, if the number on a cell equals the number of adjacent lights already known, any remaining adjacent cells must be empty.<\/p>\n

    If I teach the solver this rule, it can solve this much of this puzzle already.<\/p>\n

    \"Puzzle<\/a><\/p>\n

    Tactic B<\/h3>\n

    Now consider the block numbered with a 3. There are only three remaining places a light could go, so they all must be lights.<\/p>\n

    More generally, if the number on a cell subtract the number of adjacent lights already known equals the number of adjacent unknown cells, they must be lights.<\/p>\n

    These rules apply recursively. If I teach the solver this rule, it can solve this much of the puzzle already: <\/p>\n

    Legend:<\/strong> The yellow areas indicate a cell is illuminated.<\/em> <\/p>\n

    \"Puzzle<\/a><\/p>\n

    Tactic C<\/h3>\n

    Now consider the unlit, empty cell halfway up the left side.<\/p>\n

    There is only one possible place a light could go to light this cell – the bottom left.<\/p>\n

    More generally, if an unlit cell has only one unknown cell in its line-of-site. Than unknown cell must be a light.<\/p>\n

    Once we implement that rule, the final three cells are all marked as lights.<\/p>\n

    \"Puzzle<\/a><\/p>\n

    Ta daaa! A solver! Exciting!<\/p>\n

    Wait… Does it solve every puzzle?<\/p>\n

    Lets try this one:<\/p>\n

    \"Puzzle<\/a><\/p>\n

    How far do we get with Tactics A, B and C?<\/p>\n

    \"Puzzle<\/a><\/p>\n

    Oh dear! Not very far at all. Time to add a new tactic.<\/p>\n

    Tactic D<\/h3>\n

    This one is a little more complicated. Consider the cell in the bottom right corner. If it was a light, the light would illuminate two of the direct neighbours of the 3 cell nearby, making it impossible for the 3 cell to be satisfied.<\/p>\n

    More generally, if all but one of the remaining direct neighbours must be lights, then a “diagonal” cell sitting between two unknown cells must be empty.<\/p>\n

    This gives us this extra information: <\/p>\n

    \"Puzzle<\/a><\/p>\n

    If we then recursively apply all these tactics…<\/p>\n

    \"Puzzle<\/a><\/p>\n

    Ta daa! We have a solver! Wait, we’ve been here before. Does it really solve every puzzle? What about this one?<\/p>\n

    \"Puzzle<\/a><\/p>\n

    All the tactics lead to…<\/p>\n

    \"Puzzle<\/a><\/p>\n

    Nope. Not solved.<\/p>\n

    Drawing the Line<\/h2>\n

    This is the point where I stop. I don’t have any more simple crank-turning rules to hand. I could brute-force it, but that is against everything I stand for. I could look for more simple rules, but eventually I am going to fail, because Light Up turns out to be NP-complete<\/a>.<\/p>\n

    So, that’s the point where I declare this code isn’t a Light Up solver<\/em>, it is a Light Up helper<\/em>, taking away the mundane part of the puzzle and leaving the user to solve only the hard parts.<\/p>\n

    (Just so we are clear: I am declaring this a rousing success – especially as it only took an evening to knock out, with the framework.)<\/p>\n

    Implementation Details<\/h2>\n

    There was very little novel here compared to other puzzles I have discussed before.<\/p>\n

    It came in at about 400 lines, give or take, for the solver, and another 270 for the GUI.<\/p>\n

    Each cell was either a Blank Cell (to be solved), a Blank Block or a Numbered Block.<\/p>\n

    Numbered Blocks were configured with all 8 of their immediate neighbours. Each numbered block was responsible for implementing tactics A, B and D.<\/p>\n

    Blank Cells were configured with an (unordered) set of all of the other blank cells in their line-of-site. Each Blank Cell was responsible for implementing Tactic C. If it was marked as a light, it was also responsible for informing all of its line-of-site neighbours that they were empty.<\/p>\n

    Part of the elegance of the implementations of other puzzles is that each cell was responsible for figuring out its own constraints, by inspecting its neighbours. Unfortunately, this implementation wasn’t as elegant. Each of the tactics resulted in a conclusion being formed, not about the cell implementing it, but about one of its neighbours. e.g. when a Numbered Block applied Tactic A, it did not change its own state, but changed the state (via a method call) on the blank cells near it.<\/p>\n

    One minor novelty is that I added toggles to turn one or off particular tactics, so I could illustrate progress more clearly, and a screen-shot function.<\/p>\n

    Conclusion<\/h2>\n

    Another success for the Puzzle Solving Framework, but not a terribly exciting one.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Long-term readers (given the radio silence, do I have any other type?) will remember that I wrote a Puzzle Solving Framework to help solve “newspaper” pencil-and-paper puzzles. I’ve been thinking of preparing a presentation about it for a local Python group, so I decided to implement another one. Introducing Light Up Light Up is an […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_s2mail":"yes","footnotes":""},"categories":[33,34],"tags":[91],"class_list":["post-1805","post","type-post","status-publish","format-standard","hentry","category-puzzle-solving","category-software-development","tag-puzzles"],"_links":{"self":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/1805","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/comments?post=1805"}],"version-history":[{"count":6,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/1805\/revisions"}],"predecessor-version":[{"id":1822,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/1805\/revisions\/1822"}],"wp:attachment":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/media?parent=1805"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/categories?post=1805"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/tags?post=1805"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}