/*
 改进后的八皇后解法
 效率高了很多
 */
#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;
}