输入你的邮件地址，
你将不会错过任何关于：
[ C/C++教程
]的信息 |
|
八皇后问题的非递归实现
发表日期：2008-3-8 
| 
|
我们都知道八皇后问题是一个很经典的问题，当时很多解决八皇后问题的编程解法都是用递归解法，下面我用非递归的解法来实现如下：
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
其中有关设置标志位来表示该位是否可以下皇后的原理，请看郑启华的《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
|
|
上一篇：利用C语言小程序来解决大问题
人气:372
下一篇：探索C++的秘密之详解extern “C”
人气:185 |
浏览全部C/C++的内容
Dreamweaver插件下载
常用网页广告代码全集
|
|
