The Trapped Knight Revisited

12 min readMay 10, 2019

I was always intrigued by this video by Neil Sloane, called The Trapped Knight. You don’t have to see it before reading on, because I will explain it back from the beginning, but I do recommend watching it anyway. Mr. Sloane talks about this peculiar thing with a trademark passion. He’s definitely one of the “Feynmans” of number theory, although he doesn’t have the time to go very deep into this phenomenon.

I’ll take some time to analyse the situation a little deeper and try and come up with some new observations. You won’t need any advanced sort of knowledge about maths or computer science to follow this little adventure into numbers, patterns and visualisations.

The Trapped Knight

The “game” starts with the creation of a grid of numbers, stretching out to infinity.
The way it is put together is by starting with 1 from the center of the grid, and spiralling out ascending numbers, until you run out of ink — of course, the grid in the problem never really stops. Here’s a piece of the grid drawn in this fashion.

Once you have this grid, you place a knight chess piece on the center point, and start hopping according to the rules of chess. However, you don’t have it jump to just any point, you have it jump to the lowest value of all values that are not yet visited.

Eventually, the chess knight will get trapped, it has nowhere to go.
The strangest thing is, this only happens after 2015 steps!
What a seemingly large amount of steps before the knight gets trapped!
Here’s the entire path the knight has taken when it gets trapped. Also note the asymmetry of the path, which is mysteriously related to a subtle asymmetry in the grid’s spiral.

Ok, now that we have these denouements out of the way, let’s go deeper into the knight’s tale… For this, we need to model the problem.

The Grid

Actually, creating this grid is easy on a piece of paper but might challenge you a little on a computer. Try it out yourself before reading on!

Here’s my algorithm for the grid. While I was building it I realised there was a trick you can use.
I wanted to build a stateless function in (x, y), to allow getting a particular grid element’s value in O(1) time. This will definitely come in handy later, and also allows you to avoid ever storing the entire grid in memory, keeping things functional.

The way I built it, and the trick involved, is as follows:

For an element (x, y): determine which square of the spiral the point belongs to
For that square, get the value at the right-bottom point. A simple observation will show you these are the consecutive squares of odd natural numbers (1,9,25,49,…).
For x, y: determine if we are in the left, top, right, or bottom side of the square. From this, we can easily find how to retrace from the right-bottom point to get the value at (x, y).

It’s important to realise that the way this grid is built is ultimately what leads to the strange Collatz-sequence like nature. I already want to tell you I’m not able to dispel the mystery, and I don’t think it would be very easy to do so. Doing so would eventually unravel deep mysteries about prime numbers, I believe intuitively.
However, we can try, and in trying, discover a little more…

The Knight

Now that we have the grid, let’s start hopping around on it, according to the rules of the game.

We will actually allow any type of knight.
Let’s consider a standard chess knight to be represented by (1,2). This means the knight jumps one (1) step in one direction, and two (2) steps in the other direction.
Then, you can understand what a knight like (3,14) means, or (17,32). These knights do not exist in chess, but they do exist in our problem, to make it more interesting.

Note that a knight of the type (x,x) would behave like a type of bishop that can only jump so far, and a knight like (x,0) would behave like a rook in the same way. Let’s call these “abnormal” knights.
It’s easy to imagine these particular types of knights would never get trapped, and would just go on and on, so there’s no point in simulating their walks.

Here’s some code that simulates a “walk” of any type of knight. It is designed to stop at a certain amount of iterations, but as you will soon find out... all normal knights actually get trapped eventually. This in itself may or may not be remarkable to you. When I was writing this I was reminded of the Mandelbrot fractal, which is precisely about points that do not get trapped by an iterative loop, and keep escaping, so in a way it is remarkable that there are no such points in this problem.

Where move is a simple function that takes the next move according to the rules. You can download the Jupyter notebook at the end to play around yourself with this.

Walking the Knights

We can now simulate any walks, by any type of knight. This is what I did above for the standard (1,2) knight.

Here is a walk of a (12,11) knight, which is a knight that takes large hops of 12 and 11 squares. It takes a lot longer to get trapped, but it does get trapped eventually. Note how it almost seems to escape to the left top, but then changes its mind and goes back to eventually get trapped anyway. All knights share the same fate.

When I first saw this problem, my initial thought was: do all knights get trapped, and what knights are the slowest and what are fastest? So, it’s quite tempting to make a grid, that shows all the possible knight configurations, with a heat map for how long it takes for the knight to get trapped.

Here’s the code for this. Note that this part of the problem can easily be made to run in parallel — with PySpark for instance — , as each type of knight is a separate problem. Also note that I did not do a trivial optimisation where knight (2,3) and knight (4,6)… are equivalent. This would obfuscate the code, with little optimisation, although dealing with the knights as fractional numbers that way instead of as tuples gives interesting insights which I cannot go into today.
Also, it’s not entirely trivial why these knights act the same, so think about it!

I implore you to go deeper into the fractional aspect by the way, as you will discover more strange things about the knights that way.

Ok, so let’s draw the heat map.

This is pretty interesting if you look long enough. Just as a reminder, what you see here is all the possible knight configurations in (x,y) and the color indicates how long it takes for these knights to get trapped. The diagonals and verticals are the bishops and rooks — these never get trapped and so are the “hardest to trap” knights with the lightest color.
The problem is, the easily and non-easily trapped knights are very different, so there is a lot of action hidden in all of the blue goo.
Let’s normalise all the knights according to the rank they have in this little weird competition.

This is a little more revealing. As you can tell, as knights become more and more rook-like with larger strides, they tend to get trapped later in the game. The same sort of goes for when they become bishop-like, but it’s much less predictable. Actually there’s tons of chaotic elements in here. You can see diagonal lines of “easily trapped knights” where you would not expect them. You see strange blips of underperforming knights appear. They hide some strange mysteries about the numbers involved, some mysterious interplay related to prime numbers and integer division. Also if you keep staring at it you will eventually see little smiling devil faces.

Let’s look at the “easiest” and “hardest” to trap knights, to see if we can see any patterns there.

The “gray” points are the ‘easy’ to trap knights. You’ll see that these are all pretty “standard” knight ratios, including the standard chess (1,2) knight, which is one of the easiest to trap knights in the game.
The reason we see them appear in diagonals is obviously because their aforementioned equivalent brethren and sistren knights are also in the graph area.

You’ll notice that for the harder to trap knights, there’s a “curvy” nature to how they evolve in the area of more rook-like knights, as you go into more far-jumping knights. There’s a logarithmic function hidden there, but it also has a lot of chaos, with gaps. I can’t explore this further but it’s definitely an area of interest.

These are the six knights that get trapped the quickest:

(3,5): 1322 steps
(5,6): 1795 steps
(5,7): 1810 steps
(3,4): 1887 steps
(1,2): 2015 steps
(5,8): 2757 steps

Two observations here:

(1,2), our standard chess knight, is not the easiest to trap knight after all, there are four quicker ones!
There’s an eerie coincidence that (3,5) and (5,8) are consecutive Fibonacci numbers and both appear as quick knights. As you may know, the fraction of consecutive Fibonacci numbers converges to the golden mean. I will explore this further at the end.
Note that this list of fastest knights has four knights that jump 5 spaces.

These then are the five knights that get trapped the slowest (in the range of knights we investigate, which is up to (80,80):

(8,71): 2400005 steps
(6,61): 1444884 steps
(9,60): 1419454 steps
(4,67): 1303089 steps
(10,77): 1158431 steps

Wow, ok. Here are two observations for these:

None of the slowest knights are the ones close to being “rook-like” or “bishop-like”. The slow knights are actually found quite randomly.
2400005 is a super weird number to appear here. This knight is also a lot slower than all the others. You will see it in the non-normalised heat map as a bright yellow star (replicated 7 times due to symmetry). Just sit and contemplate that this particular knight needs over 2 million steps to eventually get trapped!

Because (8, 71) is our champion knight, it deserves to have its long journey drawn. Because this knight gets millions and millions of visits to get trapped, you can barely see the individual steps. It gets trapped at the point (-375, -696), eventually, after 2400005 visits to other areas.
This is, if you think about it, simply amazing, that it takes all this time to finally run out of options. A deep mystery links this final point, the numbers 8, 71 and the construction of the spiral.

To be frank it’s been a while since I have been surprised by anything as much as this particular knight configuration, and the way it is an outlier in all statistics.

A Different Starting Point

The behaviour of the knight changes dramatically if you let it start from a different place than the middle of the spiral.

This again creates an intriguing opportunity. What if we make a heat map of the grid, that says how long it takes the standard (1,2) knight to get trapped, if it starts from the corresponding position on the grid?

Here’s this heat map, for the standard (1,2) knight.

The “pattern” part of this is actually quite interesting, yet explainable, if you think about it. When you have the knight start at different positions close to the center, the resulting change is quite chaotic. However, when the knight starts in positions very far away from the center, the change to the path becomes a lot more predictable and even repetitive.
The reason for this is that the knight will simply climb down into a particular point where it starts jumping back to bigger points and embracing chaos again, like it does here when we start far away from the center:

So it’s logical that there’s a pattern to emerge here as the only thing that will change from one position to the other is the point it ends up in after climbing down.

Near to the center, it’s total chaos though. For instance, if the standard knight starts at position (4,1), it takes this extremely short path before being trapped.

Amazing, considering that with any other position the amount of steps is a lot higher.

With some analysis, we can now find the quickest knight + position combo there is. It appears that this is the one I have drawn above. In 262 steps, the standard chess knight gets trapped, if you start it from position (4,1) in the spiral, which corresponds to value “76”. This brings us full circle back to the chess knight, which reclaims its title as the fastest one to get trapped.

Odds and ends

A final observation comes from the original spiral. First, let’s draw the spiral, but color it according to whether the cell is even or odd.

Now, you may be aware that a standard chess knight always jumps from white to black square, back to white, … no matter what you do.

The same happens here obviously. However, for any knights that have jumps with the same parity— like (1,3) or (3,5) — the knight will stay on the same color square. So these knights will never visit even numbers. Note that this restricts their choices on the board, so you could falsely reason they would take shorter to get trapped. This may be the case for a knight like (3,5), which always sticks to odd squares, and gets trapped the quickest.

To end, let’s revisit the Golden Mean. If we take the following sequence of knights:

(3, 5)
(5, 8)
(8, 13)
(13, 21)
(21, 34)
(34, 55)
(55, 89)
(89, 144)
(144, 233)
(233, 377)
(377, 610)
(610, 987)
(987, 1597)

They are built from the Fibonacci sequence and so they converge towards jumping with the Golden Mean ratio. The interesting thing is that their walks gradually get harder to trap. This is one of the few examples where there seems to be real order and predictability. Here is the length of their walks mapped out (note the one long 1e7 spike is actually even bigger as this is the iteration max). Notice I almost found a predictive pattern, but then the last “Knight of Fibonacci” suddenly gets trapped in an easier fashion. Incredible, and a little frustrating.

The Fibonacci knights in general have beautiful walks, nearly symmetrical bird nests around the center; here is the (13,21) one to end. As you can see it avoids all even squares and sticks to the grey odd ones.

It finally gets trapped at the point (-16,52). Why there? I’m not sure if anybody knows.

Thanks for reading, have fun with the Jupyter notebook which you can download here: http://maartenmortier.be/knights/notebook.ipynb