Title: Use Warnsdorf's rule to find a closed knight's tour in Python

[Warnsdorf's rule lets you find a closed knight's tour on a 100x100 board almost instantly!]

A knight's tour is a path that a knight can follow on a chessboard to visit every square without visiting any square twice. A closed knight's tour is a tour that returns to its starting point.

My post Find a closed knight's tour in Python shows how to find a closed knight's tour in Python. Unfortunately, that method examines every possible tour until it finds one that works. The number of possible tours is mind-bogglingly huge so that can take a while for chessboards of even moderate size. For example, when I tried to find a closed tour on an 8×8 chessboard, I got bored after half an hour and gave the program the old Ctrl+C salute.

Way back in 1823, H. C. von Warnsdorf described a heuristic now called Warnsdorf's rule that often finds tours extremely quickly even in large chessboards. The picture at the top of this post shows a closed knight's tour on a 100×100 square chessboard and, if you look at the bottom of the picture, you'll see that the program took about 0.0657 seconds to find the tour! The program takes 3 or 4 seconds to display the tour because it needs to do a lot of drawing, but finding the tour is almost supernaturally fast.

Warnsdorf's Rule

Because it was 1823, Warnsdorf didn't have a computer so he was trying to find knight's tours by hand. That meant he needed a rule that was effective and reasonably easy to follow. Here it is.

Recursively search for a tour as usual. When you have a choice of multiple moves, start with the one that leads to the fewest possible moves in the next step.

For example, suppose you're at a point on a tour where you can make two moves A and B. If you take move A, there will be 4 possible moves. If you take move B, there will be only 2 possible moves. In that case, you should try move B first.

It turns out that this rule is so successful that it lets you find tours in boards up to 76×76 with no backtracking! The rule doesn't work perfectly on a 77&time77 board so the program must examine a lot more possible tours. While trying to find a tour on the 77×77 board, I got bored and invoked the mighty Ctrl+C.

Python Code

The code that implements Warnsdorf's rule is in the move_to function. It's similar to the code used by the previous example except it sorts possible moves by the number of moves available in the next step before it explores them.

Here's that method with the main differences highlighted in blue.

def move_to(num_squares, num_rows, num_cols, row, col, moves, move_number, use_closed_path, use_warnsdorf): ''' Move the knight to position [row][col]. Then recursively try to make other moves. Return true if we find a valid solution. Return a success code and the number of attempts. ''' # Build a list of legal moves from this position. offsets = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)] # Move the knight to this position. moves[row][col] = move_number # See if we have visited all of the squares. if move_number == num_squares: if use_closed_path: # See if this is a closed path. for dr, dc in offsets: r = row + dr c = col + dc if r < 0 or r >= num_rows: continue if c < 0 or c >= num_cols: continue if moves[r][c] == 1: return True # Can move back to start. # Cannot move back to start. moves[row][col] = 0 return False # Closed path not required. return True # Get move counts for all legal moves. legal_moves = [] for dr, dc in offsets: r = row + dr c = col + dc if r < 0 or r >= num_rows: continue if c < 0 or c >= num_cols: continue if moves[r][c] != 0: continue # This move is legal and available. Save it and its move count. move_count = num_moves(num_rows, num_cols, r, c, moves) legal_moves.append((move_count, r, c)) # Sort the legal moves by their move counts. if use_warnsdorf: legal_moves.sort(key=lambda x: x[0]) # Try all legal positions for the next move in their sorted order. move_number += 1 for move_count, r, c in legal_moves: if move_to(num_squares, num_rows, num_cols, r, c, moves, move_number, use_closed_path, use_warnsdorf): return True # This move didn't work out. Undo it and backtrack. moves[row][col] = 0 return False

The function moves to the new square and checks to see if the path is complete as before. This time, instead of trying all of the possible next moves, the code first puts those moves in the legal_moves list together with their next move counts. It then sorts the legal moves by their next move counts and then tries them in order.

The following code shows the num_moves function that returns a move's next moves count.

def num_moves(num_rows, num_cols, row, col, moves): '''Return the number of possible moves from square moves[row][col].''' # Build a list of legal moves from this position. offsets = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)] # Try all legal positions for the next move. num_moves = 0 for dr, dc in offsets: r = row + dr c = col + dc if r < 0 or r >= num_rows: continue if c < 0 or c >= num_cols: continue if moves[r][c] != 0: continue num_moves += 1 # Add one to the legal move count. return num_moves

This function simply loops through all of the possible moves starting from position [row][col]. If a move is legal and not already visited, the function increments num_moves. After it has counted the viable moves, the function returns the count.

The Catch

Warnsdorf's rule is pretty miraculous in most cases, but there is a catch. The way the program is currently structured, it builds paths recursively. A 100×100 square board has 100 × 100 = 10,000 squares, so a complete path will visit all 10,000 squares and that means the program will enter 10,000 levels of recursion. By default Python only allows 1,000 level of recursion so it can stop your program if it seems to be stuck in infinite recursion, but that stops us from finding really long tours.

You could rewrite the program so it doesn't use recursion. That's an interesting exercise but it's complicated and there's an easier workaround: change the recursion limit. Use sys.getrecursionlimit to see what the current limit is and use sys.setrecursionlimit to change it.

Here's the code that this program uses to launch its user interface.

import sys # Display the recursion limit and raise it. recursion_limit = sys.getrecursionlimit() print(f'Recursion limit: {recursion_limit}') sys.setrecursionlimit(11000) print(f'Limit now: {recursion_limit}') KnightsTourApp() # Reset the recursion limit. sys.setrecursionlimit(recursion_limit) print(f'Limit now: {recursion_limit}')

This code gets the current recursion limit and saves it in variable recursion_limit and then sets the limit to 11,000, which should be enough to find tours on a 100×100 board. The code then instantiates the KnightsTourApp class to run the program.

When the program finishes, it calls sys.setrecursionlimit to restore the recursion limit to its original value.

This lets the program find some pretty huge tours, but there's still a limit. If, for some reason, you need to find even larger tours, you can increase the recursion even more until you run out of memory.

Conclusion

[A closed knight's tour on an 8x8 board]

11:10 AM 3/15/2026 That's probably enough about the knight's tour. Warnsdorf's rule lets you find open and closed tours for some pretty huge chessboards very quickly in most cases.

There are still a few modifications you can try out if you like. For example, these examples start their tours in the upper left corner. Sometimes it may be possible to find an open tour starting from one square but not starting from another square. You could modify the program to allow the user to pick the starting square. I'll leave that to you for now.

Another modification would be to pick the next step in a tour randomly so the program wouldn't generate the same tour every time on a particular chessboard. This wouldn't be too hard, just modify the Warnsdorf rule code shown in this post to randomize the legal moves instead of sorting them by the number of next moves.

You could also make the program show every possible tour, open or closed, starting from a given point.

Yet another variation would be to look for symmetric paths.

As always, start with small boards. If the program cannot find a tour, it will examine every possible path from the starting point and there may be a ginormous number of those paths. For example, an 8×8 chessboard has 19,591,828,170,979,904 possible tours and they make up a miniscule fraction of the number of possible paths. Trying to enumerate all of the possible paths, or even finding one by examining moves randomly, could take an extremely long time.

For more information on the knight's tour problem, look online, for example on Wikipedia.

Download the example to see all of the details and to experiment with it.