首页 > 代码库 > 【Python】生成器、回溯和八皇后问题

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

八皇后问题:

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

思路:

  典型的回溯问题:

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

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

 1 def isconflict(state, nx):
 2     """
 3     验证下一个要放置的皇后是否与之前的皇后冲突
 4     """
 5     ny = len(state)
 6     for i in range(ny):
 7         if abs(state[i]-nx) in (0, ny-i):
 8             return True
 9     return False
10 
11 
12 def queens(num=8, state=[]):
13     """
14     主处理函数
15     """
16     for p in range(num):
17         if not isconflict(state, p):
18             if len(state) == num-1:
19                 yield p
20             else:
21                 for result in queens(num, state+[p]):
22                     yield [result, p]
23 
24 
25 def play3(l):
26     """
27     把返回的结果列表中的子列表裂解开
28     """
29     try:
30         try: l+‘‘
31         except TypeError: pass
32         else: raise TypeError
33         for i in l:
34             for s in play3(i):
35                 yield s
36     except TypeError:
37         yield l
38 
39 def printqueens(l):
40     """
41     打印输出结果
42     """
43     l = play3(l)
44     l = list(l)
45     n = len(l)
46     for i in range(n):
47         for j in range(n):
48             if j != l[i]:
49                 print(., end= )
50             else:
51                 print(q, end= )
52         print( )
53 
54 if __name__ == __main__:
55     l = list(queens(5))
56     print(l)
57     n = len(l)
58     print(有 {0} 种放置方法:.format(n))
59     for i in range(n):
60         print(--------------------)
61         printqueens(l[i])
62         print(--------------------)

 

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