nqueen.cpp

AI作业合集

#include<iostream.h>
const int n = 8 ; //8皇后问题.改动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的斜线方向上是不是有皇后.
//之所以用全局变量,因全局数组元素值自动为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) { //如果当前列已经下完(找不到合法位置)
//    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)  //如果是最后一个棋子
      {
//          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 ;
}