Knight Probability in Chessboard (LeetCode 688)
A knight starts on the square (row, column) of an n x n chessboard and makes exactly k moves. A knight move goes two squares in one direction and one square in the other, so from most squares it has 8 possible moves.
At every move, the knight picks one of its 8 moves with equal chance, even when that move would take it off the board. Once the knight is off the board, it stays off.
Return the probability that the knight is still on the board after it has made k moves.
Worked Examples
n = 3, k = 2, row = 0, column = 00.0625(1, 2) and (2, 1). From each of those, two of the eight moves stay on again. So the probability is 2/8 * 2/8 = 0.0625.n = 1, k = 0, row = 0, column = 01.01.0.⚖️Formal Constraints & Bounds
1 <= n <= 250 <= k <= 1000 <= row, column <= n - 1
Core Insight
Give every square the probability of the knight being there after the moves made so far, and build the next step by passing each square's share, one eighth per move, to the targets on the board: the share that falls off the board is added nowhere, so the total left on the board is the answer.
Real-World Scenario & Production Applications
Any process that moves between states by chance and can be lost for good: a particle that random-walks until it leaves a region, a customer who may churn at each step, or a system whose chance of surviving a number of random failures you want to know.
Step-by-Step Execution Trace Table
Trace of Example 1: n = 3, k = 2, the knight starts on (0, 0), so dp[0][0] = 1.0. After each move, dp shows the probability of every square, row by row.
| Move | dp after the move (rows) | Probability still on the board |
|---|---|---|
| 1 | [0.0, 0.0, 0.0]; [0.0, 0.0, 0.125]; [0.0, 0.125, 0.0] | 0.25 |
| 2 | [0.03125, 0.0, 0.01562]; [0.0, 0.0, 0.0]; [0.01562, 0.0, 0.0] | 0.0625 |
After move 1, the corner's two on-board targets (1, 2) and (2, 1) hold 1/8 each. After move 2, each of them has two moves that stay on the board, so 4 * (1/8) * (1/8) = 0.0625 remains.
| 1 | `dp[r][c]` is the probability that the knight is on `(r, c)` after the moves made so far; `dp[row][column] = 1.0`. |
| 2 | For each of the `k` moves, build `nxt`: every square passes `dp[r][c] / 8` to each of its 8 targets that is on the board. |
| 3 | A target off the board adds nothing, so its share is gone. Then `dp = nxt`. |
| 4 | Return `sum(sum(line) for line in dp)`. The trap: dividing by 8 once at the end, or not at all, counts paths, not probability. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
In a probability problem, a state does not hold a best value or a count: it holds a chance. Probability DP gives every state the probability of being there after the steps made so far, and each step spreads every state's probability over the states it can move to, weighted by how likely each move is. The answer is the total probability on the states that count.
🎲 The Analogy: Pouring Water Through Pipes
Imagine one litre of water on the knight's start square. Each step, every square pours its water equally into its 8 target squares. Water poured off the board is gone. After k steps, the water left on the board is the probability that the knight stayed on the board.
🔑 The Key Idea in the Code
nxt is built from dp and then replaces it, so a step never reads the share it has just received. The share that falls off the board is not added anywhere, which removes it for every later step.
Forgetting the chance of each move: each move has chance
1 / 8, so a square passesdp[r][c] / 8, notdp[r][c]. Without the division the table counts paths and the answer is far above 1.Letting the knight wrap around the edge: a move off the board ends the walk. Taking
nr % nkeeps the knight on a torus, which gives a larger, wrong probability.Updating
dpin place: a square read after it received a share would pass that share on in the same step, so the knight moves twice in one step. Buildnxtand replacedpafter the pass.Reading only the start square: the answer is the total over every square, because the knight may end anywhere on the board.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The probability that the knight is still on the board after k random moves": every move is equally likely, the board is the set of states, and a state that is left is lost for good. A question about a chance that depends on a number of steps, with the same rule at each step, points to Probability DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
dp[r][c] is the probability that the knight stands on (r, c) after the moves made so far without having left. One step builds nxt from dp: each square adds dp[r][c] / 8 to each of its 8 targets that is on the board. The answer is the total of the table after k steps.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Probability DP. Let dp of r, c be the probability that the knight is on square r, c after the moves made so far and has never left the board. At the start it is one on the start square. For each of the k moves, I build a fresh board: every square passes its probability divided by eight to each of its eight targets that is still on the board, and a target off the board adds nothing, so that share is gone for good. After k moves, the total of all squares is the probability that the knight is still on the board. That is order K times N squared time and order N squared space.
Complexity & Mathematical Proof
O(K * N^2)
Look at the loops. The outer loop runs k times. Each pass visits every one of the n * n squares, and for each square the inner loop tries the 8 moves, each one a constant-time check and addition. That is k * n^2 * 8 steps, so time is O(K * N^2). The board is at most 25 x 25 and k at most 100, so there are about 500,000 steps.
O(N^2)
dp and nxt are each an n x n table: O(N^2). Only two boards exist at a time, whatever k is, because nxt replaces dp after every pass. There is no recursion.
Derivation Progression
for _ in range(k) builds the board after one more move, once for each move.
for r and for c visit every square of the board in each pass.
8 = O(1)
for dr, dc in moves tries 8 moves, each one a bounds check and an addition.
Steps times squares times a constant number of moves.
Variable Definitions
Board size, n
Number of moves, k
Probability that the knight is on square (r, c) after the moves made so far
Memory Architecture & Bounds
O(1): loops only, no recursion
O(N^2): the boards dp and nxt, two N x N tables at a time
O(1): one real number
Boundary Best / Worst Cases
: every pass visits every square, whatever the start square is.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the probability that the knight is still on the board", "each move is equally likely". The state is a square, the rule is the same at every step, and a lost walk never returns, so this is Probability DP: pass each square's share to its targets, one step at a time.
and , so the table has squares and the loops do about steps: well under a millisecond in a compiled language. Following every sequence of moves is . The answer is a probability, so a double is enough; answers within are accepted.
A double keeps about 15 digits, and the probabilities after 100 steps can be tiny (about in a corner), which is still a valid double. Summing many tiny values is accurate here, because every term is non-negative. For an exact answer, use fractions, but the table then grows with in the denominators.
Knight Probability in Chessboard (LeetCode 688)
A knight starts on the square (row, column) of an n x n chessboard and makes exactly k moves. A knight move goes two squares in one direction and one square in the other, so from most squares it has 8 possible moves.
At every move, the knight picks one of its 8 moves with equal chance, even when that move would take it off the board. Once the knight is off the board, it stays off.
Return the probability that the knight is still on the board after it has made k moves.
Worked Examples
n = 3, k = 2, row = 0, column = 00.0625(1, 2) and (2, 1). From each of those, two of the eight moves stay on again. So the probability is 2/8 * 2/8 = 0.0625.n = 1, k = 0, row = 0, column = 01.01.0.⚖️Formal Constraints & Bounds
1 <= n <= 250 <= k <= 1000 <= row, column <= n - 1
Core Insight
Give every square the probability of the knight being there after the moves made so far, and build the next step by passing each square's share, one eighth per move, to the targets on the board: the share that falls off the board is added nowhere, so the total left on the board is the answer.
Real-World Scenario & Production Applications
Any process that moves between states by chance and can be lost for good: a particle that random-walks until it leaves a region, a customer who may churn at each step, or a system whose chance of surviving a number of random failures you want to know.
Step-by-Step Execution Trace Table
Trace of Example 1: n = 3, k = 2, the knight starts on (0, 0), so dp[0][0] = 1.0. After each move, dp shows the probability of every square, row by row.
| Move | dp after the move (rows) | Probability still on the board |
|---|---|---|
| 1 | [0.0, 0.0, 0.0]; [0.0, 0.0, 0.125]; [0.0, 0.125, 0.0] | 0.25 |
| 2 | [0.03125, 0.0, 0.01562]; [0.0, 0.0, 0.0]; [0.01562, 0.0, 0.0] | 0.0625 |
After move 1, the corner's two on-board targets (1, 2) and (2, 1) hold 1/8 each. After move 2, each of them has two moves that stay on the board, so 4 * (1/8) * (1/8) = 0.0625 remains.
| 1 | `dp[r][c]` is the probability that the knight is on `(r, c)` after the moves made so far; `dp[row][column] = 1.0`. |
| 2 | For each of the `k` moves, build `nxt`: every square passes `dp[r][c] / 8` to each of its 8 targets that is on the board. |
| 3 | A target off the board adds nothing, so its share is gone. Then `dp = nxt`. |
| 4 | Return `sum(sum(line) for line in dp)`. The trap: dividing by 8 once at the end, or not at all, counts paths, not probability. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
In a probability problem, a state does not hold a best value or a count: it holds a chance. Probability DP gives every state the probability of being there after the steps made so far, and each step spreads every state's probability over the states it can move to, weighted by how likely each move is. The answer is the total probability on the states that count.
🎲 The Analogy: Pouring Water Through Pipes
Imagine one litre of water on the knight's start square. Each step, every square pours its water equally into its 8 target squares. Water poured off the board is gone. After k steps, the water left on the board is the probability that the knight stayed on the board.
🔑 The Key Idea in the Code
nxt is built from dp and then replaces it, so a step never reads the share it has just received. The share that falls off the board is not added anywhere, which removes it for every later step.
Forgetting the chance of each move: each move has chance
1 / 8, so a square passesdp[r][c] / 8, notdp[r][c]. Without the division the table counts paths and the answer is far above 1.Letting the knight wrap around the edge: a move off the board ends the walk. Taking
nr % nkeeps the knight on a torus, which gives a larger, wrong probability.Updating
dpin place: a square read after it received a share would pass that share on in the same step, so the knight moves twice in one step. Buildnxtand replacedpafter the pass.Reading only the start square: the answer is the total over every square, because the knight may end anywhere on the board.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The probability that the knight is still on the board after k random moves": every move is equally likely, the board is the set of states, and a state that is left is lost for good. A question about a chance that depends on a number of steps, with the same rule at each step, points to Probability DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
dp[r][c] is the probability that the knight stands on (r, c) after the moves made so far without having left. One step builds nxt from dp: each square adds dp[r][c] / 8 to each of its 8 targets that is on the board. The answer is the total of the table after k steps.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Probability DP. Let dp of r, c be the probability that the knight is on square r, c after the moves made so far and has never left the board. At the start it is one on the start square. For each of the k moves, I build a fresh board: every square passes its probability divided by eight to each of its eight targets that is still on the board, and a target off the board adds nothing, so that share is gone for good. After k moves, the total of all squares is the probability that the knight is still on the board. That is order K times N squared time and order N squared space.
Complexity & Mathematical Proof
O(K * N^2)
Look at the loops. The outer loop runs k times. Each pass visits every one of the n * n squares, and for each square the inner loop tries the 8 moves, each one a constant-time check and addition. That is k * n^2 * 8 steps, so time is O(K * N^2). The board is at most 25 x 25 and k at most 100, so there are about 500,000 steps.
O(N^2)
dp and nxt are each an n x n table: O(N^2). Only two boards exist at a time, whatever k is, because nxt replaces dp after every pass. There is no recursion.
Derivation Progression
for _ in range(k) builds the board after one more move, once for each move.
for r and for c visit every square of the board in each pass.
8 = O(1)
for dr, dc in moves tries 8 moves, each one a bounds check and an addition.
Steps times squares times a constant number of moves.
Variable Definitions
Board size, n
Number of moves, k
Probability that the knight is on square (r, c) after the moves made so far
Memory Architecture & Bounds
O(1): loops only, no recursion
O(N^2): the boards dp and nxt, two N x N tables at a time
O(1): one real number
Boundary Best / Worst Cases
: every pass visits every square, whatever the start square is.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the probability that the knight is still on the board", "each move is equally likely". The state is a square, the rule is the same at every step, and a lost walk never returns, so this is Probability DP: pass each square's share to its targets, one step at a time.
and , so the table has squares and the loops do about steps: well under a millisecond in a compiled language. Following every sequence of moves is . The answer is a probability, so a double is enough; answers within are accepted.
A double keeps about 15 digits, and the probabilities after 100 steps can be tiny (about in a corner), which is still a valid double. Summing many tiny values is accurate here, because every term is non-negative. For an exact answer, use fractions, but the table then grows with in the denominators.