What is the Probability that a Knight Stays on Chessboard

Given the size of the chess board and initial position of the knight, what is the probability that after k moves the knight will be inside the chess board.

1) The knight makes its all 8 possible moves with equal probability.
2) Once the knight is outside the chess board it cannot come back inside.



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 memoize this information in a tabular form.


#define MAXSIZE 100
#define MAXK 100

int vis[MAXSIZE][MAXSIZE][MAXK]; //stores 1 if there is a corresponding dp entry, 0 otherwise

double prob_knight(int x, int y, int size, int step, int k)
    //if knight is outside the board
    if(x < 0 || y < 0 || x >= size || y >= size) return 0;
    //if all moves are exhausted
    if(step == k) return 1;

    //if dp table has the this value stored return it
    if(vis[x][y][k] != 0)
        return dp[x][y][k];

    vis[x][y][step] = 1;

    //all possible x direction's for knight to move
    int dirx[] = {2, 2, -2, -2, 1, 1, -1, -1};
    //corresponding y direction for knight
    int diry[] = {1, -1, 1, -1, 2, -2, 2, -2};

    double ans = 0;
    for(int i = 0;i < 8; ++i){
        //knight makes the next move with probability (1 / 8)
        ans = ans + ((double)1 / (double)8) * prob_knight(x + dirx[i], y + diry[i], size, step + 1, k);

    //update the dp table
    dp[x][y][k] = ans;

    return ans;

Expected time complexity:
O((n ^ 2) * k) where n is the size of the board and k is the number of moves.

Expected space complexity:
O((n ^ 2) * k) where n is the size of the board and k is the number of moves.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation