#include <stdio.h>
#include <math.h>
#include <stack>
using namespace std;
/*八皇后问题是在8*8的棋盘上放置8枚皇后，使得棋盘中每个横向、纵向、左上至右下斜向、右上至左下斜向均只有一枚皇后*/

const int N = 8; //棋盘行数
int a[N] = {0}; //表示棋盘，若a[2]=2,则表示在第3行第2列放一个皇后，因为同一行不能放两个皇后，所以只需要1维数组就可以表示一个棋盘。

int solution = 0;//解的个数

struct Node
{
	int row;
	int col;
};

//row行，col列, 是否可以摆皇后
bool IsOK(Node node)
{
	for (int i = 0; i < node.row; i++)
	{
		if (a[i] == node.col || (abs(a[i] - node.col) == node.row - i))
		{
			return false;
		}
	}
	return true;
}

//打印出所有解
void Print()
{
	printf("第%d种解：\n", ++solution);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (a[i] == j)
			{
				printf("%d", i);
			}
			else
			{
				printf("#");
			}
		}
		printf("\n");
	}

	printf("-----------------\n");
}

void DSF()
{
	Node node;
	stack<Node> stack;

	node.row = 0;
	node.col = 0;
	stack.push(node);
	while(stack.size() >= 1)
	{
		//--find
		node = stack.top();
		while (node.col < N && !IsOK(node))
		{
			node.col++;
		}

		if (node.col < N)
		{
			//--forward
			if (node.row < N-1)
			{
				//把ok的节点放到当前层
				a[node.row] = node.col;
				stack.pop();
				stack.push(node);
				
				//进入下一层的第一个节点
				node.row++;
				node.col = 0;
				stack.push(node);
			}
			else
			{
				//--done
				a[node.row] = node.col;
				Print();
				
				//进入当前层的下一个结点
				//node = stack.top();
				node.col++;
				stack.pop();
				stack.push(node);
			}
		}
		else
		{
			//--back
			stack.pop();
			
			if (stack.size() == 0)
			{
				return;
			}
			node = stack.top();
			node.col++;
			stack.pop();
			stack.push(node);

		}

	}

}

int main()
{
	DSF();
	return 0;
}