LeetCode No51. N 皇后
题目
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
思路
回溯算法的经典题目了。
AC代码
点击查看代码
class Solution {
List> res;
int[] queens;
Set cols;
Set leftLine;
Set rigthLine;
private List drawGrid(int[] queens, int n) {
List grid = new ArrayList();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
grid.add(new String(row));
}
return grid;
}
private void DFS(int row, int n) {
if( row == n ) {
List list = drawGrid(queens, n);
res.add(list);
return ;
}
for(int i=0; i> solveNQueens(int n) {
queens = new int[n];
Arrays.fill(queens, -1);
cols = new HashSet<>();
leftLine = new HashSet<>();
rigthLine = new HashSet<>();
res = new ArrayList<>();
DFS(0, n);
return res;
}
}