《C编程技巧:117个问题解决方案示例 》 —3.8 解决八皇后问题

网友投稿 612 2022-05-28

《C编程技巧:117个问题解决方案示例 》 —3.8 解决八皇后问题

3.8 解决八皇后问题

问题

你想利用回溯法来解决八皇后问题。

解决方案

回溯法是一种通用算法,用于查找计算问题的一些或所有可能的解决方案。在回溯中,首先考虑所有可能的候选者(可能成功),然后丢弃无法成功的候选者。最后,只剩下那些成功解决问题的候选人。在国际象棋棋盘上,八个皇后的排列方式使得没有皇后可以攻击另一个皇后。一个成功的解决方案要求没有两个皇后在相同的行、列或对角线上。编写一个C程序,依照以下规格说明使用递归来解决八皇后问题:

定义名为queen()的函数。两个int值将作为输入参数传递给此函数:棋盘上的行号和棋盘上的皇后数(在本例中为8)。

函数queen()以递归方式调用函数print()、函数place()以及函数queen()本身。

函数place()检查将皇后放置在棋盘上方格的可能性。如果一切正常,则返回1,否则,它返回0。

函数print()在屏幕上显示皇后的成功位置。

以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序,并将其保存在文件夹C:\Code中,文件名为queens.c:

编译并执行此程序。请注意,这个问题有92种成功的解决方案。执行开始时,屏幕上会显示解决方案1,如此处所示。按Enter键,然后屏幕上显示解决方案2。如果你对查看所有92种解决方案不感兴趣,只需按住Enter键并保持几秒钟即可。

这个程序的运行结果在这里给出:

工作原理

LOC 5~10定义main()函数。在LOC 7中,int变量p的值设置为8,因为棋盘上的皇后数是8。在LOC 8中,调用函数queen()。queen()的第一个参数是int值1,它表示第1行,queen()的第二个参数是int变量p,p的值设置为int值8(即棋盘上的皇后个数)。LOC 47~61定义了函数queen()。函数queen()调用函数place()来检查放置情况(正在考虑中)对于皇后是否安全。如果一切正常,则place()返回1,一旦找到了皇后的一种成功放置情况,那么函数queen()调用函数print()来在屏幕上显示成功的放置情况,如LOC 56所示。在LOC 58中,函数queen()递归调用自己,进一步调查正在考虑的放置情况。

c语言 C 语言

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:mongodb几种备份恢复方式比较
下一篇:Linux_LVM、RAID_RHEL7
相关文章