Knight Probability in Chessboard

Medium

Asked by:

43 views

Topics:

Dynamic Programming

On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed, so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).

A chess knight has eight possible moves it can make, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly k moves or has moved off the chessboard.

Return the probability that the knight remains on the board after it has stopped moving.

Example 1:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

Example 2:

Input: n = 1, k = 0, row = 0, column = 0
Output: 1.00000

Constraints:

1 <= n <= 25
0 <= k <= 100
0 <= row, column <= n - 1

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 are the constraints on N (the size of the chessboard), K (the number of moves), r (the starting row), and c (the starting column)?
If the knight goes out of bounds before K moves are completed, should I consider the probability to be 0 for those remaining moves?
Is K guaranteed to be non-negative? What if K is 0?
Is it possible for the starting row 'r' or starting column 'c' to be out of bounds initially? If so, how should I handle that case?
What type should I return for the probability - can I return a double, and how many decimal places of precision are expected?

Brute Force Solution

Approach

The brute force method to calculate the knight's probability involves simulating every possible move sequence. Starting from the knight's initial position, we explore every possible move the knight can make at each turn. We then determine the probability that the knight remains on the board after the given number of moves.

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

Start with the knight at its initial square on the chessboard.
Consider all eight possible moves a knight can make from that square.
For each of those moves, check if the knight stays within the boundaries of the chessboard.
If a move takes the knight off the board, discard that possibility.
If a move keeps the knight on the board, repeat the process for the next move. That is, from this new square, consider all eight possible knight moves again.
Keep doing this for each possible move, at each step, until the knight has made the required number of moves.
Count the number of move sequences that end with the knight still on the board.
Divide that count by the total number of possible move sequences (8 raised to the power of the number of moves) to find the probability.

Code Implementation

def knight_probability_brute_force(board_size, number_of_moves, start_row, start_column):

    possible_moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2),
                      (1, -2), (1, 2), (2, -1), (2, 1)]

    def is_valid_move(row_coordinate, column_coordinate):
        return 0 <= row_coordinate < board_size and 0 <= column_coordinate < board_size

    def calculate_number_of_ways(current_row, current_column, moves_remaining):
        # Base case: If no more moves are left, we've found a valid path
        if moves_remaining == 0:
            return 1

        number_of_valid_ways = 0

        # Explore all possible knight moves from the current position
        for move_row, move_column in possible_moves:
            next_row = current_row + move_row
            next_column = current_column + move_column

            # Only consider moves that keep the knight on the board
            if is_valid_move(next_row, next_column):

                number_of_valid_ways += calculate_number_of_ways(next_row, next_column, moves_remaining - 1)

        return number_of_valid_ways

    # Calculate number of ways to stay on board
    number_of_ways_to_stay_on_board = calculate_number_of_ways(start_row, start_column, number_of_moves)

    # Calculate total possible move sequences
    total_possible_sequences = 8 ** number_of_moves

    return number_of_ways_to_stay_on_board / total_possible_sequences

Big(O) Analysis

Time Complexity

O(8^k) – The algorithm explores all possible move sequences for the knight. At each move, the knight has 8 possible moves. Since the algorithm explores all sequences up to k moves, the total number of move sequences explored is 8 * 8 * ... * 8 (k times), which equals 8^k. Therefore, the time complexity is O(8^k), where k is the number of moves.

Space Complexity

O(8^K) – The brute force approach explores every possible move sequence to a depth of K (the number of moves). In essence, it implicitly builds a call stack representing the current path of moves. Since each move has 8 possibilities, at the deepest level (level K), there can be 8^K active call stacks or branches explored simultaneously. Therefore, the space used by the call stack will grow exponentially based on the number of moves, K. No other significant auxiliary space is used.

Optimal Solution

Approach

This problem asks for the probability a knight stays on a chessboard after a number of moves. The smart approach is to build up the probabilities step-by-step, using previous results to calculate the next, instead of trying to simulate every possible move sequence.

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

Imagine the chessboard as a grid where each square holds the probability of the knight being there at a given time.
Start with the knight at its initial position, meaning that square has a probability of 1 (or 100%), and all other squares have a probability of 0.
For each move, go through every square on the board.
If a square has a non-zero probability, consider all eight possible knight moves from that square.
For each valid knight move (that stays on the board), add a fraction of the current square's probability to the destination square. This fraction is 1/8 because a knight has 8 possible moves.
Repeat this process for the specified number of moves, updating the probabilities on each square after each move.
After the final move, sum the probabilities of all the squares on the board. This gives the overall probability of the knight staying on the board.

Code Implementation

def knight_probability(board_size, number_of_moves, start_row, start_column):    current_probabilities = [[0.0] * board_size for _ in range(board_size)]
    current_probabilities[start_row][start_column] = 1.0

    knight_moves = [
        (-2, -1), (-2, 1), (-1, -2), (-1, 2),
        (1, -2), (1, 2), (2, -1), (2, 1)
    ]

    for _ in range(number_of_moves):
        next_probabilities = [[0.0] * board_size for _ in range(board_size)]

        # Iterate through each cell of the chessboard
        for row in range(board_size):
            for column in range(board_size):
                # Only process cells with non-zero probability
                if current_probabilities[row][column] > 0:
                    # Iterate through possible knight moves
                    for move_row, move_column in knight_moves:
                        next_row = row + move_row
                        next_column = column + move_column

                        # Check if the next move is within the board
                        if 0 <= next_row < board_size and 0 <= next_column < board_size:
                            # Accumulate probability for the next position
                            next_probabilities[next_row][next_column] += current_probabilities[row][column] / 8.0

        current_probabilities = next_probabilities

    # Calculate the total probability of the knight staying on the board
    total_probability = 0.0
    for row in range(board_size):
        for column in range(board_size):
            total_probability += current_probabilities[row][column]

    return total_probability

Big(O) Analysis

Time Complexity

O(k * n * n) – The algorithm iterates k times, representing the number of moves. Within each move, it traverses every cell on the n x n chessboard. For each cell, a constant number (8) of potential knight moves are considered to update probabilities. Therefore, the time complexity is driven by k iterations of visiting each of the n*n cells, resulting in O(k * n * n).

Space Complexity

O(N^2) – The algorithm uses two 2D arrays to store the probabilities of the knight being on each square of the chessboard. Each array has dimensions N x N, where N is the size of the board. Therefore, the space required is proportional to N^2 for each array, and since we have two such arrays, the auxiliary space is 2 * N^2, which simplifies to O(N^2).

Edge Cases

Case	How to Handle
N = 0 (Board size is zero)	Return 0.0 as the knight cannot make any moves on an empty board.
K = 0 (No moves allowed)	Return 1.0 if the starting position is within the board, otherwise return 0.0, as no moves means no probability of falling off after 0 moves if initial position is inside.
r, c outside initial bounds (r < 0, c < 0, r >= N, c >= N)	Return 0.0, because starting outside the board makes any further move impossible to stay inside.
N = 1 (Board size is 1x1)	If K>0 return 0.0 as any move will lead to falling off the board, if K=0 return 1.0 if r=0 and c=0 otherwise return 0.0.
Large N and K (potential stack overflow with recursion)	Use dynamic programming (iterative approach) to avoid exceeding recursion depth limitations.
Intermediate probabilities becoming very small (floating point precision)	Floating-point operations are used, and inherent precision limitations exist, but probability calculations will still be accurate enough for practical purposes.
r and c being very close to the edge of the board	The algorithm correctly handles cases where initial position is at the edge since it iterates on possible moves and checks for boundary conditions after each move.
Integer overflow if intermediate calculations exceed maximum integer size.	Using double data type will avoid integer overflow during probability calculation because probabilities are small positive values anyway.

N = 0 (Board size is zero)

How to Handle:

Return 0.0 as the knight cannot make any moves on an empty board.

K = 0 (No moves allowed)

How to Handle:

Return 1.0 if the starting position is within the board, otherwise return 0.0, as no moves means no probability of falling off after 0 moves if initial position is inside.

r, c outside initial bounds (r < 0, c < 0, r >= N, c >= N)

How to Handle:

Return 0.0, because starting outside the board makes any further move impossible to stay inside.

N = 1 (Board size is 1x1)

How to Handle:

If K>0 return 0.0 as any move will lead to falling off the board, if K=0 return 1.0 if r=0 and c=0 otherwise return 0.0.

Large N and K (potential stack overflow with recursion)

How to Handle:

Use dynamic programming (iterative approach) to avoid exceeding recursion depth limitations.

Intermediate probabilities becoming very small (floating point precision)

How to Handle:

Floating-point operations are used, and inherent precision limitations exist, but probability calculations will still be accurate enough for practical purposes.

r and c being very close to the edge of the board

How to Handle:

The algorithm correctly handles cases where initial position is at the edge since it iterates on possible moves and checks for boundary conditions after each move.

Integer overflow if intermediate calculations exceed maximum integer size.

How to Handle:

Using double data type will avoid integer overflow during probability calculation because probabilities are small positive values anyway.