How to Solve the Knight’s Tour Problem in Python?

Estimated read time 3 min read

The Knight’s Tour problem is a classic algorithmic problem that asks you to find a sequence of moves for a knight on a chessboard such that the knight visits every square exactly once. Here is an example of how to solve this problem in Python using a backtracking algorithm:

def knights_tour(n):
    board = [[-1] * n for _ in range(n)]
    moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
    
    def backtrack(row, col, num_moves):
        if num_moves == n**2:
            return True
        for move in moves:
            new_row = row + move[0]
            new_col = col + move[1]
            if 0 <= new_row < n and 0 <= new_col < n and board[new_row][new_col] == -1:
                board[new_row][new_col] = num_moves
                if backtrack(new_row, new_col, num_moves+1):
                    return True
                board[new_row][new_col] = -1
        return False
    
    # start

In this solution, we use a nested function backtrack to recursively generate all possible solutions to the Knight’s Tour problem. The function takes three input values: row, col, and num_moves.

row and col represent the current row and column on the chessboard, and num_moves represents the number of moves the knight has made so far.

In the main function, we first initialize a 2D list board of size n by n with all values set to -1. We also define a list moves of all possible knight moves.

Then, we call backtrack with initial values of 0, 0, and 1 to start the knight’s tour from the top-left corner of the board.

Inside the backtrack function, we first check if the knight has visited every square on the board (num_moves == n**2). If this is the case, we return True to indicate that a solution has been found.

Otherwise, we iterate through each possible knight move from the current square. If the move is valid (i.e., it does not go off the board and does not visit a square that has already been visited), we update the board with the new move and recursively call backtrack with the updated values of row, col, and num_moves.

If the recursive call returns True, we return True to indicate that a solution has been found. Otherwise, we undo the last move by resetting the board at the new square to -1.

Finally, in the main function, we return the board if a solution has been found, and None otherwise.

To use this function, simply call knights_tour(n) with the appropriate integer value of n. The function will return a 2D list representing a valid knight’s tour on an n by n chessboard, or None if no valid tour exists.

You May Also Like

More From Author

+ There are no comments

Add yours

Leave a Reply