Turn out the Lights

Computer Science Level 3

Consider an $$N \times N$$ 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.

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 $$5 \times 5$$ grid can be solved by pressing the five numbered squares in their labeled order:

Imgur

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:

Imgur

Grid configurations will be represented as a series of lines in a text file. The first line will be a single integer, $$N$$, specifying the size of the grid. The following $$N$$ lines will specify the contents of the grid, where '$$\text{#}$$' characters indicate lights that are on, and '$$\text{.}$$' 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  5 .#..# #..#. #.#.. .#### ...#. 5 .#... .##.. #.... ..... ..... 

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, $$10000$$ light grids, with sizes $$5 \leq N \leq 16$$. Precisely $$X$$ of these grids are solvable.

Find $$X$$.

Note: An efficient program can find $$X$$ in well under one minute. If your program is taking hours to complete, you may need to rethink your approach.

×