The Knight’s Tour: Finding Some of its Solutions
F uelled by lockdown boredom and a certain Netflix show, I (like many others) have found myself enjoying the occasional game of chess. I may be terrible and I may blunder my pieces more often than not, but it has given me a fantastic way to put off that growing stack of Uni work. Procrastination aside, it has also inspired me to take another look at a well-known and well-loved classic puzzle: the Knight’s Tour.
The problem of the Knight’s Tour is quite simple; given an mxn chessboard and a starting position, can you move the knight around the board so that every square is visited and no square is visited twice? It’s a fairly managable problem on a small board, but as the size gets bigger it becomes a little more daunting to figure out what that path may be, especially if you don’t know if it’s even possible!
We can break down the problem of the Knight’s Tour into something more familiar for mathematicians. Imagine the chessboard as a graph with the squares as nodes and edges between nodes that are reachable within one knight’s move. We can imagine our knight moving between nodes that have an edge connecting them, and our problem becomes that of finding a path in our graph that visits every node exactly once. In other words, we find a Hamiltonian Cycle from our starting position.
