【搜索与回溯算法】N皇后问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【搜索与回溯算法】N皇后问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1236字，纯文字阅读大概需要2分钟。

内容图文

题目来源：【JZOJ】

题目描述

在一个$n*n$n?n的国际象棋棋盘上放置$n(n&lt;=12)$n(n<=12)个皇后，使它们不能互相攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。试求出第一种（皇后在第$i$i行最靠前的情况下，以后各行也尽量靠前）排列方案，和所有方法。

输入

输入一个数$n (n&lt;=12)$n(n<=12)

输出

输出所有的排列方案总数。

样例输入

4

样例输出

2

分析：这道题到手之后，可以看出来，这是属于一个图的搜索（似乎是在一本正经的胡说八道，哪里有图了！？）根据题意：“两个皇后不能在同一行、同一列或同一对角线上”，得出三个合法得走法分别是：$i、i+j、i-j+n$i、i+j、i?j+n，那现在只需要对每个方向做判断和标记即可。
Code：

#include<bits/stdc++.h>//懒得打头文件了，直接Van能头
using namespace std;
int n,total;
bool a[13],b[100],c[100];//三个bool类型得数组，用来做标记
void s(int i)//定义一个无返回值得函数
{
	for(register int j=1;j<=n;j++){
		if(!a[j]&&!b[i+j]&&!c[i-j+n]){//判断是否标记
			a[j]=true;
			b[i+j]=true;
			c[i-j+n]=true;//往三个方向依次搜索
			if(i==n) total++;//如果可行，答案增加
			else s(i+1);//不然的话，就进入下一层搜索
			a[j]=false;
			b[i+j]=false;
			c[i-j+n]=false;//回溯一步
		}
	}
}
int main()
{
	scanf("%d",&n);
	s(1);//从1开始搜索
	printf("%d\n",total);
	return 0;
}

嗯这篇blog就到这里了，楼下隐形字，欢迎扫一扫查看↓。。。

我这么蔡，不点赞，关个注鼓励一下再走吗？

内容总结

以上是互联网集市为您收集整理的【搜索与回溯算法】N皇后问题全部内容，希望文章能够帮你解决【搜索与回溯算法】N皇后问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---