We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Knight Probability in Chessboard

Number: 688

Difficulty: Medium

Paid? No

Companies: Apple, Goldman Sachs, Meta, Google, Amazon, Citadel

Problem Description

Given an n x n chessboard, a knight starts at a specified cell (row, column) and makes exactly k moves. Every move is chosen uniformly at random from the knight’s 8 possible moves (even if a move would take it off the board). The task is to calculate the probability that the knight remains on the board after making k moves.

Key Insights

  • Use Dynamic Programming since the state (i.e., cell and number of moves remaining) overlaps.
  • A recursive approach with memoization or iterative bottom-up DP can be applied.
  • Each knight move occurs with a probability of 1/8.
  • Base cases include k=0 (the knight is on the board) and moves leading off the board contribute 0 probability.
  • Transition: For each valid cell at a certain move, accumulate the probability from all 8 possible moves from that cell.

Space and Time Complexity

Time Complexity: O(k * n^2) as we iterate over k moves and each cell of the board. Space Complexity: O(n^2) if using iterative DP with two 2D arrays (or O(k * n^2) for a memoization approach).

Solution

We solve the problem using a bottom-up dynamic programming approach. We maintain a 2D DP array that represents the probability of the knight being at each cell after a given number of moves. We start by initializing the starting position with a probability of 1. For each move, we compute a new probability distribution over the board by iterating through each cell and distributing its probability over the 8 knight moves (only if the move remains within bounds). After k moves, the sum of the probabilities in the DP table gives the final answer. This iterative updating avoids repeated computations and elegantly manages the probability propagation.

Code Solutions

# Python solution using iterative DP

def knightProbability(n, k, row, column):
    # Define the 8 possible moves for a knight
    moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), 
             (-2, -1), (-1, -2), (1, -2), (2, -1)]
    
    # Initialize dp with probability 0 for each cell, and set starting cell to 1
    dp = [[0 for _ in range(n)] for _ in range(n)]
    dp[row][column] = 1.0
    
    # Iterate for each move
    for move_num in range(k):
        # Create temporary dp for the next move
        dp_next = [[0 for _ in range(n)] for _ in range(n)]
        # Process each cell
        for i in range(n):
            for j in range(n):
                if dp[i][j] > 0:
                    # Try each knight move
                    for dx, dy in moves:
                        ni, nj = i + dx, j + dy
                        # Check board boundaries
                        if 0 <= ni < n and 0 <= nj < n:
                            dp_next[ni][nj] += dp[i][j] / 8.0
        # Update dp for the current move
        dp = dp_next
    
    # Sum probabilities of all cells for the final answer
    total_probability = sum(map(sum, dp))
    return total_probability

# Example usage:
#print(knightProbability(3, 2, 0, 0))
← Back to All Questions