I was trying out

CodePudding user response：

Top down approach:

Let P(x, y, k) be the probability that the knight is at the square (x, y) at the k-th step. Look at all squares that the knight could have come from (you can get them in O(1), just look at the board with a pen and paper and get the formulas from the different cases, like knight in the corner, knight in the border, knight in a central region etc). Let them be (x1, y1), ... (xj, yj). For each of these squares, what is the probability that the knight jumps to (x, y) ? Considering that it can go out of the border, it's always 1/8. So:

P(x, y, k) = (P(x1, y1, k-1) ... P(xj, yj, k-1))/8

The base case is k = 0.

P(x, y ,0) = 1 if (x, y) = (x_start, y_start) and P(x, y, 0) = 0 otherwise.

That is your recurrence formula. You can use dynamic programming to calculate it.

Open question: how to analyze the time complexity of this solution ? Is it equivalent to the bottom-up approach described in my other answer ?

CodePudding user response：

Bottom up approach:

Start by filling P(x_start, y_start, 0) = 1 and setting (x_start, y_start) in a map (from positions to booleans) previous_layer_map. Also, set the counter current_layer to 1.

Iterate though each of the n^2 positions of the board. For each of them, check in O(1) if it reaches a square in previous_layer_map. If so:

If (x, y) was never saw before in the current layer (current_layer_map[x][y] == false), fill

P(x, y, current_layer) = P(x_reached, y_reached, current_layer-1)/8

and set (x, y) in current_layer_map.

Else, set

P(x, y, current_layer) = P(x_reached, y_reached, current_layer-1)/8

After you finish iterating though each of the n^2 positions of the board, empty previous_layer_map, fill it with the elements of current_layer_map and empty current_layer_map. Also, increase the counter current_layer. Then, start a new iteration. Go like this until you reach the k-th layer.

Total time complexity: O(k * n^2).