8皇后问题

国际象棋有8×8格,每个格子可放一个棋子。皇后的规则是可以横、竖、斜移动。在一个棋盘放置8个皇后,并使它们互相无法威胁到彼此。
答:以下是可执行C代码,采用非递归解法,你如果想了解皇后问题的算法的详细过程可看下面网址:
http://www.cnjcw.cn/infoview/2005031720203563221270.html
不过下面的代码是以列优先进行试探的,不是上面网址介绍的那样以行优先的,当然本质是一样的。

#include <iostream.h>
#define QUEEN 8  //皇后数量

int queen[QUEEN] ;  //下标代表所在列号,值代表所在行号,
          //queen[1]=2表示第1列第2行有个皇后
bool row_YN[QUEEN] ;      //棋局的每一行是否有棋,有则为1,无为0 ;
bool passive_YN[2*QUEEN-1] ;  //斜率为1的斜线方向上是否有棋,共有2*QUEEN-1个斜线

bool negative_YN[2*QUEEN-1] ; //斜率为负1的斜线方向上是否有棋
//用全局变量,因全局数组元素值自动为0
int main()

  int row = 0 ;//游标,当前移动的棋子(以列计
)
  bool flag = false ;   //当前棋子位置是否合法

  queen[0] = -1 ;      //0列棋子准备,因一开始移动的就是第0列棋子
  int count = 0 ;      //一共有多少种解法的计数器 ;

  while(row>=0 ) //跳出条件是回溯到无法回溯时
 
  {
    queen[row]++ ;      //row列上的皇后走到下一行试试

    if(queen[row] >= QUEEN) //当前列全部走完
    {  
      queen[row] = -1 ; //
当前列棋子置于准备状态
      row-- ;        //回溯到上一列的棋子
      if(row>=0)      //回溯时要清理如下行,斜线的标志位   
      {
        row_YN[queen[row]] = false ; 
        passive_YN[queen[row] + row] = false ;
        negative_YN[QUEEN-1 + row - queen[row]] = false ;
      } 
    }
    else
    { 
      //先判断棋子所在行没有棋子

      if(row_YN[queen[row]] == false) 
      {
        flag = true ; 
        //
以下检查当前棋子是否与之前的棋子斜线相交
        if( passive_YN[queen[row] + row] == true || negative_YN[QUEEN-1 + row - queen[row]] == true)  
          flag = false ;
        else     
          flag = true ;
        if(flag)  // flag
为真表示位置合法
        {  
          if(row == QUEEN-1)  //
列到达最后,即最后一个皇后也找到位置,输出解
          {
            count++ ;  //
解法的数目加一 ;
            cout<<"***"<<count<<"种解法
***"<<endl  ;
            for(int i=0;i<QUEEN;i++)
              cout<<""<<i<<"列皇后在第"<<queen[i]<<"
"<<endl;
          }
          row_YN[queen[row]] = true ;// 当前行设为有棋子

          passive_YN[queen[row] + row] = true ;//当前行正斜率方向有棋子
          negative_YN[QUEEN-1 + row - queen[row]] = true ; //当前行负斜率方向上也有棋子
          row++ ;
          if(row >= QUEEN) 
          {  // 
找到解后再次回溯找另外的解,这同上面无解回溯是一样的
            row-- ;
            row_YN[queen[row]] = false ; 
            passive_YN[queen[row] + row] = false ;
            negative_YN[QUEEN-1 + row - queen[row]] = false ;//
原理同回溯
          }      
          flag = false ;     
          }
      }
    }
  }
  cout<<QUEEN<<"
皇后问题一共有"<<count<<"种解法"<<endl  ;
  return 0 ;
}


 

原文地址:https://www.cnblogs.com/byfei/p/3112248.html