Leetcode（三）——N皇后（回溯问题，set()）

目录

 

题目：

求解：

分析：

1、set()

2、回溯问题

---

题目：

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

 

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例：

输入：4 输出：[  [".Q..",  // 解法 1   "...Q",   "Q...",   "..Q."],

 ["..Q.",  // 解法 2   "Q...",   "...Q",   ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。

提示：

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

求解：

class Solution: def solveNQueens(self, n: int) -> List[List[str]]: res = [] s = "." * n def backtrack(i, tmp, col, z_diagonal, f_diagonal): if i == n: res.append(tmp) return for j in range(n): if j not in col and i+j not in z_diagonal and i-j not in f_diagonal: backtrack(i+1, tmp+[s[:j]+"Q" + s[j+1:]],col|{j}, z_diagonal|{i+j},f_diagonal{i-j}) backtrack(0,[],set(),set(),set()) return res

分析：

1、set()

集合set是一个无序的不重复元素序列。

可使用{ }或set（）创建。（空集合必须用set()）

集合操作：

s = set(('a','b')) s.add('m') # {'a','b','m'} s.remove('m') # {'a','b'} 移除不存在的元素，报错 s.discard('s') # {'a','b'} 移除不存在的元素，不报错 s.len(s) # 2 s.clear #清空集合

2、回溯问题

该部分整理自回溯算法详解

 

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

 

“解决一个回溯问题，实际上就是一个决策树的遍历过程。”

 

回溯算法经典框架：

result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择