The Knight’s Tour

Medium

Asked by:

3 views

Topics:

RecursionGraphsArrays

A knight is placed on a chessboard of size n x n. Find a sequence of moves for the knight so that it visits each square exactly once.

We represent the chessboard as a 2D array where (0, 0) is the top-left square and (n-1, n-1) is the bottom-right square.

The knight can move in eight possible directions:

(2, 1)
(2, -1)
(-2, 1)
(-2, -1)
(1, 2)
(1, -2)
(-1, 2)
(-1, -2)

A valid tour is a sequence of moves such that:

The knight starts at position (0, 0).
The knight visits each square exactly once.
All moves are within the bounds of the chessboard.

You need to implement a function that takes the size of the chessboard n as input and returns a 2D array representing a valid knight's tour. If a valid tour is not possible, return an empty array [].

The returned array should be an n x n matrix where each cell contains the order in which the knight visited that square (starting from 0). If a solution exists, there will only be one valid solution.

Example 1:


Input: n = 5
Output:
[
  [0, 3, 14, 17, 8],
  [13, 16, 7, 2, 5],
  [4, 1, 18, 9, 12],
  [15, 6, 11, 24, 21],
  [20, 23, 22, 19, 10]
]

Explanation:

The knight starts at (0, 0), visits (0, 3) next, then (2, 4), and so on until it has visited all the cells in the board exactly once.

Example 2:


Input: n = 2
Output: []

Explanation:

For a 2x2 board, it's impossible for the knight to visit all cells exactly once.

Constraints:

1 <= n <= 8

Try coding it in LeetCode

The Knight’s Tour

Medium

Asked by:

3 views

Topics:

RecursionGraphsArrays

A knight is placed on a chessboard of size n x n. Find a sequence of moves for the knight so that it visits each square exactly once.

We represent the chessboard as a 2D array where (0, 0) is the top-left square and (n-1, n-1) is the bottom-right square.

The knight can move in eight possible directions:

(2, 1)
(2, -1)
(-2, 1)
(-2, -1)
(1, 2)
(1, -2)
(-1, 2)
(-1, -2)

A valid tour is a sequence of moves such that:

The knight starts at position (0, 0).
The knight visits each square exactly once.
All moves are within the bounds of the chessboard.

You need to implement a function that takes the size of the chessboard n as input and returns a 2D array representing a valid knight's tour. If a valid tour is not possible, return an empty array [].

The returned array should be an n x n matrix where each cell contains the order in which the knight visited that square (starting from 0). If a solution exists, there will only be one valid solution.

Example 1:


Input: n = 5
Output:
[
  [0, 3, 14, 17, 8],
  [13, 16, 7, 2, 5],
  [4, 1, 18, 9, 12],
  [15, 6, 11, 24, 21],
  [20, 23, 22, 19, 10]
]

Explanation:

The knight starts at (0, 0), visits (0, 3) next, then (2, 4), and so on until it has visited all the cells in the board exactly once.

Example 2:


Input: n = 2
Output: []

Explanation:

For a 2x2 board, it's impossible for the knight to visit all cells exactly once.

Constraints:

1 <= n <= 8

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the board (n)? Are there any constraints on n?
If a valid knight's tour doesn't exist for the given board size, should I return an empty array, null, or throw an exception?
Are there specific performance requirements I should be aware of, given the potential for large board sizes?
Is there any preference if multiple valid Knight's Tours exist? Should I aim for a specific type of tour (e.g., a closed tour)?
Can I assume 'n' will always be a positive integer?

Brute Force Solution

Approach

The Knight's Tour problem is about finding a sequence of moves for a knight on a chessboard so it visits every square exactly once. A brute-force approach to this problem involves trying every possible move sequence until we find one that works.

Here's how the algorithm would work step-by-step:

Start the knight at a specific square on the chessboard.
From that square, consider all possible knight moves (there are usually 8).
Choose one of the possible moves and move the knight to that new square.
Mark the new square as visited, so you don't visit it again in the same tour.
From the new square, again consider all possible knight moves that lead to unvisited squares.
Keep repeating the process of choosing a move, moving the knight, and marking the square as visited.
If you reach a point where the knight has no valid moves (all possible squares are already visited), go back to the previous square and try a different move there.
Continue trying different move combinations, step by step, backtracking when you hit a dead end.
If the knight successfully visits every square on the board exactly once, then you have found a solution.
If after trying every possible combination of moves, you can't find a solution, then the brute force approach has failed to find a tour from the initial starting square.

Code Implementation

def knights_tour_brute_force(board_size, start_row, start_column): 
    board = [[-1 for _ in range(board_size)] for _ in range(board_size)]
    row_moves = [2, 1, -1, -2, -2, -1, 1, 2]
    column_moves = [1, 2, 2, 1, -1, -2, -2, -1]
    board[start_row][start_column] = 0

    def is_valid_move(row, column, chess_board):
        return (0 <= row < board_size and 0 <= column < board_size and
                chess_board[row][column] == -1)

    def solve_knights_tour(move_number, current_row, current_column, chess_board):
        if move_number == board_size * board_size:
            return True

        # Iterate through all possible knight moves.
        for move_index in range(8):
            new_row = current_row + row_moves[move_index]
            new_column = current_column + column_moves[move_index]

            # Check if the move is valid.
            if is_valid_move(new_row, new_column, chess_board):
                chess_board[new_row][new_column] = move_number

                # Recursively solve the rest of the tour.
                if solve_knights_tour(move_number + 1, new_row, new_column, chess_board):
                    return True

                # Backtrack if the current move doesn't lead to a solution.
                chess_board[new_row][new_column] = -1

        return False

    # Start the recursive solution.
    if solve_knights_tour(1, start_row, start_column, board):
        return board
    else:
        return None

Big(O) Analysis

Time Complexity

O(8^n^2) – The Knight's Tour, using the brute force approach described, explores every possible sequence of knight moves. In the worst case, from each of the n^2 squares on the board, the knight has up to 8 possible moves. The algorithm recursively explores these moves, backtracking when a dead end is reached. Thus, the algorithm explores a tree of possible moves with a branching factor of up to 8 at each node and a maximum depth of n^2 (the number of squares on the board). This leads to a time complexity that is exponential, specifically O(8^n^2), representing the exploration of all possible move sequences.

Space Complexity

O(N) – The algorithm uses a board to keep track of visited squares, which is of size N, where N is the total number of squares on the chessboard. Furthermore, in the worst-case scenario, the recursion stack can grow to a depth of N, representing the path the knight has taken. Therefore, the space complexity is dominated by the board and the recursion stack, both of which scale linearly with the number of squares. This results in an auxiliary space complexity of O(N).

Optimal Solution

Approach

The Knight's Tour problem asks you to find a sequence of moves for a knight on a chessboard so that it visits every square exactly once. The optimal approach uses a specific strategy to guide the knight's movement, making it much faster than just trying random moves.

Here's how the algorithm would work step-by-step:

Start the knight at a corner or edge square of the chessboard. These locations tend to have fewer possible moves, which helps in finding a complete tour.
When choosing the next square to move to, always pick the square that has the fewest available onward moves from it. This is called Warnsdorff's Rule.
If there's a tie in the number of onward moves, you can pick any of the tied squares randomly.
Continue moving the knight according to Warnsdorff's Rule until all squares have been visited or the knight has no valid moves left.
If the knight successfully visits every square, you've found a valid Knight's Tour. If not, try starting from a different corner or edge square and repeat the process.

Code Implementation

def knights_tour(board_size):
    def get_possible_moves(current_position):
        row, col = current_position
        possible_moves = [
            (row - 2, col - 1),
            (row - 2, col + 1),
            (row - 1, col - 2),
            (row - 1, col + 2),
            (row + 1, col - 2),
            (row + 1, col + 2),
            (row + 2, col - 1),
            (row + 2, col + 1),
        ]
        valid_moves = [
            (row_new, col_new)
            for row_new, col_new in possible_moves
            if 0 <= row_new < board_size and 0 <= col_new < board_size
        ]
        return valid_moves

    def get_number_of_available_moves(position, board_state):
        possible_next_moves = get_possible_moves(position)
        available_moves_count = 0
        for next_row, next_col in possible_next_moves:
            if board_state[next_row][next_col] == -1:
                available_moves_count += 1
        return available_moves_count

    def find_tour(start_row, start_col):
        board_state = [([-1] * board_size) for _ in range(board_size)]
        row, col = start_row, start_col
        board_state[row][col] = 0
        move_number = 1

        for _ in range(board_size * board_size - 1):
            # Warnsdorff's Rule: Prioritize squares with fewer onward moves.
            possible_moves = get_possible_moves((row, col))
            valid_moves = [
                (row_new, col_new)
                for row_new, col_new in possible_moves
                if board_state[row_new][col_new] == -1
            ]

            if not valid_moves:
                return None  # No valid moves, tour failed.

            move_counts = []
            for next_row, next_col in valid_moves:
                move_counts.append(
                    get_number_of_available_moves((next_row, next_col), board_state)
                )

            # Move to the position with the fewest onward moves
            min_moves = min(move_counts)
            best_moves = [
                valid_moves[i]
                for i, count in enumerate(move_counts)
                if count == min_moves
            ]

            row, col = best_moves[0]
            board_state[row][col] = move_number
            move_number += 1

        return board_state  # Return the board if the tour is successful

    # Try starting from a corner. 
    start_positions = [(0, 0), (0, board_size - 1), (board_size - 1, 0), (board_size - 1, board_size - 1)]
    for start_row, start_col in start_positions:
        tour = find_tour(start_row, start_col)
        if tour:
            return tour

    return None #If all start positions failed, return none

Big(O) Analysis

Time Complexity

O(n²) – The Knight's Tour algorithm, employing Warnsdorff's Rule, iterates through each of the n squares on the chessboard (where n represents the number of squares). For each square, it determines the next best move by examining a limited set of at most 8 possible knight moves (a constant). Finding the square with the fewest onward moves involves comparing these 8 possible moves, which is O(1). Therefore, visiting all n squares, each requiring a constant time to select, results in a time complexity proportional to n. Since n is proportional to boardWidth*boardHeight, or size*size, the overall time complexity is approximated by size * size = n² , leading to O(n²).

Space Complexity

O(N^2) – The algorithm uses an N x N chessboard to track visited squares, where N represents the dimension of the board. This visited array requires N^2 space to store boolean values indicating whether each square has been visited. Additionally, the recursive calls, in the worst-case scenario where a solution isn't immediately found and the algorithm explores many branches, could lead to a call stack depth proportional to the number of squares, although iterative implementations avoid this stack overhead. Thus, the dominant auxiliary space usage is the N x N chessboard, leading to O(N^2) space complexity.

Edge Cases

Case	How to Handle
n <= 0 or n == 1	Return empty array since a knight's tour is impossible on boards of this size.
n == 2	Return empty array since a knight's tour is impossible on a 2x2 board.
n == 3	Return empty array since a knight's tour is impossible on a 3x3 board.
No valid tour exists for the given n	Backtracking algorithm should exhaust all possibilities and return an empty array if no solution is found.
Stack Overflow for large n if recursion is not optimized	Optimize recursion through tail call optimization if available or use iterative approach to avoid stack overflow.
Integer overflow for very large n causing index out of bounds	Use appropriate data types (e.g., long) to store board size and move numbers to prevent potential overflow.
Algorithm visits the same square twice	Backtracking condition should prevent revisits, and ensure the algorithm explores other paths to find a valid solution.
Memory constraints for excessively large n	If possible, consider space-optimized data structures or algorithms (although likely impractical for this problem on very huge n).