【火山数据结构与算法】递归-八皇后问题(回溯算法)

林峰

八皇后问题是一个古老而又著名的问题，是学习回溯算法的一个经典案例。今天我们就一起来探究一下吧！

时间退回到1848年，国际西洋棋棋手马克斯·贝瑟尔提出了这样的一个问题，

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。

后面陆续有不同的学者提出自己的见解。大数学家高斯认为一共有76种摆法，1854年在柏林的象棋杂志上不同的作者发表了共计40种不同的见解，后来还有人利用图论的方法得出共有92种摆法。

现在我们就使用程序的方式来给大家进行解答

八皇后算法思路分析:

1) 第一个皇后先放第一行第一列
2) 第二个皇后放在第二行第一列,然后判断是否符合规则,如果不符合,继续放在第二列、第三列、依次把所有列都放完,直到找到一个合适的
3) 继续第三个皇后,还是第一列、第二列.......直到第8个皇后也能放到一个不冲突的位置,就找到了一个正确解
4) 当得到一个正确的解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后放到第一列的所有正确解全部得到.（重要）
5)然后回头继续将第一个皇后放在第一行第二列,后面继续循环执行 1,2,3步骤

这种思路就是回溯思想，先从某一条路开始走，一条路走到黑，出现死胡同了，就回到上一个路口（回溯），从另一个方向再次出发，又出现死胡同了，就再返回刚刚的路口，直到将该路口的所有岔道走遍了，如果还是走不通，就继续向前回溯，回到上上个路口，直到找到出路为止。

代码实现:
八皇后问题.rar (113.07 KB, 下载次数: 19)

2021-8-11 18:06 上传

点击文件名下载附件

八皇后在线游戏

伟业

学习

阿丘

谢谢分享！