Leetcode: Knight Probability in Chessboard: Recursive Solution

Problem Description

Problem description is given in Leetcode: Knight Probability in Chessboard.

Recursive Solution

At each position a knight may go to 8 new positions. Probability of moving to a new position is probability of being at current position divided by 8. Thus we can recursively calculate probabilities for each move. After last move, we can take sum of all probabilities which gives total probability of staying on board.

The knight starts at row r and column c in a board of NxN. K shows total moves, k shows kth move. Probability of being on board after k moves is given by function f.

At the beginning k=0. S contains 8 next possible positions where the knight can move from current position.

At the end where k=K and (c,r) is inside the board;

Implementation

Recursive implementation calculates probabilities by making depth-first-search in the movements space. Each recursive function call makes 8 new calls and takes average of the results and returns the average result.

There are 3 base cases.

• The night is off-board.
• The night makes K moves and still in the board.
• Current cell is already visited and probability value is cached.

In recursive case:

• Makes 8 recursive calls for possible 8 new positions.
• Take average of all probabilities returned by recursive calls. Cache the resulting probability.
• Return the probability.

class Solution {
    public double knightProbability(int N, int K, int r, int c) {
        double[][][] probs = new double[K+1][N][N];
        return recursiveFindProbability(N, K, r, c, probs);
    }
    
    public double recursiveFindProbability(int N, int K, int r, int c, double[][][] probs){
        boolean onBoard = areWeOnBoard(N, r, c);
        
        if(!onBoard)
            return 0;
        
        if(K==0)
            return 1.0;
        
        
        if(probs[K][r][c]>0){
            return probs[K][r][c];
        }
        
        int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};
        int[] dc = new int[]{1, -1, 2, -2, 2, -2, 1, -1};
        
        double probSum=0;
        for (int m=0;m<8;m++){
            int nr = r+dr[m];
            int nc = c+dc[m];
            
            probSum +=recursiveFindProbability(N, K-1, nr, nc, probs);
        }
        
        probSum/=8;
        
        probs[K][r][c] = probSum;
        
        return probSum;
    }
    
    public boolean areWeOnBoard(int N, int r, int c){
        if(r<N && r>=0 && c<N && c>=0)
            return true;
        
        return false;
    }
}

Complexity

Space complexity is . We need to keep probabilities for each cell after each move.

Time complexity is .

At each method execution, 8 more methods are called. Depth of the call tree is determined by K.