八皇后

作者: Soujiro | 来源:发表于2018-04-12 10:01 被阅读0次

    什么是八皇后问题?

    八皇后问题是一个古老的问题,于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

    参考文章:漫画:什么是八皇后问题?

    相关文章

      网友评论

          本文标题:八皇后

          本文链接:https://www.haomeiwen.com/subject/gwtxkftx.html