n-皇后问题
题目 n-皇后问题
思路分析
对于上题的改变其实就在于 每个位置都可以选择放与不放而不需要看该位置是不是棋盘 另外 现在额外要判断两个东西 就是正反对角线也不能放 对角线怎么判断是这题的关键 详细分析的话 见——n-皇后问题分析
x,y
(0,0) (0,1) (0,2) (0,3) (0,4)
(1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
(3,0) (3,1) (3,2) (3,3) (3,4)
(4,0) (4,1) (4,2) (4,3) (4,4)
x+y
(0) (1) (2) (3) (4)
(1) (2) (3) (4) (5)
(2) (3) (4) (5) (6)
(3) (4) (5) (6) (7)
(4) (5) (6) (7) (8)
每条从右上到左下的对角线 横纵坐标相加的值都是相等的
x-y+n
(5) (4) (3) (2) (1)
(6) (5) (4) (3) (2)
(7) (6) (5) (4) (3)
(8) (7) (6) (5) (4)
(9) (8) (7) (6) (5)
n-x+y
(5) (6) (7) (8) (9)
(4) (5) (6) (7) (8)
(3) (4) (5) (6) (7)
(2) (3) (4) (5) (6)
(1) (2) (3) (4) (5)
正对角线 x+y 反对角线： n-x+y或者x-y+n
那还是一样 先写从点入手的
再优化成从行入手的
代码实现
从点入手
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=10;
char g[N][N];
bool row[N],col[N],dg[N*2],udg[N*2];
int n;
void dfs(int x,int y,int cnt){
if(cnt>n) return;
if(y==n) y=0,x++;
if(x==n){
if(cnt==n){
for(int i=0;i<n;i++)
puts(g[i]);
puts("");
}
return;
}
//不放
g[x][y]='.';
dfs(x,y+1,cnt);
//放 满足横纵斜都没放过才行
if(!row[x] && !col[y] && !dg[x+y] && !udg[n-x+y]){
row[x]=col[y]=dg[x+y]=udg[n-x+y]=true;
g[x][y]='Q';
dfs(x,y+1,cnt+1);
g[x][y]='.';
row[x]=col[y]=dg[x+y]=udg[n-x+y]=false;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
dfs(0,0,0);
return 0;
}
从行入手
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=10;
char g[N][N];
bool col[N],dg[N*2],udg[N*2];
int n;
void dfs(int u/*,int cnt*/){
// if(cnt>n) return;//与下面同理 n一定是刚好满足的 所以剪枝失效 cnt也可以不传入
if(u==n){
//if(cnt==n){
for(int i=0;i<n;i++)
puts(g[i]);
puts("");
//}
return;
}
for(int i=0;i<n;i++){
//不放 由于n皇后是n*n放n个 所以每行必须有一个 现在不存在不放的情况
// g[u][i]='.';
// dfs(u+1,cnt);
//放 满足横纵斜都没放过才行
if(!col[i] && !dg[u+i] && !udg[n-u+i]){
col[i]=dg[u+i]=udg[n-u+i]=true;
g[u][i]='Q';
dfs(u+1/*,cnt+1*/);
g[u][i]='.';
col[i]=dg[u+i]=udg[n-u+i]=false;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]='.';
dfs(0/*,0*/);
return 0;
}
精简
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=10;
char g[N][N];
bool col[N],dg[2*N],udg[2*N];
int n;
void dfs(int u){
if(u>n-1){
for(int i=0;i<n;i++)
puts(g[i]);
puts("");
return;
}
for(int i=0;i<n;i++){
if(!col[i] && !dg[u+i] && !udg[n-u+i]){
col[i]=dg[u+i]=udg[n-u+i]=true;
g[u][i]='Q';
dfs(u+1);
g[u][i]='.';
col[i]=dg[u+i]=udg[n-u+i]=false;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]='.';
dfs(0);
return 0;
}
💬 评论