前言

概念介绍

1. 八皇后问题起源

• 八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
• 问题描述：在8×8的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。
• 请问一共有多少种摆法？

原理讲解

• 由于篇幅限制，我们将八皇后问题简化为4皇后问题来讲解其原理（八皇后问题和4皇后问题的原理是一致的）

1. 第一步，我们从第一行开始，遍历第一行中所有的列，找到第一个适合放置皇后的位置。皇后位置用黑色背景表示。此时效果如下图所示

2. 由于任意两个皇后不得处在同一行、同一列或者同一对角斜线上。所以第1个皇后所在的行、列和对角线上的位置都是危险位置，不能再放置第2个皇后。危险位置我们用红色背景表示，安全位置我们用绿色背景表示。此时效果如下图所示

3. 第二步，我们从第二行开始，遍历第二行中所有的列，在安全位置范围内找到第一个适合放置皇后的位置。皇后位置用黑色背景表示。此时效果如下图所示

4. 由于任意两个皇后不得处在同一行、同一列或者同一对角斜线上。所以第2个皇后所在的行、列和对角线上的位置都是危险位置，不能再放置第3个皇后。危险位置我们用红色背景表示，安全位置我们用绿色背景表示。此时效果如下图所示

5. 第三步，我们从第三行开始，遍历第三行中所有的列，在安全位置范围内找到第一个适合放置皇后的位置。由于在第三行找不到放置皇后的位置，所以我们进行回退，重新放置第2个皇后的位置。此时效果如下图所示

6. 由于任意两个皇后不得处在同一行、同一列或者同一对角斜线上。所以第2个皇后所在的行、列和对角线上的位置都是危险位置，不能再放置第3个皇后。危险位置我们用红色背景表示，安全位置我们用绿色背景表示。此时效果如下图所示

7. 第四步，我们从第三行开始，遍历第三行中所有的列，在安全位置范围内找到第一个适合放置皇后的位置。皇后位置用黑色背景表示。此时效果如下图所示

8. 由于任意两个皇后不得处在同一行、同一列或者同一对角斜线上。所以第3个皇后所在的行、列和对角线上的位置都是危险位置，不能再放置第4个皇后。危险位置我们用红色背景表示，安全位置我们用绿色背景表示。此时效果如下图所示

9. 第五步，我们从第四行开始，遍历第四行中所有的列，在安全位置范围内找到第一个适合放置皇后的位置。由于在第四行找不到放置皇后的位置，所以我们进行回退。由于第2个，第3个皇后已经没有可选的位置，所以我们重新放置第1个皇后的位置。此时效果如下图所示

10. 由于任意两个皇后不得处在同一行、同一列或者同一对角斜线上。所以第1个皇后所在的行、列和对角线上的位置都是危险位置，不能再放置第2个皇后。危险位置我们用红色背景表示，安全位置我们用绿色背景表示。此时效果如下图所示

11. 第六步，我们从第二行开始，遍历第二行中所有的列，在安全位置范围内找到第一个适合放置皇后的位置。皇后位置用黑色背景表示。此时效果如下图所示

12. 由于任意两个皇后不得处在同一行、同一列或者同一对角斜线上。所以第2个皇后所在的行、列和对角线上的位置都是危险位置，不能再放置第3个皇后。危险位置我们用红色背景表示，安全位置我们用绿色背景表示。此时效果如下图所示

13. 第七步，我们从第三行开始，遍历第三行中所有的列，在安全位置范围内找到第一个适合放置皇后的位置。皇后位置用黑色背景表示。此时效果如下图所示

14. 由于任意两个皇后不得处在同一行、同一列或者同一对角斜线上。所以第3个皇后所在的行、列和对角线上的位置都是危险位置，不能再放置第4个皇后。危险位置我们用红色背景表示，安全位置我们用绿色背景表示。此时效果如下图所示

15. 第八步，我们从第四行开始，遍历第四行中所有的列，在安全位置范围内找到第一个适合放置皇后的位置。皇后位置用黑色背景表示。此时效果如下图所示

16. 至此，我们已经成功的在4×4的象棋上摆放四个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。当然这只是其中一种解法，还有另一种解法。留着读者自行研究。

效果展示

更多算法学习请关注我的公众号

说明

• 在公众号中回复“算法源码”即可获取十大经典算法源码
• 在公众号中回复“算法书籍”即可获取经典入门算法书籍
• 在公众号中回复“数据结构”即可获取数据结构相关源码