八皇后

2018-04-12 本文已影响0人 Soujiro

什么是八皇后问题?

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

解决思路

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

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

递归回溯过程(同一行只会有一只皇后)

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

图1

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

图2

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

图3

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

图4

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

图5

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

图6

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

图7

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

代码实现

1.定义一个长度8的二维数组表示棋盘,数组初始值是0，代表没有落子。当有皇后放置的时候，对应的元素值改为1

code1

2.定义check方法,检查合法性

code2

3.递归回溯

code3

4.结果输出

code4

code5

其中一种结果:

10000000

00001000

00000001

00000100

00100000

00000010

01000000

00010000