Turn out the Lights

Solving this problem involves making a number of critical observations which enable us to solve a much simpler problem, followed by solving the simpler problem really fast ten thousand times.

Observation 1: The order of moves does not matter.

For any move sequence, the state of any given light depends on the initial configuration, and the number of times it was toggled. The former is fixed, and the latter is additive based on the moves made, and since addition is commutative, this number is irrespective of the order of the moves.

Observation 2: Each light need only be pressed at most once.

Since we've established that the order of moves doesn't matter, we can reorder any solution's moves however we like without changing its impact. Note what happens if we put two moves on the same light right next to each other - the toggles made by the first move are canceled by the second one, making the solution identical to one where neither of those moves were made. We can repeat this process to show that any move sequence can be reduced to an equivalent sequence with at most one press per light, so those are the only solutions we need to explore.

With Observations 1 and 2, we've restricted the set of move sequences we must analyze to a finite number to determine whether a board is solvable. Unfortunately, this number is $2^{N \cdot N}$ , which is in lifetime-of-the-universe territory for $N = 16$ . We need to discover more opportunities for efficiency.

Observation 3: The first row of moves in a solution uniquely determines all moves in all remaining rows.

What this means is, given a list of 'press' or 'don't press' for all buttons in the first row of a grid, we can explicitly figure out the rest of a working solution from that data. The procedure is simple:

• First, make the moves needed in the first row. To get all the lights turned off in the first row, we need to press the lights below the lights which are 'on' in the first row, in the second row, and only those lights in the second row. If we press other lights, we'll turn on other lights in the first row which we then have no way to turn off, and vice versa.
• This process must be repeated, inductively, for all rows.

So, to determine if a board is solvable, it suffices to consider all move sets we could make in the first row alone, and see if any of them lead to a solution by the procedure described.

Observations 1 through 3 are all that's needed to come up with a solution that will finish in many hours, which, while sub-par, is a perfectly legitimate approach.

For each board, try all $2^N$ move sets on the first row, procedurally mutate from each one, and see if any such move set leads to an empty grid. This will take $O(10000 \cdot N^2 \cdot 2^N)$ time. We can do a lot better than this, though.

Observation 4: All solvable board states are reachable from each other.

This stems from the fact that all move sequences are invertible, and by the very same move sequence as well. The consequence of this is that the only solvable board states are those that are reachable from the empty board state.

The greater, more useful consequence, is the induced transitive property. For any board state $b$ , and any board state $c$ than can be reached from $b$ , $b$ is solvable if and only if $c$ is solvable. We can use this truth to achieve great computational efficiency.

Recall that Observation 3 provided us with a way to check whether a given board state was solvable. Now, let $C$ be the set of all boards for which only lights in the bottom row are on, if any. For each $N$ , we will compute $S_N \subseteq C$ , the set of all $c \in C$ that are solvable.

Note that in the procedure outlined in Observation 3, the steps taken are completely independent of the configuration of lights in the bottom row - we only ever consider the states of lights in the preceding rows when determining the moves to be made. Thus, in inspecting all possible top-row move sets and their deterministic followings for a given $c \in C$ , we in fact inspect the case for all $c \in C$ , since the prodecure is the same.

Since a move sequence is its own inversion, if a sequence of moves solves some $c \in C$ , the same sequence also mutates the empty state into $c$ . By considering all $2^N$ top-row move sets, and applying the procedure in Observation 3, we thus determine all $c \in C$ that are reachable from the empty state, and therefore all $c \in C$ that are solvable, which is $S_N$ .

So, for each $N \in [5,6,...,16]$ , we can compute $S_N$ in $O(N^2 \cdot 2^N)$ time. Then, for each board $b$ in the file input, we use the procedure in Observation 3 for the empty top-row move set to mutate the board into some $c \in C$ . By the transitive property in Observation 4, $b$ is solvable if and only if $c \in S_N$ . Since we precomputed all these sets, each $b$ only costs $O(N^2)$ runtime, for a total of $O(10000 \cdot N^2)$ runtime after precomputation.

The precomputation time turns out to be the bottleneck, with $N = 16$ being the most expensive component. However, reasonably efficient code can compute all $S_N$ in well under a minute, and the queries for the $10000$ grids take a mere fraction of a second in comparison.

When all is said and done, code will identify that $\boxed{8986}$ of the $10000$ boards are solvable, and the rest are not.

Of course, other solutions exist! This game is well known , and very well analyzed .

One alternative solution (which I have not checked for speed), involves solving the board by treating the moves as variables in $\mathbb{Z}_2$ , and doing Gaussian Elimination. This runs in $O(10000 \cdot N^6)$ time.

Bonus Trivia:

Interestingly enough, upon further analysis, I found that, of the possible $N$ for this problem, only boards of size $5$ , $9$ , $11$ , $14$ , and $16$ have unsolvable instances. That is to say, that if $N$ is not one of those numbers, the board is guaranteed to be solvable, regardless of configuration!

Predictably, OEIS comes to the rescue, and the rabbit hole goes down to Chebyshev polynomials of the second kind . Mathematics is truly an extraordinary rabbit hole.

With linear algebra , runtime about 2 seconds.

For a grid $n\times n$ , let's consider $P$ and $S$ , two $\mathbb{F}_2$ -vector space of dimension $n^2$ , one dimension for each light/button of the grid.

A vector in $P$ represents which button are Pressed (value 1) or not (value 0). A vector in $S$ represents which lights are Switched on (value 1) or off (value 0).

If $n=2$ , $p=\begin{pmatrix}1\\0\\1\\1\end{pmatrix}\in P$ represents pressing on buttons 1, 3 and 4. $s=\begin{pmatrix}0\\1\\1\\0\end{pmatrix}\in S$ represents lights 2 and 3 being switched on.

Let $A$ be a matrix of dimension $n^2\times n^2$ such that if $p\in P$ and $A·p=s$ , then $s\in S$ is the list of lights that have been switched. The $i^{th}$ column of $A$ has 1 for each light that is switched by pressing button $i$ .

If $n=2$ , $A=\begin{pmatrix}1&1&1&0\\1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix}$ and for example, $A·\begin{pmatrix}1\\0\\1\\1\end{pmatrix}=\begin{pmatrix}0\\0\\1\\0\end{pmatrix}$ , which means that pressing buttons 1, 3 and 4 switches light 3.

Now, given a grid $s$ of lights, the problem is to find a vector $p\in P$ such that $A·p=s$ . (It's always possible if $A$ in invertible in $\mathbb{F}_2$ , which is the case for $n=1,2,3,6,7,8,10,12,13,15,\dots$ ).

I tried to solve each of the 4'209 grids on 10'000 with non invertible matrix, but it took several minutes and didn't give the right answer.

I then tried to solve once for each $n$ by changin the matrix to row echelon form, so as to get conditions on $s$ . That worked well and took 1 second to compute the matrixes and 1 second to check each grid.

Step 1: creating matrixes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# Change a light number to a grid position
def numToGrid(size, num):
        return (num%size, num/size)
# Change a grid position to a light number 
def gridToNum(size, x, y): 
        return y * size + x 

def createMatrix(n):
        m = []
        for n1 in xrange(n*n):
                m += [ (n*n) * [0] ]
                x1, y1 = numToGrid(n, n1) 
                for n2 in xrange(0, n1+1):
                        x2, y2 = numToGrid(n, n2) 
                        if abs(x1-x2) + abs(y1-y2) <= 1:
                                m[n1][n2] = 1 
                                m[n2][n1] = 1 
        return m

Step 2: Changing to row echelon form and finding conditions on lights to turn off for a solution to exist.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def getConditions(m):
        n = len(m)
        # Adding an identity matrix on the right
        for line in xrange(n):
                m[line] += n*[0]
                m[line][n + line] = 1

        # For each column, take 1's away under currentLine
        currentLine = 0
        for currentCol in xrange(n):
                if m[currentLine][currentCol] == 0:
                        # try to find a line with 1 in currentCol
                        t1 = [i for i in xrange(currentLine + 1, n) if m[i][currentCol] == 1]
                        # if found, exchange the lines
                        if len(t1) > 0:
                                m[currentLine], m[t1[0]] = m[t1[0]], m[currentLine]
                        else:
                                # if not, continue with same currentLine, but on next column
                                continue
                # take away all 1's under currentLine
                for line in xrange(currentLine + 1, n):
                        if m[line][currentCol] == 1:
                                # change other columns, to only 1 or 0
                                for col in xrange(currentCol, len(m[line])):
                                        m[line][col] = ((m[line][col] - m[currentLine][col]) + 2) %2
                # go to next line to preserve the remaining 1 in currentCol
                currentLine += 1


        # From row echelon matrix, read last lines with only 0's
        # The right part of the matrix (identity at start)
        #     gives the required conditions
        conditions = []
        for line in xrange(currentLine, n):
                conditions += [ m[line][n:] ]
        return conditions

Step 3: Checking if a grid satisfies conditions to have a solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

CONDITIONS = {}
for i in xrange(5, 17):
        CONDITIONS[i] = getConditions(createMatrix(i))

def hasSolution(lights):
        global CONDITIONS
        for cond in CONDITIONS[int(math.sqrt(len(lights)))]:
                if sum([lights[i]*cond[i] for i in xrange(len(lights))])%2 == 1:
                        return False
        return True

Step 4 Initialize, read file and check grids

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

f = open('lights.txt')
line = f.readline().strip()
nbOk = 0
while line:
        # read one grid
        n = int(line)
        tab = []
        for i in xrange(n):
                tab += [f.readline().strip()]

        # optimizing when there's no condition
        if n in [4,5,9,11,14,16]:
                # change grid to vector
                lights = []
                for i in xrange(n**2):
                        if tab[i/n][i%n] == '.':
                                lights += [0]
                        else:
                                lights += [1]

                # check if grid has solution
                if hasSolution(lights):
                        nbOk += 1
        else:
                nbOk += 1
        line = f.readline().strip()

print nbOk