皇后问题2.cpp

皇后问题解法任意皇后可解

#include<iostream.h>
# include<malloc.h>

char e; 
int n  ; //15皇后问题.改动n可变成N皇后问题
 int n_sub ;
int *queen ;  //N个棋子.N对应每一列,如n=0的棋子只下在0列,1下1....类推
bool *row ;    //棋局的每一行是否有棋,有则为1,无为0 ;
bool *passive ;  //斜率为1的斜线方向上是不是有皇后
bool *negative ; //斜率为负1的斜线方向上是不是有皇后.
//之所以用全局变量,因全局数组元素值自动为0

void main()
{ 

	while(1)
	{
		do
		{
		cout<<"请输入皇后的个数："<<endl;
	cin>>n;
		}while(n<=0);
	//n=8;
	n_sub=n-1;
	int**qipan;
	qipan=(int**)malloc(n*sizeof(int*));
	for(int j=0;j<n;j++)
		qipan[j]=new int[n];
	for(j=0;j<n;j++)
	{
		for(int i=0;i<n;i++)
			qipan[j][i]=0;
	}
	queen=new int[n];
	row=new bool[n];
	passive=new bool[2*n-1];
	negative=new bool[2*n-1];
	for(int i=0;i<n;i++)
		queen[i]=row[i]=0;
	for(i=0;i<(2*n-1);i++)
		passive[i]=negative[i]=0;
 int cur = 0 ;//游标,当前移动的棋子(哪一列的棋子)
 bool flag = false ; //当前棋子位置是否合法
 queen[0] = -1 ;  //第0列棋子准备,因一开始移动的就是第0列棋子
 int count = 0 ; //一共有多少种下法 ;
 cout<<"============================Starting============================="<<endl ;

 while(cur>=0)
 {  
  while(cur>=0 && queen[cur]<n && !flag) //当还不确定当前位置是否可下 
  {
   queen[cur]++ ;
//   cout<<"第"<<cur<<"列棋子开始走在第"<<queen[cur]<<"行"<<endl ;
//   cin.get() ;
   if(queen[cur] >= n) { //如果当前列已经下完(找不到合法位置)
//    cout<<"当前行是非法行,当前列棋子走完,没有合法位置,回溯上一列棋子"<<endl ;
//    cin.get() ;
    queen[cur] = -1 ; //当前列棋子置于准备状态
    cur-- ; //回溯到上一列的棋子
    if(cur>=0)  {
        row[queen[cur]] = false ; 
        passive[queen[cur] + cur] = false ;
           negative[n_sub + cur - queen[cur]] = false ;
    }
    //由于要移下一步,所以回溯棋子原位置所在行应该没有棋子啦.置row[]为false  
   //并且棋子对应的斜线的标志位passive[cur]和negative[cur]也应该要设为false ;     
   }
   else { 
    //先判断棋子所在行没有棋子
    if(row[queen[cur]] == false)  { //当前行没有棋子
//        cout<<"棋子"<<cur<<"所在行没有其他棋子,正在检查斜线"<<endl ;
        flag = true ; // 暂设为true,或与之前棋子斜交,则再设为false ;
     //以下检查当前棋子是否与之前的棋子斜线相交
     if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true)  {
      flag = false ;
//      cout<<"出现斜线相交,该位置不合法"<<endl ;
     }
     else     
      flag = true ;
     if(flag)  { //没有斜交,位置合法
//         cout<<"斜线也没有相交,该位置合法"<<endl ;
         if(cur == n-1)  //如果是最后一个棋子
		 {  
			 for(j=0;j<n;j++)
	{
		for(int i=0;i<n;i++)
			qipan[j][i]=0;
	}
			 for(int i=0;i<n;i++)
		 {
			 
		 qipan[i][queen[i]]=1;
		 }
			  cout<<"第"<<count+1<<"种方法为(1为皇后的位置,0位没有棋子)"<<endl;
		 cout<<endl;
		 for( i=0;i<n;i++)
		 {
			 for(int j=0;j<n;j++)
				 cout<<qipan[i][j]<<' ';
			 cout<<endl;
		 }
		 cout<<endl;
		
//          cout<<"棋子走完一轮,总走法加1"<<endl ;
          count++ ;  //总走法加一 ;
      }
         row[queen[cur]] = true ;// 当前行设为有棋子
      passive[queen[cur] + cur] = true ;//当前行正斜率方向有棋子
      negative[n_sub + cur - queen[cur]] = true ; //当前行负斜率方向上也有棋子
      cur++ ;
      if(cur >= n)  {
       cur-- ;
       row[queen[cur]] = false ; 
       passive[queen[cur] + cur] = false ;
             negative[n_sub + cur - queen[cur]] = false ;//原理同回溯
      }      
      flag = false ;     
     }
    }
   }//else
  }
 }
 cout<<n<<"皇后问题一共有"<<count<<"种解法"<<endl  ;
 cout<<"==============================end=========================================="<<endl;
 cout<<endl<<endl;

 cout<<"要继续吗(y/n)?";
 cin>>e;
 if(e!='y')
	 return;
 }
 
 

}