Knight Probability in Chessboard
Last Updated: March 28, 2026
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.
The key insight is that probability flows like water through a graph. The knight starts at one cell with probability 1.0. After one move, that probability splits equally among the 8 possible destinations. Any probability that "falls off" the board is lost forever. After k moves, we sum up whatever probability remains on the board.
This is fundamentally a dynamic programming problem. The state is (move number, row, column), and we need to 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. This is small enough for O(n^2) per move step.0 <= k <= 100-> Up to 100 moves. Combined with the board size, a 3D DP with dimensions k x n x n gives at most 100 x 25 x 25 = 62,500 states, which is very manageable.0 <= row, column <= n - 1-> The starting position is always valid (on the board).
Approach 1: Recursive Brute Force
Intuition
The most natural approach is to simulate every possible sequence of moves the knight can make. Starting from (row, column), we try all 8 possible moves. For each move that stays on the board, we recurse with k-1 remaining moves. When k reaches 0, the knight is still on the board, so that path contributes to the probability.
Each move has a 1/8 chance of being chosen. So the probability of a particular k-move sequence is (1/8)^k. We sum up the probabilities of all sequences that keep the knight on the board.
The problem is that the knight has 8 choices at each step, and there are k steps. So the total number of paths is 8^k. With k up to 100, that is astronomically large, way beyond what any computer can handle.
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. What if we cached each result the first time we computed it?
Approach 2: Top-Down DP (Memoization)
Intuition
The recursive solution has a massive amount of redundant work. But notice that the function solve(k, r, c) depends only on three parameters: 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 unique combinations. If we cache the result of each (k, r, c) the first time we compute it, every subsequent call with the same parameters returns instantly.
This is classic memoization. The recursion structure stays exactly the same, but we add a 3D memo table. Before computing, we check if we already have the answer. After computing, we store it. This single change drops the time complexity from exponential to polynomial.
The memoization works because the probability of surviving from any cell (r, c) with m moves remaining is completely determined by those three values. It does not matter how the knight arrived at (r, c). This is the optimal substructure property: the solution to the overall problem is built from solutions to independent subproblems, and those subproblems overlap heavily across different paths.
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 to compute layer step, we only need layer step - 1. What if we iterated bottom-up and only kept two layers at a time?
Approach 3: Bottom-Up DP with Space Optimization
Intuition
Instead of thinking top-down ("what is the probability of surviving from here?"), we can think bottom-up ("how does probability spread across the board?").
Start with the knight at (row, column) with probability 1.0. This is our "current" probability distribution. Then for each of the k moves, we create a "next" distribution by spreading each cell's probability to its 8 knight-move destinations. Any probability that lands outside the board simply vanishes.
After processing all k moves, we sum up the probabilities across the entire board. That total is our answer.
The beauty of this approach is that we only ever need two n x n grids: the current step's probabilities and the next step's probabilities. After processing each move, the "next" grid becomes the "current" grid for the following step. This brings the space down from O(k * n^2) to O(n^2).
This is the same DP recurrence as the memoized approach, just computed in a different order. Instead of starting from the final state and working backward via recursion, we start from the initial state and push probability forward through each move. The math is identical: the probability of being at cell (r, c) after step s equals the sum of (probability at source cell after step s-1) / 8, taken over all source cells that can reach (r, c) via a knight move.
The space optimization works because when computing step s, we only read from step s-1. Once we are done with step s-1, we never look at it again. So two grids are all we need.
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:
a. Create a new 2D array next, initialized to all zeros.
b. For each cell (r, c) where current[r][c] > 0, distribute current[r][c] / 8.0 to each on-board knight destination in next.
c. 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.