Watch 10 video solutions for Knight Probability in Chessboard, a medium level problem involving Dynamic Programming. This walkthrough by Pepcoding has 21,162 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 250 <= k <= 1000 <= row, column <= n - 1Problem Overview: You have an n x n chessboard and a knight starting at position (row, column). The knight makes exactly k moves, choosing one of the 8 legal knight moves each time with equal probability. The task is to compute the probability that the knight remains on the board after all k moves.
Approach 1: Recursive Memoization (Time: O(k * n^2), Space: O(k * n^2))
Model the problem as a recursive search over moves. From a cell (r, c) with movesRemaining, try all 8 knight directions and recursively compute the probability of staying on the board. Each move contributes 1/8 of the probability. Many states repeat because the same cell can be reached with the same remaining moves through different paths. Store results in a memo table keyed by (r, c, movesRemaining). When the knight moves off the board, return 0. When no moves remain, return 1. Memoization avoids recomputation and turns an exponential recursion into a polynomial-time solution.
This approach naturally expresses the state transition and is easy to reason about. The state space is bounded by n * n * k, and each state explores 8 directions, giving O(k * n^2) time complexity. It relies on caching overlapping subproblems, a classic pattern in Dynamic Programming and Memoization.
Approach 2: Dynamic Programming (Bottom-Up) (Time: O(k * n^2), Space: O(n^2))
Instead of recursion, build probabilities iteratively. Maintain a 2D grid dp[r][c] representing the probability of the knight being at cell (r, c) after the current number of moves. Initialize the starting position with probability 1. For each of the k moves, create a new grid and distribute the probability from each cell to its 8 valid knight destinations using probability / 8.
Each iteration processes all n^2 cells and updates up to 8 destinations. After completing k iterations, sum the probabilities of all cells to get the probability that the knight remains on the board. Because only the previous step is required to compute the next step, you can reuse two grids and keep the space complexity at O(n^2). This formulation directly represents state transitions typical in Dynamic Programming problems.
Recommended for interviews: Interviewers typically expect the bottom-up Dynamic Programming solution. It clearly models probability transitions and avoids recursion overhead. Explaining the recursive memoization version first demonstrates understanding of overlapping subproblems, while the iterative DP version shows you can optimize state transitions and memory usage—skills commonly tested in recursion and DP interview questions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Memoization | O(k * n^2) | O(k * n^2) | When modeling the problem naturally with recursion and caching repeated states |
| Dynamic Programming (Bottom-Up) | O(k * n^2) | O(n^2) | Preferred for interviews and production code due to iterative transitions and lower memory usage |