回溯法之N皇后问题

//回溯法之N皇后问题
//1.问题描述：在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。
//2.设计思想与分析：
//基本思路：X(j)表示一个解的空间，j表示行数，里面的值表示可以放置在的列数，抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法，当可以放置皇后时就继续到下一行，不行的话就返回到第一行，重新检验要放的列数，如此反复，直到将所有解解出。 
#include "stdafx.h"
#include <iostream>
#include <math.h>
using namespace std;
/*检查可不可以放置一个新的皇后*/
bool place(int k, int *X)
{
	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 Nqueens(int n,int *X)
{
	int k;
	X[1]=0;k=1;
	while(k>0)
	{
		X[k]=X[k]+1;
		while((X[k]<=n)&&(!place(k, X)))
			X[k]=X[k]+1;
		if(X[k]<=n)
			if(k==n)
			{
				for(int i=1;i<=n;i++)
					cout<<X[i]<<" ";
				cout<<"\n";
			}
			else
			{
				k=k+1;
				X[k]=0;
			}
		else k=k-1;
	}
}
void main()
{
	cout<<"|--------------N皇后问题--------------|"<<endl;
	cout<<"|---power by zhanjiantao(028054115)---|"<<endl;
	cout<<"|-------------------------------------|"<<endl<<endl;
	int n;
	int *X;
	int i = 1;
	while(i)
	{
		cout<<"请输入皇后的个数:";
		cin>>n;
		X=new int[n];
		cout<<"问题的解有:"<<endl;
		Nqueens(n,X);
		cout<<"Press<1> to run again"<<endl;
		cout<<"Press<0> to exit"<<endl;
		cin>>i;
	}
}