Knight Probability in Chessboard

Knight Probability in Chessboard

1. What is this problem about?

The Knight Probability in Chessboard interview question asks for the probability that a knight remains on an $N imes N$ board after $K$ random moves. In each step, the knight chooses one of its 8 legal moves with equal probability (1/8 each). If a move takes the knight off the board, it stays off forever.

2. Why is this asked in interviews?

Companies like Goldman Sachs and Google use the Knight Probability coding problem to test a candidate's understanding of Probability and DP. It evaluations whether you can distinguish between "counting paths" and "summing probabilities." It tests your ability to handle floating-point results and 3D state spaces.

3. Algorithmic pattern used

This problem uses Dynamic Programming with a probability state.

1. DP State: dp[k][r][c] is the probability the knight is at $(r, c)$ after exactly k moves.
2. Transition: The probability of being at $(r, c)$ at step $k$ is the sum of $(1/8 imes ext{probability at neighbor at step } k-1)$ for all neighbors that can jump to $(r, c)$.
3. Base Case: dp[0][startRow][startCol] = 1.0. All other cells at step 0 are 0.0.
4. Final Step: The answer is the sum of probabilities across all cells $(r, c)$ on the board at step $K$.

4. Example explanation

$3 imes 3$ board, start at (0,0), $K=1$.

• 8 possible moves from (0,0).
• Only 2 moves land on the board: (1,2) and (2,1).
• Each has 1/8 probability.
• Probability of being on board: $1/8 + 1/8 = 0.25$.

5. Common mistakes candidates make

• Simulating individual paths: Using random simulation (Monte Carlo) or recursion without memoization. Both are either too slow or too imprecise.
• Integer division: Performing $1/8$ as an integer (0) instead of a double (0.125).
• Redundant State: Using a full 3D array when you only need the previous 2D board state.

6. Interview preparation tip

Practice "state reduction" in DP. For problems where the current time/step only depends on the immediately preceding one, you can always optimize space complexity by using only two copies of the base structure (current and previous). This is a vital Matrix interview pattern trick.