MediumDynamic Programming

Knight Probability in Chessboard

1 approach, code in every language

You are given an n x n chessboard and a knight that starts on cell (row, column). The knight must make exactly k moves. On every move it chooses one of the eight standard knight moves uniformly at random, so each candidate destination is picked with probability 1/8.

The knight keeps moving even if a chosen destination lands outside the board, but once it steps off the board it is lost and can never come back. Return the probability that the knight is still standing on the board after it has completed all k moves.

Example 1

Input: n = 3, k = 2, row = 0, column = 0

Output: 0.06250

From the corner (0,0) only two of the eight moves stay on the board. From each of those cells only two of the next eight moves stay on the board, so the surviving probability is 2 * (1/8) * (2/8) = 0.0625.

Example 2

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

Output: 1.00000

With zero moves to make the knight never leaves its starting cell, so it remains on the board with certainty.

Constraints

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

Dynamic Programming over Remaining Moves

Define the survival probability as a function of how many moves are left and the current cell, then average the eight successors.

Loading animation…

Intuition

The key observation is that the probability of surviving depends only on the current cell and the number of moves still to be made, not on the path taken to get there. This lets us define dp(movesRemaining, r, c) as the probability of staying on the board when the knight is at (r, c) with movesRemaining moves left. Because every one of the eight knight jumps is equally likely, the probability at a cell is simply the average of the sub-probabilities of the eight destinations. Destinations that fall off the board contribute zero, which naturally encodes the 'lost forever' rule. The recursion bottoms out at movesRemaining == 0, where any on-board cell survives with probability 1. Memoizing on the triple avoids recomputing the same state across overlapping subtrees.

Algorithm walkthrough

1If the current cell is off the board, return probability 0 because the knight has already been lost.
2If no moves remain and the cell is on the board, return probability 1.
3Otherwise generate the eight knight destinations from (r, c) and recurse with movesRemaining reduced by one.
4Sum the eight returned sub-probabilities and divide by 8 to get the average, since every move is equally likely.
5Cache the result for (movesRemaining, r, c) so repeated states are answered in constant time.
6Return dp(k, row, column) as the final answer for the starting position.

Implementation

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2),
                 (1, -2), (1, 2), (2, -1), (2, 1)]
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(moves_left: int, r: int, c: int) -> float:
            if r < 0 or r >= n or c < 0 or c >= n:
                return 0.0
            if moves_left == 0:
                return 1.0
            total = 0.0
            for dr, dc in moves:
                total += dp(moves_left - 1, r + dr, c + dc)
            return total / 8.0

        return dp(k, row, column)

Time

O(k * n^2)

Space

O(k * n^2)

There are k * n^2 states and each does a constant amount of work over the eight fixed moves, so the eight-way branching factor is a constant.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

The Piece That Stays on the Grid is our own problem on the technique behind Knight Probability in Chessboard: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free