MyException - 我的异常网
当前位置:我的异常网» 编程 » 一种便于理解的8皇后有关问题的回溯解法

一种便于理解的8皇后有关问题的回溯解法

www.myexceptions.net  网友分享于:2013-04-10  浏览:0次
一种便于理解的8皇后问题的回溯解法
/*
8皇后问题的C++算法
author: alaclp@163.com
published date: 2013-4-8
问题:若是16皇后问题?
皇后数 解个数
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
*/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <stdlib.h>

using namespace std;

//位置数据类型
typedef struct pos {
	int row;
	int col;
	pos(int x, int y): row(x), col(y) {};
	pos() : row(-1), col(-1) {};
} pos;

#define nrow 8
#define ncol 8

vector<pos> rst;        //存放皇后位置的向量
int resultCount = 0;    //存放排放可能数量

int vals[nrow][ncol] = {0}; //初始化所有元素值为0

//调试时输出中间状态的值
void outputVals()
{
	cout << "-->" << endl;
	for(int i = 0; i < nrow; i++)
	{
		for(int j = 0; j < ncol; j++)
			printf("%2d ", vals[i][j]);
		cout << endl;
	}
	cout << endl;
}

//备份中间状态的值到bkvals中
void backup(int *bkvals)
{
	int cnt = 0;
	for(int i = 0; i < nrow; i++)
	{
		for(int j = 0; j < ncol; j++)
			bkvals[cnt++] = vals[i][j];
	}	
}

//从备份的bkvals中回复之前的搜索状态给vals
void restore(int *bkvals)
{
	int cnt = 0;
	for(int i = 0; i < nrow; i++)
	{
		for(int j = 0; j < ncol; j++)
			vals[i][j] = bkvals[cnt++];
	}	
}

//取得下一个可能的合理位置
pos getNextPos()
{
	pos p;
	for(int i = 0; i < nrow; i++)
		for(int j = 0; j < ncol; j++)
			if (vals[i][j] == 0)
			{
				p.row = i;
				p.col = j;
				return p;
			}
	return p;
}

//设置p位置的行、列、斜线元素值为-1
void setNot(pos p)
{
	//设置与p同行的元素值为-1
	for(int i = 0; i < nrow; i++)
		vals[i][p.col] = -1;
	//设置与p同列的元素值为-1
	for(int i = 0; i < nrow; i++)
		vals[p.row][i] = -1;	
	//设置与p在四个方向斜向的元素值为-1
	for(int i = 0; i < nrow; i++)
	{
		if ( (p.row - i >= 0 && p.row - i < nrow) && (p.col - i >= 0 && p.col - i < nrow) )
			vals[p.row-i][p.col-i] = -1;
		if ( (p.row - i >= 0 && p.row - i < nrow) && (p.col + i >= 0 && p.col + i < nrow) )
			vals[p.row-i][p.col+i] = -1;
		if ( (p.row + i >= 0 && p.row + i < nrow) && (p.col - i >= 0 && p.col - i < nrow) )
			vals[p.row+i][p.col-i] = -1;
		if ( (p.row + i >= 0 && p.row + i < nrow) && (p.col + i >= 0 && p.col + i < nrow) )
			vals[p.row+i][p.col+i] = -1;
	}
	//设置该位置的值为1,只是为了中间输出时便于查看
	vals[p.row][p.col] = 1;
}

//N皇后问题的递归解法
void queueN()
{
	pos p;
	//获取一个适合放皇后的位置
	p = getNextPos();
	//若无满足条件的位置
	if (p.row == -1)
	{
		//若已排放N个皇后,则计数并输出结果
		if (rst.size() == nrow)
		{
			int tvals[nrow][ncol] = {0};
			resultCount++;
			cout << "Result " << resultCount << " := " << endl;
			for(int i = 0; i < nrow; i++)
				tvals[rst[i].row][rst[i].col] = 2;
			for(int i = 0; i < nrow; i++)
			{
				for(int j = 0; j < nrow; j++)
					if (tvals[i][j] == 0)
						cout << ". ";
					else
						cout << "* ";
				cout << endl;
			}
			cout << endl;			
			return;
		}
		//无解
		else
		{
			//cout << "Not found" << endl;
			return;
		}
	}
	else
	{
		//存储p到结果中
		rst.push_back(p);
		//分配备份数据用内存空间
		int *bkvals = new int[nrow * ncol];
		//备份当前搜索状态
		backup(bkvals);
		//设置p点及其行、列、斜线点不可搜索
		setNot(p);
		//outputVals();
		//搜索后续皇后排放位置
		queueN();
		//若此次搜索完毕,则恢复搜索前的vals状态值
		restore(bkvals);
		//删除申请的内存
		delete []bkvals;
		//弹出上次压栈操作压入的元素
		rst.pop_back();
		//设置p点为已搜索点
		vals[p.row][p.col] = 1;	
		//搜索p后的点,看是否满足条件
		queueN();
	}
}

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

运行结果:

Result 1 :=
* . . . . . . .
. . . . * . . .
. . . . . . . *
. . . . . * . .
. . * . . . . .
. . . . . . * .
. * . . . . . .
. . . * . . . .

Result 2 :=
* . . . . . . .
. . . . . * . .
. . . . . . . *
. . * . . . . .
. . . . . . * .
. . . * . . . .
. * . . . . . .
. . . . * . . .

Result 3 :=
* . . . . . . .
. . . . . . * .
. . . * . . . .
. . . . . * . .
. . . . . . . *
. * . . . . . .
. . . . * . . .
. . * . . . . .

Result 4 :=
* . . . . . . .
. . . . . . * .
. . . . * . . .
. . . . . . . *
. * . . . . . .
. . . * . . . .
. . . . . * . .
. . * . . . . .

Result 5 :=
. * . . . . . .
. . . * . . . .
. . . . . * . .
. . . . . . . *
. . * . . . . .
* . . . . . . .
. . . . . . * .
. . . . * . . .

Result 6 :=
. * . . . . . .
. . . . * . . .
. . . . . . * .
* . . . . . . .
. . * . . . . .
. . . . . . . *
. . . . . * . .
. . . * . . . .

Result 7 :=
. * . . . . . .
. . . . * . . .
. . . . . . * .
. . . * . . . .
* . . . . . . .
. . . . . . . *
. . . . . * . .
. . * . . . . .

Result 8 :=
. * . . . . . .
. . . . . * . .
* . . . . . . .
. . . . . . * .
. . . * . . . .
. . . . . . . *
. . * . . . . .
. . . . * . . .

Result 9 :=
. * . . . . . .
. . . . . * . .
. . . . . . . *
. . * . . . . .
* . . . . . . .
. . . * . . . .
. . . . . . * .
. . . . * . . .

Result 10 :=
. * . . . . . .
. . . . . . * .
. . * . . . . .
. . . . . * . .
. . . . . . . *
. . . . * . . .
* . . . . . . .
. . . * . . . .

Result 11 :=
. * . . . . . .
. . . . . . * .
. . . . * . . .
. . . . . . . *
* . . . . . . .
. . . * . . . .
. . . . . * . .
. . * . . . . .

Result 12 :=
. * . . . . . .
. . . . . . . *
. . . . . * . .
* . . . . . . .
. . * . . . . .
. . . . * . . .
. . . . . . * .
. . . * . . . .

Result 13 :=
. . * . . . . .
* . . . . . . .
. . . . . . * .
. . . . * . . .
. . . . . . . *
. * . . . . . .
. . . * . . . .
. . . . . * . .

Result 14 :=
. . * . . . . .
. . . . * . . .
. * . . . . . .
. . . . . . . *
* . . . . . . .
. . . . . . * .
. . . * . . . .
. . . . . * . .

Result 15 :=
. . * . . . . .
. . . . * . . .
. * . . . . . .
. . . . . . . *
. . . . . * . .
. . . * . . . .
. . . . . . * .
* . . . . . . .

Result 16 :=
. . * . . . . .
. . . . * . . .
. . . . . . * .
* . . . . . . .
. . . * . . . .
. * . . . . . .
. . . . . . . *
. . . . . * . .

Result 17 :=
. . * . . . . .
. . . . * . . .
. . . . . . . *
. . . * . . . .
* . . . . . . .
. . . . . . * .
. * . . . . . .
. . . . . * . .

Result 18 :=
. . * . . . . .
. . . . . * . .
. * . . . . . .
. . . . * . . .
. . . . . . . *
* . . . . . . .
. . . . . . * .
. . . * . . . .

Result 19 :=
. . * . . . . .
. . . . . * . .
. * . . . . . .
. . . . . . * .
* . . . . . . .
. . . * . . . .
. . . . . . . *
. . . . * . . .

Result 20 :=
. . * . . . . .
. . . . . * . .
. * . . . . . .
. . . . . . * .
. . . . * . . .
* . . . . . . .
. . . . . . . *
. . . * . . . .

Result 21 :=
. . * . . . . .
. . . . . * . .
. . . * . . . .
* . . . . . . .
. . . . . . . *
. . . . * . . .
. . . . . . * .
. * . . . . . .

Result 22 :=
. . * . . . . .
. . . . . * . .
. . . * . . . .
. * . . . . . .
. . . . . . . *
. . . . * . . .
. . . . . . * .
* . . . . . . .

Result 23 :=
. . * . . . . .
. . . . . * . .
. . . . . . . *
* . . . . . . .
. . . * . . . .
. . . . . . * .
. . . . * . . .
. * . . . . . .

Result 24 :=
. . * . . . . .
. . . . . * . .
. . . . . . . *
* . . . . . . .
. . . . * . . .
. . . . . . * .
. * . . . . . .
. . . * . . . .

Result 25 :=
. . * . . . . .
. . . . . * . .
. . . . . . . *
. * . . . . . .
. . . * . . . .
* . . . . . . .
. . . . . . * .
. . . . * . . .

Result 26 :=
. . * . . . . .
. . . . . . * .
. * . . . . . .
. . . . . . . *
. . . . * . . .
* . . . . . . .
. . . * . . . .
. . . . . * . .

Result 27 :=
. . * . . . . .
. . . . . . * .
. * . . . . . .
. . . . . . . *
. . . . . * . .
. . . * . . . .
* . . . . . . .
. . . . * . . .

Result 28 :=
. . * . . . . .
. . . . . . . *
. . . * . . . .
. . . . . . * .
* . . . . . . .
. . . . . * . .
. * . . . . . .
. . . . * . . .

Result 29 :=
. . . * . . . .
* . . . . . . .
. . . . * . . .
. . . . . . . *
. * . . . . . .
. . . . . . * .
. . * . . . . .
. . . . . * . .

Result 30 :=
. . . * . . . .
* . . . . . . .
. . . . * . . .
. . . . . . . *
. . . . . * . .
. . * . . . . .
. . . . . . * .
. * . . . . . .

Result 31 :=
. . . * . . . .
. * . . . . . .
. . . . * . . .
. . . . . . . *
. . . . . * . .
* . . . . . . .
. . * . . . . .
. . . . . . * .

Result 32 :=
. . . * . . . .
. * . . . . . .
. . . . . . * .
. . * . . . . .
. . . . . * . .
. . . . . . . *
* . . . . . . .
. . . . * . . .

Result 33 :=
. . . * . . . .
. * . . . . . .
. . . . . . * .
. . * . . . . .
. . . . . * . .
. . . . . . . *
. . . . * . . .
* . . . . . . .

Result 34 :=
. . . * . . . .
. * . . . . . .
. . . . . . * .
. . . . * . . .
* . . . . . . .
. . . . . . . *
. . . . . * . .
. . * . . . . .

Result 35 :=
. . . * . . . .
. * . . . . . .
. . . . . . . *
. . . . * . . .
. . . . . . * .
* . . . . . . .
. . * . . . . .
. . . . . * . .

Result 36 :=
. . . * . . . .
. * . . . . . .
. . . . . . . *
. . . . . * . .
* . . . . . . .
. . * . . . . .
. . . . * . . .
. . . . . . * .

Result 37 :=
. . . * . . . .
. . . . . * . .
* . . . . . . .
. . . . * . . .
. * . . . . . .
. . . . . . . *
. . * . . . . .
. . . . . . * .

Result 38 :=
. . . * . . . .
. . . . . * . .
. . . . . . . *
. * . . . . . .
. . . . . . * .
* . . . . . . .
. . * . . . . .
. . . . * . . .

Result 39 :=
. . . * . . . .
. . . . . * . .
. . . . . . . *
. . * . . . . .
* . . . . . . .
. . . . . . * .
. . . . * . . .
. * . . . . . .

Result 40 :=
. . . * . . . .
. . . . . . * .
* . . . . . . .
. . . . . . . *
. . . . * . . .
. * . . . . . .
. . . . . * . .
. . * . . . . .

Result 41 :=
. . . * . . . .
. . . . . . * .
. . * . . . . .
. . . . . . . *
. * . . . . . .
. . . . * . . .
* . . . . . . .
. . . . . * . .

Result 42 :=
. . . * . . . .
. . . . . . * .
. . . . * . . .
. * . . . . . .
. . . . . * . .
* . . . . . . .
. . * . . . . .
. . . . . . . *

Result 43 :=
. . . * . . . .
. . . . . . * .
. . . . * . . .
. . * . . . . .
* . . . . . . .
. . . . . * . .
. . . . . . . *
. * . . . . . .

Result 44 :=
. . . * . . . .
. . . . . . . *
* . . . . . . .
. . * . . . . .
. . . . . * . .
. * . . . . . .
. . . . . . * .
. . . . * . . .

Result 45 :=
. . . * . . . .
. . . . . . . *
* . . . . . . .
. . . . * . . .
. . . . . . * .
. * . . . . . .
. . . . . * . .
. . * . . . . .

Result 46 :=
. . . * . . . .
. . . . . . . *
. . . . * . . .
. . * . . . . .
* . . . . . . .
. . . . . . * .
. * . . . . . .
. . . . . * . .

Result 47 :=
. . . . * . . .
* . . . . . . .
. . . * . . . .
. . . . . * . .
. . . . . . . *
. * . . . . . .
. . . . . . * .
. . * . . . . .

Result 48 :=
. . . . * . . .
* . . . . . . .
. . . . . . . *
. . . * . . . .
. * . . . . . .
. . . . . . * .
. . * . . . . .
. . . . . * . .

Result 49 :=
. . . . * . . .
* . . . . . . .
. . . . . . . *
. . . . . * . .
. . * . . . . .
. . . . . . * .
. * . . . . . .
. . . * . . . .

Result 50 :=
. . . . * . . .
. * . . . . . .
. . . * . . . .
. . . . . * . .
. . . . . . . *
. . * . . . . .
* . . . . . . .
. . . . . . * .

Result 51 :=
. . . . * . . .
. * . . . . . .
. . . * . . . .
. . . . . . * .
. . * . . . . .
. . . . . . . *
. . . . . * . .
* . . . . . . .

Result 52 :=
. . . . * . . .
. * . . . . . .
. . . . . * . .
* . . . . . . .
. . . . . . * .
. . . * . . . .
. . . . . . . *
. . * . . . . .

Result 53 :=
. . . . * . . .
. * . . . . . .
. . . . . . . *
* . . . . . . .
. . . * . . . .
. . . . . . * .
. . * . . . . .
. . . . . * . .

Result 54 :=
. . . . * . . .
. . * . . . . .
* . . . . . . .
. . . . . * . .
. . . . . . . *
. * . . . . . .
. . . * . . . .
. . . . . . * .

Result 55 :=
. . . . * . . .
. . * . . . . .
* . . . . . . .
. . . . . . * .
. * . . . . . .
. . . . . . . *
. . . . . * . .
. . . * . . . .

Result 56 :=
. . . . * . . .
. . * . . . . .
. . . . . . . *
. . . * . . . .
. . . . . . * .
* . . . . . . .
. . . . . * . .
. * . . . . . .

Result 57 :=
. . . . * . . .
. . . . . . * .
* . . . . . . .
. . * . . . . .
. . . . . . . *
. . . . . * . .
. . . * . . . .
. * . . . . . .

Result 58 :=
. . . . * . . .
. . . . . . * .
* . . . . . . .
. . . * . . . .
. * . . . . . .
. . . . . . . *
. . . . . * . .
. . * . . . . .

Result 59 :=
. . . . * . . .
. . . . . . * .
. * . . . . . .
. . . * . . . .
. . . . . . . *
* . . . . . . .
. . * . . . . .
. . . . . * . .

Result 60 :=
. . . . * . . .
. . . . . . * .
. * . . . . . .
. . . . . * . .
. . * . . . . .
* . . . . . . .
. . . * . . . .
. . . . . . . *

Result 61 :=
. . . . * . . .
. . . . . . * .
. * . . . . . .
. . . . . * . .
. . * . . . . .
* . . . . . . .
. . . . . . . *
. . . * . . . .

Result 62 :=
. . . . * . . .
. . . . . . * .
. . . * . . . .
* . . . . . . .
. . * . . . . .
. . . . . . . *
. . . . . * . .
. * . . . . . .

Result 63 :=
. . . . * . . .
. . . . . . . *
. . . * . . . .
* . . . . . . .
. . * . . . . .
. . . . . * . .
. * . . . . . .
. . . . . . * .

Result 64 :=
. . . . * . . .
. . . . . . . *
. . . * . . . .
* . . . . . . .
. . . . . . * .
. * . . . . . .
. . . . . * . .
. . * . . . . .

Result 65 :=
. . . . . * . .
* . . . . . . .
. . . . * . . .
. * . . . . . .
. . . . . . . *
. . * . . . . .
. . . . . . * .
. . . * . . . .

Result 66 :=
. . . . . * . .
. * . . . . . .
. . . . . . * .
* . . . . . . .
. . * . . . . .
. . . . * . . .
. . . . . . . *
. . . * . . . .

Result 67 :=
. . . . . * . .
. * . . . . . .
. . . . . . * .
* . . . . . . .
. . . * . . . .
. . . . . . . *
. . . . * . . .
. . * . . . . .

Result 68 :=
. . . . . * . .
. . * . . . . .
* . . . . . . .
. . . . . . * .
. . . . * . . .
. . . . . . . *
. * . . . . . .
. . . * . . . .

Result 69 :=
. . . . . * . .
. . * . . . . .
* . . . . . . .
. . . . . . . *
. . . * . . . .
. * . . . . . .
. . . . . . * .
. . . . * . . .

Result 70 :=
. . . . . * . .
. . * . . . . .
* . . . . . . .
. . . . . . . *
. . . . * . . .
. * . . . . . .
. . . * . . . .
. . . . . . * .

Result 71 :=
. . . . . * . .
. . * . . . . .
. . . . * . . .
. . . . . . * .
* . . . . . . .
. . . * . . . .
. * . . . . . .
. . . . . . . *

Result 72 :=
. . . . . * . .
. . * . . . . .
. . . . * . . .
. . . . . . . *
* . . . . . . .
. . . * . . . .
. * . . . . . .
. . . . . . * .

Result 73 :=
. . . . . * . .
. . * . . . . .
. . . . . . * .
. * . . . . . .
. . . * . . . .
. . . . . . . *
* . . . . . . .
. . . . * . . .

Result 74 :=
. . . . . * . .
. . * . . . . .
. . . . . . * .
. * . . . . . .
. . . . . . . *
. . . . * . . .
* . . . . . . .
. . . * . . . .

Result 75 :=
. . . . . * . .
. . * . . . . .
. . . . . . * .
. . . * . . . .
* . . . . . . .
. . . . . . . *
. * . . . . . .
. . . . * . . .

Result 76 :=
. . . . . * . .
. . . * . . . .
* . . . . . . .
. . . . * . . .
. . . . . . . *
. * . . . . . .
. . . . . . * .
. . * . . . . .

Result 77 :=
. . . . . * . .
. . . * . . . .
. * . . . . . .
. . . . . . . *
. . . . * . . .
. . . . . . * .
* . . . . . . .
. . * . . . . .

Result 78 :=
. . . . . * . .
. . . * . . . .
. . . . . . * .
* . . . . . . .
. . * . . . . .
. . . . * . . .
. * . . . . . .
. . . . . . . *

Result 79 :=
. . . . . * . .
. . . * . . . .
. . . . . . * .
* . . . . . . .
. . . . . . . *
. * . . . . . .
. . . . * . . .
. . * . . . . .

Result 80 :=
. . . . . * . .
. . . . . . . *
. * . . . . . .
. . . * . . . .
* . . . . . . .
. . . . . . * .
. . . . * . . .
. . * . . . . .

Result 81 :=
. . . . . . * .
* . . . . . . .
. . * . . . . .
. . . . . . . *
. . . . . * . .
. . . * . . . .
. * . . . . . .
. . . . * . . .

Result 82 :=
. . . . . . * .
. * . . . . . .
. . . * . . . .
* . . . . . . .
. . . . . . . *
. . . . * . . .
. . * . . . . .
. . . . . * . .

Result 83 :=
. . . . . . * .
. * . . . . . .
. . . . . * . .
. . * . . . . .
* . . . . . . .
. . . * . . . .
. . . . . . . *
. . . . * . . .

Result 84 :=
. . . . . . * .
. . * . . . . .
* . . . . . . .
. . . . . * . .
. . . . . . . *
. . . . * . . .
. * . . . . . .
. . . * . . . .

Result 85 :=
. . . . . . * .
. . * . . . . .
. . . . . . . *
. * . . . . . .
. . . . * . . .
* . . . . . . .
. . . . . * . .
. . . * . . . .

Result 86 :=
. . . . . . * .
. . . * . . . .
. * . . . . . .
. . . . * . . .
. . . . . . . *
* . . . . . . .
. . * . . . . .
. . . . . * . .

Result 87 :=
. . . . . . * .
. . . * . . . .
. * . . . . . .
. . . . . . . *
. . . . . * . .
* . . . . . . .
. . * . . . . .
. . . . * . . .

Result 88 :=
. . . . . . * .
. . . . * . . .
. . * . . . . .
* . . . . . . .
. . . . . * . .
. . . . . . . *
. * . . . . . .
. . . * . . . .

Result 89 :=
. . . . . . . *
. * . . . . . .
. . . * . . . .
* . . . . . . .
. . . . . . * .
. . . . * . . .
. . * . . . . .
. . . . . * . .

Result 90 :=
. . . . . . . *
. * . . . . . .
. . . . * . . .
. . * . . . . .
* . . . . . . .
. . . . . . * .
. . . * . . . .
. . . . . * . .

Result 91 :=
. . . . . . . *
. . * . . . . .
* . . . . . . .
. . . . . * . .
. * . . . . . .
. . . . * . . .
. . . . . . * .
. . . * . . . .

Result 92 :=
. . . . . . . *
. . . * . . . .
* . . . . . . .
. . * . . . . .
. . . . . * . .
. * . . . . . .
. . . . . . * .
. . . . * . . .


文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有