688. Knight Probability in Chessboard

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex Pitfalls

Problem Description

You have an n x n chessboard with a knight piece starting at position (row, column). The board uses 0-based indexing, meaning the top-left corner is (0, 0) and the bottom-right corner is (n - 1, n - 1).

A knight in chess moves in an "L" shape - it moves two squares in one direction (horizontal or vertical) and then one square perpendicular to that direction. This gives the knight 8 possible moves from any position.

The knight will make exactly k moves. For each move, it randomly chooses one of the 8 possible moves with equal probability (1/8 chance for each move), regardless of whether that move would take it off the board. If the knight moves off the board, it cannot return.

Your task is to calculate the probability that after making exactly k moves, the knight is still on the chessboard.

For example, if n = 3, k = 2, and the knight starts at (0, 0):

The knight has 8 possible first moves, but only 2 keep it on the board
From each valid position after the first move, some second moves keep it on board and others don't
The final probability is the sum of all paths that keep the knight on board, weighted by their probabilities

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

DP over (moves, row, col) sums probabilities from the eight knight predecessors divided by 8.

Open in Flowchart

Intuition

Simulating every sequence of moves is too slow: with k moves and 8 choices per move there are 8^k paths. Many of these paths pass through the same square with the same number of moves left, though, and from that point on they behave identically. That repeated work points to dynamic programming.

The useful question to ask about a square is: "If the knight stands on (i, j) and still has h moves to make, what is the probability that it is on the board after all of them?" Call this value dp[h][i][j].

With h = 0 moves left, the knight is already on the board, so dp[0][i][j] = 1 for every square.

With h moves left, the knight picks one of the 8 moves, each with probability 1/8. A move that leaves the board ends that path with probability 0 of staying on. A move that lands on (x, y) leaves h - 1 moves to make from there, which succeeds with probability dp[h-1][x][y]. So:

dp[h][i][j] = sum of dp[h-1][x][y] / 8 over the on-board squares (x, y) one knight move from (i, j)

Computing the table for h = 1, 2, ..., k builds each layer from the previous one. The answer is dp[k][row][column]: the probability of staying on the board when starting from the given square with all k moves still to make.

Pattern Learn more about Dynamic Programming patterns.

Uses dynamic programmingNew to the pattern? This video builds dynamic programming up from scratch.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

We implement the solution using a 3D dynamic programming array dp[h][i][j] where:

h is the number of moves still to be made (from 0 to k)
i and j are the knight's current position on the board
the value is the probability that the knight is still on the board after making those h moves from (i, j)

Initialization: We create a 3D array with dimensions (k+1) × n × n. For the base case h = 0 (no moves left), we set dp[0][i][j] = 1 for every square, because a knight that is on the board and makes no more moves stays on the board.

State Transition: For each h from 1 to k and each square (i, j), we look at the 8 squares one knight move away.

The knight has 8 possible moves, represented by the displacement pairs:

(-2, -1), (-2, 1), (2, -1), (2, 1) - moving 2 squares vertically, 1 horizontally
(-1, -2), (-1, 2), (1, -2), (1, 2) - moving 2 squares horizontally, 1 vertically

The code stores these in the list knight_moves. For each square (r, c) and each offset, it computes the neighbor (r + row_offset, c + col_offset):

If the neighbor is on the board, the knight can move there and then has h - 1 moves left, so we add dp[h-1][neighbor] / 8
If the neighbor is off the board, that move contributes 0
The division by 8 is the probability of choosing that particular move

(The code names the neighbor prev_row, prev_col. Because the set of knight moves is symmetric, the squares one move away from (r, c) are the same squares that can reach (r, c) in one move, so either reading gives the same sum.)

Mathematical Formula:

dp[h][i][j] = Σ (dp[h-1][x][y] / 8)

where the sum is over all on-board squares (x, y) one knight move from (i, j).

Final Answer: After filling the table, dp[k][row][column] is the probability that the knight remains on the board after exactly k moves starting from (row, column).

The time complexity is O(k × n² × 8) = O(k × n²) since we visit every square for each value of h and check 8 neighbors. The space complexity is O(k × n²) for the 3D DP array.

Example Walkthrough

Let's walk through a small example with n = 3 (3×3 board), k = 2 moves, starting at position (0, 0).

Base Case (h = 0): We create dp with 3 layers of 3×3 and set every entry of dp[0] to 1:

dp[0] = [[1, 1, 1],
         [1, 1, 1],
         [1, 1, 1]]

With no moves left, a knight on any square is on the board.

One Move Left (h = 1): dp[1][i][j] is the number of on-board knight moves from (i, j) divided by 8.

For (0, 0): the moves land on (2, 1) and (1, 2); the other 6 leave the board.

dp[1][0][0] = dp[0][2][1]/8 + dp[0][1][2]/8 = 1/8 + 1/8 = 1/4

For (0, 1): the moves land on (2, 0) and (2, 2), so dp[1][0][1] = 2/8 = 1/4.

For the center (1, 1): every knight move leaves a 3×3 board, so dp[1][1][1] = 0.

By symmetry, every corner and every edge square has exactly 2 on-board moves:

dp[1] = [[1/4, 1/4, 1/4],
         [1/4,  0,  1/4],
         [1/4, 1/4, 1/4]]

Two Moves Left (h = 2): We need dp[2][0][0]. From (0, 0) the only on-board moves go to (2, 1) and (1, 2):

dp[2][0][0] = dp[1][2][1]/8 + dp[1][1][2]/8 = (1/4)/8 + (1/4)/8 = 1/32 + 1/32 = 1/16

Final Answer: dp[2][0][0] = 1/16 = 0.0625 is the probability that the knight remains on the board after exactly 2 moves starting from (0, 0).

This matches a direct count: from (0, 0), 2 of the 8 first moves stay on the board, and from each of those squares 2 of the 8 second moves stay on the board, so (2/8) × (2/8) = 1/16.

Solution Implementation

1class Solution:
2    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
3        # dp[moves][r][c] represents the probability of knight staying on board
4        # after 'moves' moves starting from position (r, c)
5        dp = [[[0.0] * n for _ in range(n)] for _ in range(k + 1)]
6      
7        # Base case: with 0 moves, knight is always on board (probability = 1)
8        for r in range(n):
9            for c in range(n):
10                dp[0][r][c] = 1.0
11      
12        # All 8 possible knight moves: (row_offset, col_offset)
13        knight_moves = [
14            (-2, -1), (-2, 1), (-1, -2), (-1, 2),
15            (1, -2), (1, 2), (2, -1), (2, 1)
16        ]
17      
18        # Fill the dp table for each number of moves from 1 to k
19        for moves in range(1, k + 1):
20            for r in range(n):
21                for c in range(n):
22                    # For each position, calculate probability by summing
23                    # probabilities from all valid previous positions
24                    for row_offset, col_offset in knight_moves:
25                        prev_row = r + row_offset
26                        prev_col = c + col_offset
27                      
28                        # Check if the previous position is within the board
29                        if 0 <= prev_row < n and 0 <= prev_col < n:
30                            # Add probability from previous position divided by 8
31                            # (since knight has 8 possible moves)
32                            dp[moves][r][c] += dp[moves - 1][prev_row][prev_col] / 8.0
33      
34        # Return the probability at the starting position after k moves
35        return dp[k][row][column]
36

1class Solution {
2    public double knightProbability(int n, int k, int row, int column) {
3        // dp[moves][r][c] represents the probability of knight staying on board
4        // after 'moves' moves starting from position (r, c)
5        double[][][] dp = new double[k + 1][n][n];
6      
7        // Base case: with 0 moves, knight is definitely on board (probability = 1)
8        for (int i = 0; i < n; i++) {
9            for (int j = 0; j < n; j++) {
10                dp[0][i][j] = 1.0;
11            }
12        }
13      
14        // Knight moves in chess: 8 possible L-shaped moves
15        // Each pair of consecutive elements represents (deltaRow, deltaCol)
16        int[] directions = {-2, -1, -2, 1, -1, -2, -1, 2, 1, -2, 1, 2, 2, -1, 2, 1};
17      
18        // Calculate probability for each number of moves from 1 to k
19        for (int move = 1; move <= k; move++) {
20            // For each position on the board
21            for (int currentRow = 0; currentRow < n; currentRow++) {
22                for (int currentCol = 0; currentCol < n; currentCol++) {
23                    // Try all 8 possible knight moves
24                    for (int dir = 0; dir < 8; dir++) {
25                        int prevRow = currentRow + directions[dir * 2];
26                        int prevCol = currentCol + directions[dir * 2 + 1];
27                      
28                        // Check if the previous position is within board boundaries
29                        if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
30                            // Add probability from previous position divided by 8
31                            // (since knight has 8 equally likely moves)
32                            dp[move][currentRow][currentCol] += dp[move - 1][prevRow][prevCol] / 8.0;
33                        }
34                    }
35                }
36            }
37        }
38      
39        // Return the probability of staying on board after k moves from (row, column)
40        return dp[k][row][column];
41    }
42}
43

1class Solution {
2public:
3    double knightProbability(int n, int k, int row, int column) {
4        // dp[move][i][j] represents the probability of the knight being at position (i, j) 
5        // after 'move' moves
6        double dp[k + 1][n][n];
7        memset(dp, 0, sizeof(dp));
8      
9        // Initialize: after 0 moves, the knight is at its starting position with probability 1
10        // We set all positions to 1 because we'll calculate backwards
11        for (int i = 0; i < n; ++i) {
12            for (int j = 0; j < n; ++j) {
13                dp[0][i][j] = 1.0;
14            }
15        }
16      
17        // Knight can move in 8 directions: 
18        // (-2,-1), (-2,+1), (+2,-1), (+2,+1), (-1,-2), (-1,+2), (+1,-2), (+1,+2)
19        int knightMoves[9] = {-2, -1, 2, 1, -2, 1, 2, -1, -2};
20      
21        // Calculate probability for each number of moves
22        for (int moveCount = 1; moveCount <= k; ++moveCount) {
23            // For each position on the board
24            for (int i = 0; i < n; ++i) {
25                for (int j = 0; j < n; ++j) {
26                    // Check all 8 possible previous positions the knight could have come from
27                    for (int direction = 0; direction < 8; ++direction) {
28                        int prevRow = i + knightMoves[direction];
29                        int prevCol = j + knightMoves[direction + 1];
30                      
31                        // If the previous position is valid (within board boundaries)
32                        if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
33                            // Add the probability of being at the previous position divided by 8
34                            // (since knight has 8 possible moves from any position)
35                            dp[moveCount][i][j] += dp[moveCount - 1][prevRow][prevCol] / 8.0;
36                        }
37                    }
38                }
39            }
40        }
41      
42        // Return the probability of the knight being at the starting position after k moves
43        return dp[k][row][column];
44    }
45};
46

1/**
2 * Calculates the probability that a knight remains on the board after exactly k moves
3 * @param n - The size of the n x n chessboard
4 * @param k - The number of moves the knight will make
5 * @param row - The starting row position of the knight
6 * @param column - The starting column position of the knight
7 * @returns The probability that the knight remains on the board
8 */
9function knightProbability(n: number, k: number, row: number, column: number): number {
10    // Create a 3D DP array: dp[move][row][col]
11    // dp[h][i][j] represents the probability of reaching position (i, j) after h moves
12    const dp: number[][][] = Array.from({ length: k + 1 }, () =>
13        Array.from({ length: n }, () => Array(n).fill(0)),
14    );
15  
16    // Initialize: probability of being at any position after 0 moves is 1
17    // (assuming we start from a valid position)
18    for (let i = 0; i < n; ++i) {
19        for (let j = 0; j < n; ++j) {
20            dp[0][i][j] = 1;
21        }
22    }
23  
24    // Knight moves: 8 possible directions
25    // Pairs of (row offset, column offset) for each knight move
26    const knightMoves: number[] = [-2, -1, 2, 1, -2, 1, 2, -1, -2];
27  
28    // Calculate probabilities for each number of moves
29    for (let moves = 1; moves <= k; ++moves) {
30        // For each position on the board
31        for (let currentRow = 0; currentRow < n; ++currentRow) {
32            for (let currentCol = 0; currentCol < n; ++currentCol) {
33                // Check all 8 possible knight moves
34                for (let direction = 0; direction < 8; ++direction) {
35                    // Calculate the previous position that could lead to current position
36                    const previousRow: number = currentRow + knightMoves[direction];
37                    const previousCol: number = currentCol + knightMoves[direction + 1];
38                  
39                    // If the previous position is valid (within board boundaries)
40                    if (previousRow >= 0 && previousRow < n && previousCol >= 0 && previousCol < n) {
41                        // Add the probability of reaching current position from previous position
42                        // Divide by 8 since knight has 8 equally likely moves
43                        dp[moves][currentRow][currentCol] += dp[moves - 1][previousRow][previousCol] / 8;
44                    }
45                }
46            }
47        }
48    }
49  
50    // Return the probability of being at the starting position after k moves
51    return dp[k][row][column];
52}
53

Time and Space Complexity

The time complexity of this code is O(k × n^2). The analysis breaks down as follows:

The outermost loop iterates k times (from 1 to k)
For each iteration of k, there are two nested loops that each iterate n times, giving us n^2 iterations
Inside the innermost loops, the code checks the 8 knight move directions in knight_moves, which is a constant factor
Therefore, the total time complexity is O(k × n^2 × 8) = O(k × n^2)

The space complexity is O(k × n^2). This is because:

The 3D array dp has dimensions (k+1) × n × n
This stores the probability values for each cell on the board at each step from 0 to k
The total space required is therefore O((k+1) × n^2) = O(k × n^2)

Here, k represents the number of moves the knight can make, and n represents the size of the n × n chessboard.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing the Direction of Dynamic Programming

The Pitfall: Many developers mistakenly interpret the DP state incorrectly. They think dp[h][i][j] represents "the probability of reaching position (i,j) after h moves starting from the initial position (row, column)". This leads to incorrect initialization and state transitions.

Why This Happens: The problem statement asks for the probability of staying on board after k moves starting from a specific position, which can be ambiguous about whether we're tracking forward from the start or backward from all positions.

The Correct Interpretation: dp[h][i][j] actually represents "the probability of staying on the board for the remaining h moves if the knight is currently at position (i,j)". This is a backward DP approach where:

dp[0][i][j] = 1 for all valid positions (with 0 moves left, we're definitely on board)
We work backwards to calculate dp[k][row][column]

2. Incomplete or Asymmetric Move List

The Pitfall:

# WRONG: only 4 of the 8 knight moves
knight_moves = [(-2, -1), (-2, 1), (2, -1), (2, 1)]

Why This Happens: It is easy to list only the "2 rows, 1 column" moves and forget the "1 row, 2 columns" moves. Each move still has probability 1/8, so a missing move silently counts as a move off the board. For n = 3, k = 1, (row, column) = (0, 0), this list finds only (2, 1) and returns 0.125 instead of 0.25.

The Correct Approach: List all 8 displacements. Whether you add or subtract the offsets does not matter: the full set of knight moves is symmetric (for every (a, b) it also contains (-a, -b)), so r + row_offset and r - row_offset visit the same 8 neighbors.

knight_moves = [
    (-2, -1), (-2, 1), (-1, -2), (-1, 2),
    (1, -2), (1, 2), (2, -1), (2, 1)
]

3. Space Optimization Misimplementation

The Pitfall: Trying to optimize space by using only 2D arrays but incorrectly managing the state updates:

# WRONG: Modifying the same array being read from
dp = [[1.0] * n for _ in range(n)]
for move in range(k):
    for r in range(n):
        for c in range(n):
            dp[r][c] = 0  # Clearing before we're done reading!
            # ... calculate new value

The Solution: Use two alternating 2D arrays or properly manage temporary storage:

# CORRECT: Using two arrays and swapping
prev = [[1.0] * n for _ in range(n)]
curr = [[0.0] * n for _ in range(n)]

for move in range(k):
    for r in range(n):
        for c in range(n):
            curr[r][c] = 0
            for row_offset, col_offset in knight_moves:
                prev_row = r + row_offset
                prev_col = c + col_offset
                if 0 <= prev_row < n and 0 <= prev_col < n:
                    curr[r][c] += prev[prev_row][prev_col] / 8.0
    prev, curr = curr, prev  # Swap arrays

return prev[row][column]

4. Integer Division in Python 2 vs Python 3

The Pitfall: In older Python 2 code or when habits carry over:

# Potential issue in Python 2 (not Python 3)
dp[moves][r][c] += dp[moves - 1][prev_row][prev_col] / 8

The Safe Approach: Always use float division explicitly to ensure compatibility:

dp[moves][r][c] += dp[moves - 1][prev_row][prev_col] / 8.0

5. Misunderstanding the Problem Requirements

The Pitfall: Some might think the knight stops moving once it goes off the board and count that as a valid end state, or they might think the knight can return to the board after going off.

The Correct Understanding:

Once the knight moves off the board, it cannot return
We only count cases where the knight remains on the board after ALL k moves
Every move has exactly 8 choices regardless of validity (the 1/8 probability applies to all 8 directions)

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers