I first came across the knight’s tour problem in the early ’80s when a performer on the BBC’s The Paul Daniels Magic Show demonstrated that he could find a route for a knight to visit every square on the chess board, once and only once, from a random start point chosen by the audience. Of course, the act was mostly showmanship, but it was a few years before I realized that he had simply memorized a closed (or reentrant) tour (one that ended back where he started), so whatever the audience chose, he could continue the same sequence from that point.

In college a few years later, I spent some hours trying, and failing, to find any knight’s tour, using pencil and paper in various systematic and haphazard ways. And for no particular reason, this memory came to me while I was driving to work today, along with the realization that the problem can be reduced to finding a Hamiltonian cycle—a closed path that visits every vertex—of the graph of possible knight moves. Something that is easy to do in Mathematica. Here is how.

The first thing that we have to do is construct the graph of knight moves. A knight can move to eight possible squares in the open, but as few as two in the corners. But if you ignore that and think of when you were taught chess, you were probably told that a knight could move along two and across one, or vice versa. This gives the knight the property that it always moves a EuclideanDistance of √5. We can use this test to construct the edges of our graph from the list of all possible pairs of positions.

Sorting removes unhelpful multiple edges that just slow the computation down. Ignoring chess conventions, I choose x and y to both take values 1–8 (rather than x being from A to H).

Now that we have the graph, we can find a tour.

Which looks very nice visualized on a chess board.

I understand that this problem is often used as an exercise in computer science courses, and you can find some iterative solutions and specific solutions at demonstrations.wolfram.com. But at four lines, this graph theory solution isn’t too much of a challenge. Indeed, it seemed a little unsatisfying to stop here.

Giving FindHamiltonianCycle a second argument finds more than one tour. But scrolling through a notebook of the first 1,000 didn’t reveal anything interesting. And the properties of differently sized chess boards have been well studied. So I decided to extend the idea in a slightly more whimsical way.

Oddly, all the definitions of a knight’s tour that I found on the web assume a rectangular space. Indeed, Mathematica contains a built-in function KnightTourGraph, which does roughly the same as my knightGraph function, but assumes a rectangular grid. But if I bring in Mathematica‘s image processing, it is easy to generate the knight’s tour graph over points in non-rectangular shapes, like this:

First I Binarize the pixels of some source image. The knight is allowed to visit the black pixels in the result, but not the white. Then I get the coordinates of the black pixels and map them to the coordinate space of my plotting function.

Now I just solve and plot that graph as before, but this time visualize with the black pixels, instead of a chess-board grid.

It turns out that most irregular shapes do not have a closed knight’s tour, but messing around with the image size can find exceptions. So a bit of search code is needed. This one takes a single character, rasterizes it at different font sizes, and returns the size for which a tour exists. The Monitor part lets you watch the progress; tour finding scales poorly and can get very slow if you let the font sizes grow too big.

Let’s start by searching simple filled circles.

So out of the 42 sizes tested, only these 5 have solutions. The smaller, more crowded font sizes produce more irregular tour paths.

But larger image sizes make the shape more recognizable.

Playing around with other characters is amusing for a while. Here is the letter “o” in 34 point:

An asterisk at 52 point:

And since chess puts us firmly in the “games” space, here are some playing card suits:

And finally my rendition of Pacman:

Feel free to share any interesting discoveries in the comments section.

Download this post as a Computable Document Format (CDF) file.