I've been playing a lot of chess lately. But I'm pretty bad. I don't have the patience to memorize openings nor the care to learn endgame theory. So I end up doing middle-game puzzles. And I love those, mainly because the knight, my favorite piece, is the most fun in the middle-game. Knights are tricky and trappy, and how can't you love them? But often, when I see my knight on one square and I want to move it to some other square, it takes a couple of seconds to calculate the optimal route for it to take.
An obvious way to find the quickest path from one square to another is to just try all paths (in a breadth-first search). We can see, for example, that a knight needs at most 4 moves starting from the center of an empty board to reach any other square.
We can do this on larger boards, too. We might wonder how long it takes to reach any square from any other square on some \(n \times n\) board. For example, it takes 22 moves to get from one corner of a \(32 \times 32\) board to the opposite corner.
This question can be answered pretty easily with some code (or by analyzing diameters of knight graphs); see OEIS sequence A232007. Instead, I'm interested in colorings of these graphs. Namely, the heat maps of these graphs, where a tile is colored based on the minimum number of moves it takes to reach it.
Above is a heat map of a knight on an \(8 \times 8\) board. The pattern is cool, but I think we can go bigger. Of course, we can increase the board size, but more dramatically we can consider different chess pieces. If you think about how other pieces would work for a couple of seconds, though, you realize that they're actually not that interesting. A queen, for example, can get to any other square in just two moves. In particular, we want pieces with fixed movement distance (compared the the queen, bishop, and rook, who all have unlimited movement in certain directions). In the wonderful world of fairy chess, these pieces are called leapers. We can denote a leaper as a \((n, m)\)-leaper, which can move \(n\) squares in one direction and \(m\) in another. So a vanilla knight is a \((1, 2)\)-leaper (or identically, a \((2, 1)\)-leaper).
Moving the sliders below, you can change the value of \(n\) and \(m\) and the number of colors used on a \(65 \times 65\) board.
We can notice immediately that when gcd\((n, m) > 1\) or \(n\) and \(m\) are both odd, there are gaps, which makes sense. The most interesting patterns come from when \(n\) and \(m\) are coprime and not both odd. Some of my favorites on 10 colors are \((4, 11)\), \((14, 11)\), \((20, 7)\), \((1,20)\) and \((7, 4)\).
One quick note about the visualization above: for optimization purposes, I prevent the knight from going off the board. As we'll see later, we really care about what happens on an infinite board. Note that on, for example, \((1, 20)\) we get gaps in the board (seen more easily with the 'pastel' color pallet). These gaps wouldn't exist on an infinite board, as we'll see, and is important to keep in mind if referring back to this visual.
Now we have a sense of the tool we're working with — the trail of a leaper. The visualizations are just mesmerizing (at least I think so), but also seemingly unpredictable. Well, it's obvious what a \((0, 1)\)-leaper and a \((1, 1)\)-leaper will do, and it makes sense in retrospect that a \((1, 2)\)-leaper's pattern converges to an octagon (by the 8-fold symmetry of its moves), but why does, say a \((5, 6)\)-leaper not converge to an octagonal shape. Or does it, but only on a larger board? Here are some questions to explore in later parts.
This is the first part in an exploration of these pretty tilings. I don't know if there already exists anything about these patterns (I couldn't find anything online, but it's also not easy to look up). So if anyone is reading this and knows anything about leaper patterns, please email me!