Domain 2MediumMEDIUM

Knight Probability in Chessboard

LeetCode problem 688: Knight Probability in Chessboard (medium).

Domain: medium•Updated: 2026-08-30
#Dynamic Programming

Problem Breakdown

We are given an N×NN \times N chessboard where a knight starts at position (r,c)(r, c). The goal is to calculate the probability that the knight remains on the board after making exactly K random moves.

Inputs:

  • n: Integer representing board size (1≤n≤251 \le n \le 25).
  • k: Number of moves allowed (0≤k≤1000 \le k \le 100).
  • row, col: Starting coordinates (guaranteed valid initially).

Output: A float value between 0 and 1 representing the probability.

Implicit Constraints & Edge Cases:

  • K=0: If no moves are made, the knight is on the board with probability 1.
  • Small N: For N<3N < 3, many moves will immediately take the knight off-board regardless of direction logic (though standard bounds checking handles this naturally).
  • Randomness: The problem states “chooses one of eight possible moves uniformly at random”. This implies every move has a weight of 1/81/8. Moves landing off-board result in failure for that path.

Intuition

A brute-force simulation would try to track all individual paths the knight can take. Since there are 8 branches per step, after K steps we have roughly O(8K)O(8^K) states. With K=100, this is computationally impossible (81008^{100}).

However, notice that at any given move count (step), all knights on the board occupy specific cells with certain probabilities. The state of a knight after step i only depends on its position and not how it got there previously. This suggests Dynamic Programming.

We can define DP[i][r][c]DP[i][r][c] as the probability that the knight is at row r, column c after exactly i moves. To compute this for step i+1, we look at all possible previous positions (pr,pc)(pr, pc) and sum their probabilities multiplied by the transition chance (1/81/8). Since each move has 8 options regardless of whether they stay on board or not, any probability mass moving off-board is effectively lost (contributes to failure).

Approach

  1. State Representation: Use a 2D array dp where dp[r][c] holds the current step’s probability distribution across the board. Initialize it with 1.0 at (row, col) and 0.0 elsewhere.
  2. Transition Logic: We need two buffers (current_dp and next_dp) because a knight can move from any cell to multiple others in one turn; updating in-place would corrupt data needed for the same step’s calculations.
  3. Iteration Loop: Run this transition logic exactly K times.
  4. Move Off-Board Handling: For every valid neighbor calculated by adding offsets, check bounds. If within [0, N), add probability mass to next_dp. If out of bounds, that path ends (probability is discarded).
  5. Final Calculation: After the loop finishes, sum all values in dp array. This total represents the accumulated probability mass remaining on valid squares after exactly K moves.

Complexity Analysis

  • Time Complexity: O(K⋅N2)O(K \cdot N^2). We iterate K times (steps). In each step, we scan every cell of the board (N2N^2 cells), and for each cell perform constant work (8 directions). Given constraints (N=25,K=100N=25, K=100), operations ≈6.25×104\approx 6.25 \times 10^4, which is well within limits.
  • Space Complexity: O(N2)O(N^2). We store the probability distribution for two rows/columns of cells (or one full board). With N up to 25, this uses negligible memory.

Solution

class Solution:
    def knightProbability(self, n: int, k: int, row: int, col: int) -> float:
        # Define the 8 possible moves for a Knight (L-shape)
        directions = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), 
                      (1, -2), (1, 2), (2, -1), (2, 1)]
        
        # Initialize DP table: dp[r][c] = probability of being at r,c after current step count.
        # Start with the knight on board at start position having prob 1.0.
        dp = [[0.0 for _ in range(n)] for _ in range(n)]
        dp[row][col] = 1.0
        
        # Iterate K times to simulate each move
        for _ in range(k):
            new_dp = [[0.0 for _ in range(n)] for _ in range(n)]
            
            # Traverse every cell on the board
            for r in range(n):
                for c in range(n):
                    if dp[r][c] > 0:
                        prob_mass = dp[r][c] / 8.0
                        
                        # Try all 8 possible moves from current position (r, c)
                        for dr, dc in directions:
                            nr, nc = r + dr, c + dc
                            
                            # If the new position is within board boundaries
                            if 0 <= nr < n and 0 <= nc < n:
                                new_dp[nr][nc] += prob_mass
            
            dp = new_dp
        
        # Sum all probabilities remaining on valid squares after K moves
        return sum(sum(row) for row in dp)

Edge Cases Handled

  • K=0: The loop range(k) does not execute. dp remains initialized with 1.0 at start and 0 elsewhere. Return value is 1.0, which is correct (no moves made).
  • N < K or Small Boards: Bounds checking (if 0 <= nr < n) ensures that any move taking the knight off-board simply drops its probability mass without crashing.
  • Start Position Off-Boundaries: The problem guarantees start on board; however, if row/col were