# Knight Probability in Chessboard
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/knight-probability-in-chessboard)
Canonical: https://scaleengineer.com/dsa/problems/knight-probability-in-chessboard
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
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.

![](https://assets.glich.co/dsa/knight-probability-in-chessboard/image0.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

**Constraints:**

* `1 <= n <= 25`
* `0 <= k <= 100`
* `0 <= row, column <= n - 1`

# Approaches
## Brute-Force Recursion
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).
**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`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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)`.

## Dynamic Programming with Memoization
The brute-force approach suffers from re-computing the same subproblems. For instance, the probability of a knight staying on the board for `m` moves from cell `(r, c)` is always the same, regardless of how it arrived there. We can optimize this by using memoization, a top-down dynamic programming technique. We store the result for each state `(k, r, c)` in a 3D array. When the function is called with a state that has already been computed, we return the cached result instead of re-calculating it.
**Time:** O(k * n^2) - The number of states is `k * n * n`. Each state is computed once, and the computation involves a constant number of operations (a loop of 8). · **Space:** O(k * n^2) - The space is dominated by the memoization table of size `(k+1) * n * n`.
**Pros:** Efficient enough to pass the given constraints.; Guarantees that each subproblem is solved only once.
**Cons:** Requires a significant amount of memory, `O(k * n^2)`, which might be large for the given constraints.
### Explanation
This method avoids the exponential time complexity by ensuring that each unique subproblem `(k, r, c)` is solved only once. The state is defined by the number of moves remaining, the row, and the column. The number of unique states is `k * n * n`. For each state, we perform a constant number of operations (8 recursive calls, which now become lookups if the subproblem is solved). This drastically reduces the time complexity.

```java
class Solution {
    private int[][] moves = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
    private double[][][] memo;

    public double knightProbability(int n, int k, int row, int column) {
        memo = new double[k + 1][n][n];
        for (double[][] layer : memo) {
            for (double[] r : layer) {
                java.util.Arrays.fill(r, -1.0);
            }
        }
        return solve(n, k, row, column);
    }

    private double solve(int n, int k, int r, int c) {
        if (r < 0 || r >= n || c < 0 || c >= n) {
            return 0.0;
        }
        if (k == 0) {
            return 1.0;
        }
        if (memo[k][r][c] != -1.0) {
            return memo[k][r][c];
        }

        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);
        }

        memo[k][r][c] = probability;
        return probability;
    }
}
```
### Algorithm
1. This approach is an optimization of the brute-force recursion.
2. Create a 3D array `memo[k+1][n][n]` to store the results of subproblems. Initialize it with a value indicating that no state has been computed yet (e.g., -1).
3. Modify the recursive function `solve(k, r, c)`:
   - Before any computation, check if `memo[k][r][c]` has already been computed. If so, return the stored value.
   - The base cases and recursive logic remain the same as the brute-force approach.
   - After computing the probability for a state `(k, r, c)`, store it in `memo[k][r][c]` before returning.
4. The initial call remains `solve(k, row, column)`.

## Space-Optimized Bottom-Up Dynamic Programming
This approach uses a bottom-up, iterative dynamic programming method. Instead of calculating the probability of staying on the board from a certain point, we calculate the probability of the knight being at each cell `(r, c)` after `m` moves. We can observe that the probabilities for move `m` only depend on the probabilities from move `m-1`. This allows us to optimize space by only keeping track of the probabilities for the previous and current moves, using two 2D arrays.
**Time:** O(k * n^2) - We iterate `k` times. In each iteration, we scan the `n x n` board, and for each cell, we perform 8 constant-time operations. · **Space:** O(n^2) - We only need two 2D arrays of size `n x n` to store the probabilities for the current and next moves.
**Pros:** Most efficient approach in terms of space complexity.; Iterative nature avoids potential stack overflow issues from deep recursion.; Generally faster in practice due to better memory locality and no recursion overhead.
**Cons:** Can be slightly less intuitive to formulate compared to the recursive top-down approach.
### Explanation
We start with a probability of 1.0 at the starting cell and 0 everywhere else. Then, we simulate the process move by move for `k` moves. In each move, we calculate the probability distribution for the next state based on the current state. A `dp` grid stores the probabilities for the current move, and a `nextDp` grid is used to compute the probabilities for the next move. After computing all possibilities for the next move, `nextDp` becomes the new `dp` for the subsequent iteration. This avoids recursion and reduces space complexity significantly compared to the standard DP approach.

```java
class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] moves = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};

        double[][] dp = new double[n][n];
        dp[row][column] = 1.0;

        for (int move = 1; move <= k; move++) {
            double[][] nextDp = new double[n][n];
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    if (dp[r][c] > 0) {
                        for (int[] m : moves) {
                            int nextR = r + m[0];
                            int nextC = c + m[1];

                            if (nextR >= 0 && nextR < n && nextC >= 0 && nextC < n) {
                                nextDp[nextR][nextC] += dp[r][c] / 8.0;
                            }
                        }
                    }
                }
            }
            dp = nextDp;
        }

        double totalProbability = 0.0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                totalProbability += dp[r][c];
            }
        }

        return totalProbability;
    }
}
```
### Algorithm
1. Let `dp[r][c]` be the probability that the knight is at cell `(r, c)`.
2. Initialize a 2D array `dp` of size `n x n`. Set `dp[row][column] = 1.0` and all other cells to `0`.
3. Loop `k` times, once for each move.
4. In each iteration, create a new 2D array `nextDp` of size `n x n`, initialized to zeros.
5. Iterate through every cell `(r, c)` of the `dp` board.
6. If `dp[r][c] > 0`, it means there's a non-zero probability of the knight being at this cell.
7. For each of the 8 possible moves from `(r, c)` to a new cell `(nr, nc)`:
   - If `(nr, nc)` is within the board's boundaries, add the probability to the new cell: `nextDp[nr][nc] += dp[r][c] / 8.0`.
8. After iterating through all cells, `nextDp` holds the probabilities for the next move. Update `dp` by setting `dp = nextDp`.
9. After `k` iterations, the `dp` array contains the probability of the knight being at each cell.
10. The final answer is the sum of all values in the `dp` array.

# Solutions
### Java

```java
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 ]; } }
```

### CPP

```cpp
class Solution { public: double knightProbability ( int n , int k , int row , int column ) { double f [ k + 1 ][ n ][ n ]; memset ( f , 0 , sizeof ( f )); for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { f [ 0 ][ i ][ j ] = 1 ; } } int dirs [ 9 ] = { - 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 ]; } };
```

### Python

```python
class Solution : def knightProbability ( self , n : int , k : int , row : int , column : int ) -> float : f = [[[ 0 ] * n for _ in range ( n )] for _ in range ( k + 1 )] for i in range ( n ): for j in range ( n ): f [ 0 ][ i ][ j ] = 1 for h in range ( 1 , k + 1 ): for i in range ( n ): for j in range ( n ): for a , b in pairwise (( - 2 , - 1 , 2 , 1 , - 2 , 1 , 2 , - 1 , - 2 )): x , y = i + a , j + b if 0 <= x < n and 0 <= y < n : f [ h ][ i ][ j ] += f [ h - 1 ][ x ][ y ] / 8 return f [ k ][ row ][ column ]
```