LeetCode 688: Knight Probability in Chessboard

Problem Restatement

We are given an n x n chessboard.

A knight starts at cell:

(row, column)

The knight makes exactly k moves.

On each move, it chooses one of the 8 possible knight moves uniformly at random. It may choose a move that goes off the board. If it moves off the board, it cannot return. We need to return the probability that the knight remains on the board after it has stopped moving.

Input and Output

Example function shape:

def knightProbability(n: int, k: int, row: int, column: int) -> float:
    ...

Examples

Example 1:

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

The knight starts in the top-left corner.

From (0, 0), only two knight moves stay on the board:

(1, 2)
(2, 1)

The other six moves go off the board.

After two moves, only a small fraction of all possible random paths remain on the board.

Answer:

0.0625

Example 2:

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

The knight makes no moves.

It starts on the board and remains there.

Answer:

1.0

First Thought: Enumerate All Paths

A direct solution is to simulate every possible sequence of moves.

For each move, the knight has 8 choices.

So after k moves, there are:

8^k

possible move sequences.

For each sequence, we could check whether the knight ever goes off the board.

This is too expensive when k is large.

The problem has overlapping subproblems: many different paths can reach the same cell after the same number of moves. Dynamic programming avoids recomputing them.

Key Insight

Instead of tracking every path, track probability mass.

Let:

dp[r][c]

mean the probability that the knight is at cell (r, c) after the current number of moves, while still being on the board.

Initially:

dp[row][column] = 1.0

because the knight starts there with probability 1.

For each move, we create a new board next_dp.

From each cell (r, c) with probability p, the knight sends p / 8 probability to each valid next cell.

Moves that go off the board are ignored, because they no longer contribute to the probability of staying on the board.

After k moves, the answer is the sum of all probabilities still on the board.

Knight Moves

A knight can move in these 8 directions:

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

Each move has probability:

1 / 8

Algorithm

1. Create an n x n table filled with 0.0.
2. Set the starting cell to 1.0.
3. Repeat k times:
   • Create a new n x n table filled with 0.0.
   • For every cell (r, c):
     • If dp[r][c] is nonzero, try all 8 knight moves.
     • If the next cell is inside the board, add dp[r][c] / 8 to that cell in next_dp.
   • Replace dp with next_dp.
4. Return the sum of all values in dp.

Walkthrough

Consider:

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

Start:

dp[0][0] = 1.0

From (0, 0), only two moves stay on the board:

(1, 2)
(2, 1)

Each receives probability:

1 / 8 = 0.125

After one move:

The total probability still on the board is:

0.125 + 0.125 = 0.25

For k = 2, we repeat the same transition once more. The final probability for the official example is:

0.0625

Correctness

The dynamic programming table stores exactly the probability that the knight is at each board cell after a fixed number of moves, without having left the board.

The base case is correct because before any moves, the knight is at the starting cell with probability 1.

For each transition, the knight chooses one of 8 moves uniformly at random. Therefore, each possible move receives one eighth of the current cell’s probability.

If a move lands inside the board, that probability contributes to the corresponding cell in the next table.

If a move lands outside the board, that probability is lost and should not appear in the next table.

Thus, after each iteration, the table correctly represents the distribution of the knight over all on-board cells after that many moves.

After k moves, the knight remains on the board exactly when it is in any cell of the board. Summing all cells gives that probability.

Therefore, the algorithm returns the correct result.

Complexity

Let n be the board size.

The factor 8 is constant.

Implementation

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),
        ]

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

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

            for r in range(n):
                for c in range(n):
                    if dp[r][c] == 0.0:
                        continue

                    probability = dp[r][c] / 8.0

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

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

            dp = next_dp

        return sum(sum(row_values) for row_values in dp)

Code Explanation

The moves list contains all legal knight displacement patterns.

The table:

dp = [[0.0] * n for _ in range(n)]

stores the current probability distribution.

The starting cell gets probability 1:

dp[row][column] = 1.0

For each move, we build a fresh table:

next_dp = [[0.0] * n for _ in range(n)]

For every nonzero cell, we split its probability into 8 equal parts:

probability = dp[r][c] / 8.0

Then each valid destination receives that probability:

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

Invalid destinations are skipped because they represent paths where the knight has left the board.

After all moves, the total remaining probability is:

return sum(sum(row_values) for row_values in dp)

Testing

def run_tests():
    s = Solution()

    assert abs(s.knightProbability(3, 2, 0, 0) - 0.0625) < 1e-9
    assert abs(s.knightProbability(1, 0, 0, 0) - 1.0) < 1e-9

    assert abs(s.knightProbability(1, 1, 0, 0) - 0.0) < 1e-9
    assert abs(s.knightProbability(8, 1, 3, 3) - 1.0) < 1e-9
    assert abs(s.knightProbability(2, 1, 0, 0) - 0.0) < 1e-9

    print("all tests passed")

run_tests()

Test meaning: