fourqueens.cpp

四后问题算法和克鲁卡斯尔算法的具体实现算法

#include <iostream.h>
#include <math.h>
bool place (int x[],int k);
void n_queens(int n,int * x);
void main ()
{
     int n;	 int x[50];
   cout<<"please enter the size of the queens:";
	cin>>n;cout<<endl;
    n_queens(n,x); 
	for ( int i=1;i<=n;i++)
	cout <<x[i]<<endl;
}
bool place (int x[],int k)
{
	int i;
	for (i=1;i<k;i++)
		if ((x[i]==x[k])||(abs(x[i]-x[k])==abs(i-k)))
			return false ;
	return true ;
}
void n_queens(int n ,int x[])
{
	int k=1;	x[1]=0;
	while (k>0){
		x[k]=x[k]+1;  /* 在当前列加1的位置开始搜索*/
    	while ((x[k]<=n)&&(!place(x,k))) /*当前列位置是否满足条件*/
	        x[k]=x[k]+1; /*不满足条件，继续搜索下一列位置*/  
		if (x[k]<=n) { /*存在满足条件的列?*/
			if(k==n) break;/* 是最后一个皇后，完成搜索*/
			else {
				k=k+1; x[k]=0;/*不是，则处理下一个皇后*/
			}
		}
		else{    /*已判断完n列，均没有满足条件*/
			x[k]=0;k=k-1; /*第k行复位为0，回溯到前一行*/
		}
	}
}