跳至正文
View Categories

< 1 min read

八皇后问题 #

  1. 八皇后问题的介绍
  2. 八皇后问题的算法分析
  3. 八皇后问题代码实现

八皇后问题的介绍 #

八皇后问题是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击(如下图所示)。即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

八皇后问题的算法分析 #

八皇后问题可以简化为:在每一行放置一个皇后使皇后处于不同列、不同对角线上。问题的关键在于如何判断每一个皇后是否在对角线上。我们不妨定义一个列表S1[i]，来表示第i行，皇后所在的列数。如上图我们可以发现:

  • 在同一列时s1[i]=s1[j](i!=j,第i行和第j行),也即是不同行不能选择列数相同的皇后
  • 在’/’对角线时，i+s1[i]=j+s1[j](i!=j,第i行和第j行),即是在’/’的皇后，行数和列数和相同
  • 在’\’对角线时，i-s1[i]=j-s1[j](i!=j,第i行和第j行),即是在’\’的皇后，行数和列数的差值相同

    • 掌握了上述的条件后我们可以发现，八皇后的回溯问题，其实就是限制条件更多的排列问题。

    八皇后问题的代码实现 #

    和普通回溯问题一样，我们分八步解决该问题，套用回溯代码框架:

    res=[0]*9 #存储每一步的选择，这里每一步也代表每一行
s1=[True]*9 #控制不同列
s2=[True]*20#控制对角线'/'，例如s2[9],代表行列数之和为9的方格是否能选
s3=[True]*20#控制对角线'\\'，例如s3[1],代表行列数之差为1的方格是否能选
def dfs(step):#定义dfs(step),step代表每一步的选择，
    if step>8:#大于8，解决问题的一条路径生成，输出
        res[0]+=1#res[0]代表路径有多少条
        print(res)
        return
    for i in range(1,9):#i代表1~8列
        if(s1[i] and s2[i+step] and s3[i-step]):#同时满足上述三个筛选条件
            res[step]=i#当前step行的第i列放置皇后
            s1[i]=False#第i列在后续步骤中不能再被选择
            s2[i+step]=False#'/'对角线的位置在后续步骤中不能被选择
            s3[i-step]=False#'\'对角线的位置在后续步骤中不能被选择
            dfs(step+1)#递归寻找下一个皇后位置
            s1[i]=True #以下三条指令，撤销当前的选择
            s2[i+step]=True
            s3[i-step]=True
dfs(1)

    事实上在求解8皇后问题时，回溯是比较好的的方法，如果使用单纯的穷举，则每一步有8种选择，则一共有8**8种选择，从这么多种选择中选取符合条件的八皇后排列，是十分费时的。

    小结 #

    • 根据八皇后问题，理解回溯算法的思想
    • 掌握八皇后求解的回溯算法

    习题 #

    1. 如果取消八皇后中’\’对角线条件的限制，试求八皇后问题有多少个解
    2. 8皇后问题中，如果使用(x,y)来表示第x行，第y列放置皇后：(1,6),(2,3),(3,7),(4,4),(5,1),(6,8),(7,2),(8,5)是八皇后问题的解吗？请画图并用程序验证
    What are your Feelings