首页 > 代码库 > 八皇后，回溯与递归
八皇后，回溯与递归
python语句的八皇后代码，摘自《Python基础教程》，代码相对于其他语言，来得短小且一次性可以打印出92种结果。同时可以扩展为九皇后，十皇后问题。
问题：在一个8*8棋盘上，每一行放置一个皇后旗子，且它们不冲突。冲突定义：同一列不能有两个皇后，每一个对角线也不能有两个皇后。当然，三个皇后也是不行的，四个也是不行的，应该凭智商应该可以理解吧。
解决方案：回溯法和递归法
1 import random 2 3 def conflict(state,col): 4 row=len(state) 5 for i in range(row): 6 if abs(state[i]-col) in (0,row-i): 7 return True 8 return False 9 10 11 12 def queens(num=8,state=()):13 for pos in range(num):14 if not conflict(state, pos):15 if len(state)==num-1:16 yield(pos,)17 else:18 for result in queens(num, state+(pos,)):19 yield (pos,)+result20 21 22 23 def queenprint(solution):24 def line(pos,length=len(solution)):25 return ‘. ‘*(pos)+‘X ‘+‘. ‘*(length-pos-1)26 for pos in solution:27 print line(pos)28 29 30 for solution in list(queens(8)):31 print solution32 print ‘ total number is ‘+str(len(list(queens())))33 print ‘ one of the range is:\n‘34 queenprint(random.choice(list(queens())))
介绍：
1.回溯法
2.递归法
待续
八皇后，回溯与递归
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。