#include<iostream.h>
const int n = 8 ; //8皇后問題.改動(dòng)n可變成N皇后問題
const int n_sub = n - 1 ;
int queen[n] ;  //N個(gè)棋子.N對(duì)應(yīng)每一列,如n=0的棋子只下在0列,1下1....類推
bool row[n] ;    //棋局的每一行是否有棋,有則為1,無為0 ;
bool passive[2*n-1] ;  //斜率為1的斜線方向上是不是有皇后
bool negative[2*n-1] ; //斜率為負(fù)1的斜線方向上是不是有皇后.
//之所以用全局變量,因全局?jǐn)?shù)組元素值自動(dòng)為0
int main()
{ 
 int cur = 0 ;//游標(biāo),當(dāng)前移動(dòng)的棋子(哪一列的棋子)
 bool flag = false ; //當(dāng)前棋子位置是否合法
 queen[0] = -1 ;  //第0列棋子準(zhǔn)備,因一開始移動(dòng)的就是第0列棋子
 int count = 0 ; //一共有多少種下法 ;
 cout<<"============================Starting============================="<<endl ;
 while(cur>=0)
 {  
  while(cur>=0 && queen[cur]<n && !flag) //當(dāng)還不確定當(dāng)前位置是否可下 
  {
   queen[cur]++ ;
//   cout<<"第"<<cur<<"列棋子開始走在第"<<queen[cur]<<"行"<<endl ;
//   cin.get() ;
   if(queen[cur] >= n) { //如果當(dāng)前列已經(jīng)下完(找不到合法位置)
//    cout<<"當(dāng)前行是非法行,當(dāng)前列棋子走完,沒有合法位置,回溯上一列棋子"<<endl ;
//    cin.get() ;
    queen[cur] = -1 ; //當(dāng)前列棋子置于準(zhǔn)備狀態(tài)
    cur-- ; //回溯到上一列的棋子
    if(cur>=0)  {
        row[queen[cur]] = false ; 
        passive[queen[cur] + cur] = false ;
           negative[n_sub + cur - queen[cur]] = false ;
    }
    //由于要移下一步,所以回溯棋子原位置所在行應(yīng)該沒有棋子啦.置row[]為false  
   //并且棋子對(duì)應(yīng)的斜線的標(biāo)志位passive[cur]和negative[cur]也應(yīng)該要設(shè)為false ;     
   }
   else { 
    //先判斷棋子所在行沒有棋子
    if(row[queen[cur]] == false)  { //當(dāng)前行沒有棋子
//        cout<<"棋子"<<cur<<"所在行沒有其他棋子,正在檢查斜線"<<endl ;
        flag = true ; // 暫設(shè)為true,或與之前棋子斜交,則再設(shè)為false ;
     //以下檢查當(dāng)前棋子是否與之前的棋子斜線相交
     if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true)  {
      flag = false ;
//      cout<<"出現(xiàn)斜線相交,該位置不合法"<<endl ;
     }
     else     
      flag = true ;
     if(flag)  { //沒有斜交,位置合法
//         cout<<"斜線也沒有相交,該位置合法"<<endl ;
         if(cur == n-1)  //如果是最后一個(gè)棋子
      {
//          cout<<"棋子走完一輪,總走法加1"<<endl ;
          count++ ;  //總走法加一 ;
      }
         row[queen[cur]] = true ;// 當(dāng)前行設(shè)為有棋子
      passive[queen[cur] + cur] = true ;//當(dāng)前行正斜率方向有棋子
      negative[n_sub + cur - queen[cur]] = true ; //當(dāng)前行負(fù)斜率方向上也有棋子
      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  ;
 return 0 ;
}