我理解的回溯法
- 回溯法本质上就是穷举法，对穷举法的优化，优化的关键在于判断哪些情况是不需要考虑的，然后不去遍历这些不必要的情况（剪枝）。
- 理解穷举法，要理解回溯法就要先真正明白穷举法。用下面例题来理解一下穷举法
输出给的数字的全排列
输入：1 2 3
输出：
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]核心步骤的伪代码：
Permutation(array A, array B){ If Array B is OK Return array A Else For I in B: Permutation(A add I, B remove I)}Python实现：
# Full Permutation全排列def permute(numbers: list): sorted(numbers) visited = [0 for i in numbers] output = [] middle = [] helper(numbers, visited, middle, output) return outputdef helper(numbers: list, visited: list, middle: list, output: list): if len(middle) is len(numbers): output.append(middle.copy()) return for i in range(0, len(numbers)): if visited[i] is 0: visited[i] = 1 middle.append(numbers[i]) helper(numbers, visited, middle, output) visited[i] = 0 middle.pop()if __name__ == '__main__': nums = [1, 2, 3] print(permute(nums))- N皇后问题，这个在回溯法中比较经典，我们理解了穷举法的全排列，就可以试着理解N皇后问题，其实全排列实现也是用到了回溯的思想。
我们以8皇后为例，8*8的棋盘上，放8个皇后的棋子，使他们不能在同行同列和对角线上。
输入：8
输出：92
Python实现：
# N queen n 皇后问题def n_queens(n: int): output = [0] middle = [-1 for i in range(0, n)] compute_n_queen(n, 0, middle, output) return output[0] def compute_n_queen(n: int, row: int, middle: list, output: list): if n is row: output[0] += 1 return # 一行一行来 for column in range(0, n): flag = 1 middle[row] = column # 这里回溯之前放置的棋子，是否和这次放置的冲突，也就是回溯法的剪枝 for j in range(0, row): # 因为我们是一行一行判断的，所以不用判断是否在同一行，只判断是否在同一列 # 是否在同一对角线判断即行列相减相加是否相同 if middle[row] is middle[j] or row - middle[row] is j - middle[j] or row + middle[row] is j + middle[j]: flag = 0 break if flag: compute_n_queen(n, row + 1, middle, output) if __name__ == '__main__': print(n_queens(8))