C++回溯算法Demo：以4皇后问题为例

回溯算法实际上是构造一棵推理树，并由树的叶子节点反向输出历史步骤；

其中，树的构建过程较为复杂；一种简化的方法是使用链表连接和构造各个节点的关系；

以4皇后问题为例，采用C++ vector容器——避免使用指针（当然换成了整数来代替指针表达对象的位置），解决了该问题。整体算法思路清晰，便于理解。

见代码；与书中不同，此代码实际输出的是所有4皇后问题的不同走法

//title：4皇后问题的回溯算法求解
//Demo: 1）回溯算法实现4皇后问题；2）难点：树形结构的表达；3）用线性容器表达树形结构，并实现树的扫描——降低了树实现的难度
//author: Liping Chen
//email: [email protected]
//published date: 20125-4-11
#include <iostream>
#include <string.h>
#include <vector>
#include <stdlib.h>

using namespace std;

//定义4皇后棋局的数据结构及方法
typedef struct Queen4 {
	int vals[16];
	int nQueens;
	int parent;

	//默认构造函数
	Queen4() { 
		for(int i = 0; i < 16; i++) 
			vals[i] = 0; 
		parent = 0;
		nQueens = 0;
	}

	//构造函数1
	Queen4(int nvals[16]) { 
		for(int i = 0; i < 16; i++) 
			vals[i] = nvals[i]; 
		parent = 0;
		nQueens = 0;
	}

	//找到当前布局中不为0的位置
	int getPosition() {
		for(int i = 0; i < 16; i++) 
			if (vals[i] == 0) {
				return i;
			}
		return -1;
	}

	//当设置皇后位置时，标记水平、垂直和斜线位置掩码
	void setQueen(int pos) {
		int row, col;
		vals[pos] = 1;
		nQueens++;
		row = pos / 4;
		col = pos % 4;
		for(int c = 1; c <= 3; c++) {
			//右下
			if (row + c < 4 && col + c < 4) 
				if (vals[(row + c) * 4 + (col + c)] == 0)
					vals[(row + c) * 4 + (col + c)] = 2;
			//左上
			if (row - c >= 0 && col - c >= 0) 
				if (vals[(row - c) * 4 + (col - c)] == 0)
					vals[(row - c) * 4 + (col - c)] = 2;
			//左下
			if (row + c < 4 && col - c >= 0) 
				if (vals[(row + c) * 4 + (col - c)] == 0)
					vals[(row + c) * 4 + (col - c)] = 2;
			//右上
			if (row - c >= 0 && col + c >= 0) 
				if (vals[(row - c) * 4 + (col + c)] == 0)
					vals[(row - c) * 4 + (col + c)] = 2;
			//右水平
			if (col + c < 4) 
				if (vals[row * 4 + (col + c)] == 0)
					vals[row * 4 + (col + c)] = 2;
			//左水平
			if (col - c >= 0) 
				if (vals[row * 4 + (col - c)] == 0)
					vals[row * 4 + (col - c)] = 2;
			//下
			if (row + c < 4) 
				if (vals[(row + c) * 4 + col] == 0)
					vals[(row + c) * 4 + col] = 2;
			//上
			if (row - c >= 0) 
				if (vals[(row - c) * 4 + col] == 0)
					vals[(row - c) * 4 + col] = 2;
		}
	}
	
	//输出当前棋局
	void output(int level) {
		int cnt = 0;
		char chars[100];
		for(int k = 0; k < level; k++)
			chars[k] = ' ';
		chars[level] = '\0';
		cout << chars << "Queen4=" << endl  << chars;
		for(int i = 0; i < 16; i++) {			
			cout << vals[i] << " ";
			cnt++;
			if (cnt % 4 == 0) cout << endl << chars;
		}
	}

	//递归调用输出历史棋局
	void outputHist(vector<Queen4>& tr) {
		if (parent)
			tr[parent].outputHist(tr);			
		output(0);
	}
	
	//由棋的当前布局产生下一布局
	void reproduce(vector<Queen4>& tr, int pos) {
		int nvals[16];
		bool inserted;
		//思考：为什么要使用nvals
		for(int i = 0; i < 16; i++)
			nvals[i] = vals[i];
		for(int i = 0; i < 16; i++) {
			if (nvals[i] == 0) {
				nvals[i] = 1;
				//新结果加入容器
				Queen4 q(tr[pos].vals);
				q.setQueen(i);
				q.parent = pos;
				tr.push_back(q);
			}
		}
	}
}Queen4;


//程序主函数
int main() {
	Queen4 q0;								//调用默认构造函数
	vector<Queen4> tr;						//向量容器——作用相当于队列，可以向期中添加新的棋盘布局
	int levels[1024] = {0};					//记录每层的孩子数量——用于分层
	
	tr.push_back(q0);						//将初始棋盘加入容器
	int oldn = 0, newn = 1, level = 0;      //存储变量
	//让根节点产生新孩子，并把新孩子加入容器
	//若不再产生新孩子了，则认为已找到答案
	//那么，最底层的就是答案（需要记录每层所产生的孩子数）
	while(newn != oldn) {
		//让最后的孩子再产生新孩子
		for(int i = oldn; i < newn; i++) tr[i].reproduce(tr, i);
		//更新老孩子和新孩子的数量
		oldn = newn;
		levels[++level] = newn;
		newn = tr.size();		
	}
	oldn = 1;
	//输出4皇后问题共有多少种解法
	for(int i = levels[level-1]; i < levels[level]; i++) {
		cout << "4皇后放置走法：" << oldn++ << endl;
		tr[i].outputHist(tr);
	}
	return 0;
}