八皇后 算法改进

/*
改进后的八皇后解法
效率高了很多
*/
#include<iostream>
#include<cmath>
using namespace std;
int queen[10];
bool legal(int depth,int n)//判断该位置(depth行n列)是否可放置一个皇后
{
	int i;
	for(i=1;i<depth;i++)
		if(n==queen[i]||((int)fabs((double)n-(double)queen[i])==depth-i))//判断对角线及列上是否有皇后
			return false;
	return true;
}
void print()//输出结果
{
	int i;
	for(i=1;i<=8;i++)
		cout<<queen[i];
	cout<<endl;
}
void DFS(int depth)
{
	if(depth>8) return;//八个都已经放置完毕返回
	int i;
	for(i=1;i<=8;i++)//扫描depth行上的每一列
	{
		if(legal(depth,i))//如果可以放置
		{
			queen[depth]=i;//标记
			DFS(depth+1);//放置下一个皇后
			if(depth==8)//放置完毕
				print();//输出
		}
	}
}
int main()
{
		freopen("output.txt","w",stdout);
	    DFS(1);//从第一行开始输出
		return 0;
}