Scale Engineer

Knight Probability in Chessboard

Med
#0642Time: O(8^k) - At each of the `k` steps, the function branches into 8 recursive calls. This leads to an exponential number of operations, making it infeasible for `k > 10`.Space: O(k) - This is due to the maximum depth of the recursion stack, which corresponds to the number of moves `k`.1 company
Patterns
Dynamic Programming
Companies
Citadel

Prompt

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 <= 25
  • 0 <= k <= 100
  • 0 <= row, column <= n - 1

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a straightforward recursive method to simulate the knight's movement. We define a function that explores all possible paths of length k from the starting position. For each step, the function recursively calls itself for all 8 possible moves, decrementing the remaining moves k. The probability is divided by 8 at each step. The base cases for the recursion are when the knight moves off the board (probability 0) or when it completes all k moves while on the board (probability 1 for that path).

Algorithm

  1. Define a recursive function solve(k, r, c) that computes the probability of the knight staying on the board.
  2. Base Cases:
    • If the knight is off the board (i.e., r < 0, r >= n, c < 0, or c >= n), it has failed to stay on. Return 0.
    • If the knight has made all k moves (i.e., k == 0), it has successfully stayed on the board for this path. Return 1.
  3. Recursive Step:
    • If k > 0 and the knight is on the board, it will make one of its 8 possible moves.
    • Initialize a variable probability = 0.
    • Iterate through all 8 possible moves (dr, dc).
    • For each move, recursively call solve(k - 1, r + dr, c + dc).
    • Since each move has a probability of 1/8, add (1/8) * solve(...) to the probability.
  4. Return the total probability.
  5. The initial call is solve(k, row, column).

Walkthrough

The core idea is to model the problem as a traversal of a state graph where each state is (moves_left, current_row, current_col). From any state, there are 8 possible transitions. The probability of a path of k moves is (1/8)^k. We need to count the number of valid paths that stay on the board for all k moves and multiply by (1/8)^k. The recursive function calculates this sum. However, since it re-calculates the result for the same state multiple times, its time complexity is exponential.

class Solution {    private int[][] moves = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};     public double knightProbability(int n, int k, int row, int column) {        return solve(n, k, row, column);    }     private double solve(int n, int k, int r, int c) {        // Base case 1: Knight is off the board        if (r < 0 || r >= n || c < 0 || c >= n) {            return 0.0;        }         // Base case 2: Knight has completed all moves        if (k == 0) {            return 1.0;        }         // Recursive step: Explore all 8 moves        double probability = 0.0;        for (int[] move : moves) {            int nextR = r + move[0];            int nextC = c + move[1];            probability += 0.125 * solve(n, k - 1, nextR, nextC);        }         return probability;    }}

Complexity

Time

O(8^k) - At each of the `k` steps, the function branches into 8 recursive calls. This leads to an exponential number of operations, making it infeasible for `k > 10`.

Space

O(k) - This is due to the maximum depth of the recursion stack, which corresponds to the number of moves `k`.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Directly translates the problem statement into code.

Cons

  • Extremely inefficient due to a massive number of redundant calculations for the same state (k, r, c).

  • Will result in a 'Time Limit Exceeded' error for most constraints given in the problem.

Solutions

class Solution { public double knightProbability ( int n , int k , int row , int column ) { double [][][] f = new double [ k + 1 ][ n ][ n ]; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { f [ 0 ][ i ][ j ] = 1 ; } } int [] dirs = {- 2 , - 1 , 2 , 1 , - 2 , 1 , 2 , - 1 , - 2 }; for ( int h = 1 ; h <= k ; ++ h ) { for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { for ( int p = 0 ; p < 8 ; ++ p ) { int x = i + dirs [ p ], 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 ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem