cyberangles blog

Probability of Knight to Remain in the Chessboard

In the world of chess, the knight moves in a unique way, which makes it an interesting subject for probability analysis. Given a knight placed on a standard 8x8 chessboard (or a chessboard of any size), and it is allowed to make a certain number of moves according to its L - shaped movement rule, we often want to find out the probability that the knight remains within the boundaries of the chessboard after these moves. This problem has applications in algorithm design, probability theory, and even in some strategic games where the movement of pieces is restricted to a grid. In this blog, we will delve into the mathematical and programming aspects of calculating this probability.

2026-07

Table of Contents#

  1. Rules of Knight's Movement
  2. Mathematical Approach to Calculate the Probability
    • Understanding the Total Possible Moves
    • Calculating the Valid Moves
    • Deriving the Probability Formula
  3. Programming Implementation
    • Using Python to Solve the Problem
    • Example Code and Explanation
  4. Common Practices and Best Practices
    • Handling the Edge Cases
    • Optimizing the Algorithm
  5. Example Usage
    • Practical Examples of the Problem
  6. Conclusion
  7. References

1. Rules of Knight's Movement#

A knight in chess moves in an L - shaped pattern. From a given square ((x,y)) on the chessboard, a knight can move to one of the following eight positions:

  • ((x + 1,y+2))
  • ((x + 1,y - 2))
  • ((x - 1,y+2))
  • ((x - 1,y - 2))
  • ((x + 2,y+1))
  • ((x + 2,y - 1))
  • ((x - 2,y+1))
  • ((x - 2,y - 1))

These moves are only valid if the resulting position is within the boundaries of the chessboard.

2. Mathematical Approach to Calculate the Probability#

2.1 Understanding the Total Possible Moves#

At each step, a knight has 8 possible moves regardless of whether these moves are valid or not. If the knight makes (n) moves, the total number of possible move sequences is (8^n) because for each of the (n) moves, there are 8 choices.

2.2 Calculating the Valid Moves#

We need to calculate the number of moves that keep the knight within the chessboard at each step. Let's assume the chessboard has size (N\times N). To check if a move ((x',y')) from a current position ((x,y)) is valid, we need to ensure that (0\leq x'\lt N) and (0\leq y'\lt N).

We can use a recursive approach to calculate the number of valid moves after (n) steps. Let (f(x,y,n)) be the number of valid paths starting from position ((x,y)) and making (n) moves. Then: [f(x,y,n)=\sum_{move} f(x',y',n - 1)] where the sum is taken over all valid moves ((x',y')) from ((x,y))

2.3 Deriving the Probability Formula#

The probability (P(x,y,n)) that a knight starting from position ((x,y)) remains on the chessboard after (n) moves is given by the ratio of the number of valid move sequences to the total number of possible move sequences: [P(x,y,n)=\frac{f(x,y,n)}{8^n}]

3. Programming Implementation#

3.1 Using Python to Solve the Problem#

We can implement the solution using Python. Here is the example code:

def knightProbability(N, K, r, c):
    # Create a 3D dynamic programming array
    dp = [[[0]*(K + 1) for _ in range(N)] for _ in range(N)]
    directions = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
    # Base case: when K = 0, the knight is on the board with probability 1
    dp[r][c][0] = 1
    for k in range(1, K + 1):
        for x in range(N):
            for y in range(N):
                for dx, dy in directions:
                    prev_x, prev_y = x - dx, y - dy
                    if 0 <= prev_x < N and 0 <= prev_y < N:
                        dp[x][y][k] += dp[prev_x][prev_y][k - 1]
    total = 0
    for i in range(N):
        for j in range(N):
            total += dp[i][j][K]
    return total / (8**K)

3.2 Example Code and Explanation#

  • Initialization: We create a 3D array dp of size (N\times N\times(K + 1)) to store the number of valid paths. dp[x][y][k] represents the number of valid paths starting from position ((x,y)) and making (k) moves.
  • Base Case: When (k = 0), the knight is on the board with probability 1, so dp[r][c][0]=1 where ((r,c)) is the starting position.
  • Recursive Step: For each move (k) from (1) to (K), we iterate through all positions ((x,y)) on the board. For each position, we check all 8 possible moves. If the previous position ((prev_x,prev_y)) is valid, we add the number of valid paths from ((prev_x,prev_y)) with (k - 1) moves to the number of valid paths from ((x,y)) with (k) moves.
  • Calculating the Probability: After calculating the number of valid paths after (K) moves for all positions on the board, we sum them up and divide by (8^K) to get the probability.

4. Common Practices and Best Practices#

4.1 Handling the Edge Cases#

  • Empty Board: If the size of the chessboard (N = 0), the probability is always 0 because there is no board.
  • No Moves: If (K = 0), the probability is 1 because the knight doesn't move and remains on the board.

4.2 Optimizing the Algorithm#

  • Reducing Space Complexity: We can reduce the space complexity from (O(N^2K)) to (O(N^2)) by only keeping track of the previous move and the current move. We can use two 2D arrays instead of a 3D array.
def knightProbabilityOptimized(N, K, r, c):
    dp = [[0] * N for _ in range(N)]
    dp[r][c] = 1
    directions = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
    for _ in range(K):
        new_dp = [[0] * N for _ in range(N)]
        for x in range(N):
            for y in range(N):
                for dx, dy in directions:
                    prev_x, prev_y = x - dx, y - dy
                    if 0 <= prev_x < N and 0 <= prev_y < N:
                        new_dp[x][y] += dp[prev_x][prev_y]
        dp = new_dp
    total = 0
    for row in dp:
        total += sum(row)
    return total / (8**K)

5. Example Usage#

Let's assume we have an 8x8 chessboard ((N = 8)), the knight starts at position ((0,0)) ((r = 0,c = 0)), and it makes 3 moves ((K = 3)).

N = 8
K = 3
r = 0
c = 0
probability = knightProbability(N, K, r, c)
print(f"The probability that the knight remains on the board after {K} moves starting from position ({r},{c}) is {probability}")

This code will calculate and print the probability that the knight remains on the 8x8 chessboard after 3 moves starting from the top - left corner.

Conclusion#

Calculating the probability of a knight remaining on the chessboard is an interesting problem that combines probability theory and algorithm design. We have explored the mathematical approach, programming implementation, and best practices to solve this problem. By understanding the rules of knight's movement and using dynamic programming, we can efficiently calculate the probability for different board sizes and number of moves.

References#

  • "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
  • Online chess resources for understanding the rules of knight's movement.
  • Python official documentation for programming implementation details.