力扣刷题Day 67：N 皇后（51）

1.题目描述

2.思路

方法1（自己写的传统型回溯）：将第一行的皇后依次放置在0 ~ n - 1上，可以发现0 ~ (⌊n / 2⌋ - 1)上的放置方案与⌈n / 2⌉ ~ (n - 1)上的放置方案是对称的，此外，如果n是奇数的话还需额外考虑⌊n / 2⌋处的放置方案。声明一个长度为n的布尔数组unselected标记当前方案里每一列的占用情况（False即当前索引列未占用，True即当前索引列已占用），然后用回溯的方法深度优先搜索可行的放置方案。判断当前方案是否可行的条件就是题目当中所说的棋子们不能出现同在一行/一列/斜线上的情况，不能在同一行所以每次回溯都要将row加1，不能在同一列所以每次回溯都要在unselected里面选择值为0的索引对应列，不能在同一斜线上所以每次回溯前都要判断两行之差的绝对值与两列之差的绝对值是否相等（之所以加绝对值判断是因为既有y = x方向上的斜线又有y = -x方向上的斜线）。

方法2（灵茶山艾府佬的排列型回溯）：灵神题解的精髓就在于，将这个问题看作枚举列号的全排列然后剔除皇后相互攻击的情况（灵神判断皇后相互攻击的方法是，两个皇后的行号加列号相等或行号减列号相等）。

3.代码（Python3）

方法1：

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:def backtrack(row ,col, tmp):tmp.append([row, col])unselected[col] = Trueif row == n - 1:res.append(["." * q_col + "Q" + "." * (n - q_col - 1) for q_row, q_col in tmp])tmp.pop()unselected[col] = Falsereturnfor i in range(len(unselected)):if not unselected[i]:diagonal = Falsefor q_row, q_col in tmp:if abs(row + 1 - q_row) == abs(i - q_col):diagonal = Truebreakif not diagonal: backtrack(row + 1, i, tmp)tmp.pop()unselected[col] = Falsereturnres = []unselected = [False] * n# 计算左半边for i in range(int(n / 2)):backtrack(0, i, [])# 将左半边复制给右半边for i in range(len(res)):tmp = []for row in res[i]:tmp.append(row[:: -1])res.append(tmp)# 若n为奇数则需额外计算中间一列if n % 2 != 0:backtrack(0, int(n / 2), [])return res

方法2：

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:def dfs(i):if i == n:res.append(['.' * j + 'Q' + '.' * (n - j - 1) for j in tmp])return# 在(i, j)放置皇后for j, ok in enumerate(col):if not ok and not diagonal_1[i + j] and not diagonal_2[i - j]:tmp[i] = jcol[j] = diagonal_1[i + j] = diagonal_2[i - j] = Truedfs(i + 1)col[j] = diagonal_1[i + j] = diagonal_2[i - j] = Falseres = []tmp = [0] * n # 皇后的坐标是(i, tmp[i])col = [False] * n # diagonal_1 = [False] * (2 * n - 1) # 之前放置的皇后的行号加列号diagonal_2 = [False] * (2 * n - 1) # 之前放置的皇后的行号减列号dfs(0)return res

4.执行情况

方法1：

方法2：

5.感想

灵神的代码其实我没仔细研究，只是粗看了一下，大佬就是大佬，代码的精简度和高效我只能望其项背。