什么是八皇后问题?
八皇后问题是一个古老的问题,于1848年由一位国际象棋棋手提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,如何求解?
解决思路
递归回溯. 从棋盘的第一行开始尝试摆放第一个皇后,摆放成功后,递归一层,再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放,则向右移动一格再次尝试,如果摆放成功,则继续递归一层,摆放第三个皇后......
如果某一层看遍了所有格子,都无法成功摆放,则回溯到上一个皇后,让上一个皇后右移一格,再进行递归。如果八个皇后都摆放完毕且符合规则,那么就得到了其中一种正确的解法。
递归回溯过程(同一行只会有一只皇后)
1.第一层递归,尝试在第一行摆放第一个皇后:
图12.第二层递归,尝试在第二行摆放第二个皇后(前两格被第一个皇后封锁,只能落在第三格)
图23.第三层递归,尝试在第三行摆放第三个皇后(前四格被第一第二个皇后封锁,只能落在第五格)
图34.第四层递归,尝试在第四行摆放第四个皇后(第一格被第二个皇后封锁,只能落在第二格)
图45.第五层递归,尝试在第五行摆放第五个皇后(前三格被前面的皇后封锁,只能落在第四格)
图56.由于所有格子都“绿了”,第六行已经没办法摆放皇后,于是进行回溯,重新摆放第五个皇后到第八格
7.第六行仍然没有办法摆放皇后,第五行也已经尝试遍了,于是回溯到第四行,重新摆放第四个皇后到第七格
图78.继续摆放第五个皇后,以此类推......
代码实现
1.定义一个长度8的二维数组表示棋盘,数组初始值是0,代表没有落子。当有皇后放置的时候,对应的元素值改为1
code12.定义check方法,检查合法性
code23.递归回溯
code34.结果输出
code4 code5其中一种结果:
10000000
00001000
00000001
00000100
00100000
00000010
01000000
00010000
参考文章:漫画:什么是八皇后问题?
网友评论