Solve the Knight’s Tour with Python: A Step-by-Step Backtracking Guide

Knight's Moves on the Board

The knight moves in an L‑shape: two squares in one direction and then one square perpendicular, or one square then two squares. Near the edges or corners the number of possible moves decreases.

In Python the eight possible L‑shaped moves are represented by the list:

<code>knight_moves = [
    (2, 1), (1, 2), (-1, 2), (-2, 1),
    (-2, -1), (-1, -2), (1, -2), (2, -1)
]
</code>

Initializing the Board

We create an 8×8 board where each cell is initially marked as unvisited with -1 :

<code>def initialize_board(size):
    """Create an empty board, using -1 for unvisited squares."""
    return [[-1 for _ in range(size)] for _ in range(size)]
</code>

Validating Moves

A move is valid if it stays within the board limits and the target cell has not been visited yet:

<code>def is_valid_move(x, y, board):
    """Check whether a move is inside the board and unvisited."""
    size = len(board)
    return 0 <= x < size and 0 <= y < size and board[x][y] == -1
</code>

Backtracking Algorithm

The recursive backtracking function tries every possible move from the current position, marking the board with the move count. If all squares are visited, it returns True ; otherwise it backtracks:

<code>def solve_knights_tour(board, x, y, move_count):
    """Recursively attempt to solve the Knight's Tour using backtracking."""
    size = len(board)
    if move_count == size * size:
        return True
    for dx, dy in knight_moves:
        new_x, new_y = x + dx, y + dy
        if is_valid_move(new_x, new_y, board):
            board[new_x][new_y] = move_count
            if solve_knights_tour(board, new_x, new_y, move_count + 1):
                return True
            board[new_x][new_y] = -1
    return False
</code>

Printing the Board

After a solution is found, the board is printed to the console, showing the step number for each square:

<code>def print_board(board):
    """Print the board with the knight's path."""
    for row in board:
        print(' '.join(str(cell).rjust(3) for cell in row))
</code>

Putting It All Together

The main routine initializes the board, places the knight at the top‑left corner (0, 0), and starts the search. If a solution exists, it prints a success message and the board layout:

<code>def main():
    size = 8
    board = initialize_board(size)
    start_x, start_y = 0, 0
    board[start_x][start_y] = 0
    if solve_knights_tour(board, start_x, start_y, 1):
        print("Found a solution!")
        print_board(board)
    else:
        print("No solution exists.")

if __name__ == "__main__":
    main()
</code>

Result Example

The program outputs a board where each cell contains the move index, demonstrating a complete tour that visits every square exactly once.

Conclusion

The Knight’s Tour problem requires defining the eight L‑shaped moves, initializing an 8×8 board, validating each move, and using a recursive backtracking algorithm to explore paths. The final solution is displayed by printing the board, showing the exact sequence of moves that covers every square.