nqueens.cpp

this is a file named juanji.m,which is used computing

/*filename<Nqueens.cpp>
由N^2个方块排成N行N列的正方形称为”N元棋盘”，
如果两个皇后位于N元棋盘上的同一或同一列或 同一对角线上，
则称他们为互相攻击。
要求输出使N元棋盘上的N个皇后互不攻击的所有布局。  
要求如下：  
1 N可由键盘输入  
2 在输入N后，动态建立方法说明中所需要建立的数组空间，
程序运行结束时释放该存储空间  
3 分别用N=4，5，6运行你的程序 


  建议本程序的测试数据适当小些
 */



#include<iostream>
#include<math.h>
using namespace std;
void queen(int n,int *q);
void queen(int n,int *q)
{

	for(int i=0;i<n;i++)
    {
        q[i]=0;                        /*开始时，所有行的皇后均在第 0 列，(每行只有一个皇后)*/
    } 

    i=0;                                 /*从第 0 行开始安排皇后*/
    while(i<n)
    {
        if(q[i]<n)                     /*当皇后列号 < n*/
        {
            int k=0;
                                         /*
                                           下行检查当前 (i 行) 皇后与 k=0 到 k=i-1 行皇后有没有攻击。如果检查了 k=i-1 行皇后都没有攻击，k=k+1=i
                                           (fabs(q[k]-q[i])-fabs(k-i)) 就是|q[k]-q[i]|-|k-i|，如果等于 0，第 k 行与第 i 行的皇后在某一对角线上。而如果 (q[k]-q[i]) = 0，它们在同一列上
                                           两个相乘不为 0 就是既不在对角线上也不在同一列上
                                         */
            while((k<i)&&((q[k]-q[i])*(abs(q[k]-q[i])-abs(k-i)))!=0) 
				k=k+1;
            if(k<i)                     /*如果当前皇后与前面的皇后有攻击*/
            {
                q[i]=q[i]+1;        /*当前皇后右移一个位置*/
            }
            else                        /*如果当前皇后与前面的皇后没有攻击*/
            { 
                if(i==n-1)            /*如果当前安排好的是最后一行皇后*/
                {
                    for(int j=0;j<n;j++)    /*输出互不攻击的布局*/
                        cout<<q[j]+1<<" "<<" "<<" ";
                    q[i]=q[i]+1;
                    cout<<endl;/*最后一行皇后右移一个位置，看还有没有互不攻击的布局*/
                }
                else                      /*如果当前安排好的不是最后一行皇后，考虑安排下一行皇后*/
                {
                    i=i+1;
                }
            }
        }
        else                              /*如果当皇后列号 = n，当前行安排不了*/
        {
            q[i]=0;                      /*将当前行皇后重新安排在第 0 列*/
            i=i-1;                         /*考虑重新安排上一行皇后*/
            if(i<0)                        /*如果已经回溯出顶，要完工了，释放内存空间，return*/
                {
                 return;
                }
            q[i]=q[i]+1;                 /*否则把上一行皇后右移一位*/
        }
    }

}
  

void main()
{
 cout<<"|---------------------N皇后问题--------------|"<<endl;
 cout<<"|--------------------------------------------|"<<endl;
 cout<<"|--------------------------------------------|"<<endl;
 cout<<"******q[i]表示第i行上皇后所在的列号:*********|"<<endl<<endl;
 int n=0;
 int *q=0;
 int i=0;
 char *str=0;
  while(!i)
  {
   cout<<"请输入皇后的个数:";
in:
   cin>>n;
   if(n<4)
   {
	   cout<<"符合条件的布局不存在"<<endl;
	   cout<<"n必须大于等于4的整数"<<endl;
	   cout<<"请重新输入n:"<<endl;
	   goto in;
   }
   else
   {
	   q=new int[n];
	   if(!q)
	   {
		   cout<<"allocation failure"<<endl;
		  
	   }
	   cout<<"问题的解有:"<<endl;
	   queen(n,q);
	   delete []q;
   }
   cout<<"Press<0> to run again"<<endl;
   cout<<"Press<1> to exit"<<endl;
   cin>>i;
  }
 
}