# Knight Probability in Chessboard

Posted: 27 Feb, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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)
``````

#### 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
`````` Approach 1

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.