qq三国华容道怎么走,三国华容道怎么玩

上文完成了Python用深度优先算法求解三国华容道，本文在上文的基础上，将算法改为广度优先的算法。深度优先算法可以获得较快的求解速度，但棋子移动步骤较长。广度优先算法可以获得较短的移动步骤，但求解速度较慢（以下图的棋局为例，需要计算19分钟，结果为113步棋子移动就可以将qfdmf脱困）。

深度优先遍历用堆栈存储搜索树，搜索树的每一层只会有当前搜索的节点在栈中，已搜索过无解答的节点以及未搜索过的节点都不会入栈，但需要保存搜索历史在栈中节点内，如下图（左）所示：

广度优先搜索使用队列，首先将根节点入队列，然后进入循环，每次将队首节点的全部孩子节点依次如队列，在此过程中，如果遇到了qfdmf脱困的节点，则游戏成功结束，如果队首节点的全部孩子都入栈了，但未遇到脱困节点，则将队首节点移出队列，继续循环。如上图（右）所示。

深度优先中，堆栈的层次关系揭示了双亲和孩子的关系，所以在节点中不需要有指针。但在广度优先中，队列中前后关系不能代表的节点之间的双亲和孩子的关系，所以需要用到《数据结构》中介绍的双亲表示法，记录搜索树的结构。这就需要在节点的结构中加入一个双亲指针，代码如下：

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.移动队列=[] #存储该chess_game所有的可能下一步 self.parent=None #双亲指针

代码如下：

import copy上,下,左,右=0,2,3,1D={0:”上”,2:”下”,3:”左”,1:”右”,}class chess_piece: #棋子 def __init__(self, name,chess_type,chess_position): self.name=name self.chess_type=chess_type 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.移动队列=[] #存储该chess_game所有的可能下一步 self.parent=None #双亲 def 对称(self): #计算chess_game的左右对称的chess_game 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,棋子): z=棋子.chess_type 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: 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==”qfdmf”: 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])qfdmf=chess_piece(“qfdmf”,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])#51步 19分钟根节点.chess_game.append(qfdmf)根节点.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) 棋局队列.append(根节点) #根节点入队列 while True: while True: if 棋局队列[0].当前移动>=len(棋局队列[0].移动队列): #队首节点的全部孩子已入队列，将其移出队列棋局队列.pop(0) #队首节点出队列 #该节点仍然在内存中，可通过其孩子节点的双亲指针访问到 continue 节点=copy.deepcopy(棋局队列[0]) 节点.移动棋子(节点.移动队列[节点.当前移动]) 棋局队列[0].当前移动+=1 节点.更新棋盘占据位置() if 节点.board in 已产生棋局的位示图: continue elif 节点.对称() in 已产生棋局的位示图: continue #break else: break 节点.更新棋盘移动性() 节点.生成移动队列() 节点.parent=棋局队列[0] #记录该节点的双亲节点已产生棋局的位示图.append(节点.board) if 节点.成功(): count=0 print(“成功”) 节点.print_board() print(“———————–“) while True: if 节点.parent: #从结果节点沿双亲指针打印出全部移动步骤 count+=1 节点=节点.parent 节点.print_board() print(“———————–“) else: break print(“步数：{}”.format(count)) break else: 棋局队列.append(节点) #入队列

运行结果截图：