Title: Find a closed knight's tour in Python

[A closed knight's tour on a 6x6 board]

My post Find a closed knight's tour in Python explained how to find a knight's tour: a path that a knight can follow to visit every square on a chessboard without visiting any square twice. This post shows how to find such a path that returns to its starting point. Such a path is called closed.

This is actually a small change to the previous program. Before we get to that change, however, we need to talk about board size.

Checking Board Size

Every time the knight moves, it moves from a white square to a black one or vice versa. In other words, every time the knight moves the color of its square changes.

In a closed tour, the knight returns to the square where it started. That also means it must return to the color where it started. Because the square color changes with every move, that means the path must contain an even number of moves, including the move that puts it back where it started.

For example, if the board has 5 rows and 7 columns, then it has 35 squares so any closed path would need to make 35 moves. Because 35 is odd, that cannot be a closed path.

This lets us add the following quick test before we start searching for a closed path.

# If we need a closed path, make sure the board # has an even number of squares. if use_closed_path and (num_rows * num_cols) % 2 == 1: print('Closed paths are only possible if the board has an even number of squares') return None

If we are looking for a closed path and the number of squares on the board is odd, this code simply displays a failure message and returns.

Closing the Path

Here's how the previous version of the program works.

The program's move_to function moves the knight to a new board position that has not yet been visited. If it has then visited every square, the function returns True to indicate that it found a complete path. Here's the code that performs this test.

# If we have visited all of the squares, this is a solution. if move_number == num_squares: return True

If move_to has not visited every square, it calls itself recursively to try moving the knight to every nearby square that it has not already visited. If any of those calls returns True, the function also returns True to indicate that the current path is complete and control unwinds to the top-level function call so the program can display the result. If all of the recursive calls return False, the current call also returns False so the program can try other paths.

See the earlier post for a longer explanation.

The new program only requires a small tweak to the test to see whether the current path is a solution.

# 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

If the function has visited every square, it then checks its use_closed_path parameter to see if we're looking for a closed path. If we are, the code checks whether the final square in the path is one square away from the starting square (0, 0). To do that, it loops through the offsets that give the knight's possible moves (see the earlier post for details) and, if any of those moves leads to the start square, the function returns True. If none of the moves leads to the start square, then this is a complete path but not a closed path, so the function returns False.

If the use_closed_path parameter is False, we don't need a closed path so the function simply returns True.

Conclusion

That's all we need to do to check for a closed path.

Note that a closed path must visit every square on the board so it doesn't matter which square you pick for the starting point. This post starts at square (0, 0). If a closed path is possible, it will eventually visit whichever square you pick.

That's not true with non-closed paths. It is possible that an open path might be possible from one starting square but not another.

Download the example to try it out and to see all of the details. As I mentioned in the earlier post, start with small board sizes or be ready to press Ctrl+C to stop the program if it gets stuck looking for a hard-to-find tour.