Skip to main content

688. Knight Probability in Chessboard

medium

Probability a knight stays on an n x n chessboard after k random moves starting from a given cell. Probabilistic 2D DP — same shape as Out of Boundary Paths but with a 1/8 multiplier instead of a count.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[step][r][c] = probability of being at (r, c) after 'step' random knight moves, having stayed on the board all along.

Hint 2

Base: dp[0][row][column] = 1, everything else 0.

Hint 3

Transition: dp[step+1][r][c] = sum over the 8 knight-source cells (r', c') of dp[step][r'][c'] / 8.

Hint 4

Answer = sum of dp[k][r][c] over the board. Roll two layers — keep only the current and previous steps.

Solution approach

Reveal approach

Forward probability DP. prev[r][c] = probability the knight is currently at (r, c) after some number of moves. Initialize prev with 1.0 at (row, column) and 0 elsewhere. For each of k steps, compute curr[r][c] as the sum over the 8 knight neighbors (r', c') of prev[r'][c'] divided by 8, treating out-of-bounds neighbors as 0. Replace prev with curr. After k iterations, return sum(prev). Top-down memoization (movesLeft, r, c) is an equivalent framing — backward probability — and yields the same answer. O(k * n^2) time using two rolling boards.

Complexity

Time
O(k * n^2)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • grid-dp
  • probability

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Knight Probability in Chessboard and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →