八皇后问题的三种方案及其程序设计.pdf

1994-2010 China Academic Journal Electronic Publishing House.All rights reserved.http:/收稿日期:20020405作者简介:彭学君(1972),男,河北阜城人,在职研究生,衡水师专计算机中心讲师,主要从事计算机科学与信息经济开发研究.第18卷第4期2002年12月德 州 学 院 学 报Journal of Dezhou UniversityVol.18 No.4Dec.2002八皇后问题的三种方案及其程序设计彭学君(衡水师专计算机中心,河北衡水 053000)摘 要:八皇后问题是各类语言程序设计中的较著名的题目.关于八皇后问题的编程解多种多样,涉及BASIC、C、PASCAL等,但多是就事论事,缺少相应的比较、分析、综合.文中以非递归算法、递归算法、动态图形实现三种方案分别讨论了八皇后问题及其相应程序设计的具体实现.关键词:八皇后问题;递归算法;程序设计中图分类号:TP311.11 文献标识码:A 文章编号:1004-9444(2002)04-0051-04 八皇后问题是各类语言程序设计中的较著名的题目.该问题由19世纪著名的数学家高斯在1850年提出:在88格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法.在计算机等级考试(二级或上二级以上)或是中学编程竞赛中,甚至成人的职称计算机考试,不时出现与之相关或相近的题目类型.而关于八皇后问题的编程解多种多样,涉及BASIC、C、PAS2CAL等,但多是就事论事,缺少相应的比较、分析、综合.为此,笔者以非递归算法、递归算法、动态图形实现三种方案分别讨论了八皇后问题及其相应程序设计的具体实现.1 一种递归的方法 回溯法求解在程序设计中有一种方法叫做”回溯法”.它不是按照某种公式或确定的法则,求问题的解,而是通过试探和纠正错误的策略,找到问题的解.在理论上来说,就是在一棵搜索树中从根结点出发,找到一条达到满足某条件的子结点的路径.在此例中皇后的位置有一个一维数组来存放A(I)=J表示皇后放在第I行,第J列.下面主要来看看怎么样判断皇后是否安全的问题.1)首先,用一维数组来表示,已经解决了不在同一行的问题.2)对于列可以引进一个标志数组CJ ,若J列上已放了皇后,则CJ =FALSE.3)对于左上右下的对角线I-J为一常量,位于-7,+7之间,在此引入标志数组L-7.7;对于左下右上的对角线,类似的有I+J等于常量,用数组R2.16来表示.当在第I行,第J列上放置了皇后,则只需设置:CJ :=FALSE;L I-J :=FLASE;R I+J :=FALSE就可以解决皇后的安全问题了.3338queens.pas333Program eightqueens;var cont,i:integer;q:boolean;a:array 1.8 of byte;c:array 1.8 ofboolean;l:array-7.7 of boolean;r:array2.16of boolean;procedure pr;var i:integer;begin 1994-2010 China Academic Journal Electronic Publishing House.All rights reserved.http:/for i:=1 to 8 do write(ai4);inc(cont);writeln(cont=,cont);end;procedure try(i:integer);var j:integer;procedure erase(i:integer);begincj:=true;li-j:=true;ri+j:=true;end;beginfor j:=1 to 8 dobeginif cj and li-j and ri+j thenbeginai:=j;cj:=false;li-j:=false;ri+j:=false;if i 8 then try(i+1)else pr;erase(i);end;end;end;333333333main33333333beginfor i:=1 to 8 do ci:=true;for i:=-7 to 7 do li:=true;for i:=2 to 16 do ri:true;cont:=0;i:=1;try(i);readln;end.用递归算法编制的程序具有结构清晰与可读性高的优点,同时也存在执行效率不高的缺点.当能够找到明显的递推公式用迭代法求解时,迭代法的效率会比递归方法高很多.2 一种非递归的算法该程序平台为C/C+语言,具体算法过程参阅程序实现中的相应注释部分.#include#include#define available 1/用来标志该位是否可用,availabel表示可用,unailable表示不可用#define unavailable 0#define true 1#define false 0int j,top=-1,flag,i,is-pop,total=0;/top用来保存栈顶指针,flag用来说明该次是否成功下了一个皇后/is-pop用来说明是否把栈弹出,total用来保存共有多少种下法/i用来保存下一次皇后应下的列int stack8,a15,b15,c7;/stack保存皇后的位置,a,b,c三个数住用来保存该位是否可以下皇后void init(void);/初始化各位状态,使之可以下皇后void release(void);/当该列都不能下皇后,则解除上次下皇后试对相关位的锁定main()cout init();is-pop=false;/初始化for(;)do for(j=is-pop?stacki+1:0;j =7;j+)if(a i+j&b i-j+7&cj)/判断该位是否可用/若可用,则栈顶指针上移,在该位存入皇后号top+;stacktop =j;ai+j =bi-j+7 =cj =un2available;/并把相关位设为不可用i+;/i指向下一个应填入皇后的列flag=true;/设标志,说明成功is-pop=false;break;/则直接退出循环if(!flag)/若不成功,则释放被锁定的位release();flag=false;if(stack0+1=8&top=-1)/若第一列也没有位置可以放皇后,goto END;/则说明没有其他的放法了,则退出while(top!=7);25 德州学院学报(自然科学版)第18卷 1994-2010 China Academic Journal Electronic Publishing House.All rights reserved.http:/for(int k=0;k =7;k+)cout 3 八皇后的动态实现3.1 回溯算法的实现1)我们把棋盘的横坐标定为i,纵坐标定为j,i和j的取值范围是从1到8.当某个皇后占了位置(i,j)时,在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了.用语句实现,可定义如下三个整型数组:a8,b15,c24.其中aj-1=1第j列上无皇后aj-1=0第j列上有皇后bi+j-2=1(i,j)的对角线(左上至右下)无皇后bi+j-2=0(i,j)的对角线(左上至右下)有皇后ci-j+7=1(i,j)的对角线(右上至左下)无皇后ci-j+7=0(i,j)的对角线(右上至左下)有皇后2)为第i个皇后选择位置的算法如下for(j=1;j =8;j+)/3 第i个皇后在第j行 3/if(i,j)位置为空)/3 即相应的三个数组的对应元素值为13/占用位置(i,j)/3 置相应的三个数组对应的元素值为03/if i 8为i+1个皇后选择合适的位置;else输出一个解3.2Turbo C程序清单如下#include#include#include#include char n3=0,0;/3 用于记录第几组解3/int a8,b15,c24,i;int h8=127,177,227,277,327,377,427,477;/3 每个皇后的行坐标 3/int l 8 =252,217,182,147,112,77,42,7;/3 每个皇后的列坐标 3/void3arrow;void try(int i)int j;for(j=1;j =8;j+)if(aj-1+bi+j-2+ci-j+7=3)/3 如果第i列第j行为空 3/aj-1=0;bi+j-2 =0;ci-j+7 =0;/3 占用第i列第j行 3/putimage(h i-1 ,l j-1 ,arrow,COPY-PUT);/3 显示皇后图形 3/delay(500);/3 延时 3/if(i 9)n0+;n1=0;bar(260,300,390,340);/3 显示第n组解3/outtextxy(275,300,n);delay(3000);aj-1=1;bi+j-2=1;ci-j+7=1;putimage(h i-1 ,l j-1 ,arrow,XOR-PUT);/3 消去皇后,继续寻找下一组解 3/delay(500);int main(void)int gdrive=DETECT,gmode,errorcode;unsigned int size;initgraph(&gdrive,&gmode,);errorcode=graphresult();if(errorcode!=grOk)printf(Graphics error n);exit(1);rectangle(50,5,100,40);rectangle(60,25,90,33);/3 画皇冠 3/line(60,28,90,28);line(60,25,55,15);line(55,15,68,25);line(68,25,68,10);line(68,10,75,25);line(75,25,82,10);line(82,10,82,25);line(82,25,95,15);line(95,15,90,25);size=imagesize(52,7,98,38);arrow=malloc(size);getimage(52,7,98,38,arrow);/3 把皇冠保35第4期 彭学君:八皇后问题的三种方案及其程序设计 1994-2010 China Academic Journal Electronic Publishing House.All rights reserved.http:/存到缓冲区 3/clearviewport();settextstyle(TRIPLEX-FONT,HORIZ-DIR,4);setusercharsize(3,1,1,1);setfillstyle(1,4);for(i=0;i =7;i+)ai=1;for(i=0;i =14;i+)bi=1;for(i=0;i =23;i+)ci=1;for(i=0;i =8;i+)line(125,i335+5,525,i335+5);/3 画棋盘 3/for(i=0;i =8;i+)line(125+i350,5,125+i350,285);try(1);/3 调用递归函数 3/delay(3000);closegraph();free(arrow);参考文献:1 谭浩强,C程序设计 M.北京:清华大学出版社,1998.Three projects and their program designs of eight queens chess problemPENG Xue-jun(Computer center hengshui teachers College,Hengshui Hebei 053000,China)Abstract:Eight queens chess problem is a famous theme in all kinds program design langue.There are manyprogram explains in BASIC,C and PASCAL langue.But they consider it as its stands and are lack of com2pare,analysis and integration.In this paper,there are some discussions about eight queens with no-recur2sive algorithm,recursive algorithm and dynamic graphics implement algorithm.In the meaning time,thereare their program designs about them,too.Key words:eight queens chess problem;recursive algorithm;program design45 德州学院学报(自然科学版)第18卷