Knight Probability In Chessboard - Leetcode Solution

The Knight Probability in Chessboard problem on LeetCode is a classic dynamic programming problem that involves calculating the probability of a knight staying on the chessboard after making a certain number of moves. In this problem, we are given:

• A chessboard of size n x n
• The starting position of the knight on the chessboard
• The number of moves the knight can make

The goal is to find the probability of the knight staying on the chessboard after making all the moves.

To solve this problem, we can start by creating a 2D array of size n x n to keep track of the probabilities for each square on the chessboard. We can initialize all the probabilities to 1/n^2, which is the probability of the knight being on any given square on the chessboard before making any moves.

Next, we can use dynamic programming to calculate the probabilities of the knight being on each square after making a certain number of moves. We can do this by iterating through all the possible squares that the knight could have come from in the previous move, and calculating the probability of the knight being on the current square.

For example, if we are calculating the probability of the knight being on square (i, j) after making k moves, we can look at all the possible squares that the knight could have come from in the k-1th move. We can then add up the probabilities of the knight being on each of these squares and multiply it by the probability of moving from that square to square (i, j), which is 1/8 since the knight has 8 possible moves.

In code, the dynamic programming solution may look something like this:

def knightProbability(self, n: int, k: int, row: int, column: int) -> float: # Initialize probability array prob = [[1/(n*n)]*n for _ in range(n)]

# Possible moves for knight
moves = [(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (-1,2), (1,-2), (-1,-2)]

# Iterate through all possible moves
for _ in range(k):
    new_prob = [[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            for dx, dy in moves:
                x, y = i + dx, j + dy
                if 0 <= x < n and 0 <= y < n:
                    new_prob[i][j] += prob[x][y] * 1/8
    
    prob = new_prob

# Return probability of knight being on given square
return prob[row][column]

Overall, this solution has a time complexity of O(k * n^2), since we are iterating through all possible moves k times. The space complexity is also O(n^2), since we are using a 2D array to store the probabilities.

1