N皇后问题的回溯算法 ---- 一切为了速度

类别:软件工程 点击:0 评论:0 推荐:

 

#include<iostream.h>

const int n = 15 ; //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的斜线方向上是不是有皇后.
//之所以用全局变量,因全局数组元素值自动为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 ;
}

//计算15皇后用时1分钟15秒
//把n改成16,测16皇后用时大约8分钟
//以上测试在Barton 2000+,KingstonDDR400 256M下测试

/*

斜线判断如下:


正斜率对应数组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即可知道该斜线上是否有其他棋子.

负斜率判断如下
负余率对应数姐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]数组,若为1,则该行有棋子.
*/

本文地址:http://com.8s8s.com/it/it37191.htm