Given the size of the chess board and initial position of the knight, calculate the probability that after k
moves the knight will be inside the chess board.
Note:
The knight makes its all 8 possible moves with equal probability.
Once the knight is outside the chess board it cannot come back inside.
Input
Inputs are comma separated in the form:
l,k,x,y
where l
is the length and width of the chess board, k
is the number of moves the knight will make, x
is the x-position of the initial position of the knight, and y
is the y-position of the initial position of the knight. Note that 0,0
is the bottom-left corner of the board and l-1,l-1
is the top-right corner of the board.
Algorithm:
Start with the initial coordinates of the knight. Make all possible moves for this position and multiply these moves with their probability, for each move recursively call the function continue this process till the terminating condition is met. Terminating condition is if the knight is outside the chess board, in this case return 0, or the desired number of moves is exhausted, in this case return 1.
As we can see that the current state of the recursion is dependent only on the current coordinates and number of steps done so far. Therefore we can memorize this information in a tabular form.
Credit
This challenge is originally from a blog post of crazyforcode.com published under the CC BY-NC-ND 2.5 IN licence. It was slightly modified to make it a bit more challenging.