I am struggling with a complex version of the "lights out" puzzle

Question

Hello my fellow puzzlers. I am new to this holy land so if my question is not the kind you people like to solve, I apologize.

As some of you may know, there is a puzzle named: "lights out" based on a simple set of rules. There is a 5x5 square (usually) and every unit square is either "on" or "off" indicated by two colors (usually white and black/red). Clicking on a unit square changes the color of that square and all connected squares. Your task is to make every unit square white.

The puzzle above is easy to solve. Just click the middle square and every square turns white. But this puzzle:

This puzzle would take hours without a method guiding us. And luckily, we have just that. The method is called: "Chase the lights". And it is easy to execute. You can read about how it works in one of the links below.

https://en.wikipedia.org/wiki/Lights_Out_(game) http://www.logicgamesonline.com/lightsout/tutorial.html (less detailed)

Now, it is all fine until this point. We can solve every puzzle(if a solution exists.). But, how would we approach something like this:

https://store.steampowered.com/app/551110/Wayout/ (the game which is in the screenshot)

If you try the "chase the lights" method here, your plan will be put to a stop because of the holes. And this is only one level. There are levels that are much more complicated than this one. In some of them the board is not even a square. So, my question is this: How should I think about these puzzles? Do I have to discover a rule for each and every one of them? If so, how? I am just clueless. I hope some smart people here can enlighten me.

Answer 1

You are basically trying to solve a linear algebra question, but with XOR instead of addition. The good news is that this can be done in the usual way. See this math.SE article.

So, let me back up.

Draw up a matrix with rows and columns equal to the number of available buttons in the puzzle. In your example, it's 25-3 = 22. So a $22\times 22$ matrix. Each row will contain 1s if pressing that button changes the corresponding button. So the first row will be $(1,1,0,0,0,1,0,\ldots,0)$. This method is generalizable and represents the whole puzzle. Let's call this matrix $M$.

The suppose you have a solution vector $A$. This contains a 1 if you need to press the button and a 0 otherwise. Then $A\cdot M$ will give you the configuration of pressing all the buttons in the solution (working with XOR, so even numbers will be 0 and odd will be 1). To this you need to add your starting position which we can represent by a vector $S$. In your example, $S=(1,0,1,0,1,1,1,0,1,0,0,1,0,1,1,1,0,1,1,1,1,0)$.

So now we know that $A.M+S = 0$, where $0 = (0,0,0,\ldots,0)$. And, since we're dealing with XOR, $S = -S$, so this works out to $A.M=S$.

Now you just need to invert $M|I$ in the usual way (where $I$ is the identity matrix) and then $A=A.M.M^{-1} = S.M^{-1}$.

---

In your particular example, the solution $A=(0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0)$

Shown on your diagram, it works as follows: (Blue dots are the buttons to press; Green dots are the side effects from pressing the buttons)

It should be clear that the red squares all have an odd number of dots and the white ones all have an even number of dots.

Here's the python code I used to solve it (a bit ugly):

import numpy as np

setup = np.array([[1,1,1,1,1],
                  [1,0,1,1,1],
                  [1,1,0,1,1],
                  [1,1,1,0,1],
                  [1,1,1,1,1]],dtype=bool)

start = np.array([1,0,1,0,1,1,1,0,1,0,0,1,0,1,1,1,0,1,1,1,1,0])

M = np.zeros((np.sum(setup),np.sum(setup)+1),dtype=bool)
M[:,-1]=start

index = np.zeros(setup.shape,dtype=np.int64)
k=0
for (i,row) in enumerate(setup):
    for (j,col) in enumerate(row):
        index[i,j]=k*col
        k=k+col

for (i,row) in enumerate(setup):
    for (j,col) in enumerate(row):
        M[index[i,j],index[i,j]]=1
        if i>0:
            if setup[i-1,j]==1:
                M[index[i,j],index[i-1,j]]=1
        if j>0:
            if setup[i,j-1]==1:
                M[index[i,j],index[i,j-1]]=1
        if i<setup.shape[0]-1:
            if setup[i+1,j]==1:
                M[index[i,j],index[i+1,j]]=1
        if j<setup.shape[1]-1:
            if setup[i,j+1]==1:
                M[index[i,j],index[i,j+1]]=1

#Row reduce with np.logical_xor

for i,row in enumerate(M):
    #Find first row below i that has 1 in the ith position and swap it to the ith row
    t = i
    while M[t,i]==0:
        t=t+1
        if t==M.shape[0]:
            t=i
            break
    if t>i: #Swap row
        a = np.copy(M[t,:])
        M[t,:] = M[i,:]
        M[i,:] = a
    #Zero out the other rows
    t=0
    while True:
        if t==M.shape[0]: break
        if t==i:
            t=t+1
            continue
        if M[t,i]==0:
            t=t+1
            continue
        M[t,:] = np.logical_xor(M[t,:],M[i,:])
        t=t+1

Answer 2

Very often it is still possible to apply light chasing techniques to simplify the problem.

        A
      B   C
    D       E
  F   G   H   I
J   K       L   M
  N   O   P   Q
    R       S
      T   U
        V

In this case you could start at the corner A, and work your way diagonally down to the opposite corner V. On each diagonal row you do moves that solve the previous row.

• On the first row there is only one button, A, and you have a free choice on whether or not to press the button.
• On the second row you have a free choice for B, but (not) pressing C is forced by the state of light A.
• D and E are forced by the state of B, C.
• F, H are free choices; G, I forced.
• Row J, K, L, M forced.
• Row N, O, P, Q forced.
• Row R, S forced by the state of N, P, but if this does not also solve O, Q then you have to go back to one of the previous buttons where there was an apparently free choice, and press it. For example, if O was not solved, go back to press F, and work your way down again. If Q was not solved, press H and work your way down again.
• T, U are forced.
• V is forced by the state of T. If U and V are not also solved, again go back up to a previous free choice button (e.g. B) and press it.

It turns out in this case that A and B really are free choices and that U, V will automatically always be solved.

In general on other board shapes you want to find a light chasing order such that you have as few free choices as possible. This ensures that there are fewer occasions where you have to go back and try some other combination of those chosen button presses, and few of such combinations to try till you solve it. Basically you have reduced the problem to just a few buttons (A, B, F, H) with which you need to solve a few lights (O, Q, U, V).

I have written a Java program in which you can draw any graph and play Lights Out on that graph. It can also analyse the graph/board, and solve every possible solvable light pattern on it. You can find that program on my site here. Unless you are using a very old browser, you must download the program to run it, as no browsers still allow Java applets to run inside a web page.