八皇后

缘起

邓俊辉数据结构和算法(C++ 语言版)第四章的例子

需求是找出8*8国际象棋棋盘上放置8个皇后，这8个皇后之间彼此无法互相攻讦的摆法.

分析

递归版本和栈版本. 这是显然的, 因为递归和栈是相通的. 解决问题的想法都是逐列摆放皇后, 可以就继续, 不行就回溯.

递归版本(从啊哈算法上找的, 非常实用的模式, 可以作为回溯找解的模板了)

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
56
57
58
59
60
61
62
63
64
65
66
#include "stdafx.h"
#include <iostream>
#include <cmath>

using namespace std;

//这里考虑八皇后问题, 这里的策略是逐列放置皇后. 每次试探的是行

#define N 8

int row[N+1]; // row[i]=j 表示第i列的皇后放在第j行 i>=1
int book[N+1]; // book[i]=0 表示第i行没有放置皇后, book[i]=1 表示第i行有放置皇后, 因为如果已经在第i行放置皇后的话, 后面的列是不能在第i行放置皇后的 所以这里相当于是标记
int count; // 八皇后解的个数

// 将第col列的皇后放在第r行可不可以
bool isok(int col, int r)
{
	for (int i = 1; i< col; i++)
	{
		if (row[i]==r || abs(row[i]-r)==abs(i-col))
		{
			return false;
		}
	}
	return true;
}

// 放置N皇后的方法 col 是当前准备在第几列放置皇后
void gao(int col) {
	// 如果已经准备放置第9列的皇后了, 则算法已经结束了, 我们已经得到了一个八皇后的解
	if (col == N+1)
	{
		printf("第%d个解如下:\n", count++);
		for (int i = 1; i<= N; i++)
		{
			printf("第%d列的皇后放置在第%d行\n", i, row[i]);
		}
		cout<<endl;
		// 递归出口
		return;
	}
	// 考虑col列的皇后的放置方法
	for (int i = 1; i<=N; i++)
	{
		// 如果第i行没被占用 并且可以放置在 第col列的第i 行
		if (!book[i]&&isok(col,i))
		{
			// 锁定
			book[i]=1;
			// 将第col列的皇后放在第i行
			row[col] = i;
			// 递归
			gao(col+1);
			// 解锁不占用
			book[i]=0;
		}
	}

}


int main() {
	gao(1);
	cout<<"八皇后一共"<<count<<"个解"<<endl;
	return 0;
}

栈版本

在贴代码之前, 我们必须要讲一件很重要的事情，就是如何将递归转换为栈（递归版本容易写，因为递归嘛~ 甩手掌柜尔）. 对于递归, 遵从的程序模型是

while(condition) {

​ 出口

​ 状态转移

}

而对于栈版本而言, 回溯就是递归的出口. 什么情况下要回溯呢? 两种情况

  1. 到达了出口，就本例而言, 就是找到了一组解
  2. 状态转移失败, 即无法进行状态转移, 就本例而言, 就是皇后放在哪里都不行.
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>

//#define LOCAL
#define N 8

using namespace std;

int book[N]; // book[i]=1 表示第i行(i>=0) 已经放置了皇后, 则后续就不能继续放置皇后了, 反之为0
int row[N]; // row[j]=i 表示第j列(j>=0)的皇后放在第i行
int n; // 八皇后问题的解的个数

// 皇后结构体
struct Queen {
	// 皇后位于的行与列, z是状态, 即从它出发, 选择到了第几行, 其中 这个z 是递归转栈的关键, 因为只有记录了当前栈顶往后的抉择 回溯(即模拟栈回退)之后才能做出不一样的选择.
	int x,y,z;
	Queen(int x=0,int y=0, int z = 0):x(x),y(y),z(z){};
};

// 是否可以将皇后放在第c列, 第r行
bool isok(int c, int r)
{
	if (book[r]) // 如果第r行已经放了, 则显然不能在(r,c)放置皇后了
	{
		return false;
	}
	for (int i = 0; i< c; i++) // 考察前面c列, 是否可以放置皇后在(r,c)
	{
		if (abs(r-row[i]) == abs(c-i))
		{
			return false;
		}
	}
	return true;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	stack<Queen> solu;
	for (int k = 0; k < N; k++) // 第0列的皇后放在第k行
	{
		memset(book, 0, N*sizeof(int));
		memset(row, 0, N*sizeof(int));
		book[k] = 1; // 第k行已经被占据了
		row[0] = k; // 第0列的皇后放在第1行.
		solu.push(Queen(1, 0)); // 初始栈中状态,或者说递归的出发点
		while(!solu.empty()) { // 如果栈空了, 则表明已经考察完了 (0,N-1)
			if (solu.size() == N) // 如果已经找到一组解了
			{
				n++;
				cout<<"找到了一组解:" <<endl;
				for (int i = 0; i< N; i++)
				{
					printf("(%d, %d)",i+1, row[i]+1); // 第i+1行第row[i]+1列放置了皇后
				}
				book[solu.top().x] = 0; // 回溯
				solu.pop();
			} 
			else // 状态演化
			{
				Queen& q = solu.top(); // 当前已经决定到了 q.y列的皇后的放法. 下面要决定q.y+1列皇后的放法, 即放在第几行, 注意, 这里必须要使用引用, 而不能直接赋值给一个Queen,因为java和c/c++ 不同, java没有指针的概念, 只会引用传递. 而不会值传递, 而这里如果只写Queen而不是 Queen&的话, 就是值传递, 相当于拷贝了一份Queen, 则下面q.z就影响不到原本的栈顶元素了.
				int i = q.z;
				for (; i<N;i++) // 考察各种放法
				{
					if (isok(q.y+1, i)) // 如果可以放置在第 q.y+1列,第i行的话
					{
						solu.push(Queen(i, q.y+1)); // 放置
						book[i] = 1; // 锁定
						row[q.y+1] = i;
						q.z = i+1; // 更新当前栈顶的考察状态, 下次回溯回来的时候, 就从i+1开始了(因为状态i已经考察完毕了)
						break; // 这里必须要break, 因为这次的压栈已经完成, 换言之就是本次递归已经完成
					}
				}
				if (i == N) // 如果所有状态都考察完了, 则进行回溯
				{
					book[solu.top().x] = 0; // 栈顶元素的这个状态已经完毕, 回溯
					solu.pop();
				}
			}
		}
	}
	cout << "一共" << n << "个解" << endl;
	return 0;
}

我上面的栈版本的算法优于书上的. 书上的比较反人类.

ps: N一旦大起来, 时间复杂度就比较反人类了. 此时就要使用D· Knuth 巨巨的 舞蹈链算法.