onenoughtone

Code Implementation

Knight Probability in Chessboard Implementation

Below is the implementation of the knight probability in chessboard:

solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming (3D) approach.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbability(n, k, row, column) {
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize DP array
  // dp[m][r][c] = probability of the knight being at cell (r, c) after m moves
  const dp = Array(k + 1).fill().map(() =>
    Array(n).fill().map(() =>
      Array(n).fill(0.0)
    )
  );
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  dp[0][row][column] = 1.0;
 
  // Fill DP array
  for (let m = 1; m <= k; m++) {
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the previous position
          const prevRow = r - dr;
          const prevCol = c - dc;
 
          // If the previous position is valid (on the board)
          if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
            // Add the probability of the knight being at the previous position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            dp[m][r][c] += dp[m - 1][prevRow][prevCol] / 8.0;
          }
        }
      }
    }
  }
 
  // Calculate the final probability: sum of dp[k][r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += dp[k][r][c];
    }
  }
 
  return result;
}
 
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming with Space Optimization.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbabilityOptimized(n, k, row, column) {
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize arrays for previous and current moves
  let prev = Array(n).fill().map(() => Array(n).fill(0.0));
  let curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  prev[row][column] = 1.0;
 
  // Fill arrays
  for (let m = 1; m <= k; m++) {
    // Reset curr array
    curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the previous position
          const prevRow = r - dr;
          const prevCol = c - dc;
 
          // If the previous position is valid (on the board)
          if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
            // Add the probability of the knight being at the previous position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            curr[r][c] += prev[prevRow][prevCol] / 8.0;
          }
        }
      }
    }
 
    // Update prev array
    prev = curr.map(row => [...row]);
  }
 
  // Calculate the final probability: sum of prev[r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += prev[r][c];
    }
  }
 
  return result;
}
 
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming with further optimization.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbabilityMoreOptimized(n, k, row, column) {
  // Early return for edge cases
  if (k === 0) {
    return 1.0;
  }
 
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize arrays for previous and current moves
  let prev = Array(n).fill().map(() => Array(n).fill(0.0));
  let curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  prev[row][column] = 1.0;
 
  // Fill arrays
  for (let m = 1; m <= k; m++) {
    // Reset curr array
    curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (prev[r][c] === 0.0) {
          continue;  // Skip cells with zero probability
        }
 
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the next position
          const nextRow = r + dr;
          const nextCol = c + dc;
 
          // If the next position is valid (on the board)
          if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n) {
            // Add the probability of the knight being at the current position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            curr[nextRow][nextCol] += prev[r][c] / 8.0;
          }
        }
      }
    }
 
    // Update prev array
    prev = curr.map(row => [...row]);
  }
 
  // Calculate the final probability: sum of prev[r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += prev[r][c];
    }
  }
 
  return result;
}
 
// Test cases
console.log(knightProbability(3, 2, 0, 0));  // 0.06250
console.log(knightProbability(1, 0, 0, 0));  // 1.00000
console.log(knightProbability(8, 3, 3, 3));  // 0.33594
 
console.log(knightProbabilityOptimized(3, 2, 0, 0));  // 0.06250
console.log(knightProbabilityOptimized(1, 0, 0, 0));  // 1.00000
console.log(knightProbabilityOptimized(8, 3, 3, 3));  // 0.33594
 
console.log(knightProbabilityMoreOptimized(3, 2, 0, 0));  // 0.06250
console.log(knightProbabilityMoreOptimized(1, 0, 0, 0));  // 1.00000
console.log(knightProbabilityMoreOptimized(8, 3, 3, 3));  // 0.33594

Step-by-Step Explanation

Let's break down the implementation:

Define Knight Moves: Define the possible knight moves on a chessboard, considering the L-shaped movement pattern of a chess knight.
Initialize DP Array: Set up a dynamic programming array to keep track of the probability of the knight being at each cell after a certain number of moves.
Establish Base Case: Define the base case: the knight is at the starting position with 100% probability after 0 moves.
Fill DP Array: For each move and each cell on the board, calculate the probability of the knight being at that cell by considering all possible previous positions.
Calculate Final Probability: Sum up the probabilities of the knight being at each cell on the board after k moves to get the final probability.

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Implement the knight probability in chessboard solution in different programming languages.

Knight Probability in Chessboard Implementation

Below is the implementation of the knight probability in chessboard in different programming languages. Select a language tab to view the corresponding code.

solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming (3D) approach.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbability(n, k, row, column) {
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize DP array
  // dp[m][r][c] = probability of the knight being at cell (r, c) after m moves
  const dp = Array(k + 1).fill().map(() =>
    Array(n).fill().map(() =>
      Array(n).fill(0.0)
    )
  );
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  dp[0][row][column] = 1.0;
 
  // Fill DP array
  for (let m = 1; m <= k; m++) {
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the previous position
          const prevRow = r - dr;
          const prevCol = c - dc;
 
          // If the previous position is valid (on the board)
          if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
            // Add the probability of the knight being at the previous position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            dp[m][r][c] += dp[m - 1][prevRow][prevCol] / 8.0;
          }
        }
      }
    }
  }
 
  // Calculate the final probability: sum of dp[k][r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += dp[k][r][c];
    }
  }
 
  return result;
}
 
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming with Space Optimization.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbabilityOptimized(n, k, row, column) {
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize arrays for previous and current moves
  let prev = Array(n).fill().map(() => Array(n).fill(0.0));
  let curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  prev[row][column] = 1.0;
 
  // Fill arrays
  for (let m = 1; m <= k; m++) {
    // Reset curr array
    curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the previous position
          const prevRow = r - dr;
          const prevCol = c - dc;
 
          // If the previous position is valid (on the board)
          if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
            // Add the probability of the knight being at the previous position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            curr[r][c] += prev[prevRow][prevCol] / 8.0;
          }
        }
      }
    }
 
    // Update prev array
    prev = curr.map(row => [...row]);
  }
 
  // Calculate the final probability: sum of prev[r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += prev[r][c];
    }
  }
 
  return result;
}
 
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming with further optimization.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbabilityMoreOptimized(n, k, row, column) {
  // Early return for edge cases
  if (k === 0) {
    return 1.0;
  }
 
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize arrays for previous and current moves
  let prev = Array(n).fill().map(() => Array(n).fill(0.0));
  let curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  prev[row][column] = 1.0;
 
  // Fill arrays
  for (let m = 1; m <= k; m++) {
    // Reset curr array
    curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (prev[r][c] === 0.0) {
          continue;  // Skip cells with zero probability
        }
 
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the next position
          const nextRow = r + dr;
          const nextCol = c + dc;
 
          // If the next position is valid (on the board)
          if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n) {
            // Add the probability of the knight being at the current position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            curr[nextRow][nextCol] += prev[r][c] / 8.0;
          }
        }
      }
    }
 
    // Update prev array
    prev = curr.map(row => [...row]);
  }
 
  // Calculate the final probability: sum of prev[r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += prev[r][c];
    }
  }
 
  return result;
}
 
// Test cases
console.log(knightProbability(3, 2, 0, 0));  // 0.06250
console.log(knightProbability(1, 0, 0, 0));  // 1.00000
console.log(knightProbability(8, 3, 3, 3));  // 0.33594
 
console.log(knightProbabilityOptimized(3, 2, 0, 0));  // 0.06250
console.log(knightProbabilityOptimized(1, 0, 0, 0));  // 1.00000
console.log(knightProbabilityOptimized(8, 3, 3, 3));  // 0.33594
 
console.log(knightProbabilityMoreOptimized(3, 2, 0, 0));  // 0.06250
console.log(knightProbabilityMoreOptimized(1, 0, 0, 0));  // 1.00000
console.log(knightProbabilityMoreOptimized(8, 3, 3, 3));  // 0.33594

Step-by-Step Explanation

1Define Knight Moves

Define the possible knight moves on a chessboard, considering the L-shaped movement pattern of a chess knight.

2Initialize DP Array

Set up a dynamic programming array to keep track of the probability of the knight being at each cell after a certain number of moves.

3Establish Base Case

Define the base case: the knight is at the starting position with 100% probability after 0 moves.

4Fill DP Array

For each move and each cell on the board, calculate the probability of the knight being at that cell by considering all possible previous positions.

5Calculate Final Probability

Sum up the probabilities of the knight being at each cell on the board after k moves to get the final probability.

Language-Specific Notes

javascript

JavaScript's Array.fill().map() is used to create multi-dimensional arrays.
The map(row => [...row]) method is used to create a deep copy of a 2D array.
The continue statement is used to skip cells with zero probability in the more optimized approach.
Early return for edge cases (k === 0) improves performance by avoiding unnecessary calculations.
The === operator is used for strict equality comparison.

python

Python's list comprehension [[[0.0 for _ in range(n)] for _ in range(n)] for _ in range(k + 1)] is used to create multi-dimensional arrays.
The [row[:] for row in curr] syntax is used to create a deep copy of a 2D array.
The continue statement is used to skip cells with zero probability in the more optimized approach.
Early return for edge cases (k == 0) improves performance by avoiding unnecessary calculations.
The == operator is used for equality comparison.

java

Java's multi-dimensional arrays are created using the new keyword.
The clone() method is used to create a shallow copy of an array, so we need to clone each row separately for a deep copy.
The continue statement is used to skip cells with zero probability in the more optimized approach.
Early return for edge cases (k == 0) improves performance by avoiding unnecessary calculations.
Enhanced for loops (for (int[] dir : directions)) are used for cleaner iteration over arrays.

cpp

C++'s std::vector is used to create multi-dimensional arrays.
The std::pair class is used to represent the knight's moves as pairs of integers.
The continue statement is used to skip cells with zero probability in the more optimized approach.
Early return for edge cases (k == 0) improves performance by avoiding unnecessary calculations.
The std::cout.precision() and std::fixed manipulators are used to format the output with a fixed number of decimal places.

Key Takeaways

This problem can be solved using dynamic programming by keeping track of the probability of the knight being at each cell after a certain number of moves.
The space complexity can be optimized by only keeping track of the previous and current states.
Further optimization can be achieved by skipping cells with zero probability.
Understanding the constraints of the knight's movement on a chessboard is crucial for solving this problem.
The final probability is the sum of the probabilities of the knight being at each cell on the board after k moves.

Try It Yourself

Modify the code to implement an alternative approach and test it with the same examples.

Challenge:

Implement a function that solves the knight probability in chessboard problem using a different approach than shown above.

Common Edge Cases

Zero Moves

Handle the case where k is 0 (the knight is already on the board with 100% probability).

n = 1, k = 0, row = 0, column = 0

Small Board

Handle the case where the board is small (n = 1), which limits the knight's possible moves.

n = 1, k = 1, row = 0, column = 0

Large Board and Many Moves

Handle the case where the board is large and the knight makes many moves, which can lead to a very small probability.

n = 25, k = 100, row = 0, column = 0

Solution Approach All Problems

Problem Solution Code

onenoughtone

Back to Home

onenoughtone

Back to Home

Knight Probability in Chessboard - Implementation

Code Implementation

Knight Probability in Chessboard Implementation

Below is the implementation of the knight probability in chessboard:

solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming (3D) approach.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbability(n, k, row, column) {
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize DP array
  // dp[m][r][c] = probability of the knight being at cell (r, c) after m moves
  const dp = Array(k + 1).fill().map(() =>
    Array(n).fill().map(() =>
      Array(n).fill(0.0)
    )
  );
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  dp[0][row][column] = 1.0;
 
  // Fill DP array
  for (let m = 1; m <= k; m++) {
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the previous position
          const prevRow = r - dr;
          const prevCol = c - dc;
 
          // If the previous position is valid (on the board)
          if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
            // Add the probability of the knight being at the previous position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            dp[m][r][c] += dp[m - 1][prevRow][prevCol] / 8.0;
          }
        }
      }
    }
  }
 
  // Calculate the final probability: sum of dp[k][r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += dp[k][r][c];
    }
  }
 
  return result;
}
 
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming with Space Optimization.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbabilityOptimized(n, k, row, column) {
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize arrays for previous and current moves
  let prev = Array(n).fill().map(() => Array(n).fill(0.0));
  let curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  prev[row][column] = 1.0;
 
  // Fill arrays
  for (let m = 1; m <= k; m++) {
    // Reset curr array
    curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the previous position
          const prevRow = r - dr;
          const prevCol = c - dc;
 
          // If the previous position is valid (on the board)
          if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
            // Add the probability of the knight being at the previous position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            curr[r][c] += prev[prevRow][prevCol] / 8.0;
          }
        }
      }
    }
 
    // Update prev array
    prev = curr.map(row => [...row]);
  }
 
  // Calculate the final probability: sum of prev[r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += prev[r][c];
    }
  }
 
  return result;
}
 
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming with further optimization.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbabilityMoreOptimized(n, k, row, column) {
  // Early return for edge cases
  if (k === 0) {
    return 1.0;
  }
 
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize arrays for previous and current moves
  let prev = Array(n).fill().map(() => Array(n).fill(0.0));
  let curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  prev[row][column] = 1.0;
 
  // Fill arrays
  for (let m = 1; m <= k; m++) {
    // Reset curr array
    curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (prev[r][c] === 0.0) {
          continue;  // Skip cells with zero probability
        }
 
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the next position
          const nextRow = r + dr;
          const nextCol = c + dc;
 
          // If the next position is valid (on the board)
          if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n) {
            // Add the probability of the knight being at the current position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            curr[nextRow][nextCol] += prev[r][c] / 8.0;
          }
        }
      }
    }
 
    // Update prev array
    prev = curr.map(row => [...row]);
  }
 
  // Calculate the final probability: sum of prev[r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += prev[r][c];
    }
  }
 
  return result;
}
 
// Test cases
console.log(knightProbability(3, 2, 0, 0));  // 0.06250
console.log(knightProbability(1, 0, 0, 0));  // 1.00000
console.log(knightProbability(8, 3, 3, 3));  // 0.33594
 
console.log(knightProbabilityOptimized(3, 2, 0, 0));  // 0.06250
console.log(knightProbabilityOptimized(1, 0, 0, 0));  // 1.00000
console.log(knightProbabilityOptimized(8, 3, 3, 3));  // 0.33594
 
console.log(knightProbabilityMoreOptimized(3, 2, 0, 0));  // 0.06250
console.log(knightProbabilityMoreOptimized(1, 0, 0, 0));  // 1.00000
console.log(knightProbabilityMoreOptimized(8, 3, 3, 3));  // 0.33594

Step-by-Step Explanation

Let's break down the implementation:

Define Knight Moves: Define the possible knight moves on a chessboard, considering the L-shaped movement pattern of a chess knight.
Initialize DP Array: Set up a dynamic programming array to keep track of the probability of the knight being at each cell after a certain number of moves.
Establish Base Case: Define the base case: the knight is at the starting position with 100% probability after 0 moves.
Fill DP Array: For each move and each cell on the board, calculate the probability of the knight being at that cell by considering all possible previous positions.
Calculate Final Probability: Sum up the probabilities of the knight being at each cell on the board after k moves to get the final probability.

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Implement the knight probability in chessboard solution in different programming languages.

Knight Probability in Chessboard Implementation

Below is the implementation of the knight probability in chessboard in different programming languages. Select a language tab to view the corresponding code.

solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming (3D) approach.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbability(n, k, row, column) {
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize DP array
  // dp[m][r][c] = probability of the knight being at cell (r, c) after m moves
  const dp = Array(k + 1).fill().map(() =>
    Array(n).fill().map(() =>
      Array(n).fill(0.0)
    )
  );
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  dp[0][row][column] = 1.0;
 
  // Fill DP array
  for (let m = 1; m <= k; m++) {
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the previous position
          const prevRow = r - dr;
          const prevCol = c - dc;
 
          // If the previous position is valid (on the board)
          if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
            // Add the probability of the knight being at the previous position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            dp[m][r][c] += dp[m - 1][prevRow][prevCol] / 8.0;
          }
        }
      }
    }
  }
 
  // Calculate the final probability: sum of dp[k][r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += dp[k][r][c];
    }
  }
 
  return result;
}
 
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming with Space Optimization.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbabilityOptimized(n, k, row, column) {
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize arrays for previous and current moves
  let prev = Array(n).fill().map(() => Array(n).fill(0.0));
  let curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  prev[row][column] = 1.0;
 
  // Fill arrays
  for (let m = 1; m <= k; m++) {
    // Reset curr array
    curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the previous position
          const prevRow = r - dr;
          const prevCol = c - dc;
 
          // If the previous position is valid (on the board)
          if (prevRow >= 0 && prevRow < n && prevCol >= 0 && prevCol < n) {
            // Add the probability of the knight being at the previous position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            curr[r][c] += prev[prevRow][prevCol] / 8.0;
          }
        }
      }
    }
 
    // Update prev array
    prev = curr.map(row => [...row]);
  }
 
  // Calculate the final probability: sum of prev[r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += prev[r][c];
    }
  }
 
  return result;
}
 
/**
 * Calculate the probability that the knight remains on the board after k moves.
 * Dynamic Programming with further optimization.
 *
 * @param {number} n - Size of the chessboard
 * @param {number} k - Number of moves
 * @param {number} row - Starting row
 * @param {number} column - Starting column
 * @return {number} - Probability that the knight remains on the board
 */
function knightProbabilityMoreOptimized(n, k, row, column) {
  // Early return for edge cases
  if (k === 0) {
    return 1.0;
  }
 
  // Define the possible knight moves
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];
 
  // Initialize arrays for previous and current moves
  let prev = Array(n).fill().map(() => Array(n).fill(0.0));
  let curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
  // Base case: the knight is at the starting position with 100% probability after 0 moves
  prev[row][column] = 1.0;
 
  // Fill arrays
  for (let m = 1; m <= k; m++) {
    // Reset curr array
    curr = Array(n).fill().map(() => Array(n).fill(0.0));
 
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (prev[r][c] === 0.0) {
          continue;  // Skip cells with zero probability
        }
 
        // For each possible knight move
        for (const [dr, dc] of directions) {
          // Calculate the next position
          const nextRow = r + dr;
          const nextCol = c + dc;
 
          // If the next position is valid (on the board)
          if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n) {
            // Add the probability of the knight being at the current position
            // divided by 8 (since there are 8 possible moves, each with equal probability)
            curr[nextRow][nextCol] += prev[r][c] / 8.0;
          }
        }
      }
    }
 
    // Update prev array
    prev = curr.map(row => [...row]);
  }
 
  // Calculate the final probability: sum of prev[r][c] for all cells (r, c) on the board
  let result = 0.0;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      result += prev[r][c];
    }
  }
 
  return result;
}
 
// Test cases
console.log(knightProbability(3, 2, 0, 0));  // 0.06250
console.log(knightProbability(1, 0, 0, 0));  // 1.00000
console.log(knightProbability(8, 3, 3, 3));  // 0.33594
 
console.log(knightProbabilityOptimized(3, 2, 0, 0));  // 0.06250
console.log(knightProbabilityOptimized(1, 0, 0, 0));  // 1.00000
console.log(knightProbabilityOptimized(8, 3, 3, 3));  // 0.33594
 
console.log(knightProbabilityMoreOptimized(3, 2, 0, 0));  // 0.06250
console.log(knightProbabilityMoreOptimized(1, 0, 0, 0));  // 1.00000
console.log(knightProbabilityMoreOptimized(8, 3, 3, 3));  // 0.33594

Step-by-Step Explanation

1Define Knight Moves

Define the possible knight moves on a chessboard, considering the L-shaped movement pattern of a chess knight.

2Initialize DP Array

Set up a dynamic programming array to keep track of the probability of the knight being at each cell after a certain number of moves.

3Establish Base Case

Define the base case: the knight is at the starting position with 100% probability after 0 moves.

4Fill DP Array

For each move and each cell on the board, calculate the probability of the knight being at that cell by considering all possible previous positions.

5Calculate Final Probability

Sum up the probabilities of the knight being at each cell on the board after k moves to get the final probability.

Language-Specific Notes

javascript

JavaScript's Array.fill().map() is used to create multi-dimensional arrays.
The map(row => [...row]) method is used to create a deep copy of a 2D array.
The continue statement is used to skip cells with zero probability in the more optimized approach.
Early return for edge cases (k === 0) improves performance by avoiding unnecessary calculations.
The === operator is used for strict equality comparison.

python

Python's list comprehension [[[0.0 for _ in range(n)] for _ in range(n)] for _ in range(k + 1)] is used to create multi-dimensional arrays.
The [row[:] for row in curr] syntax is used to create a deep copy of a 2D array.
The continue statement is used to skip cells with zero probability in the more optimized approach.
Early return for edge cases (k == 0) improves performance by avoiding unnecessary calculations.
The == operator is used for equality comparison.

java

Java's multi-dimensional arrays are created using the new keyword.
The clone() method is used to create a shallow copy of an array, so we need to clone each row separately for a deep copy.
The continue statement is used to skip cells with zero probability in the more optimized approach.
Early return for edge cases (k == 0) improves performance by avoiding unnecessary calculations.
Enhanced for loops (for (int[] dir : directions)) are used for cleaner iteration over arrays.

cpp

C++'s std::vector is used to create multi-dimensional arrays.
The std::pair class is used to represent the knight's moves as pairs of integers.
The continue statement is used to skip cells with zero probability in the more optimized approach.
Early return for edge cases (k == 0) improves performance by avoiding unnecessary calculations.
The std::cout.precision() and std::fixed manipulators are used to format the output with a fixed number of decimal places.

Key Takeaways

This problem can be solved using dynamic programming by keeping track of the probability of the knight being at each cell after a certain number of moves.
The space complexity can be optimized by only keeping track of the previous and current states.
Further optimization can be achieved by skipping cells with zero probability.
Understanding the constraints of the knight's movement on a chessboard is crucial for solving this problem.
The final probability is the sum of the probabilities of the knight being at each cell on the board after k moves.

Try It Yourself

Modify the code to implement an alternative approach and test it with the same examples.

Challenge:

Implement a function that solves the knight probability in chessboard problem using a different approach than shown above.

Common Edge Cases

Zero Moves

Handle the case where k is 0 (the knight is already on the board with 100% probability).

n = 1, k = 0, row = 0, column = 0

Small Board

Handle the case where the board is small (n = 1), which limits the knight's possible moves.

n = 1, k = 1, row = 0, column = 0

Large Board and Many Moves

Handle the case where the board is large and the knight makes many moves, which can lead to a very small probability.

n = 25, k = 100, row = 0, column = 0

Solution Approach All Problems

Code Implementation

Knight Probability in Chessboard Implementation

Step-by-Step Explanation

String ProblemsShow All

Palindrome Checker

Message Encryption

Word Puzzle Challenge

Learning Objective

Knight Probability in Chessboard Implementation

Step-by-Step Explanation

1Define Knight Moves

2Initialize DP Array

3Establish Base Case

4Fill DP Array

5Calculate Final Probability

Language-Specific Notes

javascript

python

java

cpp

Key Takeaways

Try It Yourself

Challenge:

Common Edge Cases

Zero Moves

Small Board

Large Board and Many Moves

Knight Probability in Chessboard - Implementation

Code Implementation

Knight Probability in Chessboard Implementation

Step-by-Step Explanation

String ProblemsShow All

Palindrome Checker

Message Encryption

Word Puzzle Challenge

Learning Objective

Knight Probability in Chessboard Implementation

Step-by-Step Explanation

1Define Knight Moves

2Initialize DP Array

3Establish Base Case

4Fill DP Array

5Calculate Final Probability

Language-Specific Notes

javascript

python

java

cpp

Key Takeaways

Try It Yourself

Challenge:

Common Edge Cases

Zero Moves

Small Board

Large Board and Many Moves

String Problems

String Problems