Problem Description

You are given three integers: N (the size of an N x N chessboard), K (the number of moves), and the starting position (row, column) of a knight on the board.

A knight can move in 8 possible directions, as in chess. At each move, the knight chooses one of the 8 directions uniformly at random (if it stays on the board). If the knight moves off the board, it is immediately removed and cannot move again.

The task is to determine the probability that the knight remains on the board after exactly K moves, starting from (row, column).

• 1 <= N <= 25
• 0 <= K <= 100
• 0 <= row, column < N

Thought Process

The naive way to solve this problem is to simulate all possible paths the knight could take, counting how many end up on the board after K moves, and then dividing by the total number of possible paths. However, the number of possible paths grows exponentially with K (specifically, 8^K), making brute-force infeasible for larger values of K.

Instead, we look for overlapping subproblems and optimal substructure, which suggests using dynamic programming (DP). At each step, the probability of being on the board at a given position depends only on the probabilities from the previous step. This makes it possible to build up the solution step by step, avoiding redundant calculations.

By storing the probability of being at each position after each move, we can efficiently compute the answer without simulating every possible path.

Solution Approach

We solve this problem using a bottom-up dynamic programming approach. Here’s how:

1. Define the DP State:
   • Let dp[k][r][c] be the probability that the knight is on the board at position (r, c) after k moves.
2. Base Case:
   • At move 0, the knight is at its starting position with probability 1: dp[0][row][column] = 1.
   • All other positions at move 0 have probability 0.
3. State Transition:
   • For each move k from 1 to K, for every cell (r, c):
     • For each of the 8 possible knight moves, if the previous cell (nr, nc) is on the board, add dp[k-1][nr][nc] / 8 to dp[k][r][c].
4. Final Calculation:
   • The answer is the sum of probabilities dp[K][r][c] over all valid board positions (r, c).
5. Optimization:
   • We only need two 2D arrays (for the previous and current step), since each step depends only on the previous one.

This approach ensures we efficiently compute the probability without redundant calculations.

Example Walkthrough

Example Input:
N = 3, K = 2, row = 0, column = 0

1. Move 0: The knight starts at (0, 0). Probability = 1 at (0, 0).
2. Move 1: From (0, 0), the knight has 8 possible moves, but only 2 stay on the board: to (1, 2) and (2, 1). Probability at each is 1/8.
3. Move 2:
   • From (1, 2): valid moves are (0, 0), (2, 0), (2, 2). Each gets (1/8) * (1/8) = 1/64 added.
   • From (2, 1): valid moves are (0, 0), (0, 2), (1, 2). Each gets (1/8) * (1/8) = 1/64 added.
4. Sum probabilities for all board positions after 2 moves. The total is 0.0625 (or 6.25%).

This process shows how probabilities are distributed and accumulated at each step.

Time and Space Complexity

• Brute-Force Approach:
  • Time: O(8^K) — Exponential in K, since each move branches into 8 possibilities.
  • Space: O(K) — Only the recursion stack is needed if implemented recursively.
• Dynamic Programming Approach:
  • Time: O(K × N² × 8) = O(K × N²) — For each move, we update each cell using up to 8 directions.
  • Space: O(N²) — We only need to store two 2D arrays at a time (current and previous step).

The DP approach is efficient and works well within the given constraints.

Summary

This problem is a classic example where dynamic programming transforms an exponential brute-force problem into a feasible polynomial-time solution. By modeling the knight's probabilities as states and transitions, we efficiently accumulate the total probability of staying on the board. The key insight is to use previous probabilities to build up the answer step by step, leveraging overlapping subproblems and optimal substructure.

Code Implementation

class Solution:
    def knightProbability(self, N: int, K: int, row: int, column: int) -> float:
        directions = [
            (2, 1), (1, 2), (-1, 2), (-2, 1),
            (-2, -1), (-1, -2), (1, -2), (2, -1)
        ]
        dp_prev = [[0.0 for _ in range(N)] for _ in range(N)]
        dp_prev[row][column] = 1.0
        
        for step in range(1, K+1):
            dp_curr = [[0.0 for _ in range(N)] for _ in range(N)]
            for r in range(N):
                for c in range(N):
                    if dp_prev[r][c] > 0:
                        for dr, dc in directions:
                            nr, nc = r + dr, c + dc
                            if 0 <= nr < N and 0 <= nc < N:
                                dp_curr[nr][nc] += dp_prev[r][c] / 8.0
            dp_prev = dp_curr
        return sum(map(sum, dp_prev))
      

class Solution {
public:
    double knightProbability(int N, int K, int row, int column) {
        vector<vector<double>> dp_prev(N, vector<double>(N, 0.0));
        dp_prev[row][column] = 1.0;
        vector<pair<int,int>> dirs = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
        for (int step = 1; step <= K; ++step) {
            vector<vector<double>> dp_curr(N, vector<double>(N, 0.0));
            for (int r = 0; r < N; ++r) {
                for (int c = 0; c < N; ++c) {
                    if (dp_prev[r][c] > 0) {
                        for (auto d : dirs) {
                            int nr = r + d.first, nc = c + d.second;
                            if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
                                dp_curr[nr][nc] += dp_prev[r][c] / 8.0;
                            }
                        }
                    }
                }
            }
            dp_prev = dp_curr;
        }
        double ans = 0.0;
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                ans += dp_prev[r][c];
        return ans;
    }
};
      

class Solution {
    public double knightProbability(int N, int K, int row, int column) {
        double[][] dpPrev = new double[N][N];
        dpPrev[row][column] = 1.0;
        int[][] dirs = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
        for (int step = 1; step <= K; ++step) {
            double[][] dpCurr = new double[N][N];
            for (int r = 0; r < N; ++r) {
                for (int c = 0; c < N; ++c) {
                    if (dpPrev[r][c] > 0) {
                        for (int[] d : dirs) {
                            int nr = r + d[0], nc = c + d[1];
                            if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
                                dpCurr[nr][nc] += dpPrev[r][c] / 8.0;
                            }
                        }
                    }
                }
            }
            dpPrev = dpCurr;
        }
        double ans = 0.0;
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                ans += dpPrev[r][c];
        return ans;
    }
}
      

var knightProbability = function(N, K, row, column) {
    const dirs = [[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2],[1,-2],[2,-1]];
    let dpPrev = Array.from({length: N}, () => Array(N).fill(0));
    dpPrev[row][column] = 1.0;
    for (let step = 1; step <= K; ++step) {
        let dpCurr = Array.from({length: N}, () => Array(N).fill(0));
        for (let r = 0; r < N; ++r) {
            for (let c = 0; c < N; ++c) {
                if (dpPrev[r][c] > 0) {
                    for (let d of dirs) {
                        let nr = r + d[0], nc = c + d[1];
                        if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
                            dpCurr[nr][nc] += dpPrev[r][c] / 8.0;
                        }
                    }
                }
            }
        }
        dpPrev = dpCurr;
    }
    let ans = 0.0;
    for (let r = 0; r < N; ++r)
        for (let c = 0; c < N; ++c)
            ans += dpPrev[r][c];
    return ans;
};