Last Updated: 27 Feb, 2021
Knight Probability in Chessboard
Moderate
Asked in companies
You are given an N x N chessboard and a knight. On a chessboard, the knight can supposedly move in 8 different positions from its original position i.e. if the knight is originally at (i,j) then it can move to (i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1), (i + 1, j + 2), (i + 1, j - 2), (i - 1, j + 2), (i - 1, j - 2).
The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N - 1, N - 1).
(X is the Knight’s current position, O is the position Knight can visit in 1 move)
You have to make K such moves from the initial position of the knight and tell the probability of the knight being within the boundaries of the chessboard i.e you have to consider all possibilities of K moves and determine the probability that after these moves the knight will remain within the chess grid.
Note:
Print output up to 6 decimal places.
Input Format:
The first line of the input contains ‘T’ denoting the number of test cases.
In the first line of each test case take two space-separated integers, ‘N’ and ‘K’ denoting the dimension of the chessboard and the number of moves played by the knight.
In the second line of each test case take two space-separated integers, ‘Sx’ and ‘Sy’ denoting the initial position of the knight in the chessboard.
Output Format:
For each test case print the probability in the new line.
Print output up to 6 decimal places. Print the output for each test case in a separate line.
Constraints:
1 <= T <= 5
0 <= N <= 30
0 <= K <= 500
0 <= Sx, Sy <= N - 1
(Sx, Sy) being the initial coordinates of the knight.
Time Limit: 1 sec
Approaches
Explanation:
- The key point in this approach is we will calculate our answer recursively by visiting all possible positions.
- If after kth step we are within chessboard we return 1. If we are outside we return 0.
- From every position, there are 8 possible moves. Thus the probability of taking any one of the paths is ⅛ (as there are 8 possible moves). So the total probability of staying inside is the sum of probabilities from the new 8 positions divided by 8.
i.e.
P(i, j, k)= [ P(i + 2, j + 1, k - 1) + P(i + 2, j - 1, k - 1) + P(i - 2, j + 1, k - 1) + P(i - 2, j - 1, k - 1) + P(i + 1, j + 2, k - 1) + P(i + 1, j - 2, k - 1) P(i - 1, j + 2, k - 1) + P(i - 1, j - 2, k - 1) ] / 8
Where P(i, j, k) is the probability of remaining inside the chessboard when at position (i, j) and we have to make ‘k’ moves.
Algorithm:
- If ‘K’ is 0, it means we cannot make another move, so we check if we are within the chessboard or not and return 0 or 1 according to it.
- If ‘K’ is not 0, then from position (i, j) we move to correspond 8 possible positions and decrease ‘K’ by 1 and solve the problem recursively.
- We add up all the returned values and return it after dividing it by 8.
We just use memoization in the previous approach. After checking if k is 0 or not. We check if the current positions (i, j) and remaining steps k, are already calculated. If they are already calculated then we return the answer. Else we solve it using the above approach and cache it in the end.