Problem

The question is about a knight movement on an NxN chessboard. A knight will start from the given r-th row and c-th column and attempt to make exactly K numbers of moves. Each time the knight moves, it chooses one of eight possible moves uniformly at random (the knight doesn't care even if the next move takes it off the board) and moves there. The knight will keep moving until it has made exactly K moves or has moved off the chessboard. The task is to return the probability that the knight remains on the board after it has stopped moving.

For example, Input: 3, 2, 0, 0 Output: 0.0625 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 of the knight staying on the board is 0.0625.

Approach

The approach to solve this problem is by using Dynamic Programming and Representative States.

Steps

1. Initialize a 2-dimensional array with the size N and at the position (r,c), set its value as 1.0 (probability of knight staying on the board).
2. For the total number of moves K, calculate the next positions for each state (each position of the knight) with a loop over the possible directions.
3. Check if the next position (x, y) is still on the board.
4. Accumulate the probabilities of transition from old states to a new state by adding the current state probability times the transition probability (1/8).
5. Update the old states with the new states.
6. After all K steps, return the sum of all probabilities at each position.

For K moves, the complexity of this solution is O(N^2*K) and uses O(N^2) space.

Let's look at the solution in Python, Java, Javascript, C++, and C#.

Python

1
2python
3class Solution:
4    def knightProbability(self, n: int, K: int, r: int, c: int) -> float:
5        
6        # Directions the Knight can move
7        directions = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]
8        
9        # Initialize the DP table
10        dp = [[0 for _ in range(n)] for _ in range(n)]
11        dp[r][c] = 1
12        
13        for _ in range(K):
14            dp2 = [[0 for _ in range(n)] for _ in range(n)]
15            for r, row in enumerate(dp):
16                for c, val in enumerate(row):
17                    for dr, dc in directions:
18                        if 0 <= r + dr < n and 0 <= c + dc < n:
19                            dp2[r+dr][c+dc] += val / 8.0
20            dp = dp2
21        
22        return sum(map(sum, dp))

Java

1
2java
3class Solution {
4    public double knightProbability(int n, int K, int r, int c) {
5        double[][] dp = new double[n][n];
6        int[] dr = new int[] {-2, -1, 1, 2, 2, 1, -1, -2};
7        int[] dc = new int[] {1, 2, 2, 1, -1, -2, -2, -1};
8        dp[r][c] = 1;
9        for (; K > 0; K--) {
10            double[][] dp2 = new double[n][n];
11            for (int i = 0; i < n; i++) {
12                for (int j = 0; j < n; j++) {
13                    for (int k = 0; k < 8; k++) {
14                        int cr = i + dr[k];
15                        int cc = j + dc[k];
16                        if (0 <= cr && cr < n && 0 <= cc && cc < n)
17                            dp2[cr][cc] += dp[i][j] / 8.0;
18                    }
19                }
20            }
21            dp = dp2;
22        }
23        double ans = 0.0;
24        for (double[] row: dp) {
25            for (double x: row) ans += x;
26        }
27        return ans;
28    }
29}

JavaScript

1
2javascript
3var knightProbability = function(n, k, r, c) {
4    let directions = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]];
5    let dp = [...Array(n)].map(() => Array(n).fill(0));
6    dp[r][c] = 1;
7    for(let s = 0; s < k; s++){
8        let dp2 = [...Array(n)].map(() => Array(n).fill(0));
9        for(let i = 0; i < n; i++){
10            for(let j = 0; j < n; j++){
11                for(let direction of directions){
12                    let x = i + direction[0];
13                    let y = j + direction[1];
14                    if(x < 0 || y < 0 || x >= n || y >= n){ continue }
15                    dp2[x][y] += dp[i][j] / 8;
16                }
17            }
18        }
19        dp = dp2;
20    }
21    return dp.reduce((a,b) => a + b.reduce((c,d) => c + d, 0), 0)
22};

C++

1
2cpp
3class Solution {
4public:
5    double knightProbability(int n, int K, int r, int c) {
6        vector<vector<int>> moves = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
7        vector<vector<double>> dp(n, vector<double>(n, 0));
8        dp[r][c] = 1;
9        for (; K > 0; K--) {
10            vector<vector<double>> temp(n, vector<double>(n, 0));
11            for (int i = 0; i < n; i++)
12                for (int j = 0; j < n; j++)
13                    for (vector<int> move : moves) {
14                        int x = i + move[0], y = j + move[1];
15                        if (x < 0 || x == n || y < 0 || y == n)
16                            continue;
17                        temp[x][y] += dp[i][j] / 8.0;
18                    }
19            dp = temp;
20        }
21        double result = 0;
22        for (auto row : dp)
23            result += accumulate(row.begin(), row.end(), 0.0);
24        return result;
25    }
26};

C#

1
2C#
3public class Solution {
4    public double KnightProbability(int n, int k, int r, int c) {
5        int[] dx = {1, 2, 2, 1, -1, -2, -2, -1}, dy = {2, 1, -1, -2, -2, -1, 1, 2};
6        double[, ] dp1 = new double[n, n];
7        dp1[r, c] = 1.0;
8        for(; k > 0; --k){
9            double[, ] dp2 = new double[n, n];
10            for (int x = 0; x < n; ++x) {
11                for(int y = 0; y < n; ++y) {
12                    for(int i = 0; i < 8; ++i) {
13                        int nx = x + dx[i], ny = y + dy[i];
14                        if(nx >= 0 && nx < n && ny >= 0 && ny < n)
15                            dp2[nx, ny] += dp1[x, y] / 8.0;
16                    }
17                }
18            }
19            dp1 = dp2;
20        }
21        double ans = 0.0;
22        for (int i = 0; i < n; ++i)
23            for(int j = 0; j < n; ++j)
24                ans += dp1[i, j];
25        return ans;
26    }
27}

This solution is implementing the dynamic programming. The dynamic programming table dp[i][j] is representing the probability to stand on (i, j). After all K steps, we just need to add up all probabilities at each position on the chess board.# Expected Output

These implemented functions will return the probability of the knight ending up on the board after K moves. The input given to these functions would be the size of the chessboard (N x N), the number of allowed moves (K) and the starting position (R, C) of the knight.

In the given example, Python code for knightProbability function takes four parameters knightProbability(3, 2, 0, 0) which denotes the knight starts at (0,0) and attempts 2 moves on a 3x3 grid. It returns a probability figure, an output of 0.0625. This is the likelihood of the knight remaining on the board after it has completed its allotted 2 moves.

Similarly, in Java Solution, JavaScript function knightProbability, C++ Solution and C# Solution, the same logic is applied and the functions return the probability of the knight remaining on the board after its predetermined number of moves.

Please keep in mind that as the problem involves probability calculations, the answer will be a floating point number.

Time and Space Complexity

The time complexity is O(N^2 * K) meaning it is directly proportional to the number of cells on the board (N x N) and the number of moves that the knight is allowed to make. For each move that the knight can make, we update the information for each cell on the board.

The space complexity is O(N^2) because two 2D grids are used to represent the probability of the knight being on each cell for the prior and current number of moves.

The N refers to the size of the board, and K refers to the number of moves allowed.

This solution involves dynamic programming and with its space and time complexity, it's optimal for problems of this nature, where the current computation relies on previously computed results. It presents a good balance of memory usage and computation time, as it avoids repeated computations and only keeps relevant information at the cost of additional space.