#include<iostream.h>

const int n = 12 ; //15皇后問題.改動n可變成N皇后問題
const int n_sub = n - 1 ;
int queen[n] ;  //N個棋子.N對應每一列,如n=0的棋子只下在0列,1下1....類推
bool row[n] ;    //棋局的每一行是否有棋,有則為1,無為0 ;
bool passive[2*n-1] ;  //斜率為1的斜線方向上是不是有皇后
bool negative[2*n-1] ; //斜率為負1的斜線方向上是不是有皇后.
//之所以用全局變量,因全局數(shù)組元素值自動為0

int main()
{ 
 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) { //如果當前列已經(jīng)下完(找不到合法位置)
//    cout<<"當前行是非法行,當前列棋子走完,沒有合法位置,回溯上一列棋子"<<endl ;
//    cin.get() ;
    queen[cur] = -1 ; //當前列棋子置于準備狀態(tài)
    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<<"出現(xiàn)斜線相交,該位置不合法"<<endl ;
     }
     else     
      flag = true ;
     if(flag)  { //沒有斜交,位置合法
//         cout<<"斜線也沒有相交,該位置合法"<<endl ;
         if(cur == n-1)  //如果是最后一個棋子
      {
//          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  ;
 return 0 ;
}

//計算15皇后用時1分鐘15秒
//把n改成16,測16皇后用時大約8分鐘
//以上測試在Barton 2000+,KingstonDDR400 256M下測試

/*

斜線判斷如下:


正斜率對應數(shù)組passive[2*n-1] ;
0    1    2    3.... .  n
1    2    3    4.....   n+1
2    3    4    5....   .n+2
3    4    5    6.....   n+3
....................
n-1 n    n+1 n+2...2*n-1 
利用行和列的坐標相加,即可得到其對應斜線對應的passive[i].再看一下passive[i]是否為1即可知道該斜線上是否有其他棋子.

負斜率判斷如下
負余率對應數(shù)姐negative[2*n-1]
n-1 n    n+1 n+2...2*n-1 
..............................
3    4    5    6....    n+3
2    3    4    5....   .n+2
1    2    3    4.....   n+1
0    1    2    3.... .  n
用棋子所在位置的橫坐標(cur)減去縱坐標(queen[cur]),再加上n-1,即可得到對應的
negative[i]數(shù)組,若為1,則該行有棋子.
*/