7-1 N皇后问题 (用栈模拟递归)_用栈求解n皇后问题

在N * N的方格棋盘上，放置N个皇后，要求每个皇后不同行，不同列，不同左右对角线。 其中N不超过10。 要求：输出所有的解。 算法提示：用栈求解皇后问题。
输入格式:

输入N
输出格式:

逐行输出每一种解，用每个皇后的位置坐标表示，每个位置坐标之后均有一个空格符，输出最后一行为空行。
输入样例:

在这里给出一组输入。例如：

6

输出样例:

在这里给出相应的输出。例如：

1: (1,2) (2,4) (3,6) (4,1) (5,3) (6,5)
2: (1,3) (2,6) (3,2) (4,5) (5,1) (6,4)
3: (1,4) (2,1) (3,5) (4,2) (5,6) (6,3)
4: (1,5) (2,3) (3,1) (4,6) (5,4) (6,2)

思路：按照题意要求用栈模拟，学习栈的用法，借鉴了刘汝佳老师的方法标记哪些对角线已经被标记了
每个主对角线上的每个点x, y坐标之差都一样
每个副对角线上的每一个点x, y坐标之差都一样 防止为负数x - y + n
但还是没有回溯法快速
在各种优化之下才堪堪通过25ms的时限（10皇后）
当然如果自己手动实现一个栈也可以一定程度上得到优化

#include<bits/stdc++.h>

using namespace std;
const int N = 11;
struct node
{
	int a[100]; //记录数据
	int len;// 记录已经选好了几列
	bool vis1[3][100];
    //vis[0][] 标记主对角线 vis[1][]标记副对角线 vis[2][]标记每一列
};
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);//使cout，cin和printf一样
	int n;
	cin >> n;
	stack<node> q;
	for(int i = 1; i <= n; i++) //在第一行开始选
	{
		node tmp;
		tmp.a[1] = i;
		tmp.len = 1;
		memset(tmp.vis1, 0, sizeof tmp.vis1);
		tmp.vis1[0][1 + i] = tmp.vis1[1][1 - i + n] = tmp.vis1[2][i] = 1;
		q.push(tmp);
	}
	int cnt = 1;
	while(!q.empty())
	{
		node tmp = q.top();
		q.pop();
		if(tmp.len == n) // 输出
		{
			cout << cnt ++ << ":";
			for(int i = 1; i <= n; i++) printf(" (%d,%d)", i, tmp.a[i]);
			cout << endl;
			continue;
		}
		int len = tmp.len + 1;
		for(int i = 1; i <= n; i++)
		{
			node tmp1 = tmp;
			if(!tmp1.vis1[2][i] && !tmp1.vis1[0][len + i] && !tmp1.vis1[1][len - i + n]) //如果不在同一列且不在同一对角线
			{
				tmp1.vis1[0][len + i] = tmp1.vis1[1][len - i + n] = tmp1.vis1[2][i] = 1; //标记列和对角线
				tmp1.len ++;
				tmp1.a[tmp1.len] = i;
				q.push(tmp1);
			}
		}
	}
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55