首页 > 代码库 > N皇后问题 --搜索
N皇后问题 --搜索
题目描述
检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
//以下的话来自usaco官方，不代表洛谷观点
特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号删除并且不能参加USACO的任何竞赛。我警告过你了！
输入输出格式
输入格式：
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
输出格式：
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
输入输出样例
输入样例#1：
6
输出样例#1：
2 4 6 1 3 53 6 2 5 1 44 1 5 2 6 34
说明
题目翻译来自NOCOW。
USACO Training Section 1.5
/* 纯搜索 就是记录一下路径先搜到的路径一定字典序最小 因为我们是从 1 开始搜的 */#include<cmath>#include<cstdio>#include<iostream>#include<algorithm>#define MAXN 30using namespace std;int a[MAXN],n,ans;bool li[MAXN],dui[MAXN],dui2[MAXN];inline void read(int &x) { int f=1;x=0;char c=getchar(); while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();} x=x*f;}inline void print() { ans++; if(ans<=3) { for(int i=1;i<=n;i++) printf("%d ",a[i]); printf("\n"); } return;}inline void dfs(int i) { for(int j=1;j<=n;j++) { if(!li[j] && !dui[i+j] && !dui2[i-j+n-1]) { a[i]=j; li[j]=true; dui[i+j]=true; dui2[i-j+n-1]=true; if(i==n) print(); else dfs(i+1); li[j]=false; dui[i+j]=false; dui2[i-j+n-1]=false; } } return;}int main() { read(n); dfs(1); printf("%d\n",ans); return 0;}
变式
在N*N(N<=10)的棋盘上放N个皇后，使得她们不能相互攻击。两个皇后能相互攻击当且仅当它们在同一行，或者同一列，或者同一条对角线上。
找出一共有多少种放置方法。
找出一共有多少种放置方法。
搜索！
当然，也可以打表。
最普通的搜索 1s内 可以跑n<=13
代码：
1 #include<cstdio> 2 #include<iostream> 3 #define MAXN 100 4 5 using namespace std; 6 7 int n,ans; 8 9 int li[MAXN],dui[MAXN],dui2[MAXN];10 11 inline void read(int &x) {12 int f=1;x=0;char c=getchar();13 while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();}14 while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();}15 x=x*f;16 }17 18 inline void dfs(int i) {19 for(int j=1;j<=n;j++) {20 if(!li[j] && !dui[i+j] && !dui2[i-j+n-1]) {21 li[j]=true;22 dui[i+j]=true;23 dui2[i-j+n-1]=true;24 if(i==n) ans++;25 else dfs(i+1);26 li[j]=false;27 dui[i+j]=false;28 dui2[i-j+n-1]=false;29 }30 }31 return;32 }33 34 int main() {35 read(n);36 dfs(1);37 printf("%d\n",ans);38 return 0;39 }
还有可以用链表优化
1 /* 2 链表实现 3 这个链表1s内也就跑到13 4 但是效率明显比纯搜索要高 5 搜索15能跑20s左右 链表只要5s左右 6 */ 7 #include<cstdio> 8 #include<iostream> 9 #define MAXN 20010 11 using namespace std;12 13 int n,ans;14 15 int l[MAXN],r[MAXN];16 17 bool p[MAXN],q[MAXN];18 19 inline void dfs(int u) {20 if(u>n) {21 ans++;22 return;23 } 24 for(int i=r[0];i<=n;i=r[i]) {25 if(p[i+u]||q[i-u+n-1]) continue;26 r[l[i]]=r[i];27 l[r[i]]=l[i];28 p[i+u]=true;29 q[i-u+n-1]=true;30 dfs(u+1);31 p[i+u]=false;32 q[i-u+n-1]=false;33 r[l[i]]=i;34 l[r[i]]=i;35 }36 }37 38 39 40 int main() {41 scanf("%d",&n);42 for(int i=1;i<=n;i++) l[i]=i-1,r[i]=i+1; //r[i]代表 i点右边的点的编号 l[i] 代表i点左边的编号43 r[0]=1;l[n+1]=n;44 dfs(1);45 printf("%d\n",ans);46 return 0;47 }
N皇后问题 --搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。