Knight Probability in Chessboard

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
3 upvotes
Asked in companies
Goldman SachsPhonePeAmazon

Problem statement

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).

chessboard

(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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 1
2 2
3 2
0 0
Sample Output 1:
1.000000
0.062500
Explanation For Sample Input 1:
In test case 1: 
Refer to the diagram above.
From positions (2,2) you can make 8 possible moves all of which lie within the chessboard.

In test case 2:
There are two possible moves (out of 8) from  (0,0) i.e. 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 (4/64).
Sample Input 2:
2
15 5
5 7
20 1
10 2
Sample Output 2:
0.885132
1.000000
Explanation For Sample Input 2:
In test case 1, the total probability of knight been in chessboard is 0.885132.

In test case 2, the knight will remain in the chessboard only after a move. Thus, its probability is 1.
Hint

Try to find all possible place where knight will move after K steps.

Approaches (2)
Recursive Solution

Explanation:

  1. The key point in this approach is we will calculate our answer recursively by visiting all possible positions.
  2. If after kth step we are within chessboard we return 1. If we are outside we return 0.
  3. 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:

  1. 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.
  2. 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.
  3. We add up all the returned values and return it after dividing it by 8.
Time Complexity

O(8^K), where K is the number of moves.

 

From every position, we can move to 8 different positions on the chessboard. Hence the total number of moves possible is 8^K.

Space Complexity

O(8^K), where K is the number of moves.

 

No additional memory will be used except for the reserved stack memory as it can be of 8^K.

Code Solution
(100% EXP penalty)
Knight Probability in Chessboard
Full screen
Console