1、需求来历
某天娃拿着华容道板块来,喊她爹我求解，大约如图这样的一个东西，我：…,一把年岁了，和你玩这个破东西？自己一边玩去。
花了一支烟时刻想了下，算了，帮你写一个程序来破解吧，后面别来烦我就行了。
2、初步建模
面板大小为 4 X 5 的数组，人物咱们称为卡片。 咱们观察人物有：曹操、关羽、张飞、黄忠、马超和4个卒（为了表明便利，四个卒咱们以为是四个不同人物）。 用一个二维数组表明游戏状况，为每个人物界说一个值。 人物值界说，卒用小写字母表明（谁叫你不是大佬？），大将们用大写字母表明，空白用 0 表明。（其实怎么界说都没关系，主要是为了便利阅读和同名不冲突） 如下：
# "0"：空
# "a"：卒1
# "b"：卒2
# "c"：卒3
# "d"：卒4
# "M"：马超
# "H"：黄忠
# "Z"：张飞
# "Y"：赵云
# "G"：关羽
# "C"：曹操
除了 0 值，其他相邻的相同值，咱们以为是不可分割的一块，根据界说，咱们构造其间一个初始化局势如下：
[ ["H","C","C","Y"],
["H","C","C","Y"],
["Z","G","G","M"],
["Z","b","c","M"],
["a","0","0","d"]
]
从初始状况开端，遍历每个可以移动的卡片进行下一个状况生成，得到一个状况树。
最终生成树下假如把“曹操”人物移动到（1，3）、（2，3）（1，4）、（2，4）（如下图,蓝色数据移动到红色方位）表明完毕，拿到答案了:
3、笼统目标化
在状况树图中，怎么从一个状况生成另一个状况？假如用上面的一个二维数组来做逻辑处理，比较复杂，如：
1） 除了0，相同的值的移动需求一起移动；
2） 移意向的范畴不能超出4X5区域范围并且方针要是0（空白）；
3） 离开的区域，需求设置为0 等等。
根据二维数组做这些状况表逻辑处理，稍微复杂，将它们笼统简化下。
细想华容道游戏，包括一个面板，多个人物卡片，和两个空白方位这几种不同数据。咱们怎么把”面板”、”人物卡片”、”空白点”这三类有机的组合起来？过程如下：
1）从卡片开端，咱们界说一个Card 目标，它有人物值，有方位，有大小；
class Card:
def __init__(self, role, x, y, width, height):
self.role = role
self.x = x
self.y = y
self.width = width
self.height = height
2）空白点较为简略，界说为（x，y） 这样的一个元组即可，不过多规划了。
3）面板上包括属性有卡片，和空白点。卡片人物值是仅有的，用一个dir(role:Card) 表明人物；还有两个空白点，由于空白点也是仅有的，为了运算便利，咱们把它界说到调集set 里面。
面板模型代码：
class Board:
'''
cards: dir{role:card}
blanks:set((x,y))
'''
def __init__(self, cards, blanks):
self.cards = {card.role:card for card in cards}
self.blanks = blanks
目前的 Board 目标和前面的状况state数组，它们表明是完全等价的。目标化之后，操作逻辑大大简化了，例如面板上移动一个卡片，便是两个过程：
1）对card 进行x，y进行加减操作（如Card提供 move 函数）；
2）对进入区域和离开区域的空白方位的替换。
class Card:
# 若干代码
def move(self, offset_x, offset_y):
self.x = self.x + offset_x
self.y = self.y + offset_y
相对原来的要对 state 数组操作，清晰明了许多。
4、主要逻辑
再来收拾下建模游戏的主要逻辑，由于华容道答案是希望寻求最短途径的，所以需求一个广度优先算法。 从初始化局势（根局势）开端：
1）枚举每个卡片，对每个卡片进行上下左右可移动判别，并生成所有或许状况局势，记载到列表；
2）对每个生成状况局势进行判别，假如是答案，则返回“演化”前史；假如不是，则记载到“下一层”遍历列表；
3）对“下一层”遍历列表每个状况局势进行递归处理，回到过程 1)。
简略说说可移动判别逻辑，比方一个卡片想往上移动，它能往上移动的条件是什么？
1）卡片本身不能在最贴顶部；
2）卡片顶边的上方，每个格子都没有其他卡片，看状况二维数组，便是状况为“0”，在 Board 目标来看，便是上方的（x，y）点，都在 Board.blanks 内。
收拾好思路后，逻辑就简略了：
class Card:
# 判别是否现已到顶部
def isTopMost(self):
return self.y == 0
# 求顶边各个点
def getTopLines(self):
return [(self.x + i, self.y) for i in range(self.width)]
# ... 其他许多代码
向上移动，假如是顶部了，则不能往上移动；否则，获取顶部各点的上方一格，并且判别上一个是空白，则可以移动了。 还需求笼统一个game 来做游戏总控制。
class Game:
def __init__(self):
pass
# 返回移动后的状况，None 表明不合法移动
def moveUp(self, card, board):
if card.isTopMost():
return None
# 进入区域为顶边偏移-1，离开区域为底边，偏移值得 为(0,-1)
above_tops = [(x, y - 1) for (x, y) in card.getTopLines()]
return self.move(card, board, above_tops, card.getBottomLines(), 0, -1)
def move(self, card, board, enter_points, leave_points, offset_x, offset_y):
# 进入的空间要求为空白
if not board.isAllBlanks(enter_points):
return None
new_card = card.clone()
new_card.move(offset_x, offset_y)
new_board = board.clone()
new_board.updateCard(new_card)
new_board.updateBlanks(enter_points, leave_points)
return new_board
递归算法，采用广度优先遍历，枚举每个局势，中心代码便是这么一点了：
def dfs(self, forest, traversed):
next_forest = []
for tree in forest:
child_boards = self.nextBoards(tree.board)
for child_board in child_boards:
child_tree = Tree(tree, child_board)
if self.isAnswer(child_board):
return child_tree.sourceBoard()
next_forest.append(child_tree)
if len(next_forest) == 0:
return []
return self.dfs(next_forest, traversed)
5、算法优化
1）由于移动卡片时分，移动先后两个卡片几次后，或许会呈现两个面板是相同的，所以针对每个局势进行hash 记载，前史上呈现过了，不需求再做便利，可以大大减少局势遍历量。
2）形状相同的两个卡片，假如呈现了方位互换，两个盘面其实是等价的，咱们以为两个卡片是等价的，所以他们hash 记载理应相同，省去不必要的遍历。
代码见Board.hash() 相关逻辑。
相同的两个状况，没有优化的情况下，跑一个小时还没有出成果，做了这两点优化后，约10秒出成果。优化作用是比较客观的。
6、输出界面
本来想简略偷闲点，用个文字替换输出的，这个样子：
但考虑娃看不懂这种“高档”的诙谐，我不得不又花了她爸的一个多小时去抠图，然后编码…刷刷刷～弄了个6岁儿童能看得懂的界面作用：
7、完整代码分享
不多说了，上代码吧。
github 链接：github.com/yuccnx/klot…
