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

输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[[“Q”]]
提示：
- 1 <= n <= 9
我的代码（Python）
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result = []
currentResult = []
def setNextQueen():
nonlocal n, result, currentResult
l = len(currentResult)
if l == n:
result.append(currentResult.copy())
return
for j in range(n):
canSet = True
for x, y in currentResult:
if j == y or abs(x - l) == abs(y - j):
canSet = False
break
if canSet:
currentResult.append((l,j))
setNextQueen()
currentResult.pop()
return
setNextQueen()
# print(f'result: {result}')
finalResult = []
for r in result:
tr = [["." for _ in range(n)] for _ in range(n)]
for x, y in r:
tr[x][y] = "Q"
finalResult.append(["".join(row) for row in tr])
print(f'finalResult: {finalResult}')
return finalResult点评
解开了但是效率不高。
思路和官方大体一样，都是一行一行推进，每行放一个，放下一个时断会不会和前面的相冲突。
但是我在判断时是对之前的所有皇后坐标依次进行计算和判定，这一点比较慢。
最直接的一点是没必要存储坐标，按我的做法，行号必定是按顺序递增的，只存储列信息足够了，这也会有优化。
官方是通过三个数组或者整数来处理的，每次比较不需要计算，这样会快一些。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog