WEB开发网
开发学院软件开发C++ 八皇后问题的非递归实现 阅读

八皇后问题的非递归实现

 2008-03-08 21:27:07 来源:WEB开发网   
核心提示:我们都知道八皇后问题是一个很经典的问题,当时很多解决八皇后问题的编程解法都是用递归解法,八皇后问题的非递归实现,下面我用非递归的解法来实现如下:

  我们都知道八皇后问题是一个很经典的问题,当时很多解决八皇后问题的编程解法都是用递归解法,下面我用非递归的解法来实现如下:

  其中有关设置标志位来表示该位是否可以下皇后的原理,请看郑启华的《pascal程序设计(第二版)>〉清华大学出版社出版的。代码如下:

#include

#define available 1 //用来标志该位是否可用,availabel表示可用,unailable表示不可


#define unavailable 0

#define true 1

#define false 0

int j,top=-1,flag,i,is_pop,total=0;
  // top用来保存栈顶指针,flag用来说明该次是否成功下了一个皇后
    //is_pop用来说明是否把栈弹出,total用来保存共有多少种下法
    //i用来保存下一次皇后应下的列

int stack[8],a[15],b[15],c[7];
   //stack保存皇后的位置,a,b,c三个数住用来保存该位是否可以下皇后

void init(void);//初始化各位状态,使之可以下皇后

void release (void);//当该列都不能下皇后,则解除上次下皇后试对相关位的锁定

main()

{

  cout<
  init();

  is_pop=false;//初始化

  for( ; ;)

  {

   do {

    for (j=is_pop? stack[i]+1:0;j<=7;j++)

     if (a[i+j]&&b[i-j+7]&&c[j])//判定该位是否可用
      {//若可用,则栈顶指针上移,在该位存入皇后号

      top++;

      stack[top]=j;

      a[i+j]=b[i-j+7]=c[j]=unavailable;//并把相关位设为不可用

      i++;//i指向下一个应填入皇后德列

      flag=true;//设标志,说明成功

      is_pop=false;

      break;//则直接退出循环

     }

    if (!flag)//若不成功,则释放被锁定的位

     release();

    flag=false;

    if (stack[0]+1==8&&top==-1)//若第一列也没有位置可以放皇后,

      goto END; //则说明没有其他的放法了,则退出

   }

   while (top!=7);

   for (int k=0;k<=7;k++)

    cout

Tags:皇后 问题 递归

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接