Computer-Generated Patterns Inspired by a Game of Lights

Grigory Solomatov & Mark Meleka · January 2021 · ~15 min read

An in-depth walkthrough of how to solve the Game of Lights — turning a toy puzzle into linear algebra over finite fields, and the patterns its solutions make.

A large solution pattern rendered as a dense grid of multicoloured small squares in red, yellow, green, blue, and pink hues.

This is an in-depth explainer article on how to solve the “game of lights”.

Play the game
Browse the patterns
5-minute summary including spoilers, technical jargon, conjecture list
Linear systems over the binary field notebook (Python; CoLab)
Linear systems over the integers-modulo-p notebook (SageMath/Python; CoCalc)

Here is a sneak peek at some of our favourite patterns:

A large solution pattern rendered as a dense grid of teal, brown, and cream small squares.

A small solution pattern rendered as a grid of dark purple and lighter purple squares with a symmetrical design.

A large solution pattern rendered as a dense grid of red and black small squares with a symmetrical spiral-like design.

A black-and-white solution pattern rendered as a grid of black and white squares with a QR-code-like appearance.

A solution pattern rendered as coloured squares in teal, brown, and gold with a symmetrical design.

A 4x4 solution pattern rendered as coloured squares in varying shades of blue, from dark navy to pale, with two white cells forming a cross shape.

A black-and-white solution pattern for the lights puzzle rendered as a grid of black and white squares.

We pretentiously (and narcissistically) name these patterns Solomatov–Meleka Matrices to justify the dozens of human and computer hours we put into this project.

Explainer

Game Intro

Comic: one stick figure introduces the lights-on game to Grig, who hasn't heard of it, and invites them to help solve a brain teaser.

You are given a grid of lights starting in an “off” state and we want to turn them all “on”.

When you “toggle the switch” for a light, all of the adjacent lights switch their state: beside, above, and below, but not diagonal. For example, turning on the middle light and then turning it off again creates:

Three 3x3 grids of light bulbs showing: all lights off, then a cross-shaped group of five lights lit after pressing the centre, then all lights off again.

Here’s an example where we toggle the switch for the top left light, top middle, and top right lights, one after the other.

Four 3x3 grids of light bulbs showing a sequence of moves: starting all off, toggling the top-left column, then spreading lit cells, then reaching a nearly fully-lit state.

The goal is to go from a grid of all “off” lights to a grid of all “on” lights.

Here is a solution for the 2×2 grid:

Five 2x2 grids of light bulbs showing a four-step sequence toggling lights to turn on all four from an all-off start.

Comic: two stick figures exchange pleasantries — one says "Easy, right?" and the other replies "So far so good!"

Can you find the solution for a 3×3 grid? Take a few minutes and try it on your own. You can try virtually with this link: try it virtually

Comic: one stick figure warns "There's a spoiler below!" while the other asks "Who are you talking to?"

Here’s the solution:

Six 3x3 grids of light bulbs showing a five-step sequence of moves to turn on all nine lights from an all-off start.

Comic: one stick figure asks the other to confirm they understand each step of the matrix derivation; the other says "Yeah!" with an augmented matrix visible on the chalkboard.

Now that you’ve tried the 3×3 grid, consider trying the 4x4 grid, the 10x10 grid, 15x15 grid, and so on... The virtual game, linked here, makes it easy to try many grid sizes.

Do you notice any patterns?

Brainteaser: Can you find a reliable method to convert any size grid from all “off” to all “on”?

Comic: one stick figure proposes modelling the puzzle as a linear algebra problem; the other calls them a nerd, then admits they didn't do well in math class but agrees to walk through it together.

Many real-life problems can be modelled as math problems. Real-life problems can be hairy and complicated. If we can simplify the problem by adding assumptions it becomes much easier to find an analog in math with known solutions. Believe it or not, as our problem is currently stated, it already has an analog in math!

Comic: three panels — two stick figures discuss glasses in a confused exchange, then one approaches a chalkboard alone.

Binary Fields

We’re going to model our problem as a square of 0s and 1s. Then we’ll use fancy addition and multiplication to solve our lightbulb problem!

Comic: one stick figure explains the puzzle will be modelled as a linear system over the binary field; the other responds that doing fancy arithmetic on 0s and 1s makes sense.

If you already know what this means, feel free to skip ahead!

First, we’re going to create a new set of numbers. We will have 0 representing when the lightbulb is “off” and 1 representing when the lightbulb is “on”. No other numbers exist in our set, just 0 and 1.

In fancy math notation we might write: $S = {0, 1}$

In our set of numbers we’ll have fancy addition and multiplication. We can call these binary operators. It works the same as what you’re used to, but this time $1 + 1 = 0$ . We want this because when you toggle the switch for a lightbulb that’s already on, it turns off again.

For completeness, here are the addition and multiplication tables.

+	0	1
0	0	1
1	1	0

×	0	1
0	0	0
1	0	1

This structure is known as the:

Binary field
Finite field with two elements: $F_{2}$
Galois field with two elements: $F_{2}$
Integers modulo 2: $Z_{2}$

Comic: two stick figures at a chalkboard — one says "We'll just call it the binary field" and the other replies "Cool!" with the equivalence of the two notations shown.

Fields have some useful properties you’ve seen in grade school like:

Commutativity of addition

$a + b = b + a$

Distributivity of multiplication over addition

a · (b + c) = (a · b) + (a · c)

Comic: three panels explaining that the word "binary" has two meanings — two field elements and two operator arguments — with a chalkboard showing the binary field notation.

You can read more about binary fields on its Wikipedia page: Wikipedia page.

Linear Systems

We’ll introduce linear systems of equations (or simply “linear systems”) by example.

Comic: one stick figure explains that "binary" means two things in "binary field" vs "binary operator"; the listener confirms understanding.

You might remember the following kind of math problem from high school:

Problem: Two apples and three bananas cost 19 schmeckles in total, while three apples and five bananas cost 30 schmeckles in total. How many schmeckles does one apple cost and how many schmeckles does one banana cost?

Solution: Let “a” be the price of an apple and let “b” be the price of a banana. We can set up the following “inhomogeneous linear system of equations”:

E1 : 2a + 3 $b = 19$

E2 : 3a + 5 $b = 30$

If you need a reminder of how to solve these check out the Khan Academy lessons on systems of equations: Khan Academy: systems of equations.

You could also just use a system of equation solver: Wolfram Alpha solver.

The solution in this case is $a = 5$ and $b = 3$ .

To be more pretentious we can put our original equations in matrix form:

[2335] [a b] = [1930]

Since any variable name would work we can shorten it to the following “augmented matrix”:

[33551930]

We can now find the solutions with a fancy technique called Gaussian elimination. It works basically the same as what you learned in high school, but augmented matrices make it easier to read, input into a computer, and compute many operations efficiently, especially for very large matrices. All you need to know for now is that we can make these matrices and a computer can solve them for us.

If you want to satisfy your curiosity on Gaussian elimination, check out:

What’s really cool is that instead of using “normal” numbers (i.e. the “integers”) we can use the “binary field” that we made before! In fact, Gaussian elimination works with any field.

Linear Systems over the Binary Field

Let’s apply what we’ve learned to our lightbulb problem.

Remember our 2×2 grid of lightbulbs?

A 2x2 grid of light bulbs labelled 1 through 4 (left to right, top to bottom), showing the numbering scheme for a 2x2 lights puzzle.

We have 4 lightbulbs and we want to know which of the 4 to turn on so that the whole grid is turned on.

Let’s turn this into a linear system.

First, let’s number them to make them easier to reference.

We’ll call them lightbulb-1, lightbulb-2, and so on. To make it easier, we’ll call them l1,l2,l3, and l4. We’ll use the letter “i” to refer to any lightbulb, as in “li”.

We’ll say that li can take on a value of 1 if it gets toggled and 0 if the lightbulb does not get toggled. In fancy notation:

l_{i} = {10 if we toggle lightbulb number i if we don’t toggle lightbulb number i for i = 1, \dots, n .

Each lightbulb will have its own equation that describes all of the lightbulbs that turn on when this lightbulb is turned on. For example, turning on l1 results in l1,l2, and l3 being turned on.

A 2x2 grid with cells labelled 1, 2, 3 highlighted in yellow and cell 4 off, showing which lights are toggled when light 1 is pressed.

Let’s call this set N1 and say N $1 = {1, 2, 3}$ .

Our first equation will be called E1 and E1 will be: l1 + l2+ l3 = 1. Again, this is because when l1 is toggled on it has a value of 1 and this means that l1,l2, and l3 are turned on.

In fancy math notation:

E_{i} : j \in N_{i} \sum l_{j} = 1 for i = 1, \dots, n

For completeness, the sets Ni are:

N $1 = {1, 2, 3}$

N $2 = {1, 2, 4}$

N $3 = {1, 3, 4}$

N $4 = {2, 3, 4}$

And the equations Ei are:

E_{1} : E_{2} : E_{3} : E_{4} : l_{1} + l_{2} + l_{3} + l_{4} = 1 l_{1} + l_{2} + l_{3} + l_{4} = 1 l_{1} + l_{2} + l_{3} + l_{4} = 1 l_{1} + l_{2} + l_{3} + l_{4} = 1

In matrix form (writing out the coefficients of the variables):

1110110110110111 l_{1} l_{2} l_{3} l_{4} = 1111

And as an augmented matrix (shortened version of matrix form):

11101101101101111111

Again, the augmented matrix is our preferred form because it minimizes redundant information and is fastest to type into a computer.

Comic: two stick figures celebrate solving the puzzle — one says "I got it!", the other teases "Haha, nerd!", then proposes making it harder.

Try it on your own for the 3×3 grid. The solution is below and more detail is in Appendix A.

110100000111010000011001000100110100010111010001011001000100110000010111000001011111111111

Adjacency Matrices and Symmetry (bonus)

A 4x4 binary matrix shown alongside a 2x2 grid of light bulbs, illustrating the correspondence between the adjacency matrix and the puzzle grid.

This matrix is the adjacency matrix of our grid: it is possible to reconstruct our grid just by looking at the matrix. For example: since the entry in row 1 and column 3 is 1, we know that 1 and 3 are connected. Similarly, we can see that lightbulbs 2 and 3 are not connected since the entry at row 2 and column 3 is 0.

Notice that our matrix is “symmetric”: the value at row i, column j is the same as row j, column i.

A 4x4 binary matrix with a black diagonal line and red arrows indicating the off-diagonal symmetry of the adjacency matrix.

Grids to Graphs (bonus)

Our process is not limited to square grids! We could have used any graph with nodes and edges and modelled it as an adjacency matrix using the same steps described earlier.

Consider, for example, this graph:

A graph with four nodes labelled 1, 2, 3, 4, where node 1 connects to node 4 and node 2 connects to node 3, forming an X-shaped crossing.

With adjacency matrix:

11011110011010011111

Again, we can reconstruct our graph just by looking at this matrix. For example: since row 1, column 4 has a 1, we know there is an edge between lightbulb 1 and 4. Similarly, lightbulbs 3 and 4 are not connected since the entry at row 3, column 4 is 0.

Integers modulo a prime p

The same approach extends beyond the binary field.
Working modulo any prime p gives a field with the same useful properties.
Gaussian elimination works over all of them — exactly what the harder modes of the game rely on.

Solving Linear Systems Programmatically

We can use a computer program to solve our linear system of equations.

The steps for our computer program are as follows:

Create the augmented matrix for our toggle equations.
Solve the matrix using Gaussian Elimination.

Use operations appropriate for the binary field or the integers modulo p.
i.e. in the binary fiel $d, 1 + 1 = 0$ .

Reshape the solution into the shape of our original grid for readability.

This will give us the solution in a format where we can easily see which lightbulbs to toggle, and how many times to toggle them, to turn all the lightbulbs on.

We’ve provided a basic implementation for the binary field in a popular programming language, Python, so that you can play with it yourself! Check it out in the Google Colab link.

There’s a much more efficient implementation for solving systems of equations over finite fields in the computer algebra system named SageMath. Using that implementation you can solve much larger grids much faster. We provide an implementation in the CoCalc link.

We’d love your input and feedback- feel free to submit a pull request to our Github repo!

Computer-generated Patterns!

We choose the simple-to-program case where our game starts with a square grid of size n × n.

The solution matrix is therefore an n × n matrix of numbers ranging from 0 to p, where “p” is 2 for the “simple” version of the game, and “p” is a prime number greater than 2 for the “hard” version of the game.

We map the numbers to colours and plot the result. The maximum number of colours possible is smaller than the grid-length, “n”, and our modulo, “p”. The larger the grid size and modulo, the greater the dimension of the resulting pattern (and also the longer it takes to compute a solution!).

We find one solution, where it exists, for every square grid up to size 70×70 and for every prime modulus up to 69. We apply 75 different colour maps to every one of those solutions to find the coolest patterns. This represents about 100,000 combinations (75 colour maps × 70 grids × 19 primes)! This took a few days of continuous computation using several cloud CPUs.

Most solutions we found are symmetrical along the horizontal center line, the vertical center line, a diagonal center line, or all of the above. Most of the solutions exhibit interesting patterns but the ones we particularly enjoyed were the anthropomorphic ones (some semblance of eyes and a mouth) and the ones with a high colour contrast that emphasized a shape in the center.

Here are some neat patterns, in descending order by grid size and modulo:

A large solution pattern rendered as a dense grid of multicoloured small squares in pink, purple, yellow, and blue hues.

A large solution pattern rendered as a dense grid of red, blue, and white small squares with a symmetrical design.

A large solution pattern rendered as a dense grid of teal, brown, gold, and white squares with a symmetrical kaleidoscopic design.

A solution pattern rendered as coloured squares in pink, purple, and white with a symmetrical concentric design.

Symmetric:

A large solution pattern rendered as a dense grid of multicoloured small squares in red, blue, yellow, green, and other hues.

Crosses:

A large solution pattern rendered as a dense grid of purple and lavender small squares with a symmetrical kaleidoscopic design.

A large solution pattern rendered as a dense grid of grey and white small squares with a symmetrical kaleidoscopic design.

A large solution pattern rendered as a dense grid of purple and pale blue small squares with a symmetrical kaleidoscopic design.

Cool:

A large solution pattern rendered as a dense grid of dark red and black small squares with a symmetrical kaleidoscopic design.

A 4x4 grid solution pattern with dark teal, brown, and white cells showing which lights to toggle.

Mo $d = 5$ ; Grid-lengt $h = 5$

A 4x4 solution pattern rendered as large coloured squares in red, yellow-green, teal, and dark navy.

A solution pattern rendered as coloured squares in pink, gold, olive green, and dark navy with a cross-like motif.

Mo $d = 5$ ; Grid-lengt $h = 15$

A large solution pattern rendered as a dense grid of blue, red, and white squares with a symmetrical kaleidoscopic design.

A solution pattern rendered as coloured squares in pastel yellow, green, pink, teal, and lavender with a symmetrical design.

Mo $d = 29$ ; Grid-lengt $h = 57$

A solution pattern rendered as coloured squares in blue, purple, pink, and yellow with a symmetrical design.

A large solution pattern rendered as a dense grid of multicoloured small squares in a rainbow palette with a symmetrical design.

A large solution pattern rendered as a dense grid of multicoloured small squares in many hues with a symmetrical kaleidoscopic design.

A large solution pattern rendered as a dense grid of orange, blue, and green small squares.

Diagonal symmetry:

A large solution pattern rendered as a dense grid of green and blue small squares with a symmetrical kaleidoscopic design.

A large solution pattern rendered as a dense grid of green, blue, and white small squares with a QR-code-like appearance.

A large solution pattern rendered as a dense grid of multicoloured small squares including orange, pink, navy, green, and yellow hues.

A small solution pattern rendered as coloured squares in orange, purple, yellow-green, blue, and black with a mod-like design.

A large solution pattern rendered as a dense grid of red, white, and blue small squares.

Anthropomorphic:

A solution pattern rendered as a grid of grey-green and dark grey squares with a QR-code-like appearance.

A 4x4 solution pattern rendered as coloured squares in blue-grey, purple, and dark purple with a cross-like motif.

A large solution pattern rendered as a dense grid of pink, purple, and white small squares.

Unsymmetric:

A 5x5 solution pattern rendered as coloured squares in purple, lavender, and white with a concentric diamond motif.

A large solution pattern rendered as a dense grid of brown and purple small squares.

Solution pattern for the lights puzzle rendered as a grid of green, black, and white coloured squares with a QR-code-like appearance.

A large solution pattern rendered as a dense grid of green, purple, and white small squares.

We pretentiously (and narcissistically) name these patterns Solomatov–Meleka Matrices to justify the dozens of human and computer hours we put into this project.

You can find more patterns here.

Conjecture: There are infinitely many Solomatov–Meleka Matrices. This follows from the fact that there are infinitely many integers to use as our grid length, n, and the fact that there are infinitely many primes, p, to use as moduli. We have no reason to believe that solutions stop existing at a large enough grid size or modulus but have not tried to prove it yet.

Appendix A: Linear Systems over the Binary Field 3×3 solution

Remember our 3×3 grid of lightbulbs?

A 3x3 grid of light bulbs, all off, representing the starting state of the lights puzzle.

We have 9 lightbulbs and we want to know which of the 9 to turn on so that the whole grid is turned on.

Let’s turn this into a linear system.

First, let’s number them to make them easier to reference.

A 3x3 grid of light bulbs labelled 1 through 9, showing the numbering scheme for a 3x3 lights puzzle.

We’ll call them lightbulb-1, lightbulb-2, and so on. To make it easier, we’ll call them l1,l2,...,l9. We’ll use the letter “i” to refer to any lightbulb, as in “li”.

We’ll say that li can take on a value of 1 if it gets toggled and 0 if the lightbulb does not get toggled. In fancy notation:

l_{i} = {10 if we toggle lightbulb number i if we don’t toggle lightbulb number i for i = 1, \dots, n .

Each lightbulb will have its own equation that describes which lightbulbs turn on when this lightbulb is turned on. For example, turning on l1 results in l1,l2 and l4 being turned on.

A 3x3 numbered grid with cells 1 and 4 highlighted in yellow, showing which lights are toggled when light 1 is pressed in a 3x3 puzzle.

Let’s call this set N1 and say N $1 = {1, 2, 4}$ .

Our first equation will be called E1 and E1 will be: $1 = l$ 1 + l2+ l4. Again, this is because when l1 is toggled on it has a value of 1 and this means that l1,l2 and l4 are turned on.

In fancy math notation:

E_{i} : j \in N_{i} \sum l_{j} = 1 for i = 1, \dots, n

For completeness, the sets Ni are:

N $1 = {1, 2, 4}$

N $2 = {1, 2, 3, 5}$

N $3 = {2, 3, 6}$

N $4 = {1, 4, 5, 7}$

N $5 = {2, 4, 5, 6, 7}$

N $6 = {3, 5, 6, 9}$

N $7 = {4, 7, 8}$

N $8 = {5, 7, 8, 9}$

N $9 = {6, 8, 9}$

And the equations Ei are:

E_{1} : E_{2} : E_{3} : E_{4} : E_{5} : E_{6} : E_{7} : E_{8} : E_{9} : l_{1} + l_{2} + l_{3} + l_{4} + l_{5} + l_{6} + l_{7} + l_{8} + l_{9} = 1 l_{1} + l_{2} + l_{3} + l_{4} + l_{5} + l_{6} + l_{7} + l_{8} + l_{9} = 1 l_{1} + l_{2} + l_{3} + l_{4} + l_{5} + l_{6} + l_{7} + l_{8} + l_{9} = 1 l_{1} + l_{2} + l_{3} + l_{4} + l_{5} + l_{6} + l_{7} + l_{8} + l_{9} = 1 l_{1} + l_{2} + l_{3} + l_{4} + l_{5} + l_{6} + l_{7} + l_{8} + l_{9} = 1 l_{1} + l_{2} + l_{3} + l_{4} + l_{5} + l_{6} + l_{7} + l_{8} + l_{9} = 1 l_{1} + l_{2} + l_{3} + l_{4} + l_{5} + l_{6} + l_{7} + l_{8} + l_{9} = 1 l_{1} + l_{2} + l_{3} + l_{4} + l_{5} + l_{6} + l_{7} + l_{8} + l_{9} = 1 l_{1} + l_{2} + l_{3} + l_{4} + l_{5} + l_{6} + l_{7} + l_{8} + l_{9} = 1

In matrix form:

110100000111010000011001000100110100010111010001011001000100110000010111000001011 l_{1} l_{2} l_{3} l_{4} l_{5} l_{6} l_{7} l_{8} l_{9} = 111111111

And as an augmented matrix:

110100000111010000011001000100110100010111010001011001000100110000010111000001011111111111

Bugs, observations, conjectures, and theorems to [email protected].