The Knight’s Tour is a classic problem in which a knight must visit every square on a chessboard exactly once. The knight moves in an L-shape: two squares in one direction and one square perpendicular. The challenge is to find a sequence of moves that allows the knight to cover the entire board.

Program Structure

The program uses a backtracking algorithm to explore all possible moves of the knight. It employs recursion to attempt each move, backtracking when a move leads to a dead end. The main components of the program are:

• Constants: The size of the chessboard and the possible moves a knight can make.
• Utility Functions: Functions to check if a move is valid and to print the solution.
• Backtracking Function: A recursive function that tries to place the knight on the board and checks for valid moves.
• Driver Function: Initializes the board and starts the knight’s tour.

Python Code

def print_solution(n, board):
    """Function to print the chessboard."""
    for row in board:
        print(" ".join(str(cell).rjust(2, ' ') for cell in row))
    print()

def is_safe(x, y, n, board):
    """Check if the knight's move is valid."""
    return 0 <= x < n and 0 <= y < n and board[x][y] == -1

def knight_tour_util(n, board, curr_x, curr_y, movei, x_moves, y_moves):
    """Utility function to solve the Knight's Tour problem using backtracking."""
    if movei == n * n:
        return True

    for i in range(8):
        next_x = curr_x + x_moves[i]
        next_y = curr_y + y_moves[i]
        if is_safe(next_x, next_y, n, board):
            board[next_x][next_y] = movei
            if knight_tour_util(n, board, next_x, next_y, movei + 1, x_moves, y_moves):
                return True
            # Backtracking
            board[next_x][next_y] = -1

    return False

def knight_tour(n):
    """Driver function to initialize the board and start the Knight's Tour."""
    # Initialize the board
    board = [[-1 for _ in range(n)] for _ in range(n)]

    # Possible moves of a knight
    x_moves = [2, 1, -1, -2, -2, -1, 1, 2]
    y_moves = [1, 2, 2, 1, -1, -2, -2, -1]

    # Start from the first square
    board[0][0] = 0

    if not knight_tour_util(n, board, 0, 0, 1, x_moves, y_moves):
        print("Solution does not exist")
    else:
        print_solution(n, board)

# Set the size of the chessboard
n = 8
knight_tour(n)

How to Run the Program

To run the program:

1. Copy the code into a Python file (e.g., knights_tour.py).
2. Run the file using Python 3: python knights_tour.py.
3. The program will print the chessboard with the knight’s tour solution, if one exists.

Conclusion

The Knight’s Tour problem is an excellent example of backtracking in algorithms. This program effectively demonstrates how to explore all possible knight moves and backtrack to find a valid tour of the chessboard.