|Perl: the Markov chain saw|
Lights out puzzleby ambrus (Abbot)
|on Nov 28, 2011 at 09:46 UTC||Need Help??|
Here's a quick Monday morning puzzle.
You have a 14x14 rectangular game board except that the last 7 fields of the last row are missing. Each field has a lamp, and a button that toggles the lamps on that field and each of its neighbours in a cardinal direction, altogether at most five lamps. At the start, all lights are lit. Find out which buttons to push to unlight all lights.
Why I like this puzzle is:
brute forcing won't work, but there's an intermediate algorithm that's fast enough for this board size but easier to code than the general algorithm that solves this for larger board sizes.
Update: here's an example. Suppose we have a 3x4 board with the last 1 field of the last row missing. At the start, it looks like this, all lamps lit:
Now we press the button on the bottom left field so three lights go off:
then press the button above that so two lights turn back on but two lights go off:
now press the second button in the bottom row:
now the button above that one:
finally press the top right button:
and all the lights are off, so we've solved this small board.