DAY 50 - Knight Probability in Chessboard
Tags: leetcode, cpp, tutorial
Published: 2023-07-23 16:37:58

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_](https://leetcode.com/problems/knight-probability-in-chessboard/description/)

_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._


![Knight's Moves](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6kn28pi9agcd6yjqe4tw.png)

_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.


![MoveSet](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zptfgdkv2jpoch4kzujd.png)


_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!