DAY 50 - Knight Probability in Chessboard

Hey everyone! Welcome back to another day of problem-solving. It's day 50, and I'm still going strong on my quest for consistency.
It's 50th day today and we will be solving a problem of Dynamic Programming to refresh our concepts. This question has been taken from leetcode.

Question: Knight Probability in Chessboard

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

Intuition:

• Let's start by breaking down the question and noting down our observations.
• We are on a chessboard of size n x n represented by a 0 indexed matrix and we start on a given row and column.
• We can use any of the knight's moves and all have the equal probability of being taken place.
• If you look carefully our knight can move either {1,2} combinations as well as in negative side of the graph.

So our move set would be:
int moveSet[8][2] = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}}

• Since we are given options and we can choose only one of them. It sounds a lot like recursion and we know since in a chessboard you can visit multiple places once we simply use DP to memoize our recursive relation.

Algorithm:

Step 1: Setting Up the MoveSet Array:

• The code starts by defining a moveSet array, which contains all the possible moves that a knight can make in a single step. Each entry in the moveSet array represents a pair of (row, col) offsets corresponding to the eight possible moves (L-shaped movements) a knight can make on the chessboard.

Step 2: Checking if a Cell is on the Board:

• The isOnBoard function checks whether a given cell with coordinates (row, col) is within the bounds of the n x n chessboard. It returns true if the cell is on the board and false otherwise.

Step 3: Calculating Probability Using Dynamic Programming (DP):

• The helper function is the core of the algorithm, which uses dynamic programming to calculate the probability of a knight staying on the board after making k moves starting from the cell with coordinates (row, col).
• The function takes the current row, column, the remaining number of moves (k), and a 3D DP array dp as parameters.
• If the knight moves outside the board or no more moves are allowed (k = 0), the function returns the corresponding probabilities (0 or 1) as base cases.
• It then checks if the probability for the current cell with remaining moves is already computed and stored in the dp array. If yes, it directly returns the pre-computed probability.
• Otherwise, the function calculates the probability for the current cell by exploring all the possible moves the knight can make in one step.
• For each possible move, it recursively calls the helper function with reduced moves (k-1) and updated row and column positions.
• The probabilities from all the possible moves are summed up and divided by 8 (since there are 8 possible moves) to get the final probability for the current cell and remaining moves.
• The calculated probability is stored in the dp array for memoization to avoid redundant computations.

Step 4: Solving the Problem:

• The knightProbability function initializes a 3D DP array (dp) to store the calculated probabilities.
• It calls the helper function with the given parameters (n, k, row, column, dp) to calculate the probability of the knight staying on the board after k moves starting from the given cell.
• The final probability is returned as the result.

Code:

int moveSet[8][2] = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
    bool isOnBoard(int row, int col, int n){
        if(row >= 0 && row < n && col >=0 && col < n) return true;
    return false;
    }
    double helper(int n, int k, int row, int col,vector<vector<vector<double>>> &dp){
        if(!isOnBoard(row,col,n)) return 0;
        if(k == 0) return 1;
        if(dp[row][col][k] != -1){
            return dp[row][col][k];
        }
        double probability = 0;
        for(int i = 0; i < 8; i++){
            probability += helper(n,k-1,row + moveSet[i][0], col + moveSet[i][1], dp)/8.0;
        }
        return dp[row][col][k] = probability;
    }
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(n+1, vector<vector<double>>(n+1, vector<double>(k+1,-1)));
        return helper(n,k,row,column,dp);
    }

Complexity Analysis:

• Time: O(N^2*k*8)
• Space: O(N^2*K)

Thanks for reading. Feedback is highly appreciated!