华容道
————世界三大益智游戏
引言
七巧板、九连环、华容道，都是耳熟能详的中华传统玩具。九连环一旦掌握定式，神秘感顿失，相比之下华容道变化多一些。但是华容道究竟有多少种布局？随便摆设的布局是否有解？解开一局最少需要几步？这些通常是人们初次接触华容道时，心里的疑问。
一、游戏起源
华容道一直被看作是中华传统益智玩具，但是该玩具的历史似乎并不长，普遍认为该玩具出现于 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种。
但这其中依然有大量的冗余，比如：下面的布局，15个中，即便去除镜像布局依然得到9个布局，但我们知道其实是一种布局的衍生。
1、布局类型
十个滑块，摆放在棋盘中，除了位置不同，变化更多源于五个”将“可以横放也可以竖放。因此本站将华容道布局分为：一横局、二横局、三横局、四横局、全横及全竖局。
2、布局表示
对于华容道布局的表示，本站把棋盘看做由四列五行的单元格构成，然后使用数字 0~4 表示各个单元格的内容。
0-表示空区域 1-表示兵卒 2-表示竖放的将领 3-表示横放的将领 4-表示曹操。
依照上述约定，“横刀立马”表示为“2442 2442 2332 2112 1001” 如下图。
四、解法查询
本站提供所有布局的解法演示。
参照使用说明，定义布局，查看解法演示。
