深度优先搜索——八皇后问题(洛谷 P1219)

题目选自 该题针对6—13皇后都行，只需改动输入的数字。

八皇后问题是经典的DFS问题，唯一需要注意的就是判断能够放置的条件，即满足什么状况是对的。 题目要求不能在同一行，同一列，或是对角线(注意哦 不只是主副2条对角线，与之平行的都算) 这里我们用一个一维数组ans[14]，来表示 第i个皇后，放置的位置为ans[i]，这样就已经保证不会在同一行了。 用一个book[14]数组来记录哪些列(即位置)已经被用过了，这样会使搜索或是回溯的时候，比直接每次从头开始判断效率高一点。 主要就是判断问题： 前面已经保证了不同行和列，那么对角线呢，这样需要用到简单数学的思想， 如果2个数是处于对角线的关系，那么他们的连线与水平线的夹角就是45°， 用类似求斜率的方法很容易理解，当 abs(a-i)==abs(index-ans[i]); （即，行差和列差相等，或是相比为1，tan45°=1） 这样就代表是处于对角线状态！ 剩下的就是套用深搜回溯模板了~~~

解题代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int a,ans[14],acount=0;
int book[14],djg=0;
bool check(int n,int index){  //表示放第 n 个皇后，在第 i 个位置可不可以
	for(int i=1;i<n;i++){
		if(ans[i] == index || abs(n-i)==abs(ans[i]-index)) return false;
	}
	return true;
}
void dfs(int n){
	if(n == a + 1 ){
		if(djg < 3){
		for(int i = 1;i<=a;i++){
		    if(i != 1) cout<<" ";
			cout<<ans[i];	
		}
		cout<<endl;
		}
		djg++;
		acount++;
		return;
	}
	for(int i=1;i<=a;i++){
		if(book[i]==0 && check(n,i)){
			book[i] = 1;
			ans[n] = i;
			dfs(n+1);
			book[i] = 0;
		}
	}
}
int main(){
	cin>>a;
	dfs(1);
	cout<<acount;
	return 0;
}