backtrack.cpp

数据结构算法：回溯法编程寻找八皇后问题的所有解

//回溯法搜索皇后问题的所有解
//2007-01-25 13:20

#include <iostream>
using namespace std;
#define TRUE	1
#define FALSE	0

int X[9];		//解数组，0号单元不用

int ABS(int num)
{
	if(num < 0) num = -num;
	return num;
}

int PLACE(int k)//已知X[1,…k-1],检查第k个皇后是否可放在第X[k]列
{
	int i;
	i = 1;
	while(i < k)
	{	if((X[i] == X[k])||ABS(X[i] - X[k]) == ABS(i - k))//冲突检测
		
			return FALSE;		
		i++;
	}
	return TRUE;
}

void QUEENS()//回溯法得出问题所有解
{
	int k,i,count = 0;//count记录解的数目
	X[1] = 0;
	k = 1;
	cout<<"回溯法搜索皇后问题的所有解：//格式:(行标，列标)"<<endl;
	while(k > 0){
		X[k]++;
		while((X[k] <= 8)&&!PLACE(k)){
			X[k]++;
		}
		if(X[k] <= 8)
			if(k == 8){				
				for(i = 1; i <= 8;i++)
					cout<<"("<<i<<","<<X[i]<<") ";
				cout<<"\n";
				count++;
			}
			else
			{
				k++;X[k] = 0;
			}
		else k--;
	}
	cout<<"There are totally "<<count<<" groups of Solutions !\n";
}

void main(void)
{
	QUEENS();
	getchar();
}