DSA problem
Knight Probability in Chessboard
On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The knight chooses one of its eight possible L-shaped moves uniformly at random on every step, even if the chosen move would land it off the board. Once it leaves the board it stops moving entirely. Return the probability that the knight remains on the board after exactly k moves.
The natural framing of this problem is a probabilistic dynamic program over time. Let dp[t][r][c] be the probability that the knight is on cell (r, c) after exactly t random moves, conditional on it not having stepped off the board so far. Initially dp[0][row][column] = 1 and every other cell is zero, because the knight starts at a known cell with certainty.
The transition is a sum over the eight knight moves. From a cell (r, c) the knight reaches each of its eight neighbours with probability 1/8. So dp[t][r][c] is the sum over the eight predecessor cells (pr, pc) of dp[t - 1][pr][pc] / 8, where we only include predecessors that are on the board. Equivalently, it is easier to push probability forward: from each in-board cell at step t - 1 we send 1/8 of its probability to each of its eight neighbour cells, ignoring contributions that land off the board.
The answer is the total probability mass remaining on the board after k steps: sum of dp[k][r][c] over all in-board cells. The table has O(k * n^2) cells and each transition is constant work (eight neighbours), so the total time is O(k * n^2). Only two layers are ever needed at once, so the space can be reduced to O(n^2).
Examples
n = 3, k = 2, row = 0, column = 00.0625n = 1, k = 0, row = 0, column = 01.0n = 8, k = 30, row = 6, column = 40.00019Constraints
- 1 <= n <= 25
- 0 <= k <= 100
- 0 <= row, column <= n - 1
- Answers within 1e-5 of the true probability are accepted.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.