1134MediumDynamic Programming

The Piece That Stays on the Grid

Tracked in this browser only

Trains the technique from

LeetCode 688Knight Probability in Chessboard

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A piece stands on an n by n grid at row row and column column, both counted from zero.

The piece makes exactly k hops. One hop moves two squares along one direction together with one square along the perpendicular one, so eight hops are possible, and each of the eight is chosen with the same chance every time, whether or not it lands on the grid. Once the piece leaves the grid it stops there and never returns.

Return the chance that the piece is still on the grid once all k hops are done.

Examples

Example 1

Input: n = 3, k = 1, row = 0, column = 0
Output: 0.25

From the corner of a three by three grid only two of the eight hops land back on it, so the chance is two eighths.

Example 2

Input: n = 3, k = 1, row = 1, column = 1
Output: 0.0

From the middle of a three by three grid every one of the eight hops lands outside.

Example 3

Input: n = 8, k = 1, row = 3, column = 3
Output: 1.0

The piece stands well inside an eight by eight grid, so every hop lands on it and the piece is certain to stay.

Constraints

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

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def knight_probability(n: int, k: int, row: int, column: int) -> float:

Java

public double knightProbability(int n, int k, int row, int column)

The intended approach

Time O(k * n^2) over the hops and the grid.Space O(n^2) for the two grids of chances.

Following the hops one at a time would branch eight ways per hop, which is hopeless past a handful of hops. But the piece's future depends only on the square it stands on, not on how it got there, so the chances can be gathered square by square. Hold a grid of chances, starting with all of it on the square the piece begins on. One hop takes each square's chance, splits it eight ways, and hands each eighth to the square that hop lands on. Shares landing off the grid are simply dropped, which is exactly what stopping there means, so the chances left on the grid shrink as the hops go by. Repeating that `k` times and adding up what remains on the grid gives the answer. Each hop costs the square count times the eight directions, so the whole thing is the hops times the grid.

Pythonentry point: knight_probability

def knight_probability(n, k, row, column):
    hops = ((2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2))
    board = [[0.0] * n for _ in range(n)]
    board[row][column] = 1.0
    for _ in range(k):
        step = [[0.0] * n for _ in range(n)]
        for r in range(n):
            for c in range(n):
                here = board[r][c]
                if here == 0.0:
                    continue
                share = here / 8.0
                for dr, dc in hops:
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        step[nr][nc] += share
        board = step
    total = 0.0
    for r in range(n):
        for c in range(n):
            total += board[r][c]
    return total

The obvious version

Count the surviving journeys exactly rather than tracking chances. Hold how many ways the piece can be standing on each square, hop by hop, adding whole numbers only and dropping any hop that leaves the grid. At the very end divide the surviving count by eight to the power of the hops, so only one division is ever done.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_knight_probability(n, k, row, column):
    hops = ((2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2))
    counts = {(row, column): 1}
    for _ in range(k):
        step = {}
        for spot in counts:
            r, c = spot
            ways = counts[spot]
            for dr, dc in hops:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    key = (nr, nc)
                    step[key] = step.get(key, 0) + ways
        counts = step
    total = 0
    for spot in counts:
        total += counts[spot]
    return total / (8 ** k)

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See 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