N皇后问题是把N个皇后放在一个N×N棋盘上，使皇后之间不会互相攻击。
给出一个整数n，返回n皇后问题的所有摆放方案
例如：
4皇后问题有两种摆放方案
[".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
[编程题]n-皇后
package go.jacob.day0610.chapter8_recursion;
import java.util.ArrayList;
/**
* 著名n皇后问题
* 题目解析：
* n个皇后摆放在n*n的棋盘格中，使得横、竖和两个对角线方向均不会同时出现两个皇后
* <p>
* 解题思路：
* 由于需要在n*n的棋盘格中放入n个皇后，就必须每一行放一个
* 否则就会出现一行有两个皇后的情况，会发生冲突。
* 那么就可以递归的解决每一行问题
* 最核心的问题是：如何能快速判断不合法的情况，即快速剪枝
* 同行或同列的冲突可以简单用一个数组来考虑，难点是两条对角线
* 对角线条数2*n-1
* 左对角线：坐标x+y是一个唯一定值 x+y 范围为0到2*n-2
* 右对角线：坐标x-y是一个唯一定值 x-y+n-1 范围为0到2*n-2
*/
public class Solution {
private ArrayList<String[]> res;
private boolean[] col;//列
private boolean[] dia1;//左对角线
private boolean[] dia2;//右对角线
public ArrayList<String[]> solveNQueens(int n) {
res = new ArrayList<String[]>();
if (n == 0)
return res;
col = new boolean[n];
dia1 = new boolean[2 * n - 1];
dia2 = new boolean[2 * n - 1];
putQueen(n, 0, new ArrayList<Integer>());
return res;
}
//尝试在一个n皇后问题中，摆放第index行的皇后位置,row存放的是每一行皇后存放的下标
private void putQueen(int n, int index, ArrayList<Integer> row) {
if (index == n) {
res.add(generateBoard(n, row));
return;
}
for (int i = 0; i < n; i++) {
//判断能否将第index行的皇后摆放在第i列
if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
col[i] = true;
dia1[index + i] = true;
dia2[index - i + n - 1] = true;
row.add(i);
putQueen(n, index + 1, row);
row.remove(row.size() - 1);
col[i] = false;
dia1[index + i] = false;
dia2[index - i + n - 1] = false;
}
}
}
private String[] generateBoard(int n, ArrayList<Integer> row) {
String[] list = new String[n];
for (int i = 0; i < n; i++) {
StringBuilder s = new StringBuilder();
for (int j = 0; j < n; j++) {
if (j == row.get(i))
s.append("Q");
else
s.append(".");
}
list[i] = s.toString();
}
return list;
}
}
编辑于 2018-06-10 11:14:17
回复(1)
更多回答
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
ArrayList<String[]> ret = new ArrayList<>();
public ArrayList<String[]> solveNQueens(int n) {
if(n <= 0) return ret;
int[] array = new int[n];
helper(array, 0);
return ret;
}
//A[i] = j 表示 i 行 j 列 上放置了一个皇后
public boolean check(int[] array,int k){
//验证新加入的第k行是否可以
for(int i = 0;i < k; i++){
if(array[i] == array[k] || k - i == Math.abs(array[k] - array[i])) return false;
}
return true;
}
public void helper(int[] array,int k){
if(k == array.length){
String[] s = new String[array.length];
for(int i = 0;i < array.length;i++){
char[] ca = new char[array.length];
Arrays.fill(ca, '.');
ca[array[i]] = 'Q';
s[i] = new String(ca);
}
ret.add(s);
return;
}
for(int i = 0;i< array.length;i++){
array[k] = i;
if(check(array,k)){
helper(array, k + 1);
}
}
}
}
发表于 2017-11-13 09:41:16
回复(0)
import java.util.ArrayList;
public class Solution {
static ArrayList<String[]> result;
public ArrayList<String[]> solveNQueens(int n) {
result = new ArrayList<>();
if(n <= 0)
return result;
// cols[i]代表第i个皇后所在的列
int[] cols = new int[n];
for(int i = 0; i < n; i++){
// 将第1个queen放置好
cols[0] = i;
Strategy(cols, 1);
}
return result;
}
// 递归放置皇后
public void Strategy(int[] cols, int row){
// 放到了最后一列，结束
if(row == cols.length){
// 这里其实最好用StringBuffer
String[] str = new String[cols.length];
for(int i = 0; i < str.length; i++){
str[i] = "";
for(int j = 0; j < str.length; j++){
if(j == cols[i])
str[i] += "Q";
else
str[i] += ".";
}
}
result.add(str);
return;
}
// 试凑放置皇后的位置
for(int i = 0; i < cols.length; i++){
if(isValid(cols, row, i)){
cols[row] = i;
Strategy(cols, row + 1);
}
}
}
// 判断在row行col列放置的皇后是否合法
public boolean isValid(int[] cols, int row, int col){
if(cols == null)
return false;
// 与之前皇后在同一列或者斜对角线，即不合法
for(int i = 0; i < row; i++){
if(cols[i] == col || Math.abs(cols[i] - col) == Math.abs(row - i))
return false;
}
return true;
}
}
发表于 2017-05-05 11:03:29
回复(0)
/*运行时间：151ms
占用内存：15344k
*/ import java.util.ArrayList; public class Solution { public ArrayList<String[]> solveNQueens(int n) { ArrayList<String[]> r = new ArrayList<String[]>(); char[][] cur = new char[n][n]; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++) cur[i][j] = '.'; } dfs(r,cur,n,0); return r; } private void dfs(ArrayList<String[]> r,char[][] cur,int n,int row){ if(n == row){ String[] s = new String[n]; for(int i = 0;i < n;i++){ String tmp = new String(cur[i]); s[i] = tmp; } r.add(s); return; } for(int i = 0;i < n;i++){ if(isValid(cur,n,row,i)){ cur[row][i] = 'Q'; dfs(r,cur,n,row+1); cur[row][i] = '.'; } } } private boolean isValid(char[][] cur,int n,int row,int col){ //从第一行往下面依次放入queue，所以不用考虑下面未放入的，只考虑上面已存在的 //排除行 for(int i = 0;i < col;i++){ if(cur[row][i] == 'Q') return false; } //排出列 for(int i = 0;i < row;i++){ if(cur[i][col] == 'Q') return false; } //排除斜线 for(int i = row - 1,j = col - 1;i >= 0 && j >= 0;i--,j--){ if(cur[i][j] == 'Q') return false; } // 排除反斜线 for(int i = row - 1,j = col + 1;i >= 0 && j< n;i--,j++){ if(cur[i][j] == 'Q') return false; } return true; } }
发表于 2018-03-24 15:05:47
回复(1)
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
DFS(0, board, n);
return sols_;
}
private:
vector<vector<string>> sols_;
int cols_, diag1_, diag2_;
bool available(int x, int y, int n) {
return !(cols_ & 1 << x
|| diag1_ & 1 << (x + y)
|| diag2_ & 1 << (n - 1 + x - y));
}
void putBoard(vector<string>& board, int x, int y, int n, bool flag) {
board[y][x] = flag ? 'Q' : '.';
if (flag) {
cols_ |= 1 << x;
diag1_ |= 1 << (x + y);
diag2_ |= 1 << (n - 1 + x - y);
} else {
cols_ -= 1 << x;
diag1_ -= 1 << (x + y);
diag2_ -= 1 << (n - 1 + x - y);
}
}
void DFS(int y, vector<string>& board, int n) {
if (y == n) {
sols_.emplace_back(board);
return;
}
for (int x = 0; x < n; ++x) {
if (not available(x, y, n)) continue;
putBoard(board, x, y, n, true);
DFS(y + 1, board, n);
putBoard(board, x, y, n, false);
}
}
};
发表于 2021-10-08 08:51:35
回复(0)
class Solution {
public:
vector<vector<string> > res;
vector<int> A;
int n;
vector<vector<string> > solveNQueens(int n) {
this->n=n;
A.resize(n);
findNQueens(0);
return res;
}
bool check(int row,int col){
for(int i=0;i<row;i++){
if(A[i]==col||abs(A[i]-col)==abs(i-row)){
return false;
}
}
return true;
}
void findNQueens(int k){
if(k==n){
vector<string> v(n,string(n,'.'));
for(int i=0;i<n;i++){
v[i][A[i]]='Q';
}
res.push_back(v);
return;
}
for(int i=0;i<n;i++){
if(check(k,i)){
A[k]=i;
findNQueens(k+1);
}
}
}
};
发表于 2019-07-06 18:18:17
回复(0)
深度优先DFS，维护一个vecor<vector<bool>> flag只有当bool值为true才允许放皇后；
放皇后之后将对角线和列置为false;
要注意flag是值传递。
class Solution {
public:
vector<vector<string>> res;
vector<vector<string>> solveNQueens(int n) {
vector<string> curStr;
vector<vector<bool>> flag(n, vector<bool>(n, true));
nQueens(n, 0, curStr, flag);
return res;
}
void nQueens(int &n, int cur, vector<string> &curStr, vector<vector<bool>> flag){
if(curStr.size() == n){
res.push_back(curStr);
return ;
}
for(int i = 0; i < n; i ++ ){
if(!flag[cur][i]){
continue;
}
else{
curStr.push_back(cStr(i,n));
nQueens(n, cur+1, curStr, flagTrans(flag, cur, i));
curStr.pop_back();
}
}
}
vector<vector<bool>> flagTrans(vector<vector<bool>> flag, int i, int j){
int len = flag.size();
for(int k = 0; k < len; k++ )
flag[k][j] = false;
int token1 = i, token2 = j;
while(max(++token1,++token2) < len){
flag[token1][token2] = false;
}
token1 = i, token2 = j;
while(min(--token1,--token2) >= 0){
flag[token1][token2] = false;
}
token1 = i, token2 = j;
while(++token1<len && --token2>=0){
flag[token1][token2] = false;
}
token1 = i, token2 = j;
while(--token1>=0 && ++token2<len){
flag[token1][token2] = false;
}
return flag;
}
string cStr(int index,int &n){
string s;
for(int i= 0; i<n ;i++){
if(i == index)
s+='Q';
else
s+='.';
}
return s;
}
};
发表于 2019-06-13 11:38:45
回复(1)
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> board(n, string(n, '.'));
vector<int> pos(n, 1);
vector<int> flag1(n + n - 1, 1); // ↘️的对角线
vector<int> flag2(n + n - 1, 1); // ↙️的对角线
backTrack(res, board, pos, flag1, flag2, 0);
return res;
}
void backTrack(vector<vector<string>> &res, vector<string> &board, vector<int> &pos, vector<int> &flag1, vector<int>& flag2, int idx) {
if(idx == pos.size()) {
res.push_back(board);
return;
}
for(int i = 0; i < pos.size(); ++i) {
// 不能出现同一列
if(pos[i] == 0)
continue;
// 不能出现在同一条斜线上
int n = i - idx, m = i + idx;
n += (pos.size() - 1);
if(flag1[n] == 0 || flag2[m] == 0)
continue;
pos[i] = 0;
board[idx][i] = 'Q';
flag1[n] = 0;
flag2[m] = 0;
backTrack(res, board, pos, flag1, flag2, idx + 1);
pos[i] = 1;
board[idx][i] = '.';
flag1[n] = 1;
flag2[m] = 1;
}
}
};
发表于 2018-08-29 11:12:16
回复(0)
public ArrayList<String[]> solveNQueens(int n) {
ArrayList<String[]> result = new ArrayList<String[]>();
boolean col[] = new boolean[n+1]; //列
boolean tip1[] = new boolean[n*2+1]; //右对角斜线 2~2n
boolean tip2[] = new boolean[n*2+1]; //左对角斜线 2~2n
Stack<String> stack = new Stack<String>();
nQueens(n, 1, col, tip1, tip2, result, stack);
return result;
}
public void nQueens(int n, int cou, boolean col[], boolean tip1[], boolean tip2[], ArrayList<String[]> result, Stack<String> stack){
if(cou > n){
String a[] = new String[n];
stack.toArray(a);
result.add(a);
return;
}
for(int i=1; i<=n; i++){
if(!col[i] && !tip1[cou+i] && !tip2[n-cou+1+i]){
stack.push(genString(i, n));
col[i] = true;
tip1[cou+i] = true;
tip2[n-cou+1+i] = true;
nQueens(n, cou+1, col, tip1, tip2, result, stack);
col[i] = false;
tip1[cou+i] = false;
tip2[n-cou+1+i] = false;
stack.pop();
}
}
}
public String genString(int i, int len){
char chs[] = new char[len];
Arrays.fill(chs, '.');
chs[i-1] = 'Q';
return new String(chs);
}
发表于 2018-07-28 15:52:01
回复(0)
import java.util.*;
public class Solution {
public ArrayList<String[]> solveNQueens(int n) {
ArrayList<String[]> res = new ArrayList<String[]>();
helper(n, 0, new int[n], res);//利用一个数组保存Q的位置信息，数组下标表示行，数组元素表示放置Q的列
return res;
}
private void helper(int n, int row, int[] columnForRow, ArrayList<String[]> res) {
if (row == n) {//row=n表示已经找到了数组，将数组转化为结果即可。
String[] item = new String[n];
for (int i = 0; i < n; i++) {
StringBuilder strRow = new StringBuilder();
for (int j = 0; j < n; j++) {
if (columnForRow[i] == j)//在数组记录的位置上写入Q
strRow.append('Q');
else
strRow.append('.');//在其他所有位置上写入.
}
item[i] = strRow.toString();
}
res.add(item);
return;
}
for (int i = 0; i < n; i++) {
columnForRow[row] = i;
if (check(row, columnForRow)) {
helper(n, row + 1, columnForRow, res);
}
}
}
private boolean check(int row, int[] columnForRow) {
for (int i = 0; i < row; i++) {
if (columnForRow[row] == columnForRow[i] || Math.abs(columnForRow[row] - columnForRow[i]) == row - i)
return false;
}
return true;
}
}
发表于 2017-11-22 13:45:07
回复(0)
力求LOC最短，采用map减少判断合法棋盘的开销：
class Solution(object):
def solve(self, n, i, m, l0, l1, l2):
if i == n:
return [m[:]]
res = []
for j in range(n):
if j not in l0 and i + j not in l1 and j - i not in l2:
m.append(j)
l0[j] = 1
l1[i + j] = 1
l2[j - i] = 1
res.extend(self.solve(n, i + 1, m, l0, l1, l2))
m.pop()
l0.pop(j)
l1.pop(i + j)
l2.pop(j - i)
return res
def solveNQueens(self, n):
res = self.solve(n, 0, [], {}, {}, {})
solutions = []
for r in res:
solution = []
for rr in r:
line = ""
for i in range(n):
line += "." if i != rr else "Q"
solution.append(line)
solutions.append(solution)
return solutions
编辑于 2017-10-07 19:11:25
回复(0)
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
string str;
for(int i=0;i<n;i++)
str.push_back('.');
vector<string> vec;
int a[n];
for(int i=0;i<n;i++)
vec.push_back(str);
vector<vector<string> > res;
Back(n,0,res,vec,a);
return res;
}
void Back(int n,int t,vector<vector<string> > &res,vector<string> vec,int *a)
{
if(n == t)
{
res.push_back(vec);
return;
}
for(int i=0;i<n;i++)
{
a[t] = i;
if(Push(t,a))
{
vec[t][i] = 'Q';
Back(n,t+1,res,vec,a);
vec[t][i] = '.';
}
}
}
bool Push(int m,int a[])
{
bool flag = true;
for(int i=0;i<m;i++)
{
if(a[i] == a[m] || abs(a[m]-a[i]) == (m-i))
{
flag = false;
break;
}
}
return flag;
}
};
发表于 2017-08-12 00:48:45
回复(0)
import java.util.*;
public class Solution {
ArrayList<String[]> list = new ArrayList<String[]>();
public ArrayList<String[]> solveNQueens(int n) {
char[][] res = new char[n][n];
for(char[] chs : res)
Arrays.fill(chs, '.');
int[] cols = new int[n];
int[] slash1 = new int[2*n-1];
int[] slash2 = new int[2*n-1];
DFS(res, n, 0, cols, slash1, slash2);
return list;
}
public void DFS(char[][] res, int n, int cur, int cols[], int slash1[], int slash2[]) {
if(cur == n) {
String[] s = new String[n];
for(int i=0; i<n; i++)
s[i] = new String(res[i]);
list.add(s);
}
for(int i=0; i<n; i++) {
if(cols[i] != 1 && slash1[cur + i] != 1 && slash2[n-1-cur+i] != 1) {
cols[i] = 1;
slash1[cur + i] = 1;
slash2[n-1-cur+i] = 1;
res[cur][i] = 'Q';
DFS(res, n, cur+1, cols, slash1, slash2);
cols[i] = 0;
slash1[cur + i] = 0;
slash2[n-1-cur+i] = 0;
res[cur][i] = '.';
}
}
}
}
发表于 2017-06-19 13:44:09
回复(0)
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<vector<string>> ret;
vector<string> board(n, string(n, '.'));
set<int> col_used;
DFS(ret, board, col_used, 0);
return ret;
}
void DFS(vector<vector<string>> &all_boards,
vector<string> &board, set<int> &col_used, int r){
int rows=board.size(), cols=board[0].size();
if(r>=rows)
all_boards.push_back(board);
else
for(int c=0; c<cols; ++c)
if(check(board, col_used, r, c)){
col_used.insert(c);
board[r][c]='Q';
DFS(all_boards, board, col_used, r+1);
board[r][c]='.';
col_used.erase(c);
}
}
bool check(vector<string> &board, set<int>
&col_used, int r, int c){
if(col_used.count(c))
return false;
int rows=board.size(), cols=board[0].size();
int dr, dc;
for(dr=1, dc=1; r+dr<rows&&c+dc<cols; ++dr,
++dc)
if(board[r+dr][c+dc]=='Q')
return false;
for(dr=-1, dc=-1; r+dr>=0&&c+dc>=0; --dr,
--dc)
if(board[r+dr][c+dc]=='Q')
return false;
for(dr=-1, dc=1; r+dr>=0&&c+dc<cols; --dr,
++dc)
if(board[r+dr][c+dc]=='Q')
return false;
for(dr=1, dc=-1; r+dr<rows&&c+dc>=0; ++dr,
--dc)
if(board[r+dr][c+dc]=='Q')
return false;
return true;
}
};
发表于 2017-04-20 17:01:59
回复(0)
class Solution {
public:
vector > solveNQueens(int n) {
vector > res;
vector solution;
vector occupiedCol(n, -1);
solveNQueens(0, n, solution,res, occupiedCol);
return res;
}
private:
void solveNQueens(int row, int n, vector& solution, vector >& res, vector& occupiedCol) {
if(row == n){res.push_back(solution);return;}
for(int i=0; i < n; i++) {
string s(n, '.');
s[i] = 'Q';
occupiedCol[row] = i;
solution.push_back(s);
if(ifValid(occupiedCol, row, i)) {
solveNQueens(row+1, n, solution, res, occupiedCol);
}
solution.pop_back();
occupiedCol[row] = -1;
}
}
bool ifValid(vector& occupiedCols, int i, int j) {
int len = occupiedCols.size();
for(int m = 0; m < i; m++) {//检查前面的行
int k = occupiedCols[m];
if(j == k || abs(j-k) == abs(i-m))//若前面的行皇后所在的列与j相等或者与(i,j)在同一对角线上
return false;
}
return true;
}
};
编辑于 2017-01-26 16:46:49
回复(0)
//递归回溯
vector<vector<string> > solveNQueens(int n) {
string str;
for(int i=0;i<n;i++)
str.push_back('.');
vector<string> vec;
int *arr=new int[n];
for(int i=0;i<n;i++)
vec.push_back(str);
vector<vector<string>> result;
goahead(n,0,result,vec,arr);
return result;
}
void goahead(int n,int t,vector<vector<string>> &res,vector<string> vec,int *arr){
if(n==t){
res.push_back(vec);
return;
}
for(int i=0;i<n;i++){
arr[t]=i;
if(push(t,arr)){
vec[t][i]='Q';
goahead(n,t+1,res,vec,arr);
vec[t][i]='.';
}
}
}
bool push(int m,int *arr){
bool flag=true;
for(int i=0;i<m;i++){
if(arr[i]==arr[m] ||abs(arr[m]-arr[i])==(m-i)){
flag=false;
break;
}
}
return flag;
}
发表于 2016-09-15 16:33:12
回复(0)
class Solution {
public:
//tmp[i]表示第i行的Q在哪一列
void findSolution(int n,vector<vector<int> >&pos,
vector<int>&tmp){
if(tmp.size()==n)
{
pos.push_back(tmp);
return;
}
int i,j,k;
for( i=0;i<n;i++){
k=tmp.size();
for( j=0;j<k;j++){
if(i==tmp[j]||
abs(k-j)==abs(i-tmp[j]))
break;
}
if(j<k)
continue;
tmp.push_back(i);
findSolution(n,pos,tmp);
int end=tmp.size()-1;
if(k!=end)
tmp.erase(tmp.begin()+k,
tmp.begin()+end);
else
tmp.erase(tmp.begin()+k);
}
}
void drawSolution(int n,vector<vector<string> >&solve,
vector<vector<int> >&pos){
for(int i=0;i<pos.size();i++){
string s(n,'.');
vector<string>row(n,s);
for(int j=0;j<n;j++){
row[j][pos[i][j]]='Q';
}
solve.push_back(row);
}
}
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> >solve;
if(n<1)
return solve;
vector<vector<int> >pos;
vector<int>tmp;
findSolution(n,pos,tmp);
if(pos.empty())
return solve;
drawSolution(n,solve,pos);
return solve;
}
};
发表于 2016-06-07 10:31:01
回复(0)
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> cur(n, string(n, '.')); // 初始化棋盘，所有的位置都没有摆放皇后
dfs(res, cur, n, 0);
return res;
}
void dfs(vector<vector<string>> &res, vector<string> &cur, int &n, int row) {
if (row == n) { // 当超出行数超出了棋盘，则把这次搜索的结果放入res中。
res.push_back(cur);
return;
}
for (int j = 0; j < n; j++) {
if (isValid(cur, n, row, j)) { // 判断在(row, j)处是否可以放一个皇后
cur[row][j] = 'Q'; // 如果可以，则放一个皇后
dfs(res, cur, n, row + 1); // 继续在下一行找一个位置放皇后
cur[row][j] = '.'; // 因为需要找到所有可能的情况，所以必然需要对每一行进行回退。去判断这一行的下一列是否可以放皇后。
}
}
}
bool isValid(vector<string> &cur, int &n, int row, int col) {
// 检查列
for (int i = 0; i < row; i++) {
if (cur[i][col] == 'Q') {
return false;
}
}
// 检查反斜线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (cur[i][j] == 'Q') {
return false;
}
}
// 检查斜线
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (cur[i][j] == 'Q') {
return false;
}
}
return true;
}
};
发表于 2017-11-30 17:14:12
回复(1)
我这个代码为什么提交不了？？？？？
import java.util.*;
public class Solution {
private ArrayList<String[]> res = new ArrayList<String[]>();
private int[] a;
public ArrayList<String[]> solveNQueens(int n) {
a = new int[n];
dnf(0, n, a);
return res;
}
private void dnf(int row, int n, int[] a) {
if (row == n) {
//打印a
res.add(int2str(a));
return;
}
for (int i = 0; i < n; i++) {
a[row] = i;
if (check(row, a)) {
a[row] = i;
dnf(row + 1, n, a);
}
}
}
private boolean check(int row, int[] a) {
for (int i = 0 ; i < row; i++) {
if (a[i] == a[row]) return false;
if (a[row] - a[i] == row - i) return false;
if (a[row] - a[i] == i - row) return false;
}
return true;
}
private String[] int2str(int[] a) {
String[] ab = new String[a.length];
//1302
for (int i = 0; i < a.length; i++) {
StringBuffer sb = new StringBuffer();
for (int j = 0; j < a.length; j++) {
if (i == a[j]) {
sb.append("Q");
} else {
sb.append(".");
}
}
ab[i] = sb.toString();
}
return ab;
}
}
public class Solution {
private ArrayList<String[]> res = new ArrayList<String[]>();
private int[] a;
public ArrayList<String[]> solveNQueens(int n) {
a = new int[n];
dnf(0, n, a);
return res;
}
private void dnf(int row, int n, int[] a) {
if (row == n) {
//打印a
res.add(int2str(a));
return;
}
for (int i = 0; i < n; i++) {
a[row] = i;
if (check(row, a)) {
a[row] = i;
dnf(row + 1, n, a);
}
}
}
private boolean check(int row, int[] a) {
for (int i = 0 ; i < row; i++) {
if (a[i] == a[row]) return false;
if (a[row] - a[i] == row - i) return false;
if (a[row] - a[i] == i - row) return false;
}
return true;
}
private String[] int2str(int[] a) {
String[] ab = new String[a.length];
//1302
for (int i = 0; i < a.length; i++) {
StringBuffer sb = new StringBuffer();
for (int j = 0; j < a.length; j++) {
if (i == a[j]) {
sb.append("Q");
} else {
sb.append(".");
}
}
ab[i] = sb.toString();
}
return ab;
}
}
发表于 2022-06-07 08:31:07
回复(1)
问题信息
难度：
59条回答
59收藏
21804浏览
通过挑战的用户
查看代码-
2022-08-20 16:29:03
-
2022-08-19 15:57:43
-
2022-08-12 15:15:45
-
2022-07-09 11:55:43
-
2022-06-17 00:46:24
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
