Knight Probability in Chessboard

MediumProbability DP · Grid🧩 Probability DP LeetCode #688 ↗Updated Oct 30, 2026

Problem

A knight starts on cell (row, column) of an n × n board and makes exactly k moves. Each move picks one of the 8 knight jumps uniformly at random, even if it leads off the board; once off, the knight stays off. Return the probability that it is still on the board after all k moves.

Inputn = 3, k = 2, row = 0, column = 0Output0.06250

Inputn = 1, k = 0, row = 0, column = 0Output1.00000

1 ≤ n ≤ 25 · 0 ≤ k ≤ 100 · 0 ≤ row, column < n · answers within 10^-5 are accepted

Try it yourself

Java

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The probability of surviving depends only on (cell, moves left), not on the path that got there — so 8^k paths collapse into k · n² states, each the average of its 8 neighbours.

PatternProbability DP

Instinct Asked for a probability or expected value after random moves? Run DP over (step, state) and split each state's mass across every outcome.

Memory hack Pour the probability like water - split it across the moves, let what spills off the board drain away, and the puddle that's left is your answer.

Open the Probability DP guide →

Approaches

Brute ForcePlain Recursion over All Paths

Time O(8^k)Space O(k)

P(r, c, k) = 0 if off the board, 1 if no moves are left, otherwise the average of P over the 8 jumps with k-1 moves. This literally explores every random path.

Java

private static final int[][] JUMPS =
    {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

public double knightProbability(int n, int k, int row, int column) {
    if (row < 0 || row >= n || column < 0 || column >= n) return 0.0;
    if (k == 0) return 1.0;
    double sum = 0;
    for (int[] j : JUMPS) {
        sum += knightProbability(n, k - 1, row + j[0], column + j[1]);
    }
    return sum / 8.0;
}

Matches the definition exactly, but blows up for k beyond ~10.

BetterTop-Down Memoisation

Time O(k · n²)Space O(k · n²)

Same recurrence, but cache P(r, c, movesLeft). There are only (k+1) · n² distinct states and each does 8 units of work, so overlapping paths are computed once.

Java

private static final int[][] JUMPS =
    {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
private double[][][] memo;

public double knightProbability(int n, int k, int row, int column) {
    memo = new double[k + 1][n][n];
    for (double[][] grid : memo) for (double[] line : grid) Arrays.fill(line, -1);
    return solve(n, k, row, column);
}

private double solve(int n, int left, int r, int c) {
    if (r < 0 || r >= n || c < 0 || c >= n) return 0.0;
    if (left == 0) return 1.0;
    if (memo[left][r][c] >= 0) return memo[left][r][c];
    double sum = 0;
    for (int[] j : JUMPS) sum += solve(n, left - 1, r + j[0], c + j[1]);
    return memo[left][r][c] = sum / 8.0;
}

Polynomial and easy to derive from the brute force; the memo table is the only cost.

OptimalBottom-Up Probability Spreading (Two Grids)

Time O(k · n²)Space O(n²)

Track the probability mass on every cell. Start with 1.0 on the start cell; each step, every cell sends 1/8 of its mass to each on-board jump target (mass that jumps off is simply dropped). After k steps the remaining total mass is the answer. Only the current and next grid are needed.

Java

public double knightProbability(int n, int k, int row, int column) {
    int[][] jumps = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
    double[][] cur = new double[n][n];
    cur[row][column] = 1.0;
    for (int step = 0; step < k; step++) {
        double[][] next = new double[n][n];
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (cur[r][c] == 0) continue;
                double share = cur[r][c] / 8.0;
                for (int[] j : jumps) {
                    int nr = r + j[0], nc = c + j[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n) next[nr][nc] += share;
                }
            }
        }
        cur = next;
    }
    double total = 0;
    for (double[] line : cur) for (double p : line) total += p;
    return total;
}

Same time as memo, no recursion, and memory drops to two n×n grids.

Pro tip

The forward “mass spreading” view is the same as the backward recurrence — pick whichever you can explain more clearly.

At a glance

Level	Approach	Time	Space
Brute Force	Plain Recursion over All Paths	`O(8^k)`	`O(k)`
Better	Top-Down Memoisation	`O(k · n²)`	`O(k · n²)`
Optimal	Bottom-Up Probability Spreading (Two Grids)	`O(k · n²)`	`O(n²)`

Common pitfalls

Dividing by the number of valid moves instead of always by 8.
Letting a knight that left the board come back — off-board mass must be dropped.
Using float or integer counts of paths: 8¹⁰⁰ overflows everything.

Interview tips

Write the recurrence first; memoisation then falls out naturally.
Point out the state is (cell, moves left) — the path history is irrelevant.
Mention rolling arrays to cut memory from O(k·n²) to O(n²).

Pattern

Probability DP on a grid → random moves for a fixed number of steps; each state is the average of its successors.

My notes saved in this browser