Turn out the Lights

Consider an N×NN \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×55 \times 5 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, NN, specifying the size of the grid. The following NN 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, 1000010000 light grids, with sizes 5N165 \leq N \leq 16. Precisely XX of these grids are solvable.

Find XX.


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

Image Credit: http://www.edcourtenay.co.uk/musings-of-an-idiot/2002/04/10/LightsOut
×

Problem Loading...

Note Loading...

Set Loading...