神剑山庄资源网 Design By www.hcban.com
本文实例讲述了Python解决八皇后问题的方法。分享给大家供大家参考,具体如下:
八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2。而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解。
这是一个典型的回溯算法,我们可以将问题进行分解:
首先,我们要想到某种方法来解决冲突检测问题,即不能令棋子处于能相互吃掉的位置——相邻、左右对角线。
其次,运用回溯的方法,求得问题的解。此处具体为函数的递归调用,当调用到棋盘的最后一行,便跳出,求得解。
最后,将我们的解打印出来。难点在于对递归调用函数的理解。
这仅仅是思路,是我们必须要解决的问题,但并不代表程序的运行流程。
具体代码如下:
#-*- coding:utf-8 -*- import random #冲突检查,在定义state时,采用state来标志每个皇后的位置,其中索引用来表示横坐标,基对应的值表示纵坐标,例如: state[0]=3,表示该皇后位于第1行的第4列上 def conflict(state, nextX): nextY = len(state) # print(nextY), for i in range(nextY): #如果下一个皇后的位置与当前的皇后位置相邻(包括上下,左右)或在同一对角线上,则说明有冲突,需要重新摆放 if abs(state[i]-nextX) in (0, nextY-i): #纵坐标减去下一个皇后的横坐标的绝对值 处于 0到下一皇后纵坐标减i则冲突 return True return False #采用生成器的方式来产生每一个皇后的位置,并用递归来实现下一个皇后的位置。 def queens(num, state=()): #num = 8 # print("%d "%len(state)), for pos in range(num): if not conflict(state, pos): #如果没有冲突 #产生当前皇后的位置信息 if len(state) == num-1: yield (pos, ) #生成元组 #否则,把当前皇后的位置信息,添加到状态列表里,并传递给下一皇后。 else: for result in queens(num, state+(pos,)): yield (pos, ) + result #result这个变量代表的是quees返回的元组 #若是最后一行 对于 pos in range(num)调用conflict(state, num) , #如果没有冲突,生成元组 #若不是最后一行 对于pos in range(num)调用conflict(state, pos), #如果没有冲突,state更新,递归调用queens(num, state) state将更新 #为了直观表现棋盘,用X表示每个皇后的位置 def prettyprint(solution): def line(pos, length=len(solution)): return '. ' * (pos) + 'X ' + '. '*(length-pos-1) for pos in solution: print line(pos) if __name__ == "__main__":#来判断是否是在直接运行该.py文件 prettyprint(random.choice(list(queens(8))))
运行结果:
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。
标签:
Python,八皇后问题
神剑山庄资源网 Design By www.hcban.com
神剑山庄资源网
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
神剑山庄资源网 Design By www.hcban.com
暂无Python解决八皇后问题示例的评论...
更新日志
2024年10月02日
2024年10月02日
- 孙悦.1996-伙伴【正大国际】【WAV+CUE】
- 纪钧瀚《钢琴阅读时光 雨中书店聆听轻音乐》[FLAC/分轨][399.62MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[320K/MP3][87.4MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[FLAC/分轨][184.94MB]
- 陈慧娴.2018-Priscilla-Ism演唱会3CD(2024环球红馆40复刻系列)【环球】【WAV+CUE】
- 郑秀文.1999-我应该得到(国)【华纳】【WAV+CUE】
- 陈家慧.2011-钢琴酒吧2CD【龙吟唱片】【WAV+CUE】
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[320K/MP3][45.01MB]
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[FLAC/分轨][109.13MB]
- 赞多《序章》[320K/MP3][45.54MB]
- 许巍.2004-每一刻都是崭新的【步升大风】【WAV+CUE】
- 群星.2024-四方馆影视原声带【韶愔音乐】【FLAC分轨】
- 陈雷.1997-安锁咧【金圆唱片】【WAV+CUE】
- 关淑怡.2013-MY.FAVORITE.SK.3CD【环球】【WAV+CUE】
- Sweety.2006-花言乔语【丰华】【WAV+CUE】