Knight Probability in Chessboard

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. 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: n = 3, k = 2, row = 0, column = 0. Output: 0.06250. Can you provide a solution?

class Solution:
    def knightProbability(self, n: int, k: int, row: int, col: int) -> float:
        dp = {}

        def solve(r, c, moves):
            if (r, c, moves) in dp:
                return dp[(r, c, moves)]

            if moves == 0:
                return 1 if 0 <= r < n and 0 <= c < n else 0

            if not (0 <= r < n and 0 <= c < n):
                return 0

            probability = 0
            moves_arr = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
            for dr, dc in moves_arr:
                probability += solve(r + dr, c + dc, moves - 1)

            dp[(r, c, moves)] = probability / 8.0
            return dp[(r, c, moves)]

        return solve(row, col, k)

Brute Force Solution

A brute-force solution would involve recursively exploring all possible knight moves and tracking the probability of staying on the board. However, this approach would be highly inefficient due to overlapping subproblems.

Optimal Solution

The optimal solution uses dynamic programming to store and reuse the results of subproblems. This avoids redundant calculations and significantly improves efficiency.

1. Initialization:
   • Create a dictionary dp to store the results of subproblems.
2. Recursive Function solve(r, c, moves):
   • Base Cases:
     • If moves == 0, return 1 if the knight is on the board, otherwise return 0.
     • If the knight is off the board, return 0.
   • Memoization:
     • If the result for (r, c, moves) is already in dp, return it.
   • Recursive Step:
     • Initialize probability = 0.
     • Iterate through all possible knight moves moves_arr.
     • Recursively call solve() for each move and add the result to probability.
   • Store the calculated probability in dp and return probability / 8.0.
3. Main Function:
   • Call the solve() function with the initial row, column, and number of moves.
   • Return the result.

Big(O) Run-Time Analysis

• The time complexity is O(N^2 * K), where N is the size of the board and K is the number of moves. The DP table dp stores results for each cell (r, c) and number of moves. Since r and c can range from 0 to N-1, and the number of moves can range from 0 to K, there are N * N * K possible states. For each state, we iterate through 8 possible knight moves, but this is a constant factor, so the overall time complexity remains O(N^2 * K).

Big(O) Space Usage Analysis

• The space complexity is O(N^2 * K) because the dp dictionary stores the results for each possible state (row, column, number of moves).

Edge Cases

1. Invalid Input:
   • If n is less than 1, k is negative, or row and column are out of bounds, return 0.
2. Zero Moves:
   • If k is 0, return 1 if the knight is on the board, otherwise return 0.
3. Large Number of Moves:
   • If k is very large, the probability of staying on the board may become very small. The solution handles this case correctly by accumulating probabilities.
4. Small Board Size:
   • If n is small (e.g., 1), the knight may quickly move off the board. The base cases in the recursive function handle this scenario.