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.

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.