Knight Probability in Chessboard - Solution & Explanation
Problem Statement
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 - 1
Approach Overview
Problem 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 1: Dynamic Programming Approach
In this approach, we utilize a 3D array `dp` where `dp[k][i][j]` represents the probability that the knight is on position `(i, j)` after making `k` moves. Initially, the knight is placed at `(row, column)`, so `dp[0][row][column] = 1`. For each move `k`, we calculate the probability of the knight being on each cell `(i, j)` by summing over probabilities of positions that can move to `(i, j)` in one knight move.
This involves iterating through each cell and updating the probabilities according to knight's possible moves.
The code initializes a 3D dynamic array `dp` for storing the probabilities of being on each board position `(i, j)` after `k` moves. We iterate through each move and potential knight positions, updating probabilities based on possible knight moves.
Complexity
Time Complexity: O(k * n^2), as each position on the board and each move is processed.
Space Complexity: O(k * n^2), for storing the DP states.
Approach 2: Recursive Memoization Approach
This approach leverages recursion along with memoization to optimize calculations. We define a recursive function to calculate the probability the knight remains within bounds after `k` moves. We utilize memoization to cache results of subproblems to avoid redundant calculations. If the knight's position ends within the board boundaries, it contributes to the final probability.
C implementation uses recursion with memoization to solve the problem. The `memo` table caches results for specific `(i, j, k)` states to avoid redundant computations.
Complexity
Time Complexity: O(k * n^2).
Space Complexity: O(k * n^2).
Approach 3: Dynamic Programming
We define f[h][i][j] to represent the probability that the knight remains on the board after taking h steps starting from position (i, j). The final answer is f[k][row][column].
When h=0, the knight is definitely on the board, so the probability is 1, i.e., f[0][i][j]=1.
When h \gt 0, the probability that the knight is at position (i, j) can be derived from the probabilities of the 8 possible positions it could have come from in the previous step, i.e.,
$
f[h][i][j] = sum_{x, y} f[h - 1][x][y] times \frac{1}{8}
where (x, y) is one of the 8 positions the knight can move to from (i, j).
The final answer is f[k][row][column].
The time complexity is O(k times n^2), and the space complexity is O(k times n^2). Here, k and n$ are the given number of steps and the size of the board, respectively.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(k * n^2), as each position on the board and each move is processed. |
| Recursive Memoization Approach | Time Complexity: O(k * n^2). |
| Dynamic Programming | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Knights Probability in Chessboard Dynamic Programming | Leetcode-688 (Medium) Solution • Pepcoding • 21,306 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Knight Probability in Chessboard easy or hard?
Knight Probability in Chessboard Python/Java solution
How to solve Knight Probability in Chessboard in O(n)?
What is the best approach for Knight Probability in Chessboard?
Is Knight Probability in Chessboard asked at Google/Amazon/Meta?
What data structure is used in Knight Probability in Chessboard?
What is the time complexity of Knight Probability in Chessboard?
Ready to solve this problem?
Practice Knight Probability in Chessboard with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor