Computer-Generated Patterns: a Game and Solution

Come for the pretty patterns; stay for the math.

In this post:

• We share a simple game of lights.
  [Reading time: 2 minutes]
  Play the game here.

• We model the game mathematically and solve it programmatically.
  [2 minutes]
  Linear systems over the binary field notebook (Python; CoLab)
  Linear systems over the integers-modulo-p notebook (SageMath/Python; CoCalc)

• We present very cool computer-generated patterns that represent solutions to the game!
  [3 minutes]
  Pattern repository here.

• For the average reader: We link to an in-depth explanation. Satisfy your curiosity and impress your friends!
  In-depth explainer here.

• For the math enthusiast: We share relevant observations, questions, conjectures, and theorems. We welcome your contributions!
  [5+ minutes]
  Scroll down to the bottom!

Here is a sneak peak at some of our favourite patterns (skip half-way through the post to see more):

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

---

A game of lights

Game

You are provided a grid of lights. When you toggle the switch for a light all of the adjacent lights rotate their state (this includes the lights beside, above, and below, but not diagonal). The goal is to go from a grid of all “off” lights (not yellow) to all "on" (yellow).

In the “simple” version of the game there are two states: “off”/not-yellow and “on”/yellow.

In the “hard” version of the game there are “p” states where p is a prime number. All lights begin in an “off” state and with each toggle they move to the next state. After “p” toggles, they are off again. The first state after “off” is “on”/yellow and each state in-between is something else. The higher the prime, p, the harder the difficulty.

It's easiest to understand if you open the game link and toggle some squares in “classic” and “hard” mode.

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

Solution

We can model this problem as a system of linear equations over the integers modulo p where p is a prime number. The simple version of the game is modelled using the integers modulo 2: also known as the binary field. The “hard” version of the game is modelled by the integers modulo p with p greater than 2.

Each equation in our system represents the lights that switch state when a specific lightbulb is toggled. We can solve the system using Gaussian elimination and re-shape the solution into the same shape as our original matrix. This new matrix represents the “lights” that you’d have to toggle, and the number of times that you’d have to toggle them, to go from a grid of all “off” lights to all “on”.

Zoom in to see better on mobile or visit the in-depth explainer!

A detailed explanation is in our in-depth explainer article, here.

This method will find a solution, if it exists, for any grid.

Note: this solution will also work for any graph with nodes and edges; not just square grids.

Solomatov-Meleka Matrices

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

The solution matrix is therefore an n x 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.

We could map any colors we want to 1 and 0.

The maximum number of colors 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 70x70 and for every prime modulo up to 69. We apply 75 different color maps to every one of those solutions to find the coolest patterns. This represents about 100,000 combinations: 75 colour maps * 70 grids * 19 prime numbers! 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 color contrast that emphasized a shape in the center.

Here are some neat patterns:

Symmetric:

Crosses:

Cool:

Modulo=5; Grid-length=5:

Modulo=5; Grid-length=15:

Modulo=29; Grid-length=57:

Diagonal symmetry:

Anthropomorphic:

Unsymmetric:

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 a modulo. We have no reason to believe that solutions stop existing at a large enough grid size or modulo but have not tried to prove it yet.

---

In-depth Explainer

Can you solve the whiteboard equation from the top comic?

If you want to learn more and have taken some high school math, check out our in-depth explainer, linked here.

Sections include:

1. Game introduction

2. Binary fields

3. Linear systems

4. Linear systems over the binary field
   Adjacency matrices and symmetry (bonus)
   Grids to graphs (bonus)

5. Integers modulo p-prime

6. Solving linear systems programmatically

---

Observations, Questions, Conjectures, and Theorems (bonus)

[Reading time: 5+ minutes]

For the math enthusiasts!

My favourite quote from my favourite math professor.

Consider the following and feel free to send in your own observations, questions, conjectures, and theorems. If they’re interesting we’ll post or link them here and give you credit!

Observations

Observation 1

This game can be modelled as a system of linear equations over the integers modulo p.

Observation 2

We aren’t limited to modelling grids: we can model any graph with edges and vertices.

Questions to be turned into conjectures or theorems

Question 1

Is there a solution to every size square grid in the two-state version of the problem? (“lights-off” -> “lights-on” -> “lights-off”)

• What about any size grid, not just squares?

• What about any graph?

Question 2

Is there a solution to every size square grid in the version of the problem where the lights rotate through p-prime states? (example for p-prime = 5: [“off” -> yellow -> red -> blue -> green -> “off”])

• If there isn’t always a solution, for which p-primes is there not always a solution? For which grid sizes?

• What about any size grid, not just squares?

• What about any graph?

Question 3

Can you find an algorithm that finds all solutions to a given grid size and number of lights?

Note: the provided program only finds one solution.

Question 4

For which grid sizes is the solution unique? For which is it symmetrical?

• Does symmetrical imply unique?

• Are there infinitely many unique/symmetrical solutions?

Potentially useful linear algebra theorems

[Source: theorem_sheet.pdf; author unknown]

Theorem 1.1: Uniqueness of Reduced Echelon Form

Each matrix is row equivalent to one and only one reduced echelon matrix.

Theorem 1.2: Existence and Uniqueness Theorem

A linear system is consistent if and only if the rightmost column of the augmented matrix is not a pivot column – that is, if and only if an echelon form of the augmented matrix has no row of the form:

If a linear system is consistent, then the solution set contains either
(i) a unique solution, when there are no free variables, or
(ii) infinitely many solutions, when there is at least one free variable.

Theorem 1.3

If A is an m × n matrix, with columns a₁, a₂, . . . , aₙ, and if b is in Rᵐ, the matrix equation

has the same solution set as the vector equation

which, in turn, has the same solution set as the system of linear equations whose augmented matrix is

Theorem 1.4

Let A be an m × n matrix. Then the following statements are logically equivalent. That is, for a particular A, either they are all true statements or they are all false.

a. For each b in Rᵐ, the equation Ax = b has a solution.
b. Each b in Rᵐ is a linear combination of the columns of A.
c. The columns of A span Rᵐ.
d. A has a pivot position in every row.

Theorem 1.5

If A is an m × n matrix, u and v are vectors in Rᵐ, and c is a scalar, then:

Reader-contributed theorems

Be the first contributor!