# LeetCode 688: Knight Probability in Chessboard

## Problem Restatement

We are given an `n x n` chessboard.

A knight starts at cell:

```python
(row, column)
```

The knight makes exactly `k` moves.

On each move, it chooses one of the 8 possible knight moves uniformly at random. It may choose a move that goes off the board. If it moves off the board, it cannot return. We need to return the probability that the knight remains on the board after it has stopped moving.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `n`, `k`, `row`, `column` |
| Output | Probability that the knight remains on the board |
| Board | `n x n` |
| Start cell | `(row, column)` |
| Move choice | Uniformly random among 8 knight moves |
| Off-board behavior | Once off the board, the knight is lost |

Example function shape:

```python
def knightProbability(n: int, k: int, row: int, column: int) -> float:
    ...
```

## Examples

Example 1:

```python
n = 3
k = 2
row = 0
column = 0
```

The knight starts in the top-left corner.

From `(0, 0)`, only two knight moves stay on the board:

```text
(1, 2)
(2, 1)
```

The other six moves go off the board.

After two moves, only a small fraction of all possible random paths remain on the board.

Answer:

```python
0.0625
```

Example 2:

```python
n = 1
k = 0
row = 0
column = 0
```

The knight makes no moves.

It starts on the board and remains there.

Answer:

```python
1.0
```

## First Thought: Enumerate All Paths

A direct solution is to simulate every possible sequence of moves.

For each move, the knight has 8 choices.

So after `k` moves, there are:

```text
8^k
```

possible move sequences.

For each sequence, we could check whether the knight ever goes off the board.

This is too expensive when `k` is large.

The problem has overlapping subproblems: many different paths can reach the same cell after the same number of moves. Dynamic programming avoids recomputing them.

## Key Insight

Instead of tracking every path, track probability mass.

Let:

```text
dp[r][c]
```

mean the probability that the knight is at cell `(r, c)` after the current number of moves, while still being on the board.

Initially:

```python
dp[row][column] = 1.0
```

because the knight starts there with probability `1`.

For each move, we create a new board `next_dp`.

From each cell `(r, c)` with probability `p`, the knight sends `p / 8` probability to each valid next cell.

Moves that go off the board are ignored, because they no longer contribute to the probability of staying on the board.

After `k` moves, the answer is the sum of all probabilities still on the board.

## Knight Moves

A knight can move in these 8 directions:

```python
moves = [
    (2, 1), (2, -1),
    (-2, 1), (-2, -1),
    (1, 2), (1, -2),
    (-1, 2), (-1, -2),
]
```

Each move has probability:

```text
1 / 8
```

## Algorithm

1. Create an `n x n` table filled with `0.0`.
2. Set the starting cell to `1.0`.
3. Repeat `k` times:
   - Create a new `n x n` table filled with `0.0`.
   - For every cell `(r, c)`:
     - If `dp[r][c]` is nonzero, try all 8 knight moves.
     - If the next cell is inside the board, add `dp[r][c] / 8` to that cell in `next_dp`.
   - Replace `dp` with `next_dp`.
4. Return the sum of all values in `dp`.

## Walkthrough

Consider:

```python
n = 3
k = 1
row = 0
column = 0
```

Start:

```text
dp[0][0] = 1.0
```

From `(0, 0)`, only two moves stay on the board:

```text
(1, 2)
(2, 1)
```

Each receives probability:

```text
1 / 8 = 0.125
```

After one move:

| Cell | Probability |
|---|---:|
| `(1, 2)` | `0.125` |
| `(2, 1)` | `0.125` |

The total probability still on the board is:

```text
0.125 + 0.125 = 0.25
```

For `k = 2`, we repeat the same transition once more. The final probability for the official example is:

```text
0.0625
```

## Correctness

The dynamic programming table stores exactly the probability that the knight is at each board cell after a fixed number of moves, without having left the board.

The base case is correct because before any moves, the knight is at the starting cell with probability `1`.

For each transition, the knight chooses one of 8 moves uniformly at random. Therefore, each possible move receives one eighth of the current cell's probability.

If a move lands inside the board, that probability contributes to the corresponding cell in the next table.

If a move lands outside the board, that probability is lost and should not appear in the next table.

Thus, after each iteration, the table correctly represents the distribution of the knight over all on-board cells after that many moves.

After `k` moves, the knight remains on the board exactly when it is in any cell of the board. Summing all cells gives that probability.

Therefore, the algorithm returns the correct result.

## Complexity

Let `n` be the board size.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(k * n^2)` | For each move, we scan all cells and try 8 directions |
| Space | `O(n^2)` | We keep the current and next probability tables |

The factor `8` is constant.

## Implementation

```python
class Solution:
    def knightProbability(
        self,
        n: int,
        k: int,
        row: int,
        column: int,
    ) -> float:
        moves = [
            (2, 1), (2, -1),
            (-2, 1), (-2, -1),
            (1, 2), (1, -2),
            (-1, 2), (-1, -2),
        ]

        dp = [[0.0] * n for _ in range(n)]
        dp[row][column] = 1.0

        for _ in range(k):
            next_dp = [[0.0] * n for _ in range(n)]

            for r in range(n):
                for c in range(n):
                    if dp[r][c] == 0.0:
                        continue

                    probability = dp[r][c] / 8.0

                    for dr, dc in moves:
                        nr = r + dr
                        nc = c + dc

                        if 0 <= nr < n and 0 <= nc < n:
                            next_dp[nr][nc] += probability

            dp = next_dp

        return sum(sum(row_values) for row_values in dp)
```

## Code Explanation

The `moves` list contains all legal knight displacement patterns.

The table:

```python
dp = [[0.0] * n for _ in range(n)]
```

stores the current probability distribution.

The starting cell gets probability `1`:

```python
dp[row][column] = 1.0
```

For each move, we build a fresh table:

```python
next_dp = [[0.0] * n for _ in range(n)]
```

For every nonzero cell, we split its probability into 8 equal parts:

```python
probability = dp[r][c] / 8.0
```

Then each valid destination receives that probability:

```python
if 0 <= nr < n and 0 <= nc < n:
    next_dp[nr][nc] += probability
```

Invalid destinations are skipped because they represent paths where the knight has left the board.

After all moves, the total remaining probability is:

```python
return sum(sum(row_values) for row_values in dp)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert abs(s.knightProbability(3, 2, 0, 0) - 0.0625) < 1e-9
    assert abs(s.knightProbability(1, 0, 0, 0) - 1.0) < 1e-9

    assert abs(s.knightProbability(1, 1, 0, 0) - 0.0) < 1e-9
    assert abs(s.knightProbability(8, 1, 3, 3) - 1.0) < 1e-9
    assert abs(s.knightProbability(2, 1, 0, 0) - 0.0) < 1e-9

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `n = 3, k = 2, row = 0, column = 0` | `0.0625` | Official example |
| `n = 1, k = 0` | `1.0` | No moves, still on board |
| `n = 1, k = 1` | `0.0` | Every knight move leaves the board |
| `n = 8, k = 1, row = 3, column = 3` | `1.0` | Center-ish square has all 8 moves inside |
| `n = 2, k = 1` | `0.0` | Knight cannot stay on a 2 x 2 board |