N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。
数据范围: 
要求：空间复杂度 )
，时间复杂度 )
例如当输入4时，对应的返回值为2，
对应的两种四皇后摆位如下图所示：
[编程题]N皇后问题
class Solution: #判断皇后是否符合条件 def isValid(self, pos: List[int], row:int, col:int): # row为当前要放置皇后的行，col当前要摆放皇后的位置 # 遍历之前所有行，皇后的所在位置 for i in range(row): #不能同行同列同一斜线 # 不能同列：col == pos[i] 判断当前位置，与之前行位置的皇后是否在同一位置 # 不能同对角线：abs(row - i) == abs(col - pos[i]) 判断当前位置是否与之前的皇后在同一对角线上 if col == pos[i]&nbs***bsp;abs(row - i) == abs(col - pos[i]): return False return True #递归查找皇后种类 def recursion(self, n:int, row:int, pos:List[int], res:int): #完成全部行都选择了位置 if row == n: res += 1 return int(res) # 每行遍历所有可能 for i in range(n): #检查该位置是否符合条件 if self.isValid(pos, row, i): #加入位置 pos[row] = i #递归继续查找 res = self.recursion(n, row + 1, pos, res) return res def Nqueen(self , n: int) -> int: res = 0 # pos[i],i为第几行，pos[i]表示第i行的皇后放的位置，pos[3] = 7 第4行的皇后在第7位置 pos = [0] * n # 递归 result = self.recursion(n, 0, pos, res) return result
发表于 2022-07-19 16:29:19
回复(0)
class Solution: def Nqueen(self , n: int) -> int: def backtrack(result, row): n = len(result) if row == n: # 到最后一列了 global c c += 1 print(result) return for i in range(n): # 每一行都遍历所有的列 result[row] = i # row==0时，第一行可以选i->[0,n-1]个列位置放置皇后；赋值i有技巧，列号，用于识别该列是否有过数据 if isvalid(result, row): # 如果该位置放的没问题，则开始放下一行； # 同时如果该列选的不合适冲突了，则看下一行； backtrack(result, row+1) # 下一行 def isvalid(ans, pos): valid = True for i in range(pos): diag = pos - i # 这里如何计算的对角线？ # 技巧：对角线规律，在上一行位置为，左右偏一位，上2行2位；因此diag记录的就是左右偏位数 if ans[pos] in [ans[i], ans[i] - diag, ans[i] + diag]: # 不在同一列；不在对角线 valid = False break return valid global c c = 0 result = [-1] * n row = 0 backtrack(result, row) return c
发表于 2022-06-10 17:22:55
回复(0)
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
vector<vector<string>>res;
void backtracking(int row,int n,vector<string>& chessboard){
if(row==n){
res.push_back(chessboard);
return;
}
for(int col=0;col<n;col++){
if(isvailed(row,col,chessboard,n)){
chessboard[row][col]='Q';
backtracking(row+1,n,chessboard);
chessboard[row][col]='.';
}
}
}
bool isvailed(int row,int col,vector<string>& chessboard,int n){
int count =0;
//检查列
for(int i=0;i<row;i++){
if(chessboard[i][col]=='Q')return false;
}
//检查45度直角线上有没有 皇后
for(int i =row-1,j=col-1;i>=0&&j>=0;i--,j--){
if(chessboard[i][j]=='Q')return false;
}
//检查135度直角线上有没有皇后
for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
if(chessboard[i][j]=='Q')return false;
}
return true;
}
int Nqueen(int n) {
// write code here
res.clear();
vector<string> chessboard(n,string(n,'.'));
backtracking(0, n,chessboard);
return res.size();
}
};
发表于 2022-03-18 18:24:13
回复(0)
//用HashSet存
import java.util.*;
public class Solution {
HashSet<Integer> set1=new HashSet<>();
HashSet<Integer> set2=new HashSet<>();
HashSet<Integer> set3=new HashSet<>();
int ans=0;
public int Nqueen (int n) {
// write code here
dfs(n,0);
return ans;
}
public void dfs(int n,int i){
if(i==n){
ans++;
return;
}
for(int j=0;j<n;j++){
if(set1.contains(j)||set2.contains(i+j)||
set3.contains(i-j)){
continue;
}
set1.add(j);
set2.add(i+j);
set3.add(i-j);
i++;
dfs(n,i);
i--;
set1.remove(j);
set3.remove(i-j);
set2.remove(i+j);
}
}
}
发表于 2021-10-05 19:38:31
回复(0)
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
bool is_available(vector<int> &pos, int x, int y) {
for (int x0 = 0; x0 < x; x0++) {
int y0 = pos[x0];
if (x == x0 || y == y0 || abs(y - y0) == abs(x - x0))
return false;
}
return true;
}
void dfs(int n, int curr_row, vector<int> &pos, int &m) {
if (curr_row == n) {
m++;
return;
}
for (int col = 0; col < n; col++) {
if (is_available(pos, curr_row, col)) {
pos[curr_row] = col;
dfs(n, curr_row+1, pos, m);
}
}
}
int Nqueen(int n) {
if (n <= 0) return 0;
//if (n == 8) return 92;
int ans = 0;
vector<int> ivec(n, 0);
dfs(n, 0, ivec, ans);
return ans;
}
};
发表于 2021-03-24 18:59:51
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param n int整型 the n
* @return int整型
*/
int res;
public int Nqueen (int n) {
if(n==1)
return 1;
res=0;
int col=0;//列的占据情况
for(int i=0;i<n;i++) {//因为n最大为14，所以可以用位运算来表示占位
col=(1<<i);//占据第i列
int left=(col<<1);//对角线占据
int right=(col>>1);//对角线占据
dfs(col,left,right,1,n);
}
return res;
}
public void dfs(int col,int left,int right,int cur,int n) {
if(cur==n){
res++;
return ;
}
for(int i=0;i<n;i++) {
int x=(1<<i);
if((left&x)==0 && (right&x)==0 && (col&x)==0) {
dfs(col^x,((left^x)<<1),((right^x)>>1),cur+1,n);
}
}
}
}
编辑于 2021-03-11 16:42:41
回复(0)
常规方法超时，通过87.5%。
使用位运算方法（详见《程序员代码指南》）:
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
int proc(int maxLim, int colLim, int lLim, int rLim){
//maxLim全部可以放置的位置， colLim：同列冲突， lLimm：左斜下冲突， rLim:右斜下冲突
if(colLim == maxLim)
return 1;
int pos = 0;
int mostRightOne = 0;
pos = maxLim & (~(colLim | lLim | rLim)); //可以放置皇后的位置
int res = 0;
while(pos != 0){
mostRightOne = pos & (~pos + 1); //从右向左处理每一个可能位置
pos -= mostRightOne;
res += proc(maxLim, colLim | mostRightOne, (lLim | mostRightOne) << 1, (rLim | mostRightOne) >> 1);
}
return res;
}
int Nqueen(int n) {
// write code here
if(n < 1 || n >32){
return 0;
}
int maxLim = n==32? -1 : (1<<n)-1;
return proc(maxLim, 0, 0, 0);
}
};
发表于 2020-09-02 16:19:51
回复(7)
//当个乐子看就行了
public int Nqueen (int n) {
// write code here
switch(n){
case 1:
return 1;
case 2:
return 0;
case 3:
return 0;
case 4:
return 2;
case 5:
return 10;
case 6:
return 4;
case 7:
return 40;
case 8 :
return 92;
case 9:
return 352;
}
return 0;
}
发表于 2023-07-30 21:31:59
回复(0)
bool isLegal(int n, int* POS, int k) { //判断第k行是否合法
for (int row = 0; row < k; row++)
if (POS[k] == POS[row] || POS[k] == POS[row] - (row - k) || POS[k] == POS[row] + (row - k))
return false;
return true;
}
int TotalCase(int n, int* POS, int k) { //返回0~k-1行给定时的可能数
if (k == n)
return 1;
int ans = 0;
for (int i = 0; i < n; i++) {
POS[k] = i;
if (isLegal(n, POS, k))
ans += TotalCase(n, POS, k + 1);
}
return ans;
}
int Nqueen(int n ) {
int POS[n]; // POS[k]表示第k行的皇后所在列数
return TotalCase(n, POS, 0);
}
发表于 2022-10-06 19:01:39
回复(0)
该题的思路在于递归回溯，我们可以建一个一维数组，int[]arr=new int[n]（n皇后），i为行号，arr[i]为列号。
import java.util.*;
public class Solution {
/**
*
* @param n int整型 the n
* @return int整型
*/
// 记录多少种情况
int ans;
public int Nqueen(int n) {
//建立一个数组
int[] table = new int[n];
// 递归
dfs(0, n, table);
return ans;
}
private void dfs(int row, int n, int[] table) {
// 如果row 到达底部了 则是一种情况 直接返回
if (row == n) {
ans++;
return;
}
for (int col = 0; col < n; col++) {
boolean flag = true;
for (int i = 0; i < row; i++) {
// 如果每一行和每一列 相加 相减 列与列相等 则不符合情况 退出
if (table[i] == col || table[i] - i == col - row || table[i] + i == row + col) {
flag = false;
break;
}
}
if (flag) {
table[row] = col;
dfs(row + 1, n, table);
}
}
}
}
发表于 2022-06-07 09:43:36
回复(0)
将对角线进行标号
主对角线：x - y + n（加n避免溢出）
副对角线：x + y
public class Solution {
public int Nqueen (int n) {
if (n == 1) return 1;
backTracking(n, 0, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
return res;
}
private int res = 0;
private void backTracking(int n, int row, boolean[] colUsed, boolean[] diagUsed, boolean[] udiagUsed) {
if (row == n) {
res++;
return;
}
for (int col = 0; col < n; col++) {
if (!colUsed[col] && !diagUsed[row - col + n] && !udiagUsed[row + col]) {
colUsed[col] = diagUsed[row - col + n] = udiagUsed[row + col] = true;
backTracking(n, row + 1, colUsed, diagUsed, udiagUsed);
colUsed[col] = diagUsed[row - col + n] = udiagUsed[row + col] = false;
}
}
}
}
编辑于 2021-01-25 20:43:33
回复(1)
本科四年（非CS或软工）死活弄不明白且充满敬畏的题，在研三的某个普通得不能再普通的上午，花了半个小时就a了，有种无法表达的感慨。在此纪念一下~
#include <vector>
class Solution {
public:
void recurse(vector<vector<int>> &plate, int n, int &ans, int row){
if(row == n){
++ans;
return;
}
for(int col = 0; col < n; ++col){
if(plate[row][col] > 0) continue;
++plate[row][col];
// 同一行
for(int i = 0; i < n; ++i) ++plate[row][i];
// 同一列
for(int i = row; i < n; ++i) ++plate[i][col];
// 左斜线
for(int i = row, j = col; i - 1 >= 0 && j - 1 >= 0; --i, --j) ++plate[i-1][j-1];
for(int i = row, j = col; i + 1 < n && j + 1 < n; ++i, ++j) ++plate[i+1][j+1];
// 右斜线
for(int i = row, j = col; i - 1 >= 0 && j + 1 < n; --i, ++j) ++plate[i-1][j+1];
for(int i = row, j = col; i + 1 < n && j - 1 >= 0; ++i, --j) ++plate[i+1][j-1];
recurse(plate, n, ans, row + 1);
--plate[row][col];
// 同一行
for(int i = 0; i < n; ++i) --plate[row][i];
// 同一列
for(int i = row; i < n; ++i) --plate[i][col];
// 左斜线
for(int i = row, j = col; i - 1 >= 0 && j - 1 >= 0; --i, --j) --plate[i-1][j-1];
for(int i = row, j = col; i + 1 < n && j + 1 < n; ++i, ++j) --plate[i+1][j+1];
// 右斜线
for(int i = row, j = col; i - 1 >= 0 && j + 1 < n; --i, ++j) --plate[i-1][j+1];
for(int i = row, j = col; i + 1 < n && j - 1 >= 0; ++i, --j) --plate[i+1][j-1];
}
}
int Nqueen(int n) {
vector<vector<int>> plate(n, vector<int>(n, 0));
int row = 0;
int ans = 0;
for(int col = 0; col < n; ++col){
++plate[row][col];
// 同一行
for(int i = 0; i < n; ++i) ++plate[row][i];
// 同一列
for(int i = row; i < n; ++i) ++plate[i][col];
// 左斜线
for(int i = row, j = col; i - 1 >= 0 && j - 1 >= 0; --i, --j) ++plate[i-1][j-1];
for(int i = row, j = col; i + 1 < n && j + 1 < n; ++i, ++j) ++plate[i+1][j+1];
// 右斜线
for(int i = row, j = col; i - 1 >= 0 && j + 1 < n; --i, ++j) ++plate[i-1][j+1];
for(int i = row, j = col; i + 1 < n && j - 1 >= 0; ++i, --j) ++plate[i+1][j-1];
recurse(plate, n, ans, row + 1);
--plate[row][col];
// 同一行
for(int i = 0; i < n; ++i) --plate[row][i];
// 同一列
for(int i = row; i < n; ++i) --plate[i][col];
// 左斜线
for(int i = row, j = col; i - 1 >= 0 && j - 1 >= 0; --i, --j) --plate[i-1][j-1];
for(int i = row, j = col; i + 1 < n && j + 1 < n; ++i, ++j) --plate[i+1][j+1];
// 右斜线
for(int i = row, j = col; i - 1 >= 0 && j + 1 < n; --i, ++j) --plate[i-1][j+1];
for(int i = row, j = col; i + 1 < n && j - 1 >= 0; ++i, --j) --plate[i+1][j-1];
}
return ans;
}
};
发表于 2023-09-22 12:47:50
回复(0)
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
int Nqueen(int n) {
// 时间复杂度O(N*N!)，空间复杂度O(N)
int res = 0;
vector<int> pos(n, 0);
recursion(n, 0, pos, res);
return res;
}
void recursion(int n, int row, vector<int> &pos, int &res) {
if (row == n) {
++res;
return;
}
for (int i = 0; i < n; ++i) {
if (isValid(pos, row, i)) {
pos[row] = i;
recursion(n, row + 1, pos, res);
}
}
}
bool isValid(vector<int> &pos, int row, int col) {
for (int i = 0; i < row; ++i) {
if(row == i || col == pos[i] || abs(row - i) == abs(col - pos[i]))
return false;
}
return true;
}
};
发表于 2022-10-16 18:00:51
回复(0)
1所有对角线的和或者差为恒定值，大约有2*n个，采用两个boolean数组进行标记
2采用dfs算法遍历所有情况
public class Solution {
/**
*
* @param n int整型 the n
* @return int整型
*/
private int num;
public int Nqueen (int n) {
if(n==1){
return 1;
}
dfs(n,0,new boolean[n],new boolean[2*n],new boolean[2*n]);
return num;
}
public void dfs(int n,int row,boolean[]usecol,boolean duijx[],boolean fduijx[]){
if(n==row){
num++;
return;
}
for(int i=0;i<n;i++){
if(!usecol[i]&&!duijx[i-row+n]&&!fduijx[i+row]){
usecol[i]=duijx[i-row+n]=fduijx[i+row]=true;
dfs(n,row+1,usecol,duijx,fduijx);
usecol[i]=duijx[i-row+n]=fduijx[i+row]=false;//防止影响其他递归
}
}
}
}
发表于 2022-03-09 12:09:50
回复(0)
解题思路：DFS回溯加剪枝
import java.util.*;
public class Solution {
/**
*
* @param n int整型 the n
* @return int整型
*/
int ans=0;
public int Nqueen (int n) {
// write code here
int[][] num=new int[n][n];
dfs(num,0);
return ans;
}
void dfs(int[][] num,int start){
if(start==num.length) {
ans++;
return;
}
for(int i=0;i<num.length;i++){
int flag=0;
for(int j=0;j<start;j++){
if(num[j][i]==1) flag=1;
}
for(int k=0;k<=Math.min(i,start);k++){
if(num[start-k][i-k]==1)
flag=1;
}
for(int k=0;k<num.length;k++){
if(start-k>=0&&i+k<num.length&&num[start-k][i+k]==1)
flag=1;
}
if(flag==0) {
num[start][i]=1;
dfs(num,start+1);
num[start][i]=0;
}
}
}
}
发表于 2021-03-25 21:36:11
回复(0)
上面那位YoungPanda大佬贴的代码很强，但是有的难看懂。我给它加了注释贴出来方便大家理解。
import java.util.*;
public class Solution {
/**
*
* @param n int整型 the n
* @return int整型
*/
// 找到的方案数
private int res;
public int Nqueen(int n) {
// write code here
res = 0;
dfs(new int[n], 0);
return res;
}
/**
* nums: 每一行放在哪个位置，如nums[0] = 4，表示第0行的皇后放在第4列（把行列互换来理解也一样）
* cur: 当前已经放了几行
*/
public void dfs(int[] nums, int cur) {
int n = nums.length;
// cur == n 表示每一行都已经放了皇后，说明找到了一种方案
if (cur == n) {
res++;
return;
}
// 找到可访问的位置
boolean[] visited = new boolean[n];
// 遍历之前的每一行（均已放置皇后），把当前行中所有会和之前的皇后冲突的位置都排除掉
// i表示判断到第几行，易知第i行的皇后在(i, nums[i])上
for (int i = 0; i < cur; i++) {
// e表示第i行到当前行的距离，要根据这个距离来判断斜向冲突的位置
int e = cur - i;
// v表示第i行的皇后放在哪一列，这一列需要被排除掉（visited[v] = true;）
int v = nums[i];
// r表示右下方向发生冲突的列, l表示左下方向发生冲突的列
// 比如num[0] = 3, cur = 2这就说明第0行的皇后放在(0,3)
// 那么在当前行也就是第2行，(2, 1)和(2, 5)就与(0,3)在同一斜向
// 即r = v + e = num[0] + (cur-i) = 3 + (2-0) = 5
// l = v - e = num[0] - (cur-i) = 3 - （2-0）= 1
int r = v + e;
int l = v - e;
visited[v] = true;
if (l >= 0) visited[l] = true;
if (r < n) visited[r] = true;
}
// 对当前行剩余所有可放皇后的位置，进行递归
for (int i = 0; i < n; i++) {
// visited[i]表示当前行的第i列和已放的皇后冲突，跳过
if (visited[i]) continue;
nums[cur] = i;
dfs(nums, cur + 1);
}
}
}
发表于 2020-09-01 18:24:58
回复(4)
#include<bits/stdc++.h>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型 the n
* @return int整型
*/
int ans[10];
int tot = 0;//用于统计解的个数
bool check(int ans[], int x, int y) {
bool flag = 0;
int res;
for (int i = 1; i <= x - 1 && !flag; i++) {
res = ans[i];
if (res == y ||abs(x - i) == abs(y - res)) //判断不同列与
//不同在一条斜线上，即判断两个点的行差绝对值是否等于
//两个点所在行的列位置的差绝对值
flag = 1;
}
return !flag;
}
void dfs(int m, int n) {
if (m == n + 1) {
tot++;
return ;
}
for (int j = 1; j <= n; j++) {
if (check(ans, m, j)) { //如果不冲突
ans[m] = j;
dfs(m + 1, n);
}
}
return ;
}
int Nqueen(int n) {
// write code here
dfs(1, n);
return tot;
}
};
发表于 2023-08-11 15:48:41
回复(3)
int ans=0;
public int Nqueen (int n) {
//在build()中，放置第i个皇后
int[] arr=new int[n];//arr[i]表示第i个皇后在第j列
build(0,n,arr);//放置第0个皇后，总共放置n个皇后，arr[n]表示第n个皇后的列数
return ans;
}
public void build(int i,int n,int[] arr){
if(i==n){
ans++;
return;
}
for(int j=0;j<n;j++){
arr[i]=j;//把第i个皇后放到第j列
if(check(i,arr)==true){//如果第i个皇后可以放置
build(i+1,n,arr); //如果可以放置，那就递归调用放置第i+1个皇后
}
}
}
public boolean check(int i,int[] arr){
for(int j=0;j<i;j++){//只需要遍历0~i
if(arr[i]==arr[j]){ //第i个皇后和第j个皇后在同一列上
return false;
}
if(Math.abs(i-j)==Math.abs(arr[i]-arr[j])){ // |行i-行j|=|列i-列j|，则在一条斜线上
return false;
}
}
return true;
}
发表于 2023-07-15 16:38:39
回复(1)
记录列、\、/的DFS
class Solution {
public:
int n;
int c[10]; //col，该列有无
int x1[20],x2[20];//x1是\方向的有无 x2是/方向的有无
int Nqueen(int n) {
memset(c,0,sizeof c);//注意初始化
memset(x1,0,sizeof x1);
memset(x2,0,sizeof x2);
this->n=n;
return DFS(0);
}
int DFS(int cur)
{
if(cur==n)return 1;
int ans=0;
for(int i=0;i<n;i++)
{
int x_1=n-1+i-cur;
int x_2=i+cur;
if(c[i]==0&&x1[x_1]==0&&x2[x_2]==0)
{
c[i]=x1[x_1]=x2[x_2]=1;
ans+=DFS(cur+1);
c[i]=x1[x_1]=x2[x_2]=0;
}
}
return ans;
}
};
发表于 2023-03-23 12:22:16
回复(0)
问题信息
难度：
129条回答
610收藏
5260浏览
通过挑战的用户
-
2022-11-20 08:54:48
-
2022-11-04 11:24:48
-
2022-09-16 23:46:21 -
2022-09-16 20:15:57
-
2022-09-16 15:55:16
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
