688. Knight Probability in Chessboard

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.

https://leetcode.cn/problems/knight-probability-in-chessboard/

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

Constraints:

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

Test Cases

1 2	class Solution: def knightProbability(self, n: int, k: int, row: int, column: int) -> float:

solution_test.py

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('n, k, row, column, expected', [
    (3, 2, 0, 0, 0.06250),
    (1, 0, 0, 0, 1.00000),

    (8, 30, 6, 4, 0.00019),
])
class Test:
    def test_solution(self, n, k, row, column, expected):
        sol = Solution()
        assert sol.knightProbability(n, k, row, column) == pytest.approx(expected, abs=1e-5)

    def test_solution2(self, n, k, row, column, expected):
        sol = Solution2()
        assert sol.knightProbability(n, k, row, column) == pytest.approx(expected, abs=1e-5)

Thoughts

从初始位置开始，遍历八个可能的移动位置，对于每个新位置，递归计算从该位置开始继续移动 k - 1 步仍在棋盘上的概率。最后八个概率求均值即可。

很慢，时间复杂度 O(8ᵏ)。

给递归函数加了缓存，速度还挺快，97%。缓存使用的空间大约为 O(k * n²)，而时间复杂度大约降到 O(k * n²)，因为最多对于 0 到 k 的每一个值、棋盘上的每个位置（n² 个）都要计算一次。

也可以用动态规划，但不一定真的快，因为浪费的计算比较多啊。令 dp(pos, i) 是从棋盘上 pos = (r, c) 位置开始，走 i 步之后仍在棋盘上的概率。

可知 dp(pos, i) = Σdp(move(pos), i - 1) / 8。其中 move(pos) 是从 pos = (r, c) 移动一步之后的位置（共八种移动方案）。

时间复杂度 O(k * n²)，空间复杂度 O(n²)（因为只需要保留 i 和 i - 1 两层 dp 值）。实际速度也差不多在 97%。

Code

Backtrace with Cache

solution.py

from functools import cache


class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dirs = [(-1,-2), (-2,-1), (-2,1), (-1,2), (1,2), (2,1), (2,-1), (1,-2)] # ↖ ↗ ↘ ↙

        @cache
        def dfs(i: int, r: int, c: int) -> float:
            if i == k:
                return 1.0

            p = 0.0
            for dr, dc in dirs:
                if 0 <= r + dr < n and 0 <= c + dc < n:
                    p += dfs(i + 1, r + dr, c + dc)

            return p / 8

        return dfs(0, row, column)

DP

solution2.py

from functools import cache


class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dirs = [(-1,-2), (-2,-1), (-2,1), (-1,2), (1,2), (2,1), (2,-1), (1,-2)] # ↖ ↗ ↘ ↙
        dp = [[1.0] * n for _ in range(n)]
        new_dp = [[0] * n for _ in range(n)]
        for _ in range(k):
            for r in range(n):
                for c in range(n):
                    p = 0.0
                    for dr, dc in dirs:
                        if 0 <= r + dr < n and 0 <= c + dc < n:
                            p += dp[r+dr][c+dc]
                    new_dp[r][c] = p / 8

            dp, new_dp = new_dp, dp

        return dp[row][column]

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。