Knight Probability in Chessboard - Practice Coding Problems

Knight Probability in Chessboard - Problem

Dynamic Programming Medium

On an n × 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.

Input & Output

Example 1 — Small Board

$ Input: n = 3, k = 2, row = 0, column = 0

› Output: 0.0625

💡 Note: Knight starts at (0,0). After 1 move, it can reach (1,2) and (2,1). After 2nd move, some paths stay on board, some don't. Total probability is 1/16 = 0.0625

Example 2 — No Moves

$ Input: n = 1, k = 0, row = 0, column = 0

› Output: 1.0

💡 Note: No moves means knight stays at starting position, so probability of staying on board is 1.0

Example 3 — Center Position

$ Input: n = 8, k = 1, row = 4, column = 4

› Output: 1.0

💡 Note: Knight at center of 8x8 board. All 8 possible moves stay on board, so probability is 8/8 = 1.0

Constraints

1 ≤ n ≤ 25
0 ≤ k ≤ 100
0 ≤ row, column < n

Visualization

Tap to expand

Understanding the Visualization

Input

n×n chessboard, knight at (row, col), k moves to make

Process

Knight randomly picks 1 of 8 possible moves each turn

Output

Probability knight remains on board after exactly k moves

Key Takeaway

🎯 Key Insight: Track the probability of being at each board position after each move using dynamic programming

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is that this is a probability calculation problem that can be solved efficiently using dynamic programming. We track the probability of the knight being at each position after each move. The optimal approach uses memoized recursion or bottom-up DP. Time: O(n²k), Space: O(n²k)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Simulation	O(8^k)	O(k)	Recursively explore all possible knight moves and count valid paths
Memoized Recursion	O(n²k)	O(n²k)	Cache results of recursive calls to avoid redundant calculations
Bottom-Up Dynamic Programming	O(kn²)	O(kn²)	Build probability table iteratively from base case to final answer

Recursive Simulation — Algorithm Steps

Start from initial position with k moves remaining
Try all 8 possible knight moves
Recursively calculate probability for each valid position
Return average probability across all moves

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Position

Start at given position with k moves

Try 8 Moves

Recursively explore each of 8 knight directions

Calculate Average

Sum probabilities and divide by 8

Code -

solution.c — C

#include <stdio.h>

int directions[8][2] = {{-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}};
int N;

int isValid(int r, int c) {
    return r >= 0 && r < N && c >= 0 && c < N;
}

double dfs(int r, int c, int movesLeft) {
    if (!isValid(r, c)) {
        return 0.0;
    }
    if (movesLeft == 0) {
        return 1.0;
    }
    
    double prob = 0.0;
    for (int i = 0; i < 8; i++) {
        int newR = r + directions[i][0];
        int newC = c + directions[i][1];
        prob += dfs(newR, newC, movesLeft - 1);
    }
    
    return prob / 8.0;
}

double solution(int n, int k, int row, int column) {
    N = n;
    return dfs(row, column, k);
}

int main() {
    int n, k, row, column;
    scanf("%d", &n);
    scanf("%d", &k);
    scanf("%d", &row);
    scanf("%d", &column);
    
    double result = solution(n, k, row, column);
    printf("%f\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(8^k)

Each position has 8 possible moves, and we explore k levels deep

✓ Linear Growth

Space Complexity

O(k)

Recursion stack depth is at most k moves

✓ Linear Space

89.6K Views

Medium Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler