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.
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.
Examples
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
Solution
Method 1 - Recursion (TLE)
We can start the DFS for k steps, and see what is the probability of landing in the board for each step.
Code
Java
private static final int[][] DIRS = {
{2, 1}, {2, -1}, {-2, 1}, {-2, -1},
{1, 2}, {1, -2}, {-1, 2}, {-1, -2}
};
public double knightProbability(int n, int k, int row, int column) {
return dfs(n, k, row, column);
}
public double dfs(int n, int k, int r, int c) {
if (r < 0 || r > n - 1 || c < 0 || c > n-1) {
return 0;
}
if (k == 0) {
return 1;
}
double probability = 0;
for(int[] dir: DIRS) {
probability += 0.125 * dfs(n, k - 1, r + DIRS[0], c + DIRS[1]);
}
return probability;
}
Python
def knightProbability(n, k, row, column):
# Possible moves of the knight
moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
def dfs(n, k, row, column):
# If out of bounds, return 0
if row < 0 or row >= n or column < 0 or column >= n:
return 0
# If no more moves left, return 1
if k == 0:
return 1
probability = 0
for move in moves:
next_row, next_column = row + move[0], column + move[1]
probability += dfs(n, k - 1, next_row, next_column) / 8
return probability
return dfs(n, k, row, column)
Complexity
- ⏰ Time complexity:
O(8^k)- At each step, the function makes up to 8 recursive calls (one for each possible knight move).
- The depth of the recursion is
k(the number of moves).
- 🧺 Space complexity:
O(k)assuming recursion stack
Dry Run
Lets take first example for that, so we take n = 3, k = 2, row = 0, and column = 0.
So, initial call to dfs will be dfs(3, 2, 0, 0). Now, we can move using following directions:
private static final int[][] DIRS = {
{2, 1}, {2, -1}, {-2, 1}, {-2, -1},
{1, 2}, {1, -2}, {-1, 2}, {-1, -2}
};
First level of recursion k = 2
From 0, 0 we can move to:
- Move(2, 1) ⇨
dfs(3, 1, 2, 1) - Move(2, -1) ⇨
dfs(3, 1, 2, -1)returns 0, as we are out of bounds - Move:
(-2, 1)⇨ returns 0, as we are out of bounds - Move:
(-2, -1)⇨ returns 0, as we are out of bounds - Move:
(1, 2)⇨dfs(3, 1, 1, 2) - Move:
(1, -2)⇨ returns 0, as we are out of bounds - Move:
(-1, 2)⇨ returns 0, as we are out of bounds - Move:
(-1, -2)⇨ returns 0, as we are out of bounds
Second level of recursion k = 2
From (2, 1)
We consider all possible moves from (2, 1):
- Move:
(4, 2)returns 0, as we are out of bounds - Move:
(4, 0)returns 0, as we are out of bounds - Move:
(0, 2) - Move:
(0, 0) - Move:
(3, 3)returns 0, as we are out of bounds - Move:
(3, -1)returns 0, as we are out of bounds - Move:
(1, 3)returns 0, as we are out of bounds - Move:
(1, -1)returns 0, as we are out of bounds
Now, as k is exhausted, and we return 1s:
dfs(3, 0, 0, 2) == 1 // Exact, moves exhausted, result 1
dfs(3, 0, 0, 0) == 1 // Exact, moves exhausted, result 1
Result from (2, 1) with k=1 is 2 / 8 = 0.25
From (1, 2)
We consider all possible moves from (1, 2):
- Move:
(3, 3)returns 0, as we are out of bounds - Move:
(3, 1)returns 0, as we are out of bounds - Move:
(-1, 3)returns 0, as we are out of bounds - Move:
(-1, 1)returns 0, as we are out of bounds - Move:
(2, 4)returns 0, as we are out of bounds - Move:
(2, 0) - Move:
(0, 4)returns 0, as we are out of bounds - Move:
(0, 0)
The recursive calls:
dfs(3, 0, 2, 0) == 1 // Exact, moves exhausted, result 1
dfs(3, 0, 0, 0) == 1 // Exact, moves exhausted, result 1
Result from (1, 2) with k=1 is 2 / 8 = 0.25
First level of recursion summary
Combining the results from non-out-of-bounds moves at k=2 from (0,0):
dfs(3, 2, 0, 0) = (0.25 + 0.25) / 8 * 8 = 0.50 / 8 = 0.125
Final result
We return 0.125 based on this.
Method 2 - Top Down DP
Code
Java
We can use double[row][column][k+1] as a cache to store the intermediate results, so that we can reuse them.
private static final int[][] DIRS = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
public double knightProbability(int n, int k, int row, int column) {
return dfs(n, k, row, column, new double[n][n][k + 1]);
}
public double dfs(int n, int k, int r, int c, double[][][] dp) {
if (r < 0 || r > n - 1 || c < 0 || c > n-1) {
return 0;
}
if (k == 0) {
return 1;
}
if(dp[r][c][k] != 0) {
return dp[r][c][k];
}
double probability = 0;
for(int[] dir: DIRS) {
probability += 0.125*dfs(n, k - 1, r + dir[0], c + dir[1], dp);
}
dp[r][c][k] = probability;
return probability;
}
Python
Here we are doing the same memoization with dictionary.
def knightProbability(n, k, row, column):
# Possible moves of the knight
moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
memo = {}
def dfs(n, k, row, column):
# If out of bounds, return 0
if row < 0 or row >= n or column < 0 or column >= n:
return 0
# If no more moves left, return 1
if k == 0:
return 1
# Check if the result is already calculated
if (k, row, column) in memo:
return memo[(k, row, column)]
probability = 0
for move in moves:
next_row, next_column = row + move[0], column + move[1]
probability += dfs(n, k - 1, next_row, next_column) / 8
memo[(k, row, column)] = probability
return probability
return dfs(n, k, row, column)
Complexity
- Time:
O(n^2*k)- The number of unique states is determined by the combination of
k,row, andcolumn. - The number of possible values for
rowandcolumnisn, and the number of possible values forkisk + 1. - So the total number of unique states is ( n \times n \times (k + 1) ).
- For each state, we explore up to 8 possible moves, making up to 8 recursive calls. However, due to memoization, each state is only computed once.
- The number of unique states is determined by the combination of
- Space:
O(n^2*k)for using memoization table (and also O(k) assuming recursion stack)
Method 3 - Bottom up DP
Code
Java
private static final int[][] DIRS = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
public double knightProbability(int n, int k, int row, int column) {
double[][][] dp = new double[k + 1][n][n];
dp[0][row][column] = 1;
for (int step = 1; step <= k; step++) {
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (dp[step - 1][r][c] > 0) {
for (int[] direction: directions) {
int nextRow = r + direction[0];
int nextColumn = c + direction[1];
if (nextRow >= 0 && nextRow < n && nextColumn >= 0 && nextColumn < n) {
dp[step][nextRow][nextColumn] += dp[step - 1][r][c] / 8.0;
}
}
}
}
}
}
double finalProbability = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
finalProbability += dp[k][r][c];
}
}
return finalProbability;
}
Python
def knightProbability(n, k, row, column):
# Possible moves of the knight
moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
# dp array to store the probabilities
dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
dp[0][row][column] = 1 # Initial position, 0 moves left
for step in range(1, k + 1):
for r in range(n):
for c in range(n):
for move in moves:
prev_row, prev_column = r + move[0], c + move[1]
if 0 <= prev_row < n and 0 <= prev_column < n:
dp[step][r][c] += dp[step - 1][prev_row][prev_column] / 8
# Calculate the final probability
final_probability = 0
for r in range(n):
for c in range(n):
final_probability += dp[k][r][c]
return final_probability
Complexity
- Time:
O(n^2*k) - Space:
O(n^2*k)