【代码随想录】回溯5-棋盘问题

51. N皇后

link

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例：

输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

思路

搜索皇后的位置可以理解为一棵树：

从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。那么用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

递归三部曲：

• 参数和返回值：同样使用 res 和 cur
• 终止条件：遍历到最底层就结束，并把 cur 加入到 res 中
• 单层逻辑：递归深度就是 row 控制棋盘的行，每一层里 for 循环的 col 控制棋盘的列，一行一列，确定了放置皇后的位置。每次都是要从新的一行的起始位置开始搜，所以都是从 0 开始。

此外还需要判断棋盘是否合法，可以考虑剪枝，即对于当前考虑的位置，只需要考虑当前列、左上角和右上角是否存在皇后即可，不需要遍历整个棋盘。（由于 for 循环中每次只选择一个位置放皇后，所以当前行一定是空的）

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        cur = ['.' * n for _ in range(n)]

        def isvad(row, col):
            # 检查列
            for i in range(row):
                if cur[i][col] == 'Q':
                    return False  # 当前列已经存在皇后，不合法

            # 检查 45 度角是否有皇后
            i, j = row - 1, col - 1
            while i >= 0 and j >= 0:
                if cur[i][j] == 'Q':
                    return False  # 左上方向已经存在皇后，不合法
                i -= 1
                j -= 1

            # 检查 135 度角是否有皇后
            i, j = row - 1, col + 1
            while i >= 0 and j < len(cur):
                if cur[i][j] == 'Q':
                    return False  # 右上方向已经存在皇后，不合法
                i -= 1
                j += 1

            return True  # 当前位置合法

        def backtrack(row):
            if row >= n:
                res.append(cur[:])
            for col in range(n):
                if isvad(row, col):
                    cur[row] = cur[row][:col] + 'Q' + cur[row][col+1:]
                    backtrack(row + 1)
                    cur[row] = cur[row][:col] + '.' + cur[row][col+1:]
        backtrack(0)
        return res

37. 解数独

link
编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 ‘.’ 表示。

思路

N 皇后问题是每一行每一列只放一个皇后，只需要一层 for 循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。本题中棋盘的每一个位置都要放一个数字（而 N 皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比 N 皇后更宽更深。

递归三部曲：

• 参数和返回值：返回值为 bool，因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用 bool 返回值。
• 递归终止条件：不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。
• 递归单层搜索逻辑：两层循环遍历所有可能的位置。两层循环中，会出现两种情况：
  • 当前格选不出任何合法的数字，则返回 False
  • 当前位置放下数字之后，再次递归调用，同样出现：
    • 选不出任何合法数字（或者当前的递归中没有返回 True），返回 False，然后回溯，处理下一个情况
    • 重复递归调用，一直没有报错，直到整个棋盘被填满，则返回 True。然后，回到上一层递归中，同样返回 True（代码中部的 return），即找到一个解，直接结束递归。

关于判断冲突，需要判断当前位置所在行、列、网格中是否存在当前数字。行和列比较好理解。对于网格，首先需要找到当前位置所在网格的左上角，即 [(row//3)*3, (col//3)*3]，在此基础上 +3 即为遍历的结束位置。

下面的代码会报超出时间限制

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def isvad(row, col, k):
            for i in range(9):
                if board[row][i] == k:
                    return False
                if board[i][col] == k:
                    return False
            
            for i in range(3):
                for j in range(3):
                    if board[(row // 3) * 3 + i][(col // 3) * 3 + j] == k:
                        return False
            return True
        
        def backtrack():
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for k in '123456789':
                            if isvad(i, j, k):
                                board[i][j] = k
                                if backtrack():
                                    return True
                                board[i][j] = '.'
                        return False
            return True
        backtrack()

进一步优化：使用 set 来判断是否重复。提前构建以下三个结构：

• rows[i]：第 i 行中已有数字；
• cols[j]：第 j 列中已有数字；
• boxes[i//3][j//3]：第 i,j 所在宫格已有数字。

这样 isvad() 不需要每次遍历整行整列整宫格，而是 O(1) 判断。此外通过 empty 来记录当前棋盘中空的位置，这样就不需要两重遍历了，而是直接遍历当前的 empty 数组。

单层的递归逻辑和上面的代码相同，如果递归的过程中没有返回 True，而是一直到 empty 数组的末尾，如果当前的下标超过 empty 则直接返回 True。

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        # 注意初始化写法
        boxes = [[set() for _ in range(3)] for _ in range(3)]
        empty = []

        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    empty.append((i, j))
                else:
                    rows[i].add(board[i][j])
                    cols[j].add(board[i][j])
                    boxes[i // 3][j // 3].add(board[i][j])


        def backtrack(pos):
            if pos == len(empty):
                return True

            i, j = empty[pos]
            for ch in '123456789':
                if (ch not in rows[i] and
                    ch not in cols[j] and
                    ch not in boxes[i // 3][j // 3]):

                    # 放置
                    board[i][j] = ch
                    rows[i].add(ch)
                    cols[j].add(ch)
                    boxes[i // 3][j // 3].add(ch)

                    if backtrack(pos + 1):
                        return True

                    # 撤销
                    board[i][j] = '.'
                    rows[i].remove(ch)
                    cols[j].remove(ch)
                    boxes[i // 3][j // 3].remove(ch)

            return False
        
        backtrack(0)