LeetCode 688 - Knight Probability in Chessboard

The problem asks us to compute the probability that a chess knight remains on an n x n board after making exactly k moves. A knight starts at position (row, column).

leetcodemediumdynamic-programming

LeetCode Problem 688

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

The problem asks us to compute the probability that a chess knight remains on an n x n board after making exactly k moves.

A knight starts at position (row, column). At every move, it randomly chooses one of its eight possible knight moves with equal probability, which is 1/8 for each move. Importantly, the knight does not avoid invalid moves. Even if a move would take it off the board, that move is still considered part of the random choice set.

The process stops in one of two situations:

  • The knight has completed exactly k moves
  • The knight moves off the board

Our task is to return the probability that the knight is still somewhere on the board after exactly k moves.

A knight moves in an L-shape. From a position (r, c), the eight possible moves are:

  • (r + 2, c + 1)
  • (r + 2, c - 1)
  • (r - 2, c + 1)
  • (r - 2, c - 1)
  • (r + 1, c + 2)
  • (r + 1, c - 2)
  • (r - 1, c + 2)
  • (r - 1, c - 2)

The constraints are relatively small:

  • n <= 25
  • k <= 100

These limits immediately suggest that an exponential brute-force traversal would become infeasible. Since every move branches into 8 possibilities, a naive recursive solution would explore up to 8^k paths. For k = 100, this is astronomically large.

The important edge cases include situations where:

  • k = 0, because no moves are made and the knight automatically remains on the board
  • n = 1, because the board has only one square and any move immediately leaves the board
  • The knight starts near the edge or corner, where many moves are invalid
  • Large k values, where repeated computation becomes expensive without optimization

The problem guarantees valid input coordinates, so we never need to handle invalid starting positions.

Approaches

Brute Force Approach

The brute-force strategy is to recursively simulate every possible sequence of knight moves.

At each step, the knight has eight possible moves. We recursively explore all of them, reducing the remaining move count by one each time. If the knight ever moves outside the board, that path contributes probability 0. If the knight successfully completes all k moves while staying inside the board, that path contributes probability 1.

Since every move has probability 1/8, the final probability is the average of all recursive branches.

This approach is correct because it explicitly models the full probability tree. Every possible sequence of moves is considered exactly once.

However, the same board positions are recomputed repeatedly. For example, the probability of surviving from position (2,3) with 5 moves remaining may be calculated hundreds or thousands of times.

The time complexity grows exponentially as O(8^k), which is far too slow for k = 100.

Optimal Dynamic Programming Approach

The key observation is that the problem has overlapping subproblems.

If we define:

  • dp[move][r][c]

as the probability that the knight is at cell (r, c) after move moves while still remaining on the board, then each state depends only on the previous move's states.

Instead of recomputing probabilities recursively, we build them iteratively.

We begin with probability 1.0 at the starting position. Then for each move, we distribute the current probability equally among all valid knight destinations.

This transforms the exponential recursion tree into a manageable dynamic programming solution.

Since there are at most:

  • k <= 100
  • n <= 25

the total number of states is only:

  • 100 * 25 * 25 = 62,500

which is very efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(8^k) O(k) Explores every possible move sequence recursively
Optimal Dynamic Programming O(k * n²) O(n²) Reuses previously computed probabilities

Algorithm Walkthrough

  1. Define the eight possible knight moves.

We store all legal knight movement offsets in a list. This allows us to iterate uniformly through all possible transitions from a given cell. 2. Create a probability grid for the current move state.

We use a 2D array called current. Each cell stores the probability that the knight is currently at that position after a certain number of moves. 3. Initialize the starting position.

Before any moves are made, the knight is definitely at (row, column), so:

current[row][column] = 1.0
  1. Process each move one at a time.

For every move from 1 to k, we create a fresh next_state grid initialized with zeros. 5. Distribute probabilities to reachable cells.

For every cell (r, c) in the current grid:

  • If its probability is zero, skip it
  • Otherwise, try all eight knight moves
  • If the destination cell is inside the board, add:
current[r][c] / 8

to that destination

This models the equal probability of each knight move. 6. Replace the current grid.

After processing all transitions for one move, assign:

current = next_state

so the algorithm proceeds to the next move layer. 7. Sum all remaining probabilities.

After exactly k moves, every value left in the grid represents a valid way for the knight to still be on the board.

The answer is the sum of all probabilities in the final grid.

Why it works

The dynamic programming state maintains an important invariant:

current[r][c] always represents the probability that the knight is at position (r, c) after the current number of moves while still remaining on the board.

Each transition distributes probability mass according to the knight's uniform random choices. Invalid moves are discarded automatically because they leave the board and therefore do not contribute to future states.

Since every valid path contributes exactly according to its probability, the final sum of all board probabilities equals the probability that the knight survives all k moves.

Python Solution

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        moves = [
            (2, 1),
            (2, -1),
            (-2, 1),
            (-2, -1),
            (1, 2),
            (1, -2),
            (-1, 2),
            (-1, -2),
        ]

        current = [[0.0 for _ in range(n)] for _ in range(n)]
        current[row][column] = 1.0

        for _ in range(k):
            next_state = [[0.0 for _ in range(n)] for _ in range(n)]

            for r in range(n):
                for c in range(n):
                    if current[r][c] == 0:
                        continue

                    probability = current[r][c] / 8.0

                    for dr, dc in moves:
                        nr = r + dr
                        nc = c + dc

                        if 0 <= nr < n and 0 <= nc < n:
                            next_state[nr][nc] += probability

            current = next_state

        total_probability = 0.0

        for r in range(n):
            for c in range(n):
                total_probability += current[r][c]

        return total_probability

The implementation begins by defining the eight knight move directions. These are stored as coordinate offsets so we can iterate through them efficiently.

The current matrix stores the probability distribution after the current number of moves. Initially, the knight is guaranteed to be at the starting square, so that position receives probability 1.0.

For each move iteration, we create a new matrix called next_state. This represents the probability distribution after one additional move.

We then scan every cell in the board. If a cell currently has probability zero, we skip it because no probability mass exists there.

Otherwise, we divide the cell's probability equally among the eight possible knight moves. For each valid destination cell, we add the contribution into next_state.

After processing all cells, we replace current with next_state.

Finally, we sum every probability remaining on the board. This total represents the probability that the knight never left the board during the k moves.

Go Solution

func knightProbability(n int, k int, row int, column int) float64 {
    moves := [][2]int{
        {2, 1},
        {2, -1},
        {-2, 1},
        {-2, -1},
        {1, 2},
        {1, -2},
        {-1, 2},
        {-1, -2},
    }

    current := make([][]float64, n)
    for i := range current {
        current[i] = make([]float64, n)
    }

    current[row][column] = 1.0

    for move := 0; move < k; move++ {
        nextState := make([][]float64, n)

        for i := range nextState {
            nextState[i] = make([]float64, n)
        }

        for r := 0; r < n; r++ {
            for c := 0; c < n; c++ {
                if current[r][c] == 0 {
                    continue
                }

                probability := current[r][c] / 8.0

                for _, dir := range moves {
                    nr := r + dir[0]
                    nc := c + dir[1]

                    if nr >= 0 && nr < n && nc >= 0 && nc < n {
                        nextState[nr][nc] += probability
                    }
                }
            }
        }

        current = nextState
    }

    totalProbability := 0.0

    for r := 0; r < n; r++ {
        for c := 0; c < n; c++ {
            totalProbability += current[r][c]
        }
    }

    return totalProbability
}

The Go implementation follows the same dynamic programming structure as the Python version.

The primary difference is memory allocation. In Go, we explicitly allocate each row of the 2D slice using make.

Go also uses fixed numeric types, so probabilities are stored as float64. Since all probability operations are fractional, integer types would be incorrect.

Unlike Python lists, Go slices require manual initialization before use. Aside from syntax differences, the algorithmic behavior is identical.

Worked Examples

Example 1

Input:

n = 3
k = 2
row = 0
column = 0

Initial state:

Position Probability
(0,0) 1.0

After 1 move:

From (0,0) the knight has only two valid moves:

  • (1,2)
  • (2,1)

Each receives probability:

1.0 / 8 = 0.125

State after move 1:

Position Probability
(1,2) 0.125
(2,1) 0.125

After 2 moves:

From (1,2) the valid moves are:

  • (0,0)
  • (2,0)

Each receives:

0.125 / 8 = 0.015625

From (2,1) the valid moves are:

  • (0,0)
  • (0,2)

Each also receives:

0.015625

Final probabilities:

Position Probability
(0,0) 0.03125
(2,0) 0.015625
(0,2) 0.015625

Total:

0.03125 + 0.015625 + 0.015625 = 0.0625

Answer:

0.0625

Example 2

Input:

n = 1
k = 0
row = 0
column = 0

Since no moves are made, the knight never has a chance to leave the board.

Initial state:

Position Probability
(0,0) 1.0

No iterations occur because k = 0.

Final answer:

1.0

Complexity Analysis

Measure Complexity Explanation
Time O(k * n²) For each move, we process every board cell and up to 8 transitions
Space O(n²) Only two probability grids are stored at once

The algorithm iterates through the board k times. During each iteration, every cell is examined once, and each cell considers at most 8 knight moves. Since 8 is constant, the complexity simplifies to O(k * n²).

The space complexity is O(n²) because we only maintain two 2D matrices, current and next_state, regardless of the number of moves.

Test Cases

solution = Solution()

assert abs(solution.knightProbability(3, 2, 0, 0) - 0.0625) < 1e-9
# Example case with corner start

assert abs(solution.knightProbability(1, 0, 0, 0) - 1.0) < 1e-9
# No moves means guaranteed survival

assert abs(solution.knightProbability(1, 1, 0, 0) - 0.0) < 1e-9
# Single-cell board cannot support any knight move

assert abs(solution.knightProbability(8, 1, 3, 3) - 1.0) < 1e-9
# Center of standard board, all moves remain valid

assert abs(solution.knightProbability(3, 1, 0, 0) - 0.25) < 1e-9
# Corner position with only two valid moves

assert abs(solution.knightProbability(2, 1, 0, 0) - 0.0) < 1e-9
# Small board where every move exits immediately

assert abs(solution.knightProbability(25, 0, 12, 12) - 1.0) < 1e-9
# Large board but zero moves

result = solution.knightProbability(8, 30, 4, 4)
assert 0.0 <= result <= 1.0
# Large k stress test

result = solution.knightProbability(25, 100, 12, 12)
assert 0.0 <= result <= 1.0
# Maximum constraint stress test
Test Why
n=3, k=2, row=0, col=0 Validates the official example
n=1, k=0 Tests zero-move behavior
n=1, k=1 Tests guaranteed failure after movement
n=8, k=1, row=3, col=3 Tests fully valid move set
n=3, k=1, row=0, col=0 Tests edge and corner handling
n=2, k=1, row=0, col=0 Tests tiny board behavior
n=25, k=0 Tests large board with no transitions
n=8, k=30 Stress tests repeated DP transitions
n=25, k=100 Tests maximum constraints

Edge Cases

One important edge case occurs when k = 0. In this situation, the knight never moves, so the probability of remaining on the board must always be 1.0. A buggy implementation might still attempt transitions or accidentally return 0. This solution handles the case naturally because the move loop never executes, leaving the starting cell probability unchanged.

Another critical edge case is a very small board such as n = 1 or n = 2. On these boards, many or all knight moves are invalid. A naive implementation might incorrectly assume at least one legal move exists. In this solution, every move destination is checked with boundary conditions before adding probability to the next state. Invalid moves are simply ignored.

A third important edge case is starting near a corner or edge. Knights positioned near the boundary have far fewer valid moves than knights near the center. Incorrect implementations sometimes normalize probabilities only over valid moves, which would be wrong because the problem states the knight always chooses uniformly among all eight moves. This implementation correctly divides probability by 8 regardless of how many moves remain on the board.

Another subtle edge case involves large values of k. Recursive solutions without memoization can easily time out or exceed recursion depth limits. The iterative dynamic programming approach avoids recursion entirely and efficiently handles the maximum constraint of k = 100.