How can backtracking be applied to the 'Number of Valid Move Combinations On Chessboard' problem?

Backtracking allows you to explore all possible move combinations for each piece while pruning invalid combinations early, ensuring the search remains efficient.

What are the movement rules for the chess pieces in this problem?

Rooks move horizontally or vertically, bishops move diagonally, and queens combine both rook and bishop movements.

How does pruning help in solving this problem?

Pruning eliminates invalid paths early in the backtracking process, such as when two pieces would overlap, significantly reducing the search space.

How do I combine the results of multiple pieces in this problem?

You simulate the moves for each piece individually, then combine the valid configurations where no pieces share the same square at any point in time.

Can this problem be solved without backtracking?

While it is possible to use brute force, backtracking with pruning is far more efficient, especially with the small input size (n <= 4).

#2056

Hard

auto_awesome回溯·pruning

LeetCode 题解工作台

棋盘上有效移动组合的数目

有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions ，其中 positions[i] = [r…

数组字符串回溯模拟

题目描述

有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions ，其中 positions[i] = [r_i, c_i] 表示第 i 个棋子现在在棋盘上的位置为 (r_i, c_i) ，棋盘下标从 1 开始。

每个棋子的移动中，首先选择移动的方向，然后选择 移动的步数 ，同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动：

车可以 水平或者竖直 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1) 或者 (r, c-1) 移动。
后可以 水平竖直或者斜对角 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1)，(r, c-1)，(r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。
象可以 斜对角 从 (r, c) 沿着方向 (r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。

你必须同时移动棋盘上的每一个棋子。移动组合 包含所有棋子的移动。每一秒，每个棋子都沿着它们选择的方向往前移动一步，直到它们到达目标位置。所有棋子从时刻 0 开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 不有效 。

请你返回有效移动组合的数目。

注意：

初始时，不会有两个棋子 在 同一个位置。
有可能在一个移动组合中，有棋子不移动。
如果两个棋子 直接相邻 且两个棋子下一秒要互相占据对方的位置，可以将它们在同一秒内 交换位置 。

示例 1:

输入：pieces = ["rook"], positions = [[1,1]]
输出：15
解释：上图展示了棋子所有可能的移动。

示例 2：

输入：pieces = ["queen"], positions = [[1,1]]
输出：22
解释：上图展示了棋子所有可能的移动。

示例 3:

输入：pieces = ["bishop"], positions = [[4,3]]
输出：12
解释：上图展示了棋子所有可能的移动。

示例 4:

输入：pieces = ["rook","rook"], positions = [[1,1],[8,8]]
输出：223
解释：每个车有 15 种移动，所以总共有 15 * 15 = 225 种移动组合。
但是，有两个是不有效的移动组合：
- 将两个车都移动到 (8, 1) ，会导致它们在同一个格子相遇。
- 将两个车都移动到 (1, 8) ，会导致它们在同一个格子相遇。
所以，总共有 225 - 2 = 223 种有效移动组合。
注意，有两种有效的移动组合，分别是一个车在 (1, 8) ，另一个车在 (8, 1) 。
即使棋盘状态是相同的，这两个移动组合被视为不同的，因为每个棋子移动操作是不相同的。

示例 5：

输入：pieces = ["queen","bishop"], positions = [[5,7],[3,4]]
输出：281
解释：总共有 12 * 24 = 288 种移动组合。
但是，有一些不有效的移动组合：
- 如果后停在 (6, 7) ，它会阻挡象到达 (6, 7) 或者 (7, 8) 。
- 如果后停在 (5, 6) ，它会阻挡象到达 (5, 6) ，(6, 7) 或者 (7, 8) 。
- 如果象停在 (5, 2) ，它会阻挡后到达 (5, 2) 或者 (5, 1) 。
在 288 个移动组合当中，281 个是有效的。

提示：

n == pieces.length
n == positions.length
1 <= n <= 4
pieces 只包含字符串 "rook" ，"queen" 和 "bishop" 。
棋盘上最多只有一个后。
1 <= r_i, c_i <= 8
每一个 positions[i] 互不相同。

lightbulb

解题思路

方法一：DFS

题目最多只有 $4$ 个棋子，每个棋子的移动方向最多有 $8$ 种，我们可以考虑使用 DFS 搜索所有的移动组合。

我们按照顺序依次枚举每个棋子，对于每个棋子，我们可以选择不移动，或者按照规则移动，用数组 $\textit{dist}[i]$ 记录第 $i$ 个棋子的移动情况，其中 $\textit{dist}[i][x][y]$ 表示第 $i$ 个棋子经过坐标 $(x, y)$ 时的时间，用数组 $\textit{end}[i]$ 记录第 $i$ 个棋子的终点坐标和时间。在搜索时，我们需要分别判断当前棋子是否可以停止移动，以及当前棋子是否可以继续在当前方向移动。

我们定义方法 $\text{checkStop}(i, x, y, t)$ 判断第 $i$ 个棋子是否在时间 $t$ 时停在坐标 $(x, y)$ ，如果对于此前的所有棋子 $j$ ，都有 $\textit{dist}[j][x][y] < t$ ，那么第 $i$ 个棋子可以停止移动。

另外，我们定义方法 $\text{checkPass}(i, x, y, t)$ 判断第 $i$ 个棋子是否可以在时间 $t$ 时经过坐标 $(x, y)$ 。如果此前有其它棋子 $j$ 也在时间 $t$ 经过坐标 $(x, y)$ ，或者有其它棋子 $j$ 停在 $(x, y)$ ，且时间不超过 $t$ ，那么第 $i$ 个棋子不能在时间 $t$ 时经过坐标 $(x, y)$ 。

时间复杂度 $O((n \times M)^n)$ ，空间复杂度 $O(n \times M)$ 。其中 $n$ 是棋子的数量，而 $M$ 是每个棋子的移动范围。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

rook_dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
bishop_dirs = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
queue_dirs = rook_dirs + bishop_dirs


def get_dirs(piece: str) -> List[Tuple[int, int]]:
    match piece[0]:
        case "r":
            return rook_dirs
        case "b":
            return bishop_dirs
        case _:
            return queue_dirs


class Solution:
    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:
        def check_stop(i: int, x: int, y: int, t: int) -> bool:
            return all(dist[j][x][y] < t for j in range(i))

        def check_pass(i: int, x: int, y: int, t: int) -> bool:
            for j in range(i):
                if dist[j][x][y] == t:
                    return False
                if end[j][0] == x and end[j][1] == y and end[j][2] <= t:
                    return False
            return True

        def dfs(i: int) -> None:
            if i >= n:
                nonlocal ans
                ans += 1
                return
            x, y = positions[i]
            dist[i][:] = [[-1] * m for _ in range(m)]
            dist[i][x][y] = 0
            end[i] = (x, y, 0)
            if check_stop(i, x, y, 0):
                dfs(i + 1)
            dirs = get_dirs(pieces[i])
            for dx, dy in dirs:
                dist[i][:] = [[-1] * m for _ in range(m)]
                dist[i][x][y] = 0
                nx, ny, nt = x + dx, y + dy, 1
                while 1 <= nx < m and 1 <= ny < m and check_pass(i, nx, ny, nt):
                    dist[i][nx][ny] = nt
                    end[i] = (nx, ny, nt)
                    if check_stop(i, nx, ny, nt):
                        dfs(i + 1)
                    nx += dx
                    ny += dy
                    nt += 1

        n = len(pieces)
        m = 9
        dist = [[[-1] * m for _ in range(m)] for _ in range(n)]
        end = [(0, 0, 0) for _ in range(n)]
        ans = 0
        dfs(0)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of backtracking and pruning techniques.
question_mark
The candidate is able to efficiently simulate different chess piece moves and apply constraints to avoid overlap.
question_mark
The candidate shows how to combine results from different pieces and compute the total number of valid combinations.

warning

常见陷阱

外企场景

error
Forgetting to prune invalid paths early, leading to unnecessary calculations.
error
Overcomplicating the solution by not taking advantage of the small input size (n <= 4).
error
Failing to properly handle the unique movement rules for each type of piece (rook, bishop, queen).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increasing the number of pieces to test how the solution scales.
arrow_right_alt
Introducing more complex pieces with additional movement rules.
arrow_right_alt
Adding time constraints to make the solution more efficient in a real-time chess simulation.

help

常见问题

外企场景

继续练习

#2011 执行操作后的变量值 #2109 向字符串添加空格 #1980 找出不同的二进制字符串