Leetcode N皇后
题目链接
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 1 <= n <= 9 1<=n<=9
分析：
n 个皇后分别被放到 n 行（每一行只能放一个皇后）。本题我们可以通过回溯的做法（因为我们要求的是不同的方案，不是只求一个方案），我们从第0层开始放置皇后，直到 n-1 的皇后也放置好了，没有冲突，此时的放置就是一种方案。
假设此时到了第 i 层，第 j 个位置。
我们需要先进行判断(即 第 i 层之前放置的皇后是否与位置 [ i , j ] [i,j] [i,j] 的皇后有冲突 )。如果没有冲突就在这个位置放置皇后，进入下一层；有冲突的话，就再试试 [ i , j + 1 ] , [ i , j + 2 ] . . . [ i , n − 1 ] [i,j+1],[i,j+2]...[i,n-1] [i,j+1],[i,j+2]...[i,n−1],如果其中有合法的位置就在该位置上放置皇后，再进入下一层。
最后当此时的 i == n时（因为一共只用放置 0 0 0 ~ n − 1 n-1 n−1层），说明已经放置好一个合法的方案了，我们只需要记录这个方案即可。
回溯模拟：
- 时间复杂度: O ( n ! ) O(n!) O(n!)
C++代码：
class Solution {
public:
int n;
vector<vector<string>> res;
//判断 第 r 层之前的皇后摆放 是否与 [r,c] 位置的皇后有冲突
bool check(int r,int c,vector<string>& path){
//第 0 层摆放的直接返回 true
if(r == 0) return true;
for(int i = r - 1,j = 1;i >= 0;i--,j++){
//判断跟 [r,c] 一条直线上的位置是否有冲突
if(path[i][c] == 'Q') return false;
//判断超左上的对角线是否有冲突
if(c + j < n && path[i][c+j] == 'Q') return false;
//判断超右上的对角线是否有冲突
if(c - j >= 0 && path[i][c-j] == 'Q') return false;
}
return true;
}
void backTrack(int u,vector<string>& path){
if(u==n){
res.push_back(path);
return;
}
for(int j = 0;j < n;j++){
//如果冲突了，直接跳过本轮循环
if(!check(u,j,path)) continue;
path[u][j] = 'Q';
backTrack(u+1,path);
//回溯 修改现场
path[u][j] = '.';
}
}
vector<vector<string>> solveNQueens(int n) {
this->n = n;
vector<string> path(n,string(n,'.'));
backTrack(0,path);
return res;
}
};
Java代码：
class Solution {
List<List<String>> res = new ArrayList<>();
int n;
public List<List<String>> solveNQueens(int n) {
char[][] path = new char[n][n];
this.n = n;
for (char[] c : path) {
Arrays.fill(c, '.');
}
backTrack(0, path);
return res;
}
public void backTrack(int u, char[][] path) {
if (u == n) {
res.add(Array2List(path));
return;
}
for (int j = 0;j < n; j++) {
if (isValid (u, j,path)) {
path[u][j] = 'Q';
backTrack(u+1, path);
path[u][j] = '.';
}
}
}
public List Array2List(char[][] path) {
List<String> list = new ArrayList<>();
for (char[] c : path) {
list.add(String.copyValueOf(c));
}
return list;
}
public boolean isValid(int r, int c,char[][] path) {
if(r == 0) return true;
for(int i = r - 1,j = 1;i >= 0;i--,j++){
if(path[i][c] == 'Q') return false;
if(c+j<n && path[i][c+j] == 'Q') return false;
if(c-j>=0 && path[i][c-j] == 'Q') return false;
}
return true;
}
}
第二题是求合法的方案数，实际上可以直接用第一题的代码，将返回结果改为 res.size()即可（因为res里面存的就是所有的合法方案）。
- 时间复杂度: O ( n ! ) O(n!) O(n!)
C++代码：
class Solution {
public:
int n,ans;
bool check(int r,int c,vector<string>& path){
if(r == 0) return true;
for(int i = r - 1,j = 1;i >= 0;i--,j++){
if(path[i][c] == 'Q') return false;
if(c + j < n && path[i][c+j] == 'Q') return false;
if(c - j >= 0 && path[i][c-j] == 'Q') return false;
}
return true;
}
void backTrack(int u,vector<string>& path){
if(u == n){
ans++;
return;
}
for(int i = 0;i < n;i++){
if(!check(u,i,path)) continue;
path[u][i] = 'Q';
backTrack(u+1,path);
path[u][i] = '.';
}
}
int totalNQueens(int n) {
this->n = n;
this->ans = 0;
vector<string> path(n,string(n,'.'));
backTrack(0,path);
return ans;
}
};
Java代码：
class Solution {
int n,ans;
public int totalNQueens(int n) {
this.n = n;
this.ans = 0;
char[][] path = new char[n][n];
for (char[] c : path) {
Arrays.fill(c, '.');
}
backTrack(0, path);
return ans;
}
public void backTrack(int u, char[][] path) {
if (u == n) {
ans++;
return;
}
for (int j = 0;j < n; j++) {
if (isValid (u, j,path)) {
path[u][j] = 'Q';
backTrack(u+1, path);
path[u][j] = '.';
}
}
}
public boolean isValid(int r, int c,char[][] path) {
if(r == 0) return true;
for(int i = r - 1,j = 1;i >= 0;i--,j++){
if(path[i][c] == 'Q') return false;
if(c+j<n && path[i][c+j] == 'Q') return false;
if(c-j>=0 && path[i][c-j] == 'Q') return false;
}
return true;
}
}