Knight Probability in Chessboard
Understanding the Problem
We have a knight on an n x n chessboard, and it makes exactly k random moves. At each step, the knight picks one of its 8 possible L-shaped moves with equal probability (1/8 each). If a move takes the knight off the board, it stays off permanently. We need to find the probability that after all k moves, the knight is still somewhere on the board.
Probability spreads across the board as the knight moves. The knight starts at one cell with probability 1.0. After one move, that probability splits equally among the 8 possible destinations, 1/8 to each. Any probability that lands off the board is gone for good. After k moves, the answer is the sum of whatever probability remains on the board.
This is a dynamic programming problem. The state is (move number, row, column), and we track how probability distributes across the board as the knight makes its moves.
Key Constraints:
1 <= n <= 25-> The board has at most 625 cells, small enough to process every cell on every move step.0 <= k <= 100-> Up to 100 moves. Combined with the board size, a DP over (move, row, column) has at most 100 x 25 x 25 = 62,500 states. That rules out the exponential brute force and makes a polynomial DP comfortable.
Approach 1: Recursive Brute Force
Intuition
Simulate every possible sequence of moves the knight can make. Starting from (row, column), try all 8 moves. For each move that stays on the board, recurse with k-1 remaining moves. When k reaches 0, the knight is still on the board, so that path survives.
Each move has a 1/8 chance of being chosen, so a particular k-move sequence has probability (1/8)^k. Summing over the surviving sequences is the same as averaging the 8 child results at every node: the probability from a cell with m moves left is the average of the probabilities of its 8 destinations with m-1 moves left.
This does not scale. The knight has 8 choices at each of k steps, so the recursion explores 8^k paths. With k up to 100, that count is far beyond what any machine can finish.
Algorithm
- Define a recursive function
solve(n, k, r, c)that returns the probability of staying on the board starting from(r, c)withkmoves left. - Base case: if
(r, c)is outside the board, return 0. Ifk == 0, return 1 (the knight survived all moves). - For each of the 8 knight moves, recursively compute
solve(n, k-1, newR, newC). - Return the average of all 8 recursive results (sum divided by 8).
Example Walkthrough
Code
- Time Complexity: O(8^k). At each step we branch into 8 recursive calls, and there are k levels of recursion. With k up to 100, this is beyond any practical limit.
- Space Complexity: O(k). The recursion stack goes k levels deep. No additional data structures are used.
The same (k, r, c) state gets recomputed every time a different path reaches it. The next approach caches each result the first time it is computed and reuses it afterward.
Approach 2: Top-Down DP (Memoization)
Intuition
The recursive solution repeats enormous amounts of work because solve(k, r, c) depends only on three values: the number of remaining moves and the current position. There are at most k x n x n = 100 x 25 x 25 = 62,500 distinct combinations, yet the brute force evaluates each one many times across different paths. Caching the result of each (k, r, c) the first time it is computed lets every later call with the same parameters return in O(1).
The recursion structure stays the same. The only addition is a 3D memo table: check it before computing, fill it after. That drops the time complexity from exponential to polynomial.
Caching is safe because the probability of surviving from a cell (r, c) with m moves remaining depends only on those three values, not on the path the knight took to reach (r, c). Each move is chosen uniformly at random and independently of past moves, so the future is fully determined by the present state. The same (m, r, c) subproblem therefore has one fixed answer, and storing it once is enough.
Algorithm
- Create a 3D memo array of size
(k+1) x n x n, initialized to -1 (meaning "not yet computed"). - Define
solve(k, r, c): if(r, c)is off the board, return 0. Ifk == 0, return 1. Ifmemo[k][r][c] != -1, return the cached value. - Compute the result by averaging the 8 recursive calls, store it in
memo[k][r][c], and return it.
Example Walkthrough
Code
- Time Complexity: O(k n^2). There are k n * n unique states, and each state does O(8) = O(1) work iterating over the 8 knight moves.
- Space Complexity: O(k n^2). The memo table stores one value for each of the k n * n states. The recursion stack adds O(k) depth, dominated by the memo table.
We store all k layers of the DP table, but computing layer step only reads layer step - 1. The next approach iterates bottom-up and keeps only two layers at a time, cutting the space.
Approach 3: Bottom-Up DP with Space Optimization
Intuition
Instead of the top-down question ("what is the probability of surviving from here?"), work bottom-up ("how does probability spread across the board?").
Start with the knight at (row, column) holding probability 1.0. That is the "current" probability distribution. For each of the k moves, build a "next" distribution by sending each cell's probability to its 8 knight-move destinations, 1/8 to each. Any probability that lands outside the board is dropped.
After all k moves, sum the probabilities across the board. That total is the answer.
This needs only two n x n grids at a time: the current step's probabilities and the next step's. After each move, the "next" grid becomes the "current" grid for the following step, so the space drops from O(k * n^2) to O(n^2).
This is the same DP recurrence as the memoized approach, computed in the opposite direction. Instead of starting from the final state and recursing backward, we start from the initial state and push probability forward one move at a time. The relation is the same: the probability of being at (r, c) after step s equals the sum over all source cells that reach (r, c) by a knight move of (that source's probability after step s-1) / 8. Because a knight move is symmetric, pushing 1/8 forward from each source produces the same totals as pulling from each destination.
Two grids suffice because computing step s reads only from step s-1. Once step s is built, step s-1 is never read again and can be discarded.
Algorithm
- Create a 2D array
currentof size n x n, initialized to all zeros. Setcurrent[row][column] = 1.0. - For each move from 1 to k:
- Create a new 2D array
next, initialized to all zeros. - For each cell
(r, c)wherecurrent[r][c] > 0, distributecurrent[r][c] / 8.0to each on-board knight destination innext. - Set
current = next. - Sum all values in
current. This is the total probability of remaining on the board.
Example Walkthrough
Code
- Time Complexity: O(k * n^2). We iterate k times, and in each iteration we visit all n^2 cells and check 8 moves per cell.
- Space Complexity: O(n^2). We only keep two n x n grids at any time (current and next), a significant improvement over the O(k * n^2) space used by the memoized approach.