Skip to content

688. Knight Probability in Chessboard

Problem

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

Solve

Simulation

Based on the problem description, we are trying to find the probability that a knight remains on the chessboard after making exactly k moves, starting from a given cell (row, column) on an n x n chessboard. The knight has eight possible moves it can make, as illustrated in the image provided in the problem.

To solve this problem, we can use a simulation approach to calculate the probability. We can implement a recursive function move that simulates the knight’s movement. At each step, the knight chooses one of the eight possible moves uniformly at random, and then recursively makes the next move until k moves are reached.

To improve efficiency, we can use memorization to store the results of subproblems in a cache dictionary. This way, we can avoid redundant calculations and speed up the computation.

Here’s how the simulation-based approach works:

The knightProbability function initializes the memorization cache and calls move with the starting position and zero steps taken so far.

  1. Define a function isValid to check if a given position (x, y) is within the chessboard bounds.

  2. Implement the recursive function move that calculates the probability of the knight staying on the board after k moves starting from position (x, y).

  3. In the move function, check if k moves have been reached; if yes, return 1 (representing the knight stays on the board).

  4. Check if the current state (x, y, step) exists in the cache dictionary; if yes, return the cached probability.

  5. For each of the eight possible moves the knight can make, calculate the next position (nX, nY).

  6. If the next position is valid (within the chessboard bounds), recursively call move for the next position and increment the probability with the result.

  7. Divide the accumulated probability by 8 (since there are eight possible moves) and store it in the cache.

  8. Finally, call the move function with the initial position (row, column, 0) and return the result.

This simulation-based approach accurately calculates the probability of the knight staying on the board after k moves starting from a given cell (row, column) on the chessboard. The use of memorization ensures that the function runs efficiently and avoids redundant computations.

class Solution:
    def isValid(self, x, y):
        return 0 <= x < self.n and 0 <= y < self.n

    def move(self, x, y, step):
        if step >= self.k:
            return 1
        if (x, y, step) in self.cache:
            return self.cache[(x,y, step)]
        movementDown = [(2,-1), (2,+1), (1,+2), (1,-2)]
        movementUp = [(-2,-1), (-2,+1), (-1,+2), (-1,-2)]
        nextPosition = [(x+dx, y+dy) for dx, dy in movementDown]
        nextPosition += [(x+dx, y+dy) for dx, dy in movementUp]

        probability = 0
        for nX, nY in nextPosition:
            if self.isValid(nX, nY):
                nextMove = self.move(nX, nY, step + 1)
                probability += nextMove/8
        self.cache[(x,y,step)] = probability
        return probability


    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        self.n = n
        self.k = k
        self.cache = {}
        return self.move(row, column, 0)

I also working on C implementation using same concept, and to my surprise, it throw a Time Limit Exceeded. (Which then later I found out the reason is because I forgot to update cache value) 

typedef struct {
    int x;
    int y;
} Pair;

double cache[26][26][101];

bool isValid(int x,int y,int n) { return 0 <= x && x < n && 0 <= y && y < n;}

double move(int x, int y, int step, int n, int k) {
    if (step >= k) return 1;
    // printf("Log point 2\n");

    if (cache[x][y][step] >= 0.) return cache[x][y][step];
    // printf("Log point 3\n");

    Pair nextPosition[] = {
        {x+2, y-1}, {x+2, y+1}, {x+1, y+2}, {x+1, y-2},
        {x-2, y-1}, {x-2, y+1}, {x-1, y+2}, {x-1, y-2}
    };

    // printf("Log point 4\n");
    double probability = 0.;
    double nextMove = 0.;

    for (int i=0; i<8; i++){
        int nX = nextPosition[i].x;
        int nY = nextPosition[i].y; 
        nextMove = 0.; // <- I forgot this
        if (isValid(nX, nY, n)) {
            // printf("Log point 5: nX = %d, nY = %d, step = %d,\n", nX, nY, step + 1);
            nextMove = move(nX, nY, step + 1, n, k);
        }
        probability += nextMove/8;
    }
    cache[x][y][step] = probability; // <- I forgot this
    return probability;
}

double knightProbability(int n, int k, int row, int column){
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int step = 0; step < k; step++) {
                cache[i][j][step] = -1.0;
            }
        }
    }
    // printf("Log point\n");
    return move(row, column, 0, n, k);
}

This instead, work out, which is the same one again but with way less code.

int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};

double dp[26][26][101];

int isValid(int x, int y, int n) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

double move(int x, int y, int step, int n, int k) {
    if (step >= k) {
        return 1.0;
    }
    if (dp[x][y][step] != -1.0) {
        return dp[x][y][step];
    }
    double probability = 0.0;
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isValid(nx, ny, n)) {
            probability += move(nx, ny, step+1, n, k);
        }
    }
    probability /= 8.0;
    dp[x][y][step] = probability;
    return probability;
}

double knightProbability(int n, int k, int row, int column) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int s = 0; s <= k; s++) {
                dp[i][j][s] = -1.0;
            }
        }
    }
    return move(row,column,0,n,k);
}

Possible Improvements

  1. Dynamic Programming (Bottom-up Approach): Instead of using recursion and memorization, we can utilize a dynamic programming approach to avoid excessive function calls and improve performance. We can build the solution iteratively, starting from the base case (when k = 0) and progressively calculate the probabilities for increasing k values until we reach the target value. This way, we can avoid stack overflow and reduce redundant computations.

  2. Optimized Data Structure: The current implementation uses a 3D array to store the memorized values, which can be memory-intensive and slower. We can consider using a 1D array or a hash table with a suitable hashing function to store the computed probabilities.

  3. Optimize Data Access: The current implementation uses a 3D array to store the probabilities for each (x, y, step) combination. However, in each step, we only need the probabilities from the previous step. Therefore, we can optimize data access by using two arrays, one for the current step’s probabilities and another for the previous step’s probabilities, and keep swapping them as we progress through the steps.

Based on the above improvements, here’s a refactored C implementation using dynamic programming:

typedef struct {
    int x;
    int y;
} Pair;

double cache[2][26][26];
int curStep = 0;
int prevStep = 1;

bool isValid(int x,int y,int n) { return 0 <= x && x < n && 0 <= y && y < n;}

double move(int x, int y, int n, int k) {
    Pair nextPosition[] = {
        {x+2, y-1}, {x+2, y+1}, {x+1, y+2}, {x+1, y-2},
        {x-2, y-1}, {x-2, y+1}, {x-1, y+2}, {x-1, y-2}
    };

    double probability = 0.;

    for (int i=0; i<8; i++){
        int nX = nextPosition[i].x;
        int nY = nextPosition[i].y; 
        if (isValid(nX, nY, n)) {
            probability += cache[prevStep][nX][nY] /8;
        }
    }

    return probability;
}

double knightProbability(int n, int k, int row, int column) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cache[curStep][i][j] = 0.;
            cache[prevStep][i][j] = 0.;
        }
    }
    cache[prevStep][row][column] = 1.;

    double currentTotal = 1.;
    for (int step = 1; step <= k; step++) {
        currentTotal = 0.;
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                cache[curStep][x][y] = move(x, y, n, k);
                currentTotal += cache[curStep][x][y];
            }
        }
        int temp = prevStep;
        prevStep = curStep;
        curStep = temp;
    }

    return currentTotal;
}
Last update : August 18, 2023
Created : August 16, 2023