华容道

引言    所有布局解法动画演示

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

一、游戏起源

华容道一直被看作是中华传统益智玩具，但是该玩具的历史似乎并不长，普遍认为该玩具出现于 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、布局表示，即 id

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

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

2、解法数据表示

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

  • 坐标，20个格子，以字母g~z表示。
  • 滑块，以滑块左上格的坐标指定。
  • 移动，16种方式，以十六进制数字(0~9a~f)对应。16种方式分别是左、上、右、下、左左、上上、右右、下下、左上、左下、上左、上右、右上、右下、下左、下右。

3、开放数据API

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

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

返回的解法数据为：{"id":"24422442233221121001","mirror":"0","solution":"u3w2o3p0r0z1y2q3o6tax5u0v9q3p6o6s1t1y4z4u3qfp2o2g7h0j0r5v5q2i7g2o5p0x5wcy4r3q3p6h3j4nar5v5u2tdl3hfg2o5p0m3i3j0n1v1y2q7o2g7h0i0m0j0r5p2l7h7g2o5t8w1y4z4q3p6o6s1xau0"}

  1. id: 布局表示
  2. mirror: 1或0表示是否镜像局。如果是，那么对于解法数据的解读需要按镜像对称来解读，此时滑块和移动需要做对称处理，具体说来：滑块是镜像坐标指代的滑块，移动方式中的左右互换。
  3. solution: 解法数据：（滑块+移动），参加上文说明。

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

4、联系作者

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

© klotski.online