Knight Probability in Chessboard
Real-world version: The Piece That Stays on the GridThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def knight_probability(n: int, k: int, row: int, column: int) -> float:public double knightProbability(int n, int k, int row, int column)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's