Python三国华容道程序

Python三国华容道程序

        华容道游戏实质上是一个树的搜索问题，对学习理解《数据结构》有很大帮助，本文用Python实现三国华容道程序，介绍其数据结构设计、算法设计，分别用实现深度和广度优先搜索进行华容道问题的求解。

一、华容道游戏的搜索树结构

二、数据结构设计

1 棋盘

        采用5*4的二维数组，为方便判断棋子移出界，沿棋盘四边建墙，扩充至7*6的二维数组，设墙所占数组元素为1。

         Python代码如下

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]]

2 棋子

棋子有四种：

大小编号大正方形2*24小正方形1*15横长方形1*22竖长方形2*13

将某局华容道的初始状态的棋子编号放入棋盘，形成棋子站位的位示图：

 位示图的作用：

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_piece("马超",3,[0,0])

3 棋局

棋局数据结构为列表，容纳全部棋子实例，前面的棋局例子的代码如下：

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)

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以后的移动还没有开始试探，所以，程序不必真正在内存生成一个多叉树结构，多叉树的每一层，只需要保留一个节点，可以简化成一个堆栈即可存储多叉树。如下图所示：

 

待续......