Free lesson · DSA Mastery - Interview Prep, End to End
Knight Probability in Chessboard
Knight Probability in Chessboard
Knight Probability in Chessboard is the canonical forward probability DP: a knight starts at (row, column) on an N×N chessboard and makes exactly k random moves (one of 8 possible knight moves, chosen uniformly). Find the probability the knight remains on the board after all k moves. The DP defines dp[step][r][c] = probability of being at (r, c) after step moves; transitions: dp[step+1][r'][c'] += dp[step][r][c] · (1/8) for each on-board target. Answer: sum of dp[k][r][c] over all on-board cells. It demonstrates the forward propagation of probability mass and shows that Probability DP scales naturally to grid-based random-walk problems. We present the forward DP (canonical) and the 2-layer space-optimized version (optimal).
The insight: at each step, the knight's position is a random variable over the board cells. The probability mass at each cell evolves as moves happen. After k moves, the total probability mass remaining on the board is the answer; mass that "fell off" (moved to an off-board cell) is lost. This is exactly the forward-propagation Probability DP pattern.
The Problem
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) or (2,1)) that will keep the knight on the board.
From each position, the knight has two moves to stay 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.
Approaches Overview
| # | Approach | Time | Space | Verdict |
|---|---|---|---|---|
| 1 | Forward DP over (step, row, col) | O(k · n² · 8) | O(k · n²) | Canonical |
| 2 | 2-layer space-optimized | O(k · n² · 8) | O(n²) | Optimal |
dp[step][r][c] = probability of the knight being at (r, c) after step moves (having stayed on the board the entire time). Base: dp[0][row][column] = 1. Transition: dp[step+1][r+dr][c+dc] += dp[step][r][c] · (1/8) for each of the 8 knight moves, only if (r+dr, c+dc) is on the board. Off-board contributions are lost (no negative bookkeeping needed). Answer: sum of dp[k][r][c] over all on-board cells.
Approach 1: Forward DP Over (step, row, col) - Canonical
The Idea
Propagate probability mass step by step. At step 0, all probability (1.0) is at the starting cell. At each step, each cell's mass is distributed equally (1/8 each) to its 8 knight-move neighbors. Off-board neighbors lose their mass (the knight falls off). After k steps, the on-board probability mass is the answer.
Logic Flowchart
graph TD
A["dp[0][row][column] = 1.0; all others 0"] --> B["for step from 0 to k - 1:"]
B --> C["for each (r, c):"]
C --> D{"dp[step][r][c] > 0?"}
D -->|Yes| E["for each of 8 knight moves (dr, dc):"]
D -->|No| C
E --> F{"(r+dr, c+dc) on board?"}
F -->|Yes| G["dp[step+1][r+dr][c+dc] += dp[step][r][c] / 8"]
F -->|No| H["lost (off-board)"]
G --> E
H --> E
E --> C
C --> B
B --> I["sum dp[k][r][c] over all (r, c)"]
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
style H fill:#dc2626,stroke:#ef4444,color:#f1f5f9
style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
This flowchart shows the forward Probability DP for Knight Probability: propagate probability mass step by step, distributing each cell's mass equally to its eight knight-move neighbors that remain on the board.
Code
public static double knightProbability(int n, int k, int row, int column) {
int[][] moves = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
double[][] dp = new double[n][n];
dp[row][column] = 1.0;
for (int step = 0; step < k; step++) {
double[][] next = new double[n][n];
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (dp[r][c] == 0) continue;
for (int[] m : moves) {
int nr = r + m[0], nc = c + m[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
next[nr][nc] += dp[r][c] / 8.0;
}
}
}
}
dp = next;
}
double total = 0;
for (int r = 0; r < n; r++)
for (int c = 0; c < n; c++)
total += dp[r][c];
return total;
}
// Usage:
// knightProbability(3, 2, 0, 0) -> 0.0625
// knightProbability(1, 0, 0, 0) -> 1.0
This Java code computes the knight probability via forward DP, with each step replacing the dp matrix by the next step's probability distribution.
Step-by-Step Walkthrough
Tracing knightProbability(3, 2, 0, 0):
graph LR
F0["dp[0]: only (0,0) = 1.0"]
F1["step 0 → step 1: from (0,0), 8 knight moves; only 2 land on board: (1,2) and (2,1); each gets 1/8 = 0.125"]
F2["step 1 → step 2: from (1,2), 8 moves; 2 stay on board: (0,0), (2,0); each adds 0.125 / 8 = 0.015625 to those cells. Same from (2,1): adds 0.015625 to (0,2) and (0,0)"]
F3["Total on-board prob after step 2 = sum of all dp[2][r][c] = 0.0625"]
F0 --> F1 --> F2 --> F3
style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
This walkthrough computes the knight probability for n equals three and k equals two: starting at the corner, only two moves stay on board, then from each only two further moves stay on board, giving 0.0625.
Result: 0.0625.
Complexity
Time: O(k · n² · 8). Space: O(n²) for two layers.
Approach 2: 2-Layer Space-Optimized - Optimal
The implementation above already uses two layers via the next array - that is the space-optimized version. The "k layers" version would require O(k · n²) space; the 2-layer version is O(n²). For k = 100 and n = 25, the savings are real (100 · 625 = 62,500 vs. just 1,250).
Complexity Comparison
| Approach | Time | Space | Key Idea |
|---|---|---|---|
| 2-layer forward DP | O(k · n² · 8) | O(n²) | propagate probability mass step by step, replacing the dp layer each iteration |
The 2-layer forward DP is the canonical and optimal solution. The mass-conservation property (mass that goes off-board is lost) handles the "knight falls off" case automatically.
Variations & Follow-ups
Why does mass "lost off-board" represent the failure outcome?
At each step, each cell's probability mass is divided into 8 equal portions, one per knight move. If a destination is off-board, that portion is "lost" - the knight has fallen off. The mass not lost is the probability that the knight is still on the board. After k steps, summing all on-board cells gives the survival probability. This is a clean probability bookkeeping technique: instead of tracking failure explicitly, we track success and let the "lost" mass implicitly represent failure. The general principle: forward Probability DPs handle absorbing events (failure, success) by either (a) explicit absorbing-state tracking or (b) letting probability mass "leak out" via dropped transitions. The leak-out style is simpler when failure is irreversible.
Why forward DP and not backward?
Backward would be: dp[step][r][c] = probability of staying on board for remaining step moves starting from (r, c). Both formulations work; the recurrence is symmetric. The forward formulation is slightly more intuitive here because the question is "after k moves from start, where is the knight?" - naturally a forward question.
For "expected steps to escape the board" (a different question), backward DP would be more natural - start with dp[end][r][c] = 0 for the boundary, work backward.
How does this differ from a standard random walk on a grid?
A standard random walk has 4 cardinal moves (up/down/left/right). The knight has 8 L-shaped moves. The DP structure is identical; only the moves array changes. The general principle: forward Probability DPs on grids parameterize over the move set; changing the set changes the transitions, not the framework.
Can we use matrix exponentiation for very large k?
Yes - the DP is a linear operation on the n² probability vector. The transition matrix is n² × n² (each cell to its 8 neighbors, scaled by 1/8). For very large k (e.g., k = 10^9), matrix exponentiation in O(n^6 log k) is much faster than O(k · n²). For the problem's constraint (k ≤ 100), the naive DP is faster and simpler. Matrix exponentiation becomes relevant when k > n².
What about edge cases?
- n = 1, k = 0: Knight stays at (0,0); probability 1.0.
- n = 1, k = 1: Any move goes off the 1×1 board; probability 0.0.
- k = 0: Trivially probability 1.0 (knight is on board at start).
- Large k, small n: Probability approaches 0 - eventually mass leaks off the board.
Common Interview Pitfalls
- Allocating a 3-D array dp[k+1][n][n]. Wastes memory; 2 layers suffice.
- Iterating over destination cells (pulling) when the forward formulation is more natural. Forward pushes from source; backward pulls into destination. Mixing them confuses the recurrence.
- Forgetting to scale by 1/8. Each of the 8 moves is equally likely; the per-move probability is 1/8.
- Floating-point precision. Acceptable here; sum-to-one might drift slightly across many steps but the answer is robust to small errors.
Why This Topic Matters
Knight Probability in Chessboard is the canonical forward Probability DP: state = (step, row, col), value = probability of being at that cell, transitions weighted by move probabilities (1/8 each). The mass-conservation property (mass leaking off the board represents failure) cleanly handles the "knight falls off" case. The 2-layer space optimization mirrors the standard DP optimization. The pattern - forward propagation of probability mass through a state graph - applies to all grid-based random walks, Markov chain simulations, and stochastic-process modeling on bounded domains.
The next topic, Soup Servings, is a backward Probability DP with a clever asymptotic shortcut: there are two types of soup, A and B, initially with N ml each. Each turn, one of four serving patterns is chosen uniformly: (A 100, B 0), (A 75, B 25), (A 50, B 50), (A 25, B 75). Find the probability that soup A finishes first, plus half the probability they finish simultaneously. The DP defines dp[a][b] = probability of A finishing first (plus half tie) starting from a ml A and b ml B. Recursion via the four equally-likely transitions. For large N (>4800), the probability converges to 1.0 - an asymptotic shortcut that lets the DP cap at ~4800. It demonstrates backward Probability DP with asymptotic convergence handling.