Problem Description
On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. Each time the knight is to move, it chooses one of eight possible moves uniformly at random 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.
Key Insights
- The knight has 8 possible moves from any position on the board.
- If the knight moves off the board, it is no longer considered in the probability.
- The problem can be solved using dynamic programming by storing the probabilities of the knight being on the board after each move.
- The base case is when k = 0, where the knight remains on the board with probability 1 if it starts on the board.
Space and Time Complexity
Time Complexity: O(k * n^2)
Space Complexity: O(n^2)
Solution
We can solve this problem using dynamic programming. We will create a 3D array (dp) where dp[i][j][m] represents the probability of the knight being on the board at position (i, j) after m moves. We will initialize the array for zero moves and then iterate through the number of moves, calculating the probability for each position based on the possible moves from the previous positions. The eight possible knight moves will be used to update the probabilities. Finally, we will sum up the probabilities of all positions on the board after k moves to get the final result.