八皇后问题回溯法动态演示2021_11_18版by李兴球

Python海龟宝典含200多个原创的用turtle模块制作的创意程序,原名《Python趣味编程200例》。准备参加全国创意编程与智能设计大赛的同学们可以用来做参考。

遥记我20岁左右的时候,拿着一本数据结构与算法书,PASCAL的,那个时候也是否对计算机编程充满了热爱和向往。时光飞速,我还是那个“少年”。仍旧兴趣盎然地在编程,想想我曾经是熟练的掌握了汇编语言的,可是现在我却看不懂了。写的八皇后算法那代码好糟糕。去年用我自己编写的精灵模块把八皇后代码重写了一遍,最近再次学习数据结构与算法,对动态规划、哈夫曼树、汉密尔顿路径等,感觉又有较大的长颈,确实体验到了温故而知新,收获不少。今天又把八皇后算法写了一遍,逻辑清晰了很多,对程序=数据结构+算法有了更深刻的体验。

Python八皇后演示动图

这个程序使用一个stack列表存储皇后的位置,当成栈使用。使用常见的回溯法,不断地去试探下一个位置,如果和前面的位置有冲突,则继续尝试。如果一行所有的列都尝试完了,再次回溯。代码中有注释,详情见代码:

 

import turtle
from eight_queen import *

def check_collision(stack):
    """检测皇后在row,col位置是否和其它皇后冲突"""
    row,col = stack[-1]                          # 最后摆放的  
    for x,y in stack[:-1]:
       if  abs(y-col) in (0,row-x) :return True # 列的差值等于0或者和最后一行到x行的差值一样
     
    return False           

def traceback(chess,):
    """从栈中弹出上次坐标,清除所盖图章"""
    i,j = stack.pop()
    chess[i][j] = 0     
    turtle.clearstamps(-1)  # 清除这个坐标的皇后
    j = j + 1               # 上一行的下一列位置
    return i,j
           
def output(stack):          # 以文本方式输出一个解
    for i,j in stack:
        print(j,end='')
    print()
           
chess = [[0,0,0,0,0,0,0,0],
         [0,0,0,0,0,0,0,0],
         [0,0,0,0,0,0,0,0],
         [0,0,0,0,0,0,0,0],
         [0,0,0,0,0,0,0,0],
         [0,0,0,0,0,0,0,0],
         [0,0,0,0,0,0,0,0],
         [0,0,0,0,0,0,0,0]]

turtle.setup(800,800)
turtle.speed(0)
draw_cross(770)                # 画坐标线
draw_grid(8,70)                # 画格子
turtle.penup()                 # 抬笔
turtle.addshape('queen.gif')
turtle.shape('queen.gif')
turtle.speed(1)
turtle.title('八皇后问题回溯法动态演示2021_11_18版by李兴球')
w = turtle.Turtle(visible=False)
w.penup()
w.sety(300)
ft = ('黑体',32,'normal')
w.write("八皇后问题回溯法动态演示",align='center',font=ft)

stack = []                    # 新建一个列表存储当前皇后坐标,当栈用
i ,j = 0,0

while True:
    if j<8:
       chess[i][j] = 1         # 放皇后
       place_queen(8,70,i,j)   # 在棋盘上放置皇后(盖图章)
       
    else:                      # 一行都尝试完了,超过最右边了,需要回溯
        if stack:              # 如果栈不是空的    
           i,j = traceback(chess) # 回溯到上一个位置的右边一列
           continue
        else:
           break
        
    stack.append((i,j))        # 放入stack中,保存以便回到上一个位置
    
    if check_collision(stack)  :# 发生冲突       
       i,j = traceback(chess)     # 和其它皇后发生冲突,需要回溯
       continue
    else:        
       i = i + 1               # 到下一行
       j = 0                   # 从0开始放皇后
       
       if i==8:           
           output(stack)       # 到了最后输出一个解
           i,j = traceback(chess) # 这当然也要继续到上一行继续试探
           xsleep(3)       
           
           
     
本站所有作品,教程等皆为原创,版权所有。只供个人及单位内部研究使用,对外展示或传播必需经本站同意,且注明来自本站。培训机构等用本站资源培训学生,需经本站授权。一旦付款,表示同意本站知识付费原则:数字商品,不支持退款。亦可直接向微信号scratch8付款购买。入住QQ群:225792826 和爱好者共同交流,并且能下载免费提供的Python资源(需提供真实姓名才可入群)
李兴球的博客_Python创意编程技术前沿_pygame » 八皇后问题回溯法动态演示2021_11_18版by李兴球

李兴球Python微信公众号文章列表

Python游戏海龟模块教程说明书与案例若干免费发放

爱的纪念_Python创意情景动画源代码解析

少儿Python编程到底学些什么?这些代码或许回答了问题.

Python编程家长会花絮_萍乡中小学Python家长会现场

火星路上等着你_少儿从小学什么最好呢?

国家大力整顿教育培训机构,Scratch或Python少儿编程还有得教吗?

鸿蒙系统支持Python开发_可视化编程特别兴趣小组

Scratch作品转Python作品_小猴接桃

python海龟数据可视化。第七次全国人口普查历年数据图表

你的孩子Python编程学到哪个阶段了?给孩子报编程的家长,务必仔细一读。

五一神女来对话,看看她们聊什么?赠Python教案等。

五一快乐有大礼,告诉大家我是如何上Python课的。

Python名堂多,趣味到处有,劈开机械手,帧帧是图片。速算达人之猫狮大战正在进行。 逐字动画不独享,自动生成皆有它。2行代码自动生成字幕gif动画。 Python之潮来临,我在安源区教师科技创新能力的Python讲座

小心你的Python程序,它会是你的一面镜子。小方块闯迷宫.py源代码简析。送Scratch算法集。?

铃儿响钉铛_音效怎能忘_Python配音之Pygame混音器

人面桃花相映红_winsound模块简介

《Python昨晚我想你了》_开源的游戏海龟模块实例案例浅析

《八猫联动初体验》_来自游戏海龟模块的问候

喜爱春天的人儿啊 心地纯洁的人_Python逐行像素显示

旋转之三叶炫彩扇_蟒蛇与海龟的表演

彩虹欢迎字幕_三模合体滚图形

《Python海龟宝典》简介

100%错误的算法还在用,明明没有错别字,说我有11个错别字

奇怪的Python代码,谁能帮我解释一下??

人造地球系统让人类文明充满整个宇宙之Python32768版

深夜,是什么把你的大脑搞成一团浆糊!再谈少儿编程!

5线城市萍乡的少儿Python寒假班学的是什么内容?

关于纯少儿编程课程进化的自然选择

Python海龟画图经典作品_国庆中秋双重喜庆源代码免费下载

海龟为什么要自杀!turtle制作游戏秘籍之一

朋友,你是否知道我在仰望着你_Python神笔马良案例集

酷酷的爆炸效果_Python海龟画图不仅仅是画图

虫子满屏爬_三bug多线程示例程序浅析 少儿Python视频课程A级简介

给的gif图片加文字水印_拆帧与合帧(免费下载180个Python创意源码

用Python制作酷炫图形之如意金箍棒_颜色增加模块应用

简单的用Python做酷炫图形与动画

sb3转exe,sb3素材提取器,编程小子apk, 未公开的pygame游戏集/scratch/python少儿编程免费下载集合

夜幕下的霓虹

学本领,探索更大的世界!

李兴球博客 风火轮编程主页