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

本节讲华容道自动求解算法实现中的几个关键问题。棋子移动可用行、列坐标加减1的方向数组统一描述，避免分支判断；广度优先搜索用线性表存棋局，逐个展开直到找到目标或队列为空。

本节讲华容道自动求解算法实现中的几个关键问题。棋子移动可用行、列坐标加减1的方向数组统一描述，避免分支判断；广度优先搜索用线性表存棋局，逐个展开直到找到目标或队列为空。

实现时需解决三件事：一是重复棋局，用Zobrist哈希算法把棋局编码为整数——为棋盘每个格子的每种状态分配随机编码，异或得到哈希值，棋子移动时只需对变动的格子增量异或即可更新；二是左右镜像，对称棋局解法相同，通过交换列编码直接算出镜像哈希并一并丢弃；三是连续滑动按一步计，但中间棋局仍需处理。判胜条件是代表曹操的大方块左上角到达[1,3]位置，为此在棋局结构中记录曹操的棋子编号。