N皇后
- 难度： 困难
- 通过率： 36.7%
- 题目链接：https://leetcode-cn.com/problems/n-queens
题目描述
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4 输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。
解法：
采用回溯剪枝策略，在每次深入前检查当前位置是否会产生冲突。
在检查是否发生冲突的时候，需要根据前面排定的行中皇后的位置，来决定当前位置是否合法。
同在一列的时候不合法，处于一条斜线上时不合法。
- 同一列：x 相同
- 斜线：x 之差，等于 y 之差
x
----------------->
. o . . . . . . |
. . . . . . . o |
. x . x . . x x | y
|
v
class Solution:
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
solutions = []
self.__n_queues(n, (), solutions)
return [self.__format(solution) for solution in solutions]
def __conflict(self, state, x):
y = len(state)
for i in range(y):
if abs(state[i] - x) in (0, y - i):
return True
return False
def __n_queues(self, n, state, solutions):
for pos in range(n):
if self.__conflict(state, pos):
continue
next_state = state + (pos,)
if len(next_state) == n:
solutions.append(next_state)
else:
self.__n_queues(n, state + (pos,), solutions)
def __format(self, solution):
n = len(solution)
return ['.' * pos + 'Q' + '.' * (n - pos -1) for pos in solution]