Knight Probability in Chessboard

class Solution {
public:
    double knightProbability(int n, int k, int startRow, int startCol) {
        vector<vector<int>> moves = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
        vector dp(k + 1, vector<vector<double>>(n, vector<double>(n, -1)));

        auto solve = [&](int moveLeft, int x, int y) -> double {
            if (moveLeft == 0) {
                return x == startRow && y == startCol ? 1.0 : 0.0;
            }

            if (dp[moveLeft][x][y] != -1) return dp[moveLeft][x][y];

            dp[moveLeft][x][y] = 0;
            for (const auto& move : moves) {
                int nx = x + move[0];
                int ny = y + move[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    dp[moveLeft][x][y] += solve(moveLeft - 1, nx, ny) / 8.0;
                }
            }
            return dp[moveLeft][x][y];
        };

        double probabilitySum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                probabilitySum += solve(k, i, j);
            }
        }

        return probabilitySum;
    }
};

The given C++ code implements a solution to calculate the probability that a knight remains on a chessboard after making a certain number of moves. This is a classic dynamic programming problem that utilizes recursion and memoization for efficient computation.

• The function knightProbability takes four parameters:

  • n - size of the chessboard (n x n)
  • k - number of moves the knight is allowed to make
  • startRow and startCol - initial position of the knight on the chessboard

• The knight has 8 possible moves, which are stored in the moves vector. This vector dictates the movement pattern of a knight on a chessboard (moving in an "L" shape).

• A 3D vector, dp, is used to store the probabilities. This vector has dimensions [k+1][n][n] where k+1 is the number of moves, and n x n represents the chessboard. Initialization of all elements to -1 helps in memoization to indicate that a state has not yet been computed.

• The nested lambda function solve uses a recursive approach:

  • Base Case: If no moves are left (moveLeft == 0), return 1.0 if the knight is at the starting position (startRow, startCol), otherwise return 0.0.
  • Memoization Check: If the result for the current state has already been computed (dp[moveLeft][x][y] != -1), return the stored result.
  • Recursive Case: Recursively calculate the probability for all valid moves from the current position and update the dp vector.

• The probability of each position on the board after k moves is calculated by calling solve(k, i, j) for each cell (i, j) on the chessboard.

• Finally, all the probabilities are summed up to give the total probability of the knight remaining on the board after k moves, starting from (startRow, startCol).

This implementation makes effective use of dynamic programming techniques to avoid the recomputation of states, thereby optimizing the solution for problems with larger constraints.

class Solver {
    int[][] knightMoves = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};

    private double computeProbability(double[][][] prob, int steps, int x, int y, int size, int targetX, int targetY) {
        if (steps == 0) {
            return (x == targetX && y == targetY) ? 1 : 0;
        }
        
        if (prob[steps][x][y] != -1) {
            return prob[steps][x][y];
        }

        prob[steps][x][y] = 0;

        for (int[] move : knightMoves) {
            int newX = x + move[0];
            int newY = y + move[1];

            if (newX >= 0 && newX < size && newY >= 0 && newY < size) {
                prob[steps][x][y] += computeProbability(prob, steps - 1, newX, newY, size, targetX, targetY) / 8.0;
            }
        }

        return prob[steps][x][y];
    }

    public double knightProbability(int size, int steps, int targetX, int targetY) {
        double[][][] prob = new double[steps + 1][size][size];

        for (double[][] layer : prob) {
            for (double[] row : layer) {
                Arrays.fill(row, -1);
            }
        }

        double finalProbability = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                finalProbability += computeProbability(prob, steps, i, j, size, targetX, targetY);
            }
        }

        return finalProbability;
    }
}

This Java solution involves a function knightProbability designed to calculate the probability of a knight landing on a specific cell (targetX, targetY) on a chessboard of a given size after a number of steps. The code employs a recursive approach with memoization to efficiently calculate the required probabilities.

The approach utilizes a 3D array prob that stores intermediate probabilities for each cell at each step level to avoid redundant calculations, thus optimizing the performance significantly. The initial values in this array are set to -1, indicating that the probabilities for these states have not yet been computed.

Here's the step-by-step breakdown of the code logic:

1. Initialize the prob array, which will hold intermediate results, to prevent re-calculating probabilities for the same conditions multiple times.

2. Use a nested loop to iterate through each cell on the chessboard, calculating the total probability of reaching (targetX, targetY) from every possible starting position at 0 steps.

3. The helper method computeProbability recursively computes the probability of reaching (targetX, targetY) after a given number of steps from any starting position (x, y). If steps equals 0, the method directly checks if (x, y) is the target position and returns the appropriate probability.

4. Apply recursion with memoization: If the probability for current coordinates [steps][x][y] is pre-computed (!= -1), use that value. Otherwise, recursively compute the probability considering all possible knight moves and average the possible outcomes, dividing by 8 (the number of potential knight moves).

5. After calculating the probability for all starting positions, sum them up to get the final probability and return it from the knightProbability method.

By leveraging recursion and memoization with an array to store partial results, the solution efficiently calculates the desired probability with reduced computational overhead. This approach avoids unnecessary re-computation, enhancing the overall efficiency of the solution.

class Solution:
    def findKnightProbability(self, n: int, k: int, row: int, col: int) -> float:
        moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
        memo = [[[-1] * n for i in range(n)] for move in range(k + 1)]

        def explore(m, x, y):
            if m == 0:
                return 1 if x == row and y == col else 0
            if memo[m][x][y] != -1:
                return memo[m][x][y]

            memo[m][x][y] = 0
            for dx, dy in moves:
                nx, ny = x - dx, y - dy
                if 0 <= nx < n and 0 <= ny < n:
                    memo[m][x][y] += explore(m - 1, nx, ny)
            memo[m][x][y] /= 8

            return memo[m][x][y]

        result_probability = sum(explore(k, i, j) for i in range(n) for j in range(n))

        return result_probability

The Python solution provided calculates the Knight Probability on an n x n chessboard. The algorithm assesses the chances of the knight remaining on the chessboard after making k moves from a specified starting position (row, col). The solution uses dynamic programming with memoization to optimize the process, thus preventing re-computation for previously calculated states.

In the code:

• moves represents all possible moves of a knight from the current position.
• memo is used to store previously computed probabilities for different states of the board (defined for each k, row, and col).
• The helper function explore is implemented to calculate recursively the probability from a set position by attempting all possible knight moves. If the new position (nx, ny) is within the bounds of the board, then the exploration is continued recursively.
• The probability values are accumulated and averaged considering there are 8 possible knight moves.
• The result, result_probability, aggregates the probabilities for all positions on the board after k moves starting from any position, offering an overall probability.

Understand that this approach is computationally intensive, but memoization significantly enhances its efficiency by avoiding redundant calculations. Adjustments could be necessary for large k values or board sizes due to the exponential growth of recursive calls or memory demands.