In college, some of my favorite courses involved optimizations of graph algorithms. Since I've recently spent my spare time implementing chess with a friend, it was only natural for me to reduce the chess board to a graph. An interesting tangential question then arose – what graph algorithms could I apply here?

A common coding challenge in computer science courses is to write a script that finds knight's tours. A knight's tour is a sequence of chess moves that allows a knight to visit every square on the board exactly once. It's actually just a specific instance of the Hamiltonian path problem, which is itself reducible to the travelling salesperson problem. Luckily, unlike the NP-complete travelling salesperson problem, the knight's tour problem is solvable in linear time. Still, that doesn't mean my personal machine is powerful enough to compute all possible knight's tours. On a standard 8x8 chess board, there are 26,534,728,821,064 possible directed closed knight's tours!

Directed, you say? And what's closed? Okay yes, I introduced some jargon up there, so let's cover that vocabulary really quick:

  • Directed: A directed knight's tour is one where the knight's direction is part of the solution. That means that two tours that use the same path but travel in opposite directions are considered distinct solutions.
  • Undirected: An undirected knight's tour does not include direction as part of the solution. Because every directed knight's tour can always be traced in reverse, there are always half as many undirected tours as directed ones.
  • Closed: A closed knight's tour is one where the knight ends its tour on the same position that it started.
  • Open: An open knight's tour is one where the knight does not necessarily end its tour in the same position that it started.
  • Hamiltonian path problem: A problem to determine whether there exists a path through a graph that visits every vertex exactly once.
  • Travelling salesperson problem: An optimization problem to find the shortest and most efficient path that a salesperson can take in order to visit every single destination in a list exactly once.

This vocabulary is important, because each variant adds its own difficulty to the process of counting the number of knight's tours that are possible on a board. For example, even though we can count the number of closed knight's tours on the 8x8 chess board, the number of open knight's tours is still unknown (though estimated at 33 trillion)!

I was surprised to learn how big chess boards must be for knight's tours to even be possible. They're never possible for 1 x n or 2 x n boards, which makes sense, but they also don't exist on 3 x 3 or 4 x 4 boards either. According to an older source I found, open tours are only possible for boards with dimensions 3 x 4, 3 x n where n >= 7, and m x n where m >= 4, n >=5. Closed tours are even more constrained. They're only possible on boards with dimensions of 3 x n for n >= 10 (even) or m x n for m >= 5; n >= 6 (even).

The requirement for closed knight's tours that at least one of the board's sides be an even length was initially odd to me. But it didn't take long for me to figure out why this is necessary. In a board with odd dimensions, the total number of squares on the board is odd, which means that there are an unequal number of black and white tiles and that the knight must move an odd number of times to visit every position on the board. However, since a knight alternates between black and white tiles when it moves, an odd number of moves would have it end its tour on the wrong color. There'd be no way for it to end in the same position it started on.

So how exactly are knight's tours found? Well, there's the basic brute-force algorithm that's too slow to work on anything but the smallest boards, the divide-and-conquer algorithm that doesn't necessarily find all possible tours for a board, and Warnsdorff's rule. Warnsdorff's rule is unique because it's a heuristic, so it's not possible to prove that it even produces a valid knight's tour when used!

All this knight's tour research left me feeling intrigued. I decided to implement a naive brute-force algorithm of my own. Here's the recursive solution I managed in a handful of minutes:

def knight_move(total_rows, total_columns, position):
    """
    Calculate all places where a knight can move from its current position.
    """
    row, column = position
    movements = {
        (-1, -2),
        (-1, 2),
        (1, -2),
        (1, 2),
        (-2, -1),
        (-2, 1),
        (2, -1),
        (-2, 1),
    }
    return {
        (row + i, column + j)
        for i, j in movements
        if (0 <= row + i < total_rows)
        and (0 <= column + j < total_columns)
    }


def knight_tour(total_rows, total_columns, position, visited = None):
    """
    Calculate all tours a knight can complete from the starting position.
    """
    # Visit current position
    if visited is None: visited = []
    visited.append(position)
    next_positions = knight_move(total_rows, total_columns, position)

    # End condition: successfully visited the entire board
    if len(visited) == total_rows * total_columns:
        return [visited]

    # Recursive step
    solutions = []
    for next_position in next_positions: 
        if next_position not in visited:
            solution = knight_tour(
                total_rows, total_columns, next_position, visited[:]
            )
            if solution:
                solutions.extend(solution)
    
    return solutions
    
solution = knight_tour(3, 4, (0, 0))
print(solution)
Find all open knight's tours for a given board size and knight position.

The exercise was fun and reminded me of a silly tradition I do during December every year – Advent of Code. (That's a story for another day, but if you don't know what it is, definitely check it out!) Next up, I plan to code a few other knight's tour implementations to see how big of a chess board I can find tours on!

Primary References

Knight’s Tour Notes
How many knight’s tours are there?
The knight’s tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight’s move. Tours can be cycli...
The Number of Knight’s Tours Equals 33,439,123,484,294 &mdash; Counting with Binary Decision Diagrams | The Electronic Journal of Combinatorics