【Python】生成器、回溯和八皇后问题

八皇后问题：

　　把N个皇后，放在N*N的棋盘上面，从第一行往下放，每个皇后占一行，同时，每个皇后不能处在同一列，对角线上，有多少种放置方法。

思路：

　　典型的回溯问题：

　　　　1.当要放置最后一个皇后时候，默认前N-1个皇后已经全部放置好了，那么验证在第N行上的每个位置是否可行，即是否与之前的皇后在同一列或者对角线即可；

　　　　2.如果放置的不是最后一个皇后，则回溯。回溯至刚开始放第一个元素时候，然后不断的返回上一层。每一层都认为下一层传递给自己的是正确的信息

 def isconflict(state, nx):

     """

     验证下一个要放置的皇后是否与之前的皇后冲突

     """

     ny = len(state)

     for i in range(ny):

         if abs(state[i]-nx) in (, ny-i):

             return True

     return False

 def queens(num=, state=[]):

     """

     主处理函数

     """

     for p in range(num):

         if not isconflict(state, p):

             if len(state) == num-:

                 yield p

             else:

                 for result in queens(num, state+[p]):

                     yield [result, p]

 def play3(l):

     """

     把返回的结果列表中的子列表裂解开

     """

     try:

         try: l+''

         except TypeError: pass

         else: raise TypeError

         for i in l:

             for s in play3(i):

                 yield s

     except TypeError:

         yield l

 def printqueens(l):

     """

     打印输出结果

     """

     l = play3(l)

     l = list(l)

     n = len(l)

     for i in range(n):

         for j in range(n):

             if j != l[i]:

                 print('.', end=' ')

             else:

                 print('q', end=' ')

         print(' ')

 if __name__ == '__main__':

     l = list(queens())

     print(l)

     n = len(l)

     print('有 {0} 种放置方法：'.format(n))

     for i in range(n):

         print('--------------------')

         printqueens(l[i])

         print('--------------------')

巴特西

【Python】生成器、回溯和八皇后问题

最新文章

热门文章