经典回溯算法

#include <iostream>
#include"math.h"
using namespace std;
#define TRUE	1
#define FALSE	0

const int N=8;
int X[N+1];		//解数组，0号单元不用
int count = 0;

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

void print()                       //输出函数
{
	system("cls");
	
	cout<<endl<<"     "<<count<<endl;
	for(int i=1;i<=N;i++){
		cout<<"       ";
		for(int j=1;j<=N;j++)
			if(X[i]==j) cout<<" Q";
			else cout<<" *";
		cout<<endl;
	}
	cout<<endl;

	system("pause");
}

void QUEENS()//回溯法得出问题所有解
{
	int k;//count记录解的数目
	X[1] = 0;
	k = 1;
	while(k > 0){
		X[k]++;
		while((X[k] <= N)&&!PLACE(k)){
			X[k]++;
		}
		if(X[k] <= N)
			if(k == N){				
				count++;
				print();
			}
			else
			{
				k++;X[k] = 0;
			}
		else k--;
	}
}
void main(void)
{
	QUEENS();
}