《算法的乐趣》第六十一节

本节介绍华容道游戏的背景与求解算法原理。华容道取材于关羽义释曹操的三国故事，但游戏本身由美国人Lewis W. Hardy于1909年申请专利……

本节介绍华容道游戏的背景与求解算法原理。华容道取材于关羽义释曹操的三国故事，但游戏本身由美国人Lewis W. Hardy于1909年申请专利，后由英国人John Harold Fleming于1932年发明，传入中国后才加入三国背景。游戏在5×4棋盘上通过滑动棋子让曹操走到出口，常见开局有“横刀立马”“齐头并进”等，各有不同步数的最快解法，其中“横刀立马”为81步。由于缺乏数学理论支持，求解基本依靠穷举，计算机曾用穷举得出81步的最优解。

算法上，先将棋盘抽象为可存储的“局面”：用7×6二维数组表示棋盘，中间5×4为实际布局，四周填入特殊值15作为哨兵位，以统一处理移动时的边界判断；格子值0表示空，非0表示对应武将编号。另设一维表记录每个武将的位置与类型（大方块、横长方形、竖长方形、小方块）。棋局搜索采用广度优先搜索，局面结构中增加move、step、parent三个属性，分别记录当前动作、步数和父局面，以便回溯输出移动步骤；动作由武将编号与上下左右四个方向确定，移动方向用方向数组统一处理。