Knight Probability in Chessboard: Layer-by-Layer DP

You have a knight on an n x n chessboard. It starts at position (row, column) and makes exactly k moves. Each move is chosen uniformly at random from the 8 possible knight moves. What is the probability that the knight is still on the board after all k moves? This is LeetCode 688: Knight Probability in Chessboard, and it is a clean example of layer-by-layer DP on a grid where you spread probability instead of counting paths.

The key insight is that you do not need to simulate every random walk. Instead, you track a probability grid that tells you "how likely is the knight to be at each cell after step moves?" and update it one layer at a time.

From (2, 1), the knight has 4 on-board moves and 4 off-board moves. Each move has probability 1/8, so after one step the knight stays on the board with probability 4/8 = 0.5.

The approach: DP layer by layer

Define dp[step][r][c] as the probability that the knight is at cell (r, c) after exactly step moves. The base case is simple: dp[0][row][col] = 1.0 and everything else is 0, because the knight starts at the given position with certainty.

For each subsequent step, you iterate over every cell. If the knight has some probability of being at (r, c), it moves to each of its 8 neighbors with probability 1/8. So you divide dp[step][r][c] by 8 and add that fraction to each neighbor that is still inside the board. Any move that lands outside the board is simply lost, which is what reduces the total probability over time.

After k steps, the answer is the sum of dp[k][r][c] over all cells on the board. That total represents the probability that the knight never left.

You only need two layers at a time (the current step and the next step), so you can optimize space to O(n^2) instead of O(n^2 * k).

def knightProbability(n: int, k: int, row: int, column: int) -> float:
    dp = [[0.0] * n for _ in range(n)]
    dp[row][column] = 1.0
    directions = [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]
    for _ in range(k):
        new_dp = [[0.0] * n for _ in range(n)]
        for r in range(n):
            for c in range(n):
                if dp[r][c] > 0:
                    for dr, dc in directions:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < n and 0 <= nc < n:
                            new_dp[nr][nc] += dp[r][c] / 8
        dp = new_dp
    return sum(dp[r][c] for r in range(n) for c in range(n))

Step-by-step walkthrough

Let's trace through the algorithm on a small board to see how probability flows. We will use a 3x3 board to keep things compact and show two different starting positions so you can see the mechanics clearly.

Notice how the total probability shrinks at each step. Every time the knight makes a move, some of that probability "falls off" the edge of the board. The faster the probability drops, the less likely the knight is to survive all k moves. Corner and edge positions lose probability much faster than center positions, because fewer of the knight's 8 moves land on the board.

Complexity analysis

Time: You perform k iterations. In each iteration you visit all n^2 cells, and for each cell you check 8 directions. That gives O(8 * n^2 * k), which simplifies to O(n^2 * k).

Space: You only store two n-by-n grids at a time (the current layer and the next layer), so the space is O(n^2). If you stored all layers explicitly, it would be O(n^2 * k), but the rolling-array optimization avoids that.

The building blocks

Layer-by-layer DP on a grid

This problem belongs to a family where you have a 2D grid and a number of steps, and you build the solution one step at a time. At each layer, every cell's value depends on its neighbors in the previous layer. You have seen this pattern in problems like Unique Paths and Minimum Path Sum, but those only move forward (right or down). Here the knight can jump in 8 directions, which makes the neighbor set larger but does not change the core technique.

The general recipe is: define what each cell means at each step, figure out which cells contribute to which, and sweep through the grid layer by layer. The rolling-array trick (keeping only two layers) almost always applies.

Probability spreading

Instead of counting paths, you spread probability. Each cell distributes its value equally among its valid neighbors. This is the same idea behind random walks and Markov chains. The total probability across the board starts at 1.0 and can only decrease (since some moves go off the board). It never increases. This monotonic decrease is what makes the problem well-behaved and guarantees the answer is between 0 and 1.

Edge cases

• k = 0: The knight makes no moves, so it is guaranteed to remain on the board. Return 1.0.
• n = 1: The board is a single cell. Any knight move from a 1x1 board goes off the board. If k = 0, return 1.0. If k > 0, return 0.0 because all 8 moves leave the grid.
• Knight starts in a corner on a small board: Corners have the fewest on-board knight destinations. On a 3x3 board, a corner cell has only 2 valid knight moves out of 8, so probability drops quickly.
• Large k with center start on a large board: The probability approaches 0 as k grows, but it does so slowly for center positions on large boards. The algorithm handles this naturally since it just keeps spreading and losing probability.
• All cells have zero probability mid-computation: If at some step the entire grid is 0, every subsequent step will also be 0. You could short-circuit here, but the algorithm still returns the correct answer (0.0) without the optimization.

From understanding to recall

This problem combines two ideas that come up frequently in interviews: grid DP and probability. The layer-by-layer update, the rolling array, and the probability-spreading mechanic are all patterns you will see again in problems like Out of Boundary Paths and random walk simulations. Practicing this problem a few times with spaced repetition will help you internalize the "spread and sum" technique so you can recognize and apply it quickly when a new variant appears.

Related posts

• Out of Boundary Paths - Very similar grid DP where you count paths that leave the boundary, the complementary problem
• Unique Paths - Grid DP with movement constraints, the same layer-by-layer accumulation technique
• Minimum Path Sum - Another grid DP problem that builds solutions cell by cell across the board