Problem Statement
Knight Probability in Chessboard
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 about 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) and (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
Explanation: The knight is already on the board after making 0 moves.
Constraints
- 1 <= n <= 25
- 0 <= k <= 100
- 0 <= row, column <= n - 1
Problem Breakdown
To solve this problem, we need to:
- This problem can be solved using dynamic programming.
- We need to keep track of the probability of the knight being at each cell after a certain number of moves.
- The state of the DP array is defined by the current position (row, column) and the number of moves made so far.
- The recurrence relation involves considering all possible previous positions that can lead to the current position.
- The final probability is the sum of the probabilities of the knight being at each cell on the board after k moves.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Knight Probability in Chessboard
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 about 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:
There are two moves (to (1,2) and (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:
The knight is already on the board after making 0 moves.
Problem Breakdown
Constraints:
- 1 <= n <= 25
- 0 <= k <= 100
- 0 <= row, column <= n - 1
Key Insights:
This problem can be solved using dynamic programming.
We need to keep track of the probability of the knight being at each cell after a certain number of moves.
The state of the DP array is defined by the current position (row, column) and the number of moves made so far.
The recurrence relation involves considering all possible previous positions that can lead to the current position.
The final probability is the sum of the probabilities of the knight being at each cell on the board after k moves.
Real-World Application
This problem has several practical applications:
Probability Analysis
Calculating the probability of specific outcomes in games of chance or random processes.
Game Design
Designing games with complex movement patterns and calculating the probability of game states.
Simulation Systems
Creating simulation systems that model real-world processes with random movements.