首页 > 代码库 > 【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】生成器、回溯和八皇后问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。