C++八皇后问题
编写程序对八皇后问题进行求解:在8行8列的棋盘上放置8个皇后,使任一个皇后都不能吃掉其他的7个皇后(注:皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子),并将结果以某种方式显示出来。
例如,当求出下述的一个解时,可输出如下信息来表示该解(输出了表示摆放皇后的坐标位置以及“棋盘状态”— 棋盘中有皇后的位置放一个“Q”字符,其他位置为“+”字符)。
(1,1) (5,2) (8,3) (6,4) (3,5) (7,6) (2,7) (4,8)
Q + + + + + + +
+ + + + + + Q +
+ + + + Q + + +
+ + + + + + + Q
+ Q + + + + + +
+ + + Q + + + +
+ + + + + Q + +
+ + Q + + + + +
提示:
(1) 通过“int LineNum[9]; bool a[9], b[15], c[15];”说明具有全局作用域的4个数组。其中的:
LineNum[i]表示第i列的皇后要放的行位置(只用其中的列号1到8);
a[i]为true(i =1,2,…,8)表示第i行上尚未放皇后;
b[i]为true(i =0,1,2,…,14)表示第i条斜对角线上尚未放皇后(斜对角线指的是“”状对角线,该对角线上各点的行列号之和i+j为一个常数);
c[i]为true(i=0,1,2,…,14)表示第i条反斜对角线上尚未放皇后(反斜对角线指的是“\”状对角线,该对角线上各点的行列号之差i-j为一个常数)。
从而当使用语句“if ( a[j] && b[i+j-2] && c[i-j+7] ) LineNum[i]=j;”时,可用于判断并实现:如果在第j行的第i列上放置皇后安全的话,则将一枚皇后放置到那儿。
(2)编制一个具有如下原型的递归函数solve,它负责往第i列开始的连续8-i+1列上均放上皇后,若成功则通过引用参数ok返回true(否则返回false)。
void solve(int i, bool& ok);
摆放皇后之后,若i=8即已放满时则递归出口;否则通过solve(i+1,ok);进行递归调用。
(3)编制主函数,首先初始化一个“空棋盘”,即将a、b、c数组的各元素均置为true(表示当前棋盘的8个行、15条斜对角线以及15条反斜对角线上都尚未摆放皇后)。而后执行调用语句“solve(1, ok);”,它负责往第1列开始的连续8列上均放上皇后,若成功则通过引用参数ok返回true(否则返回false)。
点评:原文请找腾讯752018766辣,文-论'文.网http://www.751com.cn
(1)可改用非递归方法设计并编写solve函数,那样的话,通常要设置数组来记录皇后的摆放位置信息,还要记录这些皇后所产生的“影响面”(所建立的“势力范围”)— 使得哪些行列位置不可再摆放皇后。当在新的行列位置摆放了皇后、但此时又无法进一步摆放其他的皇后时,要回退(回溯)到上一个位置接着去考虑另外的“行走”方法(若还有的话)等等。但注意,“回退”一步后,要同时“撤销”由于该步的回退而关联的那些“影响面”(释放“势力范围”)。
(2)本程序只是找到了某一种“摆放方案”而终止,还可进一步考虑寻找其他各种不同的“摆放方案”(实际上共有92种)。
(3)也可用同样的方法去处理其他“阶数”的皇后问题,如求解四皇后问题等。
15.2概要设计:
本程设计思路: 问题等价于在n*n格的棋盘上放置n个皇后,任何2格皇后不放在同一行或同一列或同一斜线上,即当两个皇后的位置分别为(i,j)(k,l)时若有abs(k-j)==abs(x[j]-x[k])||(x[j]==x[k])则说明两皇后在同一线上,不能放。使用Backtrack递归函数实现对整个解空间的回溯搜索。
15.3 详细设计与编码:
见上传程序。
15.4 调试分析:
这题在研究怎么样让全部结果一个一个输出时是碰到了大问题,不知道怎么实现。最好也是没有想到好的办法,就是只能是若有输入数字时就能一个一个输出,若是输入非数字的时候就全部输出。
程序执行的结果:
15.5 用户使用说明:
按提示先输入是几个皇后的问题,然后若是要一个一个解的看就输入数字就行,若是想看全部,就直接输入非数字。
15.6 设计心得:
做这题实验的时候刚好正在学的算法设计与分析中有原本的代码,而且老师还做了详细的讲解。本来一开是看到这题就是有些生怯,没有去写。不过在老师的讲解之下总算是明白了到底是怎么一回事了。所以有老师带领确实是会比自己一个人摸索来得便捷,来得容易些。1837