引言

七巧板、九连环、华容道，都是耳熟能详的中华传统玩具。九连环一旦掌握定式，神秘感顿失，相比之下华容道变化多一些。但是华容道究竟有多少种布局？随便摆设的布局是否有解？解开一局最少需要几步？这些通常是人们初次接触华容道时，心里的疑问。

一、游戏起源

华容道一直被看作是中华传统益智玩具，但是该玩具的历史似乎并不长，普遍认为该玩具出现于 20 世纪早期，中文文献最早提及该玩具是在民国时期。在西方，19世纪末，流行一种由15个木制滑块组成的游戏，叫做 “Puzzle 15”，被西方国家看作是华容道的前身。几经变换，华容道玩具于 1934 年在英格兰，由 John H. Fleming 申请了专利。

令人感到神奇的是，该玩具在不同的国家和地区都存在本地化版本，这也令游戏的起源有些扑朔迷离。例如：

• 在法国，该玩具被叫做 “红驴子”（L’Âne Rouge)
• 在日本，该玩具被称为 “箱入り娘”
• 在泰国，该玩具被称为 “Khun Chang Khun Phaen”，意思是 Khun Phaen（泰国传奇故事中一个有名的人物）逃出监狱获得自由。

1991年，该游戏以Klotski的名字——源自 Polish Klocki（光滑木块）———收录在 Windows 3.1 版本的娱乐游戏中。

尽管该玩具在不同国家地区被赋予了不同的背景故事，但应该说中华传统华容道与“关云长义释曹操”这一典故结合得堪称完美。“横刀立马”布局中仅仅关羽是横向放置，看似最大的障碍，实则明追暗放。而该布局的最优解法是八十一步，给这款游戏又增加了几分神秘。

二、游戏介绍

中华传统华容道是，如图所示，一共有十个滑块，分为三种：

• 卒：4块，面积最小的正方形块。
• 将：5块，相当于两个卒的长方形。关羽、张飞、马超、赵云、黄忠。可以横向放置或者纵向放置。
• 曹操：1块，最大的正方形。

游戏的目标：把最大的滑块“曹操”移动到棋盘最底部的正中央，那里意味着出口，表示曹操逃出蜀兵的围追堵截。

华容道游戏有很多布局，往往根据各自特点被以成语或俗语命名，最经典的布局就上上文提及的“横刀立马”。

三、游戏布局

将十个滑块全部摆放在棋盘中，共有 363480 种摆放方法。考虑到做为游戏布局，应去除如下几类：

• 曹操本身已经位于出口处的布局。（剩余 338700 种布局）
• 镜像布局（左右对称）只保留一个。（ 剩余 169515 种布局 ）
• 去除无解布局。（ 剩余 121285 种布局 ）

这 121285 种布局中，从结构上看，一横至全横、全竖局，依次有：23623，37861，38467，14594，3999，2741种。

但这其中依然有大量的冗余，比如在连通的区域内放置多个卒，排列组合会产生多种布局，但我们知道其实只是一种布局的衍生。

四、关于本站

本站遍历了所有有效布局的最优解法。

1、布局表示

对于华容道布局的表示，本站把棋盘看做由四列五行的单元格构成，然后使用数字 0~4 表示各个单元格的内容。

• 0-空区域
• 1-卒
• 2-竖放的将领
• 3-横放的将领
• 4-曹操

2、解法数据表示

解法通过记录（坐标+移动）序列构成。

• 坐标：以0-19对应棋盘的20个格子
• 移动：以0-16对应左、上、右、下、左左、上上、右右、下下、左上、左下、上左、上右、右上、右下、下左、下右。

3、开放数据API

GET https://klotski.online/solution?t=1&q={布局表示}

如，横刀立马布局的查询：GET https://klotski.online/solution?t=1&q=24422442233221121001，带有参数 t=1 表示仅返回解法数据，否则跳转到旧版的演示页面。

返回的解法数据为：24422442233221121001&u3w2o3p0r0z1y2q3o6tax5u0v9q3p6o6s1t1y4z4u3qfp2o2g7h0j0r5v5q2i7g2o5p0x5wcy4r3q3p6h3j4nar5v5u2tdl3hfg2o5p0m3i3j0n1v1y2q7o2g7h0i0m0j0r5p2l7h7g2o5t8w1y4z4q3p6o6s1xau0&0

以&分隔为三部分

1. 布局表示
2. 解法数据：（坐标+移动），其中坐标0~19对应g~z二十个字母；移动0~16为0~9a~f，恰为十六进制表示。
3. 1或0表示是否镜像局。如果是，那么对于解法数据的解读需要按镜像对称来解读，此时坐标和移动需要做对称处理。

后续会将相关的代码整理后开源。

4、联系作者

未尽事项，不明之处可以联系作者 chufazheng@126.com，高兴与您交流。保持好奇心，祝你生活愉快！