(8) Given the position(x, y) of a knight on an 8X8 chess board, what is the probability that it stays within the chess board after n moves? - Quora

(8) Given the position(x, y) of a knight on an 8X8 chess board, what is the probability that it stays within the chess board after n moves? - Quora

This is a problem from Topcoder: ChessKnight Problem Statement
A nice explanation of the solution can be found in the editorial here: 2005 TopCoder Collegiate Challenge

The problem can be solved if we write a function:

1	double FindProbability(x, y, step)

where

(x,y)

is the position of the knight on the chess board, and

step

is the number of steps remaining.

Given a position (x,y), the knight can move to 8 other locations. Hence, the probability that the knight will move to each of those 8 positions is 1/8.

Base cases:
There are 2 possible base cases:

1. If the position (x,y) is outside the board, then the probability that it is within the board is 0. So we just

   return 0;

   in this case
2. If step == 0, then we have no more moves left. In this case if the passed parameter (x,y) is within the board, then we

   return 1;

Recursion:
Once the base cases are figured out, it is easy to see that the recursion would be something like:


FindProbability(x, y, step) = $\sum_{i=1}^{8}$( FindProbability(next_x, next_y, step-1) ) / 8.0
where next_x, next_y are the possible next positions of the knight at position (x,y).

Memoization:
There are a lot of overlapping computations in the above recursion. There might be numerous calls to  the function

FindProbability

with the same parameters. In order to prevent recomputing these values again and again, we can simply cache the computed values every time we find them and just return this value for subsequent function calls with the same parameters.

For this, a 3D array

double 

memo

[

8

][

8

][

MAX_MOVES

]

is maintained, and the computed values are stored in the array.

Read full article from (8) Given the position(x, y) of a knight on an 8X8 chess board, what is the probability that it stays within the chess board after n moves? - Quora