KnightTour

Challenge

On an arbitrary n×nn \times n chessboard, find a path that a knight can take to visit every square exactly once and return to the starting square.

Solution

KnightTour is a solver for the closed knight's tour problem: finding a path for the knight to touch every square on a chessboard exactly once and return back to start.

The knight's tour problem is a more specific version of the generalized problem of finding a Hamiltonian cycle in a graph. In simple terms, a Hamiltonian cycle is a path in a graph that touches every vertex exactly once and returns to the starting vertex. In general, the Hamiltonian path problem is an NP-complete problem, meaning that it currently cannot be solved in polynomial time.

However, KnightTour takes advantage of properties of the knight's movement along a chessboard, and is able to solve complete tours in polynomial time. KnightTour breaks up any board into a series of smaller and smaller boards, computes the knight's tour on each of these boards, and then merges the tours together.

I had the idea for this solution in my freshman year of college, when my algorithms teacher used this problem as an example to teach the concepts of backtracking and exponential runtime. I thought about the problem as she was explaning it and asked her if we could do it in linear time with a divide-conquer approach, but she said she did not know of any solution in polynomial time.

Unfortunately, I was not the first person to discover this solution, but it was still fun to figure out the underlying math and logic.
KnightTour on a 12 x 12 board by generating four 6 x 6 tours and merging them


Why this works

  1. We can solve tours relatively quickly for 6 by 6, 8 by 8, and 10 by 10 square boards, as well as 6 by 8, 8 by 10, and 10 by 12 rectangular boards.
  2. Any even-sized board length greater than or equal to 12 can be divided into some arrangement of smaller solvable boards. I wrote a proof for this here, although with a little bit of thinking you can easily come to this conclusion.
  3. As the knight has to move in an L-shape, there is a region between 4 completed tours that allows the knight to find a path from the top left board, to the top right, to the bottom right, to the bottom left, and back to the top left. This ensures that any 4 completed tours can be merged together be reorienting 4 edges of the graph.