The Red & Black Knights

Intro

In this notebook, we will explore the red & black knights problem. It’s a fascinating cellular-automata-style problem that involves placing knights on a chessboard with spiral numbering in such a way that no two knights threaten each other.1

1 A cellular-automata-style problem refers to a system, visual aesthetic, or algorithm that uses simple, local rules across a grid to create complex, large-scale patterns. Instead of top-down design, the overall image or behavior emerges organically from the bottom up. The concept originates from computer science and mathematics, but has heavily influenced generative art, physics, and game design. Perhaps the most famous example is Conway’s Game of Life, where simple rules about cell survival and reproduction lead to intricate patterns and behaviors.

To understand the problem, first imagine an infinite chessboard numbered sequentially in a square spiral starting from the center (0, 1, 2, 3…). Now the rules are as follows:

  1. The pieces take turns being placed, moving sequentially along the spiral numbers. The Black knight goes first, followed by the Red knight, and they alternate turns.
  2. Knights of the same color are friendly and do not mind if they are within a knight’s move of one another.
  3. However, knights of opposite colors are hostile. A Black knight cannot be placed on any square that is under attack by a Red knight, and vice versa.
  4. On Black’s turn, a Black knight is placed on the lowest available spiral number that is not attacked by a Red knight. On Red’s turn, it places a Red knight on the lowest available number not attacked by a Black knight.

To see this problem in action, watch this video by Numberphilke: Red & Black Knights (extraordinary result).

We will solve this problem by simulating and visualizing the two knights’ placement on the spiral grid (just like in the video).

Simulation

To aid the simulation, we first define two helper functions that maps the spiral index to its corresponding (x, y) coordinates and vice versa. This will allow us to easily determine the positions of the knights on the grid and check for attacks. See a dicussion here about the mappings.

We also define a dataclass to represent the state of each knight, which will help us keep track of their current positions and the squares they have occupied and are attacking.

We further define two helper functions: one to get the squares attacked by a knight at a given position, and another to perform a turn for the current player.

Finally, we initialize the knights and simulate the game for a specified number of steps, alternating turns between the Black and Red knights.

Visualization

Now we visualize the placement of the knights on the spiral grid. We create a scatter plot where each knight’s position is marked with a different color (i.e., black for the Black knight and red for the Red knight).

Explore the resulting plot with different numbers of steps. For te first 1,000 squares, the board looks a bit chaotic and mixed, with unpredictable clusters of red and black dots everywhere. As we increase the number of steps to about 10,000, we start to see more distinct patterns emerging, with larger clusters of red and black dots forming. What pattern will emerge when you simulate for 100,000 steps?

Exercises

  1. When you simulate for 100,000 steps, what pattern emerges? Describe the pattern and any interesting observations you have about it.
  2. When simulating for 100,000 steps, the simulation runs very slowly (about 1 to 2 minutes). Can you optimize the code to run faster?
  3. Try the one-knight version of the probem where only one knight is placed on the board, and it cannot be placed on any square that is under attack by itself. What pattern emerges in this case? How does it compare to the two-knights version? (See again the Numberphile video: Red & Black Knights (extraordinary result).)
  4. Try three or more knights. Try other chess pieces. See this bonus video by Numberphile for inspirations: Amazing Chessboard Patterns (extra) - Numberphile

References