《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()递归调用自己，进一步调查正在考虑的放置情况。