Knight Probability in Chessboard

medium dp probability

Problem

Knight starts at (r, c) on n×n board. After k random L-moves, return probability it's still on the board.

Inputn=3 k=2 r=0 c=0

Output0.0625

Two moves at random has small survival probability.

input

def knight_prob(n, k, r, c):
    dp = [[0.0] * n for _ in range(n)]; dp[r][c] = 1.0
    moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
    for _ in range(k):
        nxt = [[0.0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if dp[i][j] == 0: continue
                for dr, dc in moves:
                    ni, nj = i + dr, j + dc
                    if 0 <= ni < n and 0 <= nj < n: nxt[ni][nj] += dp[i][j] / 8
        dp = nxt
    return sum(sum(row) for row in dp)

function knightProbability(n, k, r, c) {
  let dp = Array.from({length: n}, () => new Array(n).fill(0)); dp[r][c] = 1;
  const moves = [[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]];
  for (let s = 0; s < k; s++) {
    const nx = Array.from({length: n}, () => new Array(n).fill(0));
    for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) {
      if (!dp[i][j]) continue;
      for (const [dr, dc] of moves) {
        const ni = i + dr, nj = j + dc;
        if (ni >= 0 && ni < n && nj >= 0 && nj < n) nx[ni][nj] += dp[i][j] / 8;
      }
    }
    dp = nx;
  }
  return dp.flat().reduce((a, b) => a + b, 0);
}

double knightProbability(int n, int k, int r, int c) {
    double[][] dp = new double[n][n]; dp[r][c] = 1;
    int[][] moves = {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
    for (int s = 0; s < k; s++) {
        double[][] nx = new double[n][n];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if (dp[i][j] == 0) continue;
            for (int[] m : moves) {
                int ni = i + m[0], nj = j + m[1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n) nx[ni][nj] += dp[i][j] / 8;
            }
        }
        dp = nx;
    }
    double tot = 0; for (double[] row : dp) for (double v : row) tot += v; return tot;
}

double knightProbability(int n, int k, int r, int c) {
    vector> dp(n, vector(n, 0)); dp[r][c] = 1;
    int moves[8][2] = {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
    for (int s = 0; s < k; s++) {
        vector> nx(n, vector(n, 0));
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if (!dp[i][j]) continue;
            for (auto& m : moves) {
                int ni = i + m[0], nj = j + m[1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n) nx[ni][nj] += dp[i][j] / 8;
            }
        }
        dp = nx;
    }
    double tot = 0; for (auto& row : dp) for (double v : row) tot += v; return tot;
}

Explanation

A knight makes k random L-shaped moves on an n×n board. We want the chance it is still on the board at the end. Rather than simulate, we spread probability mass across the grid step by step.

We use a grid dp[i][j] that stores the probability the knight sits on cell (i,j) right now. It starts as 1.0 on the start square (r,c) and 0 everywhere else.

For each move, every cell splits its probability evenly into its 8 possible knight destinations (each gets 1/8). Any move that would land off the board is simply not added, so that mass quietly disappears — exactly the cases where the knight falls off.

After all k moves we sum every cell of dp: the leftover total is the probability of surviving on the board.

Example: n=3, k=2 starting at the corner (0,0). The knight has few escape-free moves, so the surviving probability shrinks to 0.0625.

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