grid of lights, each one either on or off. The grid can be manipulated by pressing any one light on the grid, toggling the light - however, when a given light is pressed, all lights that are edge-wise adjacent to the pressed light also get toggled.Consider an
Given an initial configuration, one might be interested in a sequence of moves that turns all of the lights on the board off, or more simply, whether such a sequence exists or not. For example, the following grid can be solved by pressing the five numbered squares in their labeled order:
As surprising as it may seem, this second board is provably unsolvable. There is no sequence of moves in existence that turns all of the lights off:
Grid configurations will be represented as a series of lines in a text file. The first line will be a single integer, , specifying the size of the grid. The following lines will specify the contents of the grid, where '' characters indicate lights that are on, and '' characters indicate lights that are off. The two grid configurations above would be encoded as:
1 2 3 4 5 6 7 8 9 10 11 12
Clicking lights.txt will trigger a download of a ~300KB zip file, which contains a text file named "lights.txt". The text file contains, in the specified format, light grids, with sizes . Precisely of these grids are solvable.
Note: An efficient program can find in well under one minute. If your program is taking hours to complete, you may need to rethink your approach.