八皇后解题思路记载

时间:2021-03-29 09:30:22

八皇后解题思路记载


恰巧同事和咱一起讨论这个问题,下面把理解和解题的思路整理出来

题目:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行同一列同一斜线上,问有多少种摆法。

这个问题经典的写法有好多,可以参考wiki:Eightqueenspuzzle.

首先看一下如何构建这个模型和对应的算法

八皇后解题思路记载

上面是棋盘

已经存在两个落点(0,0) , (1,2)

  • 如果我们是顺序从行来一行一行的放每一个皇后的话,那么行的顺序必然是 0,1,2,3,4,5,6,7,所以我们在结构里不进行记录行的数字,只建立一个记录列的list,如[0, 4, 7, 5, 2, 6, 1, 3]

  • 第一次放入皇后不需要考虑会不会被其他皇后吃掉,因为还没有任何皇后。那么下一次放入的时候就需要知道哪些能放,哪些不能放。所以我们需要定义个函数来生成可以放入皇后的安全列表Safe( a )

  • 我们需要定义一套递归结构来根据Safe生成一个回溯结构,然后取出其中个数为8的记录,就是我们要的结果。

实现的程序如下:

Safe函数:

def Safe(a):
 tl = []
 n = len(a)
 for index,var in enumerate(a):
 tl = tl + [ var-n+index , var , var+n-index ]
 tl = distinct(  [ l for l in tl if not ( l > 7 or l <0 ) ] )


 sl = [ i for i in range(8) if i not in tl ]
 return sl

queens递归函数:

def queens(alist,n):
    for l in Safe(alist):
        tmp = alist + [l]
        queens(tmp,n-1)
if len(alist) == 8 : print  alist

取唯一性的函数:

def distinct(l):
    d = {}
    map(setitem, (d,)*len(l), l, [])
    return d.keys()

main函数:

from operator import setitem
if __name__ == "__main__":
    for y in range(8):
        alist = []
        alist.append(y)
        queens(alist,8)