Combinatorics – How to Prove Whether a Grid Puzzle is Solvable or Unsolvable

combinatoricsgraph theorypuzzle

[Disclaimer: I have researched a bit before this post and I have found no other questions that address my problem specifically, hence this post]

So I have been made a puzzle concept in a python program of mine, you have a 4 x 4 grid of lights, all of which are off at the start of the puzzle, your goal is to turn all the lights on.

The positions of the grid of lights is as follows:

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

The way you change the state of the lights is that you click the lights in the grid, each individual light affects a fixed set of lights in the grid unique to that individual light only. To clarify with an example: Imagine I click the first light in the grid, and it inverts the state of the lights at positions 1, 5, 8 and 10, and on clicking the light at position 2 of the grid it inverts the state of the lights at positions 2, 7, 9 in the grid.
(From now on, I will be calling this as "mapping", for example: the mapping of light 2 is to lights 2, 7, 9)

If you know of the game LightsOut, its like that except the lights inverted are spread across according to a formula I used, instead of being the neighbors of the light clicked.

(if you are confused still and need clarification, refer to the pictures I have linked at the end of this question, I hope that will resolve any queries, if any topic is unclear then I will edit this post to explain in a better way)

So now moving on to the question I have:

I have a certain mapping for the lights which is as follows:

Light 1  inverts lights 1, 5, 8, 11, 14

Light 2  inverts lights 7, 10, 13, 16

Light 3  inverts lights 2, 9, 12, 15

Light 4  inverts lights 1, 4, 5, 11, 14

Light 5  inverts lights 3, 7, 13, 16

Light 6  inverts lights 2 , 5, 9, 15

Light 7  inverts lights 1, 4, 7, 8, 11

Light 8  inverts lights 3, 6, 10, 13 

Light 9  inverts lights 5, 8, 12, 15

Light 10 inverts lights 1, ,7, 10, 11, 14

Light 11 inverts lights 3, 9, 13, 16 

Light 12 inverts lights 2, 5, 11, 15

Light 13 inverts lights 1, 4, 7, 13, 14

Light 14 inverts lights 3, 6, 9, 16

Light 15 inverts lights 2, 5, 8, 11

Light 16 inverts lights 1, 4, 7, 10, 13

Using this mapping I have been trying to solve from a state where all lights are off to where all lights are on for TENS of hours, I have made literally 83 algorithms to help in some cases, but I am unable to turn all of them on.

However when I made the 9th element 1 and the rest as 0, essentially modified the starting grid configuration, I was able to solve it using my algorithms.

SO FINALLY, my questions are:

1) Is it possible to solve this grid with the given mapping?

2) I want to know a proper method I can use to prove whether the puzzle is solvable with a given mapping, a general method I can apply to any mapping

3) The way I generate a mapping is very simple, mainly addition of one number to a list of numbers, and its definitely not the standard, if you are aware of a better way to reliably generate mappings, that is used in professional games/ professional settings, please let me know, I realize that this may be considered more of a puzzle/ CS question, but if you know a way, please let me know, however the main answers I want are for Question 1 and 2

Here are the pictures for better understanding, however I have changed the lights in the program to be represented by 1s and 0s for more compatibility in mathematical understanding, 0 indicates off, and 1 indicates on:

Initial Grid Set-up

The grid when the first light is clicked (inverts lights at position 1, 5, 8, 11, 14)

The grid when the second light is clicked (inverts lights at position 7, 10, 13, 16)

End Goal configuration of grid

Best Answer

First, put your rules into a matrix:

enter image description here

Then, you can do something called "row reduction" modulo 2. This involves adding copies of some rows to other rows (where $1+1=0$) and possibly switching some rows around. A set of rules will be solvable from any initial state exactly when the row reduced matrix has a single 1 in each row and column. If we row reduce the above matrix we get:

enter image description here

We can see that there are states from which the game is not solvable. In fact, because there are three rows of zeroes, there are three conditions any game state that can reach the lights out position must satisfy.

You can get these equations by calculating the null space of the matrix, which is given by the three rows of this matrix:

enter image description here

If we let $L_i$ be $1$ if it is on and $0$ if it is off, then, unpacking the first row, we see that $L_4+L_7+L_8+L_9+L_{11}+L_{15}+L_{16} \mod 2$ does not change under any of your above moves. This means that you can never go between the state of no lights turned on to the state of say, just $L_4$ turned on, or indeed any odd combination of $L_4,L_7,L_8,L_9,L_{11},L_{16}.$

In particular, to answer your question of whether you can go from the all lights on state to the all lights off state, since $L_4+L_7+L_8+L_9+L_{11}+L_{15}+L_{16}$ evaluates to $7=1\mod 2$ for all lights on, this is impossible.

The other two rows of the null space matrix give two other sums of lights that don't change (up to parity) under your moves.

Interestingly, if you look at the row reduced matrix, the $1$ in the upper left has only zeroes in its row. That means that you can toggle the first light in any game position using a combination of the legal moves.

Related Question