官方链接
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 皇后问题存在两个不同的解法。
思路
用四皇后来验证
解法一
回溯
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
if n < 1:
return []
self.result = []
self.cols = set()
self.pie = set()
self.na = set()
self.dfs(n, 0, [])
return self._generate_result(n)
def dfs(self, n, row, cur_state):
# terminator
if row >= n:
self.result.append(cur_state)
return
# process
for col in range(n):
if col in self.cols or row + col in self.pie or row - col in self.na:
continue
self.cols.add(col)
self.pie.add(row + col)
self.na.add(row - col)
self.dfs(n, row + 1, cur_state + [col])
self.cols.remove(col)
self.pie.remove(row + col)
self.na.remove(row - col)
def _generate_result(self, n):
board = []
for res in self.result:
for i in res:
board.append('.' * i + 'Q' + '.' * (n - i - 1))
return [board[i: i + n] for i in range(0, len(board), n)]
class Solution {
public Set<Integer> cols = new HashSet<>();
public Set<Integer> pie = new HashSet<>();
public Set<Integer> na = new HashSet<>();
public List<List<Integer>> result = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
dfs(n, 0, new ArrayList<>());
return generateResult(n);
}
private void dfs(int n, int row, List<Integer> list) {
if (row >= n) {
result.add(new ArrayList<>(list));
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col) || pie.contains(row + col) || na.contains(row - col)) continue;
cols.add(col);
pie.add(row + col);
na.add(row - col);
list.add(col);
dfs(n, row + 1, list);
cols.remove(col);
pie.remove(row + col);
na.remove(row - col);
list.remove(list.size() - 1);
}
}
private List<List<String>> generateResult(int n) {
List<List<String>> ret = new ArrayList<>();
for (List<Integer> res: result) {
List<String> list = new ArrayList<>();
for (Integer col: res) {
char[] chars = new char[n];
Arrays.fill(chars, '.');
chars[col] = 'Q';
list.add(String.valueOf(chars));
}
ret.add(list);
}
return ret;
}
}
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
helper(res, n, 0, new boolean[n], new boolean[2*n], new boolean[2*n], new ArrayList<>());
return res;
}
private void helper(List<List<String>> res, int n, int row, boolean[] cols, boolean[] pie, boolean[] na, List<String> board) {
if (row == n) {
res.add(new ArrayList<>(board));
return;
}
for (int col = 0; col < n; col++) {
int id1 = row - col + n;
int id2 = 2*n - row - col - 1;
if (cols[col] || pie[id1] || na[id2]) continue;
char[] r = new char[n];
Arrays.fill(r, '.');
r[col] = 'Q';
board.add(row, String.valueOf(r));
cols[col] = true;
pie[id1] = true;
na[id2] = true;
helper(res, n, row + 1, cols, pie, na, board);
cols[col] = false;
pie[id1] = false;
na[id2] = false;
board.remove(board.size() - 1);
}
}
}
简洁的解法
class Solution:
# 附带非位运算判重（Python）
def solveNQueens(self, n: int) -> List[List[str]]:
self.result = []
self.dfs(n, [], [], [])
return [ ['.' * i + 'Q' + '.' * (n-i-1) for i in sol] for sol in self.result]
def dfs(self, n, queens, xy_diff, xy_sum):
length = len(queens)
if length == n:
self.result.append(queens)
return
for col in range(n): # col 是列
if col not in queens and length - col not in xy_diff and length + col not in xy_sum:
self.dfs(n, queens + [col], xy_diff + [length - col], xy_sum + [length + col])
其它解法
class Solution {
public:
std::vector<std::vector<std::string> > solveNQueens(int n) {
std::vector<std::vector<std::string> > res;
std::vector<std::string> nQueens(n, std::string(n, '.'));
solveNQueens(res, nQueens, 0, n);
return res;
}
private:
void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row, int &n) {
if (row == n) {
res.push_back(nQueens);
return;
}
for (int col = 0; col != n; ++col)
if (isValid(nQueens, row, col, n)) {
nQueens[row][col] = 'Q';
solveNQueens(res, nQueens, row + 1, n);
nQueens[row][col] = '.';
}
}
// 这里傻算不如直接用数组存储
bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) {
//check if the column had a queen before.
for (int i = 0; i != row; ++i)
if (nQueens[i][col] == 'Q')
return false;
//check if the 45° diagonal had a queen before.
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
if (nQueens[i][j] == 'Q')
return false;
//check if the 135° diagonal had a queen before.
for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
if (nQueens[i][j] == 'Q')
return false;
return true;
}
};