所谓leetcode hard级别的回溯问题

回溯问题其实就是一个模板题，都是通过【带状态恢复的dfs】实现
我们知道回溯的模板如下

def backTrack(visited_path, choice_list, global_result, target):
    # visited_path表示当前的问题阶段，choice_list表示当前问题面临的可选项，target出现表示问题无需继续向下搜索，这时result结算可行解，
    # 递归出口
    if visited_path meets target:
        update global_result
        return

    # 尝试每一个【当前可行】的选择
    for c in choice_list:
        # 2.更新问题状态: 必须包含3项，visited_path+choice_list+target
        visited_path.add(c)
        new_choice_list = choice_list.remove(c)
        update target
        # 3.递归
        backTrack(visited_path, new_choice_list, global_result, target)
        # 4.状态复原
        visited_path.remove(c)
        reset target

hard题难在什么地方呢？要说难，它就难在【当前可行】的选择需要满足更为复杂的限制条件，也仅此而已了
只要我们翻译好限制条件，将限制条件用code正确表示出来，其实就还是板子题

例1 leetcode51 N皇后

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案，要求皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例：
输入：4
输出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

思路：
假定我们从上到下逐行放置一个皇后，现在我们在第i行要放置一个皇后，那么当前可行的选择有哪些呢？第i行的哪几个位置能放呢？解决了这个问题就好。我们知道，前i-1行已经放置的皇后所在的行、列、斜线都不能放，认为是前皇后势力覆盖区域
那么，我们维护一个dict来记录整个棋盘的每个方格的势力值，初始化为0。

• 我们只能在势力值为0的方格放置新的皇后
• 每放置一个皇后，则她所在的行、列、斜线的各个方格的势力值+1
• 每次回溯撤回一个皇后，则她所在的行、列、斜线的各个方格的势力值-1

这样，我们把【已放置皇后所在的行、列、斜线都不能放新皇后】这个限制条件很好地翻译成了代码形式来确定当前可行的选择，得解

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 设置好规则，【dfs】暴力尝试所有解。如果能够dfs到第n层的，说明整个路径上的皇后位置合法，纳入结果集。
        # 用queen_pos list记录可行的皇后位置；用字典invalid_pos记录当前不可放置的位置，0可放，非0不可放
        queen_pos = list()
        invalid_pos = dict()
        for i in range(n):
            for j in range(n):
                invalid_pos[(i,j)] = 0
        final_res = []

        def helper(queen_pos, invalid_pos, row_index, final_res):
            # 已经到整个棋盘的n行，说明0-n-1行都放好了，结算并返回
            if row_index == n:
                temp = []
                for p in queen_pos:
                    s = '.'*p[1] + 'Q' + '.'*(n-1-p[1])
                    temp.append(s)
                final_res.append(temp)
                return

            for i in range(n):
                pos = (row_index, i)
                if invalid_pos[pos] == 0:
                    # 尝试放一个皇后
                    queen_pos.append(pos)
                    ## 更新不可放的位置 ##
                    additional_invalid_pos = []
                    for j in range(n):
                        # 同一行不可再放
                        additional_invalid_pos.append((row_index, j))
                    for j in range(n):
                        # 同一列不可再放
                        additional_invalid_pos.append((j, i))
                    s = row_index + i
                    delta = i - row_index
                    for j in range(n):
                        # 双斜线不可再放
                        if n > s-j >= 0 : additional_invalid_pos.append((j, s-j)) 
                        if 0 <= j + delta < n: additional_invalid_pos.append((j, j+delta)) 
                    for ele in additional_invalid_pos:
                        invalid_pos[ele] += 1
                    ## 更新不可放的位置，完毕 ##
                    # dfs
                    helper(queen_pos, invalid_pos, row_index+1, final_res)
                    # 状态复原
                    queen_pos.pop()
                    for ele in additional_invalid_pos:
                        invalid_pos[ele] -= 1
        
        helper(queen_pos, invalid_pos, 0, final_res)
        return final_res

例2 leetcode 37. 解数独

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

一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
假设给定的数独只有唯一解，且数独棋盘为9 x 9规模

思路：
好了，又是翻译复杂限制条件来确定当前可行选择的回溯问题
维护3个set row_d, col_d, block_d，对应3个限制条件，记录每行、每列、每块当前含有的数字

• 从上到下从左到右先遍历一次数独棋盘，初始化3个set
• 从上到下从左到右再遍历一次数独棋盘，
  • 如果遇到数字，到下一格去
  • 如果遇到空格，从1到9中选出不在3个set中的数字尝试放置，期间更新set和恢复set即可

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        # 维护3个set，记录每行、每列、每块当前含有的数字
        row_d, col_d, block_d = dict(), dict(), dict()
        for i in range(9):
            row_d[i] = set()
            col_d[i] = set()
            block_d[i] = set()
        # 初始化这3个set
        for i in range(9):
            for j in range(9):
                row_d[i].add(board[i][j])
                col_d[j].add(board[i][j])
                block_d[(i//3)*3+j//3].add(board[i][j])

        def backTracking(board, i, j, row_d, col_d, block_d) -> bool:
            # 递归出口，填到棋盘外的第九行，，，
            if i == 9:
                return True

            # 碰到数字格
            if board[i][j] != '.':
                if j == 8:
                    res = backTracking(board, i+1, 0, row_d, col_d, block_d)
                    if res:
                        return res
                else:
                    res = backTracking(board, i, j+1, row_d, col_d, block_d)
                    if res:
                        return res
            # 碰到空格
            else:
                for ii in range(1, 10):
                    ele = str(ii)
                    if ele not in row_d[i] and ele not in col_d[j] and ele not in block_d[(i//3)*3+j//3]:
                        # 修改状态
                        board[i][j] = ele
                        row_d[i].add(board[i][j])
                        col_d[j].add(board[i][j])
                        block_d[(i//3)*3+j//3].add(board[i][j])
                        # dfs
                        if j == 8:
                            res = backTracking(board, i+1, 0, row_d, col_d, block_d)
                            if res:
                                return res
                        else:
                            res = backTracking(board, i, j+1, row_d, col_d, block_d)
                            if res:
                                return res
                        # 恢复状态
                        row_d[i].remove(board[i][j])
                        col_d[j].remove(board[i][j])
                        block_d[(i//3)*3+j//3].remove(board[i][j])
                        board[i][j] = '.'
                return False
        
        backTracking(board, 0, 0, row_d, col_d, block_d)