{x}
blog image

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 rows and columns are 0-indexed, so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).

A chess knight has eight possible moves it can make, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly k moves or has moved off the chessboard.

Return the probability that the knight remains on the board after it has stopped moving.

 

Example 1:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

Example 2:

Input: n = 1, k = 0, row = 0, column = 0
Output: 1.00000

 

Constraints:

  • 1 <= n <= 25
  • 0 <= k <= 100
  • 0 <= row, column <= n - 1

688. Knight Probability in Chessboard

Problem Description

Given an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The knight has 8 possible moves (see image in the problem description). Each move is chosen uniformly at random. The problem asks for the probability that the knight remains on the board after making k moves.

Solution: Dynamic Programming

This problem can be efficiently solved using dynamic programming. We'll build a 3D array f where:

  • f[h][i][j] represents the probability that the knight is at position (i, j) after h moves.

Initialization:

  • f[0][i][j] = 1 for all valid positions (i, j) on the board. This is because at the start (0 moves), the knight is definitely at its initial position.

Iteration:

  • For h = 1 to k:
    • For each position (i, j) on the board:
      • Iterate through the knight's 8 possible moves from (i, j).
      • For each move, let (x, y) be the resulting position.
      • If (x, y) is within the board's boundaries (0 <= x < n and 0 <= y < n):
        • Update f[h][i][j] by adding f[h-1][x][y] / 8. This represents the probability of reaching (i, j) in h moves from (x, y) in h-1 moves.

Final Answer:

  • The final answer is f[k][row][column], which is the probability of the knight remaining on the board after k moves, starting from (row, column).

Time and Space Complexity

  • Time Complexity: O(k * n^2). We iterate through the 3D array f, which has dimensions (k+1) x n x n. The nested loops for the 8 possible moves have a constant time complexity.
  • Space Complexity: O(k * n^2). The space used is dominated by the 3D array f.

Code Implementation (Python)

def knightProbability(n: int, k: int, row: int, column: int) -> float:
    f = [[[0.0] * n for _ in range(n)] for _ in range(k + 1)]
    for i in range(n):
        for j in range(n):
            f[0][i][j] = 1.0
 
    dirs = [-2, -1, 1, 2, -2, 1, 2, -1, -2] # Pre-calculated move directions
    for h in range(1, k + 1):
        for i in range(n):
            for j in range(n):
                for p in range(0, 8):
                    x, y = i + dirs[p], j + dirs[p + 1]
                    if 0 <= x < n and 0 <= y < n:
                        f[h][i][j] += f[h - 1][x][y] / 8.0
 
    return f[k][row][column]

The code in other languages (Java, C++, Go, TypeScript, Rust) follows a similar structure and logic, just using the respective language's syntax and data structures. The core dynamic programming algorithm remains the same.