八皇后问题

什么是八皇后问题？

       国际象棋中的皇后，可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后，使得任意两个皇后都不在同一条横线、竖线、斜线方向上。

       八皇后问题是一个古老的问题，于1848年由一位国际象棋棋手提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，如何求解？

 

       以高斯为代表的许多数学家先后研究过这个问题。后来，当计算机问世，通过计算机程序的运算可以轻松解出这个问题。

       让我们来举个栗子，下图的绿色格子是一个皇后在棋盘上的“封锁范围”，其他皇后不得放置在这些格子：

 

 

下图的绿色格子是两个皇后在棋盘上的“封锁范围”，其他皇后不得放置在这些格子：

 

 

 

 

如何解决八皇后问题？

递归回溯：

所谓递归回溯，本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......

 

如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。

1. 第一层递归，尝试在第一行摆放第一个皇后：

 

 

2. 第二层递归，尝试在第二行摆放第二个皇后（前两格被第一个皇后封锁，只能落在第三格）：

 

 

3. 第三层递归，尝试在第三行摆放第三个皇后（前四格被第一第二个皇后封锁，只能落在第五格）：

 

 

4. 第四层递归，尝试在第四行摆放第四个皇后（第一格被第二个皇后封锁，只能落在第二格）：

 

 

5. 第五层递归，尝试在第五行摆放第五个皇后（前三格被前面的皇后封锁，只能落在第四格）：

 

 

6. 由于所有格子都“绿了”，第六行已经没办法摆放皇后，于是进行回溯，重新摆放第五个皇后到第八格：

 

 

7. 第六行仍然没有办法摆放皇后，第五行也已经尝试遍了，于是回溯到第四行，重新摆放第四个皇后到第七格：

 

 

8. 继续摆放第五个皇后，以此类推......

 

八皇后问题代码实现：

在研究代码实现的时候，我们需要解决几个问题：

 

1. 国际象棋的棋盘如何表示？

 

很简单，用一个长度是8的二维数组来表示即可。

 

 

由于这里使用的是int数组，int的初始值是0，代表没有落子。当有皇后放置的时候，对应的元素值改为1。

 

在这里，二维数组的第一个维度代表横坐标，第二个维度代表纵坐标，并且从0开始。比如chessBoard[3][4]代表的是棋盘第四行第五列格子的状态。

 

2. 如何判断皇后的落点是否合规？

 

定义一个check方法，传入新皇后的落点，通过纵向和斜向是否存在其他皇后来判断是否合规。

 

 

3. 如何进行递归回溯？

 

递归回溯是本算法的核心，代码逻辑有些复杂

 

 

4. 如何输出结果？

 

这个问题很简单，直接遍历二维数组并输出就可以。

 

 

5. 如何把这些方法串起来？

 

在main函数里分三步来调用：

第一步：初始化

第二步：递归摆放皇后

第三步：最后输出结果。

 

其中Queen8是整个类的名字。

 

 

最终输出如下：

 

10000000

00001000

00000001

00000100

00100000

00000010

01000000

00010000