grid47 Exploring patterns and algorithms
Aug 30, 2024
7 min read
Solution to LeetCode 688: Knight Probability in Chessboard Problem
You are given an n x n chessboard and a knight that starts at a given position (row, column). The knight moves exactly k times and can randomly choose one of eight possible knight moves at each step. The task is to determine the probability that the knight remains on the board after completing all k moves.
Problem
Approach
Steps
Complexity
Input: The input consists of four integers: n (the size of the chessboard), k (the number of moves), row (the starting row), and column (the starting column).
Example: n = 4, k = 3, row = 1, column = 1
Constraints:
• 1 <= n <= 25
• 0 <= k <= 100
• 0 <= row, column <= n - 1
Output: Return a floating point number representing the probability that the knight remains on the chessboard after k moves.
Example: 0.1250
Constraints:
Goal: The goal is to compute the probability that after exactly k moves, the knight stays on the chessboard.
Steps:
• Use a depth-first search (DFS) approach to explore all possible knight moves.
• Memoize results to optimize redundant calculations.
• At each step, check if the knight remains within the bounds of the chessboard.
Goal: The input values are constrained as follows:
Steps:
• n is between 1 and 25.
• k is between 0 and 100.
• row and column are valid indices on the chessboard.
Assumptions:
• The knight will always move randomly and uniformly at each step.
• The chessboard is represented by a 2D grid with indices from 0 to n-1.
• Input: Example 1: n = 4, k = 3, row = 1, column = 1
• Explanation: The knight has multiple possible moves, but only a subset of these will keep the knight on the board. After exploring all moves, the probability is 0.125.
Approach: We will implement a recursive DFS approach to explore all possible knight movements, using memoization to optimize and prevent recalculating the same state multiple times.
Observations:
• The knight has 8 possible moves from any given position.
• The moves can go off the chessboard, so we must handle this case.
• This problem can be solved using a depth-first search (DFS) with memoization to avoid redundant calculations.
Steps:
• Define a recursive function dfs(k, i, j) to calculate the probability of the knight staying on the board after k moves from position (i, j).
• Memoize the results of dfs to avoid recalculating the same state.
• Base case: If the knight moves out of bounds, return 0.
• Recursive case: Calculate the probability for each of the 8 possible moves and aggregate the results.
Empty Inputs:
• If k = 0, the knight stays at the starting position, so the probability is 1.
Large Inputs:
• Ensure that the algorithm handles the maximum constraints efficiently.
Special Values:
• If the knight starts at the edge of the board, fewer moves will keep it on the board.
Constraints:
• The problem should handle up to 100 moves efficiently using memoization.
int n;
vector<vector<vector<double>>> memo;
doubleknightProbability(int n, int k, int row, int col) {
this->n = n;
memo.resize(k +1, vector<vector<double>>(n, vector<double>(n, 0)));
return dfs(k, row, col);
}
doubledfs(int k, int i, int j) {
if(i <0|| j <0|| i >= n || j >= n) return0;
if(k ==0) return1;
if(memo[k][i][j] !=0 ) return memo[k][i][j];
double res =0;
res +=0.125* dfs(k -1, i +1, j -2);
res +=0.125* dfs(k -1, i +1, j +2);
res +=0.125* dfs(k -1, i +2, j +1);
res +=0.125* dfs(k -1, i +2, j -1);
res +=0.125* dfs(k -1, i -1, j +2);
res +=0.125* dfs(k -1, i -1, j -2);
res +=0.125* dfs(k -1, i -2, j +1);
res +=0.125* dfs(k -1, i -2, j -1);
return memo[k][i][j] = res;
}
1 : Variable Initialization
int n;
This initializes the variable 'n', representing the size of the chessboard.
2 : Variable Initialization
vector<vector<vector<double>>> memo;
This initializes the 'memo' 3D vector, which is used to store previously computed probabilities for specific knight positions and moves.
3 : Method Definition
doubleknightProbability(int n, int k, int row, int col) {
This defines the function 'knightProbability' which calculates the probability of the knight's survival after 'k' moves from a given position (row, col).
4 : Variable Initialization
this->n = n;
This sets the class variable 'n' to the size of the chessboard passed into the function.
This resizes the 'memo' vector to accommodate all 'k' possible moves, with dimensions based on the size of the chessboard.
6 : Recursive Call
returndfs(k, row, col);
This calls the helper function 'dfs' (depth-first search) to recursively calculate the knight's survival probability, starting from the given position.
7 : Method Definition
doubledfs(int k, int i, int j) {
This defines the recursive 'dfs' function, which computes the probability of the knight surviving after 'k' moves from position (i, j).
8 : Base Condition
if(i <0|| j <0|| i >= n || j >= n) return0;
This checks if the knight's position is out of bounds of the chessboard, in which case the probability is 0.
9 : Base Condition
if(k ==0) return1;
This checks if there are no remaining moves ('k == 0'), returning 1, as the knight is still on the board.
10 : Memoization
if(memo[k][i][j] !=0 ) return memo[k][i][j];
This checks if the probability has already been calculated for this state (position and remaining moves). If so, it returns the memoized result.
11 : Variable Declaration
double res =0;
This initializes the variable 'res', which will accumulate the total probability for all possible moves.
12 : Recursive Call
res +=0.125* dfs(k -1, i +1, j -2);
This recursively calls 'dfs' for the knight's move to position (i + 1, j - 2), contributing 0.125 to the probability.
13 : Recursive Call
res +=0.125* dfs(k -1, i +1, j +2);
This recursively calls 'dfs' for the knight's move to position (i + 1, j + 2), contributing 0.125 to the probability.
14 : Recursive Call
res +=0.125* dfs(k -1, i +2, j +1);
This recursively calls 'dfs' for the knight's move to position (i + 2, j + 1), contributing 0.125 to the probability.
15 : Recursive Call
res +=0.125* dfs(k -1, i +2, j -1);
This recursively calls 'dfs' for the knight's move to position (i + 2, j - 1), contributing 0.125 to the probability.
16 : Recursive Call
res +=0.125* dfs(k -1, i -1, j +2);
This recursively calls 'dfs' for the knight's move to position (i - 1, j + 2), contributing 0.125 to the probability.
17 : Recursive Call
res +=0.125* dfs(k -1, i -1, j -2);
This recursively calls 'dfs' for the knight's move to position (i - 1, j - 2), contributing 0.125 to the probability.
18 : Recursive Call
res +=0.125* dfs(k -1, i -2, j +1);
This recursively calls 'dfs' for the knight's move to position (i - 2, j + 1), contributing 0.125 to the probability.
19 : Recursive Call
res +=0.125* dfs(k -1, i -2, j -1);
This recursively calls 'dfs' for the knight's move to position (i - 2, j - 1), contributing 0.125 to the probability.
20 : Return Statement
return memo[k][i][j] = res;
This stores the calculated probability in the 'memo' array and returns the result.
Best Case: O(k * n^2)
Average Case: O(k * n^2)
Worst Case: O(k * n^2)
Description: The time complexity is O(k * n^2) because we are recursively calculating for each position on the chessboard and each move.
Best Case: O(k * n^2)
Worst Case: O(k * n^2)
Description: The space complexity is O(k * n^2) due to memoization storage.
