The problem of a chess horse and probability

Hello.

Not so long ago, I came across an interesting problem, the condition and solution of which I want to share. I hope it will not be a terrible "accordion". So, imagine a standard chessboard 8x8 , on which there is not a single figure. Further, we randomly place the knight in any cage. The task is to determine the probability that after N moves randomly, he will remain on the chessboard. It is assumed that if a horse leaves the board, he cannot re-enter. And each of the possible moves is equally probable. In other words, you need to implement a function:

double probability(int N, int x, int y), 0 <= x <= 7, 0 <= y <= 7, 

where N is the number of moves, and x and y are the coordinates of the initial position.

If several solutions to this problem: Markov chains and dynamic programming. Here I want to propose a solution using the technique of dynamic programming. The idea is to track the probability that the knight will be in a certain cell with each i- th move.
')
From each position a knight can make one of 8 possible moves (gray marks possible moves)



It is convenient to write down all possible positions for the current cell if you enter 2 arrays:

 int dx[] = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 }; int dy[] = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 }; 

then the next state will be

 (x + dx[i], y + dy[i]), 0 <= i <= 7. 

Next, we introduce an array of probability [steps] [xPos, yPos] , where steps is the number of steps already taken, and xPos and yPos are the cell coordinates of the board. In the starting cell, the probability is 1 , and on all the others it is 0 . After each move, the probability on one of the possible cells will be 1/8 , and on the rest, 0 will remain. Then, after N moves for any particular cell, the probability will be as the sum of the probabilities of possible cells in N-1 moves. Thus, we can calculate the probability after each move for all 64 cells and get an algorithm:

 double probability(int N, int startX, int startY) { double probability[][][] = new double[N + 1][8][8]; // init to 1 for beginning position for (int x = 0; x < 8; x++) { for (int y = 0; y < 8; y++) { probability[0][x][y] = 1; } } int dx[] = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 }; int dy[] = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 }; for(int n = 1; n <= N; n++) { for(int x = 0; x < 8; x ++) { for(int y = 0; y < 8; y++) { double currentProbability = 0.0; for(int i = 0; i < 8; i++) { if (x+dx[i] >= 0 && x+dx[i] < 8 && y+dy[i] >= 0 && y+dy[i] < 8) { currentProbability += probability[n-1][y+dy[i]][x+dx[i]] / 8.0; } } probability[n][y][x] = currentProbability; } } } return probability[N][startX][startY]; } 

Waiting for comments and possibly other ways to solve this problem. The finished implementation can be downloaded here .