[华容道]Python小程序(可自定义地图&带解密算法&详细代码注释)
完整代码(带教程&演示视频):
百度面包多搜索标题名即可下载源码
三国华容道程序设计
一
三国华容道 分为3种角色
曹操(1个):占2×2=4个格子
五虎将(5个):各占1×2,2个格子
小兵(4):各占1×1,1个格子
二
走法:
横竖上下可以移动,只要不被挡住,就可以移动
最后曹操走到出口算胜利。
设计的程序如下:
1 设计一个可以灵活移动棋子的棋盘,这个棋盘可以让使用者任意放棋子,然后能用鼠标拖动
2 棋子拖动的时候,是整体拖动,比如移动曹操,是曹操整体移动
3在一个界面含有2个棋盘,方便展示教学
4设置一个一键清屏功能,清屏后可以自己重新摆棋(特别注意,棋子位置不是固定的,只是棋子的种类和个数是一定的,五虎上将有横有竖)
华容道游戏实质上是一个树的搜索问题,对学习理解《数据结构》有很大帮助,本文用Python实现三国华容道程序,介绍其数据结构设计、算法设计,分别用实现深度和广度优先搜索进行华容道问题的求解。
小时候我们都玩过实体版的:
解密算法:
位示图的作用:
1)判断棋子的移动及方向;
2)每个棋局的位示图都将被记录下来,防止在生成搜索树时出现重复棋局
class chess_piece: #棋子
def __init__(self, name,chess_type,chess_position):
self.name=name #棋子的名称,曹操,马超等
self.chess_type=chess_type # 小正方形5 打正方形4 横长方形2 竖长方形3
self.chess_position=chess_position #棋子在棋盘的位置,以左上角位置代表整个棋子位置
self.direction=[0,0,0,0] #记录棋子可能的移动方向
self.moveable=False #记录棋子是否可能移动
#实例化棋子对象,马超的位置见上图
chess_game=[]
马超=chess_piece("马超",3,[0,0])
曹操=chess_piece("曹操",4,[0,1])
黄忠=chess_piece("黄忠",2,[0,3])
关羽=chess_piece("关羽",2,[2,0])
卒1=chess_piece("卒1",5,[2,2])
张飞=chess_piece("张飞",3,[2,3])
赵云=chess_piece("赵云",3,[3,0])
卒2=chess_piece("卒2",5,[3,1])
卒3=chess_piece("卒3",5,[3,2])
卒4=chess_piece("卒4",5,[4,3])
chess_game.append(曹操)
chess_game.append(马超)
chess_game.append(黄忠)
chess_game.append(张飞)
chess_game.append(赵云)
chess_game.append(关羽)
chess_game.append(卒1)
chess_game.append(卒2)
chess_game.append(卒3)
chess_game.append(卒4)
搜索树的每一个节点应该包含一下的信息:
1)当前棋盘位示图;
2)当前棋局;
3)该棋局全部可能的移动;
4)该棋局已试探过的移动;
设计如下:
class node:
def __init__(self):
self.board=[[1,1,1,1,1,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,1,1,1,1,1]]
self.chess_game=[] #棋局
self.移动队列=[] #存储该棋局所有的可能移动
self.当前移动=0
其中,移动队列是一个列表,其列表元素也是一个列表,形如:[0,"马超"], [1,"卒1"]...表示在该棋局中,马超可以向上移动一步,卒1可以向右移动一步。移动队列起一个多叉树孩子指针作用,其每一个可能移动都可以发展成为子树。
当前移动是一个整数,充当移动队列指针,设当前移动为i,则表示队列中的前i-1个移动已尝试过了,这就意味着该节点的前i-1个子树都不能成功让曹操脱困,而i+1以后的移动还没有开始试探,所以,程序不必真正在内存生成一个多叉树结构,多叉树的每一层,只需要保留一个节点,可以简化成一个堆栈即可存储多叉树。
由于采用了深度优先搜索,该算法可以较快找到答案,但棋子的移动步骤较多,以上面的棋局为例,该算法需要移动棋子2045步,耗时不到1分钟。将算法改成广度度优先搜索,可以获得较少的棋子移动(114步),但耗时较长(接近30分钟)。
为方便起见,程序界面采用shell字符终端界面,部分函数名和变量名采用中文。
import copy
上,下,左,右=0,2,3,1
class chess_piece: #棋子
def __init__(self, name,chess_type,chess_position):
self.name=name #棋子的名称,曹操,马超等
self.chess_type=chess_type # 小正方形5 打正方形4 横长方形2 竖长方形3
self.chess_position=chess_position #棋子在棋盘的位置,以左上角位置代表整个棋子位置
self.direction=[0,0,0,0] #记录棋子可能的移动方向
self.moveable=False #记录棋子是否可能移动
class node:
def __init__(self):
self.board= [[1,1,1,1,1,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,1,1,1,1,1]]
self.chess_game=[]
self.当前移动=0
self.移动队列=[] #存储该棋局所有的可能下一步
def 对称(self): #计算棋局的左右对称的棋局
t=copy.deepcopy(self.board)
for i in range(1,6):
for j in (1,3):
t[i][j],t[i][5-j]=t[i][5-j],t[i][j]
return t
def print_board(self):
for i in self.board:
print(i)
def 更新棋子占据位置(self,棋子):
x=棋子.chess_position[0]+1
y=棋子.chess_position[1]+1
if 棋子.chess_type==3:
self.board[x][y]=棋子.chess_type
self.board[x+1][y]=棋子.chess_type
elif 棋子.chess_type==4:
self.board[x][y]=棋子.chess_type
self.board[x+1][y]=棋子.chess_type
self.board[x][y+1]=棋子.chess_type
self.board[x+1][y+1]=棋子.chess_type
elif 棋子.chess_type==2:
self.board[x][y]=棋子.chess_type
self.board[x][y+1]=棋子.chess_type
else: #卒
self.board[x][y]=棋子.chess_type
def 更新棋盘占据位置(self):
self.board= [[1,1,1,1,1,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,0,0,0,0,1],
[1,1,1,1,1,1]]
for x in self.chess_game:
self.更新棋子占据位置(x)
def 更新棋子移动性(self,棋子):
x=棋子.chess_position[0]+1
y=棋子.chess_position[1]+1
棋子.direction=[0,0,0,0]
if 棋子.chess_type==3:
if self.board[x][y-1]==0 and self.board[x+1][y-1]==0:
棋子.direction[左]=1
if self.board[x-1][y]==0:
棋子.direction[上]=1
if self.board[x+2][y]==0:
棋子.direction[下]=1
if self.board[x][y+1]==0 and self.board[x+1][y+1]==0:
棋子.direction[右]=1
elif 棋子.chess_type==4:
if self.board[x][y-1]==0 and self.board[x+1][y-1]==0:
棋子.direction[左]=1
if self.board[x-1][y]==0 and self.board[x-1][y+1]==0:
棋子.direction[上]=1
if self.board[x+2][y]==0 and self.board[x+2][y+1]==0:
棋子.direction[下]=1
if self.board[x][y+2]==0 and self.board[x+1][y+2]==0:
棋子.direction[右]=1
elif 棋子.chess_type==2:
if self.board[x][y-1]==0 :
棋子.direction[左]=1
if self.board[x-1][y]==0 and self.board[x-1][y+1]==0:
棋子.direction[上]=1
if self.board[x+1][y]==0 and self.board[x+1][y+1]==0:
棋子.direction[下]=1
if self.board[x][y+2]==0:
棋子.direction[右]=1
else: #卒
if self.board[x][y-1]==0 :
棋子.direction[左]=1
if self.board[x-1][y]==0 :
棋子.direction[上]=1
if self.board[x+1][y]==0:
棋子.direction[下]=1
if self.board[x][y+1]==0:
棋子.direction[右]=1
if sum(棋子.direction)>0:
棋子.moveable=True
def 更新棋盘移动性(self):
for x in self.chess_game:
self.更新棋子移动性(x)
def 生成移动队列(self):
self.移动队列=[]
self.当前移动=0
for x in self.chess_game:
if x.moveable:
for i in range(4):
if x.direction[i]==1: #1表示可移动,则将[移动方向,棋子]加入移动队列
self.移动队列.append([i,x.name])
def 移动棋子(self,x):
for i in self.chess_game:
if i.name!=x[1]:
continue
if x[0]==上:
i.chess_position[0]-=1
elif x[0]==下:
i.chess_position[0]+=1
elif x[0]==左:
i.chess_position[1]-=1
elif x[0]==右:
i.chess_position[1]+=1
def 成功(self):
for i in self.chess_game:
if i.name=="曹操":
if i.chess_position[0]==3 and i.chess_position[1]==1:
return True
if i.chess_position[0]==2 and i.chess_position[1]==1:
if self.board[4+1][1+1]==0 and self.board[4+1][2+1]==0:
return True
if i.chess_position[0]==3 and i.chess_position[1]==0:
if self.board[3+1][2+1]==0 and self.board[4+1][2+1]==0:
return True
if i.chess_position[0]==3 and i.chess_position[1]==2:
if self.board[3+1][1+1]==0 and self.board[4+1][1+1]==0:
return True
return False
已产生棋局的位示图=[]
棋局堆栈=[]
根节点=node()
马超=chess_piece("马超",3,[0,0])
曹操=chess_piece("曹操",4,[0,1])
黄忠=chess_piece("黄忠",3,[0,3])
关羽=chess_piece("关羽",2,[2,0])
卒1=chess_piece("卒1",5,[2,2])
张飞=chess_piece("张飞",3,[2,3])
赵云=chess_piece("赵云",3,[3,0])
卒2=chess_piece("卒2",5,[3,1])
卒3=chess_piece("卒3",5,[3,2])
卒4=chess_piece("卒4",5,[4,3])
根节点.chess_game.append(曹操)
根节点.chess_game.append(马超)
根节点.chess_game.append(黄忠)
根节点.chess_game.append(张飞)
根节点.chess_game.append(赵云)
根节点.chess_game.append(关羽)
根节点.chess_game.append(卒1)
根节点.chess_game.append(卒2)
根节点.chess_game.append(卒3)
根节点.chess_game.append(卒4)
#初始化
根节点.更新棋盘占据位置()
根节点.更新棋盘移动性()
根节点.生成移动队列()
已产生棋局的位示图.append(根节点.board)
棋局堆栈.insert(0,根节点)
while True:
while True:
if 棋局堆栈[0].当前移动>=len(棋局堆栈[0].移动队列):
棋局堆栈.pop(0) #当前棋局已无路可走,出栈
continue
节点=copy.deepcopy(棋局堆栈[0])
节点.移动棋子(节点.移动队列[节点.当前移动])
棋局堆栈[0].当前移动+=1
节点.更新棋盘占据位置()
if 节点.board in 已产生棋局的位示图:
continue
elif 节点.对称() in 已产生棋局的位示图:
continue
else:
break
节点.更新棋盘移动性()
节点.生成移动队列()
已产生棋局的位示图.append(节点.board)
if 节点.成功():
节点.print_board()
print("成功!步数:{}".format(len(棋局堆栈)))
for k in range(len(棋局堆栈)):
#棋局堆栈[k].print_board()
print("移动棋子:{}".format(棋局堆栈[k].移动队列[棋局堆栈[k].当前移动-1]))
print("-----------------------")
break
else:
棋局堆栈.insert(0,节点)
相关文章
- python模拟双色球大乐透生成算法
- python入门-分类和回归各种初级算法
- python: easyocr的安装和使用(easyocr 1.6.2 / Python 3.7.15 )
- 简介Python设计模式中的代理模式与模板方法模式编程
- python冒泡排序算法的实现代码
- Python multiprocessing.Manager()
- 【python cookbook】【数据结构与算法】18.将名称映射到序列的元素中
- python code practice(二):KMP算法、二分搜索的实现、哈希表
- Python-GUI编程PyQT5案例:注册界面扇形菜单动画及相关事件处理
- python程序员都在用到5个酷毙的Python工具
- Python:更改默认启动的python程序及其对应的安装包路径(更改pip的默认安装包的路径)图文教程之详细攻略
- Python语言学习之双下划线那些事:python和双下划线使用方法之详细攻略
- 有关一百以内数字的Python算法
- 基于电动汽车的带时间窗的路径优化(Python&Matlab代码实现)
- 【python】学会这八个自动化脚本,摸鱼的借口那不就来啦~
- 基于双向 GRU 的文本分类 Python 算法实战
- 效率倍增!12 个必知必会的 Python 数据处理技巧!
- 【阶段三】Python机器学习13篇:机器学习项目实战:支持向量机分类的算法原理
- 【阶段三】Python机器学习12篇:机器学习项目实战:朴素贝叶斯模型的算法原理与朴素贝叶斯分类模型
- Python实现HBA混合蝙蝠智能算法优化支持向量机分类模型(SVC算法)项目实战
- 【项目实战】Python基于KMeans算法进行文本聚类项目实战
- Python排序算法之插入排序
- 【 华为OD机试 2023】 递增字符串(C++ Java JavaScript Python)
- 【Python算法】回溯法作业
- Python编程:python中的计时器timeit模块
- python 将一个JSON 字典转换为一个Python 对象
- 使用pybind11开发python扩展库(9)
- python web py入门(10)- 实现论坛注册
- Python异步Request操作: aiohttp
- Python数模笔记-模拟退火算法(5)求解旅行商问题的联合算子模拟退火算法
- 【异常】前端ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- opencv-python(PIL)图像处理之训练模型前的几种图预处理
- 《Fluent Python》读书笔记-1.5 bisect二分查找算法