Knight Probability in Chessboard solution and explanation
Google
9 more videos on this problem
Knights Probability in Chessboard Dynamic Programming | Leetcode-688 (Medium) SolutionPepcoding · 21:29 · 21K views
Knight Probability in Chessboard II Maths II Probability II Recursion II DP II Leetcode 688Aryan Mittal · 24:16 · 6K views
Coding Interview Problem - Knight Probability in ChessboardKnapsack · 10:26 · 4K views
LeetCode 688. Knight Probability in ChessboardHappy Coding · 27:55 · 2K views
688. Knight Probability in Chessboard | DP | C++ | LeetCode Daily ChallengeDeep Tech · 16:13 · 1K views
688. Knight Probability in Chessboard (Leetcode Medium)Programming Live with Larry · 14:05 · 1K views
Leetcode 688 - Knight Probability in Chessboard | Dynamic ProgrammingSkillUp with Genie · 15:31 · 1K views
LeetCode 688 Knight Probability in ChessboardJeevan Kumar - Cracckify · 12:31 · 1K views
Conquer LeetCode 688. Knight Probability in Chessboard with Python and Dynamic Programming! POTDvanAmsen · 8:05 · 775 views
Daily Leetcode #1208: Jul 22, 2023 - 688. Knight Probability in ChessboardProgramming Live with Larry · 10:12 · 687 views
The problem
On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed, so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).
A chess knight has eight possible moves it can make, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.
Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.
The knight continues moving until it has made exactly k moves or has moved off the chessboard.
Return the probability that the knight remains on the board after it has stopped moving.
Example 1:
Input: n = 3, k = 2, row = 0, column = 0 Output: 0.06250 Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board. From each of those positions, there are also two moves that will keep the knight on the board. The total probability the knight stays on the board is 0.0625.
Example 2:
Input: n = 1, k = 0, row = 0, column = 0 Output: 1.00000
Constraints:
1 <= n <= 250 <= k <= 1000 <= row, column <= n - 1
Approach overview
Problem Overview: You have an n x n chessboard and a knight starting at position (row, column). The knight makes exactly k moves, choosing one of the 8 legal knight moves each time with equal probability. The task is to compute the probability that the knight remains on the board after all k moves.
Approach 1: Recursive Memoization (Time: O(k * n^2), Space: O(k * n^2))
Model the problem as a recursive search over moves. From a cell (r, c) with movesRemaining, try all 8 knight directions and recursively compute the probability of staying on the board. Each move contributes 1/8 of the probability. Many states repeat because the same cell can be reached with the same remaining moves through different paths. Store results in a memo table keyed by (r, c, movesRemaining). When the knight moves off the board, return 0. When no moves remain, return 1. Memoization avoids recomputation and turns an exponential recursion into a polynomial-time solution.
This approach naturally expresses the state transition and is easy to reason about. The state space is bounded by n * n * k, and each state explores 8 directions, giving O(k * n^2) time complexity. It relies on caching overlapping subproblems, a classic pattern in Dynamic Programming and Memoization.
Approach 2: Dynamic Programming (Bottom-Up) (Time: O(k * n^2), Space: O(n^2))
Instead of recursion, build probabilities iteratively. Maintain a 2D grid dp[r][c] representing the probability of the knight being at cell (r, c) after the current number of moves. Initialize the starting position with probability 1. For each of the k moves, create a new grid and distribute the probability from each cell to its 8 valid knight destinations using probability / 8.
Each iteration processes all n^2 cells and updates up to 8 destinations. After completing k iterations, sum the probabilities of all cells to get the probability that the knight remains on the board. Because only the previous step is required to compute the next step, you can reuse two grids and keep the space complexity at O(n^2). This formulation directly represents state transitions typical in Dynamic Programming problems.
Recommended for interviews: Interviewers typically expect the bottom-up Dynamic Programming solution. It clearly models probability transitions and avoids recursion overhead. Explaining the recursive memoization version first demonstrates understanding of overlapping subproblems, while the iterative DP version shows you can optimize state transitions and memory usage—skills commonly tested in recursion and DP interview questions.
Approach 1: Dynamic Programming Approach
In this approach, we utilize a 3D array `dp` where `dp[k][i][j]` represents the probability that the knight is on position `(i, j)` after making `k` moves. Initially, the knight is placed at `(row, column)`, so `dp[0][row][column] = 1`. For each move `k`, we calculate the probability of the knight being on each cell `(i, j)` by summing over probabilities of positions that can move to `(i, j)` in one knight move.
This involves iterating through each cell and updating the probabilities according to knight's possible moves.
def knightProbability(n: int, k: int, row: int, column: int) -> float:
dp = [[[0.0] * n for _ in range(n)] for _ in range(k + 1)]
directions = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
dp[0][row][column] = 1.0
for m in range(1, k + 1):
for i in range(n):
for j in range(n):
for d in directions:
ni, nj = i + d[0], j + d[1]
if 0 <= ni < n and 0 <= nj < n:
dp[m][ni][nj] += dp[m-1][i][j] / 8.0
return sum(dp[k][i][j] for i in range(n) for j in range(n))public class KnightProbability {
public double knightProbability(int n, int k, int row, int column) {
double[][][] dp = new double[k + 1][n][n];
int[][] directions = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
dp[0][row][column] = 1.0;
for (int m = 1; m <= k; m++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int[] dir : directions) {
int ni = i + dir[0];
int nj = j + dir[1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
dp[m][ni][nj] += dp[m-1][i][j] / 8.0;
}
}
}
}
}
double result = 0.0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result += dp[k][i][j];
}
}
return result;
}
}#include <vector>
using namespace std;
double knightProbability(int n, int k, int row, int column) {
vector<vector<vector<double>>> dp(k+1, vector<vector<double>>(n, vector<double>(n, 0.0)));
vector<pair<int, int>> directions{{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
dp[0][row][column] = 1.0;
for (int m = 1; m <= k; ++m) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (auto &dir : directions) {
int ni = i + dir.first;
int nj = j + dir.second;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
dp[m][ni][nj] += dp[m-1][i][j] / 8.0;
}
}
}
}
}
double result = 0.0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
result += dp[k][i][j];
}
}
return result;
}function knightProbability(n, k, row, column) {
const dp = Array.from(Array(k + 1), () => Array.from(Array(n), () => Array(n).fill(0)));
const directions = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]];
dp[0][row][column] = 1.0;
for (let m = 1; m <= k; m++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (const [dx, dy] of directions) {
const ni = i + dx;
const nj = j + dy;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
dp[m][ni][nj] += dp[m - 1][i][j] / 8.0;
}
}
}
}
}
return dp[k].reduce((acc, row) => acc + row.reduce((rAcc, p) => rAcc + p, 0), 0);
}#include <stdio.h>
#define MAX 25
double knightProbability(int n, int k, int row, int column) {
double dp[k+1][MAX][MAX];
int directions[8][2] = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
// Initialize
memset(dp, 0, sizeof(dp));
dp[0][row][column] = 1;
// Fill DP table
for (int m = 1; m <= k; ++m) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dp[m-1][i][j] > 0) {
for (int d = 0; d < 8; ++d) {
int ni = i + directions[d][0];
int nj = j + directions[d][1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
dp[m][ni][nj] += dp[m-1][i][j] / 8.0;
}
}
}
}
}
}
// Sum up probabilities
double result = 0.0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
result += dp[k][i][j];
}
}
return result;
}public class Solution {
public double KnightProbability(int n, int k, int row, int column) {
double[,,] dp = new double[k + 1, n, n];
int[,] directions = { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 } };
dp[0, row, column] = 1.0;
for (int m = 1; m <= k; m++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int d = 0; d < 8; d++) {
int ni = i + directions[d, 0];
int nj = j + directions[d, 1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
dp[m, ni, nj] += dp[m-1, i, j] / 8.0;
}
}
}
}
}
double result = 0.0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result += dp[k, i, j];
}
}
return result;
}
}The Python code uses a list of lists to model the 3D `dp` array, storing probabilities for knight positions after `k` moves. The nested loops iterate through possible moves and positions to keep track of survival probabilities on the board.
Time Complexity: O(k * n^2).
Space Complexity: O(k * n^2).
Approach 2: Recursive Memoization Approach
This approach leverages recursion along with memoization to optimize calculations. We define a recursive function to calculate the probability the knight remains within bounds after `k` moves. We utilize memoization to cache results of subproblems to avoid redundant calculations. If the knight's position ends within the board boundaries, it contributes to the final probability.
from functools import lru_cache
directions = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
def knightProbability(n: int, k: int, row: int, column: int) -> float:
@lru_cache(None)
def recurse(k, row, column):
if not (0 <= row < n) or not (0 <= column < n):
return 0
if k == 0:
return 1
prob = 0.0
for dx, dy in directions:
prob += recurse(k - 1, row + dx, column + dy) / 8
return prob
return recurse(k, row, column)public class KnightProbabilityRecursive {
double[][][] memo = new double[101][25][25];
int[][] directions = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
public double knightProbability(int n, int k, int row, int column) {
for (double[][] layer : memo) for (double[] arr : layer) Arrays.fill(arr, -1.0);
return recurse(n, k, row, column);
}
private double recurse(int n, int k, int row, int column) {
if (row < 0 || row >= n || column < 0 || column >= n) return 0;
if (k == 0) return 1;
if (memo[k][row][column] != -1.0) return memo[k][row][column];
double prob = 0.0;
for (int[] dir : directions) {
int ni = row + dir[0], nj = column + dir[1];
prob += recurse(n, k - 1, ni, nj) / 8.0;
}
return memo[k][row][column] = prob;
}
}#include <vector>
using namespace std;
vector<vector<vector<double>>> memo(101, vector<vector<double>>(25, vector<double>(25, -1.0)));
vector<pair<int, int>> directions{{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
// Recursive memoization function
double recurse(int n, int k, int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= n) return 0;
if (k == 0) return 1;
if (memo[k][i][j] != -1.0) return memo[k][i][j];
double prob = 0.0;
for (auto &dir : directions) {
int ni = i + dir.first;
int nj = j + dir.second;
prob += recurse(n, k - 1, ni, nj) / 8.0;
}
return memo[k][i][j] = prob;
}
double knightProbability(int n, int k, int row, int column) {
return recurse(n, k, row, column);
}function knightProbability(n, k, row, column) {
const directions = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]];
const memo = Array.from({length: 101}, () => Array.from({length: 25}, () => Array(25).fill(-1)));
function recurse(k, row, column) {
if (row < 0 || row >= n || column < 0 || column >= n) return 0;
if (k === 0) return 1;
if (memo[k][row][column] !== -1) return memo[k][row][column];
let prob = 0.0;
for (const [dx, dy] of directions) {
prob += recurse(k - 1, row + dx, column + dy) / 8.0;
}
return memo[k][row][column] = prob;
}
return recurse(k, row, column);
}#include <stdio.h>
#include <string.h>
#define MAX 25
double memo[101][MAX][MAX];
int directions[8][2] = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
// Recursive function with memoization
double recurse(int n, int k, int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= n) return 0;
if (k == 0) return 1;
if (memo[k][i][j] != -1.0) return memo[k][i][j];
double prob = 0.0;
for (int d = 0; d < 8; d++) {
int ni = i + directions[d][0];
int nj = j + directions[d][1];
prob += recurse(n, k - 1, ni, nj) / 8.0;
}
return (memo[k][i][j] = prob);
}
double knightProbability(int n, int k, int row, int column) {
memset(memo, -1, sizeof(memo)); // Initialize memoization table
return recurse(n, k, row, column);
}public class SolutionRecursive {
double[,,] memo = new double[101, 25, 25];
int[][] directions = new int[][] {
new int[] {2, 1}, new int[] {2, -1}, new int[] {-2, 1}, new int[] {-2, -1},
new int[] {1, 2}, new int[] {1, -2}, new int[] {-1, 2}, new int[] {-1, -2}};
public double KnightProbability(int n, int k, int row, int column) {
for (int i = 0; i <= 100; ++i)
for (int j = 0; j < 25; ++j)
for (int l = 0; l < 25; ++l)
memo[i, j, l] = -1;
return Recurse(n, k, row, column);
}
private double Recurse(int n, int k, int row, int column) {
if (row < 0 || row >= n || column < 0 || column >= n) return 0;
if (k == 0) return 1;
if (memo[k, row, column] != -1.0) return memo[k, row, column];
double prob = 0.0;
foreach (var dir in directions) {
prob += Recurse(n, k - 1, row + dir[0], column + dir[1]) / 8.0;
}
return memo[k, row, column] = prob;
}
}The Python solution uses a recursive function with `lru_cache` from the `functools` module to implement memoization, reducing repeated computations by caching computed probabilities for a given position `(i, j)` with `k` moves.
Time Complexity: O(k * n^2).
Space Complexity: O(k * n^2).
Approach 3: Dynamic Programming
We define f[h][i][j] to represent the probability that the knight remains on the board after taking h steps starting from position (i, j). The final answer is f[k][row][column].
When h=0, the knight is definitely on the board, so the probability is 1, i.e., f[0][i][j]=1.
When h \gt 0, the probability that the knight is at position (i, j) can be derived from the probabilities of the 8 possible positions it could have come from in the previous step, i.e.,
$
f[h][i][j] = sum_{x, y} f[h - 1][x][y] times \frac{1}{8}
where (x, y) is one of the 8 positions the knight can move to from (i, j).
The final answer is f[k][row][column].
The time complexity is O(k times n^2), and the space complexity is O(k times n^2). Here, k and n$ are the given number of steps and the size of the board, respectively.
function knightProbability(n: number, k: number, row: number, column: number): number {
const f = Array.from({ length: k + 1 }, () =>
Array.from({ length: n }, () => Array(n).fill(0)),
);
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
f[0][i][j] = 1;
}
}
const dirs = [-2, -1, 2, 1, -2, 1, 2, -1, -2];
for (let h = 1; h <= k; ++h) {
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
for (let p = 0; p < 8; ++p) {
const x = i + dirs[p];
const y = j + dirs[p + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
f[h][i][j] += f[h - 1][x][y] / 8;
}
}
}
}
}
return f[k][row][column];
}func knightProbability(n int, k int, row int, column int) float64 {
f := make([][][]float64, k+1)
for h := range f {
f[h] = make([][]float64, n)
for i := range f[h] {
f[h][i] = make([]float64, n)
for j := range f[h][i] {
f[0][i][j] = 1
}
}
}
dirs := [9]int{-2, -1, 2, 1, -2, 1, 2, -1, -2}
for h := 1; h <= k; h++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
for p := 0; p < 8; p++ {
x, y := i+dirs[p], j+dirs[p+1]
if x >= 0 && x < n && y >= 0 && y < n {
f[h][i][j] += f[h-1][x][y] / 8
}
}
}
}
}
return f[k][row][column]
}impl Solution {
pub fn knight_probability(n: i32, k: i32, row: i32, column: i32) -> f64 {
let n = n as usize;
let k = k as usize;
let mut f = vec![vec![vec![0.0; n]; n]; k + 1];
for i in 0..n {
for j in 0..n {
f[0][i][j] = 1.0;
}
}
let dirs = [-2, -1, 2, 1, -2, 1, 2, -1, -2];
for h in 1..=k {
for i in 0..n {
for j in 0..n {
for p in 0..8 {
let x = i as isize + dirs[p];
let y = j as isize + dirs[p + 1];
if x >= 0 && x < n as isize && y >= 0 && y < n as isize {
let x = x as usize;
let y = y as usize;
f[h][i][j] += f[h - 1][x][y] / 8.0;
}
}
}
}
}
f[k][row as usize][column as usize]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(k * n^2). |
| Recursive Memoization Approach | Time Complexity: O(k * n^2). |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Memoization | O(k * n^2) | O(k * n^2) | When modeling the problem naturally with recursion and caching repeated states |
| Dynamic Programming (Bottom-Up) | O(k * n^2) | O(n^2) | Preferred for interviews and production code due to iterative transitions and lower memory usage |
Frequently asked questions
Is Knight Probability in Chessboard easy or hard?
Knight Probability in Chessboard is rated Medium difficulty. The challenge lies in recognizing overlapping subproblems and modeling probability transitions using Dynamic Programming or memoized recursion.
Knight Probability in Chessboard Python/Java solution
Both Python and Java implementations follow the same Dynamic Programming logic. Maintain a 2D grid representing probabilities for the current step, iterate for k moves, and update the next grid using the 8 possible knight directions. The final probability is the sum of all valid board cells.
How to solve Knight Probability in Chessboard in O(n)?
An O(n) solution is not possible because the knight can occupy any of the n^2 cells after each move. The optimal algorithm must process the board states for every step, leading to O(k * n^2) time complexity using Dynamic Programming or memoized recursion.
What is the best approach for Knight Probability in Chessboard?
The bottom-up Dynamic Programming approach is generally the best solution. It tracks the probability distribution of the knight across the board for each move and updates it iteratively. This method runs in O(k * n^2) time and O(n^2) space, making it efficient for typical constraints.
Is Knight Probability in Chessboard asked at Google/Amazon/Meta?
Knight Probability in Chessboard appears in interview preparation sets for companies like Amazon, Google, and other large tech firms. It tests understanding of dynamic programming, probability transitions, and state modeling on grids.
What data structure is used in Knight Probability in Chessboard?
The solution typically uses a 2D array (matrix) to store probabilities for each cell of the chessboard. In recursive implementations, a 3D memoization table indexed by row, column, and remaining moves is used to cache intermediate results.
What is the time complexity of Knight Probability in Chessboard?
The optimal solution runs in O(k * n^2) time. For each of the k moves, the algorithm iterates through all n^2 cells and distributes probability across up to 8 knight moves. The state space is bounded by the board size and number of moves.