在8×8的国际象棋棋盘上放置8个皇后，要求任意两个皇后不能在同一行、同一列或同一条对角线上。要求用递归和非递归算法实现。打印所有...
4星 · 超过85%的资源 需积分: 47 141 浏览量
2008-10-29
19:14:24
上传
评论
收藏 55KB DOC 举报 
Queue 类
public:
Queue();~Queue();
int slash[15];
int bslash[15];
int col[8];
int (*weizhi)[8]
void q();
void que();
private:
int iLine,iColumn;
void qu(int i);
int destroy(int w);
int buju(int x1,int y1);
int out();
1．问题描述：八皇后问题求解
在 8×8 的国际象棋棋盘上放置 8 个皇后，要求任意两个皇后不能在同一
行、同一列或同一条对角线上。要求用递归和非递归算法实现。打印所有可
能情况。
2．数据结构设计：通过八皇后的原理，设计出递归和非递归的算法原理，结合
数据结构的内容分析，得出八皇后求解的程序编码
3．算法原理：<1>递归调用：数组 col、slash、bslash 分别用来标记冲突，col
数组代表列冲突，从 col[0]~col[7]代表第 0 列到第 7 列，如果某列上已经有皇后，
则为 1，否则为 0；
数组 slash 代表主对角线冲突，为 slash[i-j+7]，即从 slash[0]~slash[14]，如果某
条主对角线上已经有皇后，则为 1，否则为 0；
数组 bslash 代表从对角线冲突，为 bslash[i+j]，即从 bslash[0]~bslash[14]，如果
某条从对角线上已经有皇后，则为 1，否则为 0；
通过 qu()这个函数实现递归，如果满足这样一个条件：即
if(col[iColumn]==0&&slash[i-iColumn+7]==0&&bslash[i+iColumn]==0)，则表示
无冲突，可以在 weizhi 这个指针中放皇后，相对应的 col、slash、bslash 也应该
作标记，依次类推，得出八皇后问题的结果。
<2>非递归调用：首先设置一个 que()函数，定义 m,n,i,j 四个初值为
0 的整型变量，运用一个 for(n=0;n<N;n++)循环，满足(m==N-1 && i==1)，则调
用 buju()函数，如果满足(a1==x1||b1==y1) ，((a1-b1)==(x1-y1)) ，
((a1+b1)==(x1+y1))三个条件，用“1”表示放皇后的位置；其次，如果布局完成，
调用 out()函数输出结果；最后，如果不能够布局完成，则调用 destroy()函数，
撤消以前的布局,重新再来，即把以前标记为皇后的位置都归 0(0 表示没有放皇
后)。
4．算法求解过程：定义一个 Queue 类，把 q(),que()归为公有成员函数，
slash[15] ，bslash[15] ，col[8] ，(*weizhi)[8]归为公有数据成员，把 qu(int
i),destroy(int w) buju(int x1,int y1) ,out()归为私有成员函数。运用 q()布置 8*8 的
形状，然后调用 qu(int i)，形成递归方法；运用 que()布置 8*8 的形状，在满足
条件下，依次调用 destroy(int w) buju(int x1,int y1) ,out()三个函数，形成非递归
方法。示图如下：
评论1
最新资源