華容道 (遊戲)
華容道〈Klotski，來自波蘭文的 klocki，意為木塊〉是一種滑塊類遊戲，由放在方形盘中的10块方片拼成，目標是在只滑動方塊而不從棋盤中拿走的情況下，將最大的一塊移到底部出口。流行於中國的華容道是由英國人John Harold Fleming在1932年所發明，然後本土化加上三國背景[1]。国内国外都有一些华容道的爱好者研究者[2]。
玩法
像其他的种类的滑块游戏，在一个方形盒子内放置了大小不同的方块，一般是4x5大小。在这些方块中有特殊的一个（一般是最大的）必须被移动到设计好的指定地点。玩家不允许拿起方块，但只可向平行或垂直的方向移动方块. 常见的玩法是移動最少次數，或者用最少的時間來完成遊戲。
歷史
- Lewis W. Hardy在1909年获得了名为Pennant Puzzle的专利，是華容道的前身，并被芝加哥的OK Novelty公司生产。[3] 他还在1907-12-14申请了美国专利美國專利第1,017,752号 并在1912-02-20通过[4]。
- 1932年，John Harold Fleming在英國申請專利（英國专利号411515），已與現代的華容道一模一樣，並也提供了橫刀立馬的解法[5]。
在中國的流傳
- 《科学消遣》(Science Pastime)是中國最早对于华容道游戏的记录之一，作者是一位中国教授姜长英，写于1949年。其称「估計它的歷史不過有幾十年。從前人的筆記中沒有發現有玩具華容道的記載」[6]。
- 40年代，这个玩具在上海就很流行。50年代初期，上海地摊上有薄纸印制的华容道玩具出售。后来，上海文具店里也出售过木制的华容道玩具。60年代，上海玩具十四厂和上海长春塑料厂曾把“华容道”制作成塑料玩具，没有武將名字，只是薄的彩色塑料片，被命名为船塢排檔。
- 1956年8月号的《数学通讯》杂志上，在封面的小知识栏目中提出了关羽放曹游戏。1959年5月号和6月号的《辽宁画报》上也刊登了这个游戏，命名为赶走纸老虎。
- 1982年9月号《我们爱科学》杂志刊登數學家谈祥柏写的《华容道》。
- 1984年9月，在北京市少年宫，由《我们爱科学》杂志社和首钢带钢厂粉末冶金厂联合举办少年“华容道”计时比赛，完成横刀立马局的最少时间是15秒。
- 1985年1月5日，中央电视台在少年儿童节目里播放了《小游戏“华容道”》，由余俊雄供稿，介绍了华容道的规则和历史。
- 1987年，余俊雄在《独粒钻石和华容道——迷人的智力游戏》認為華容道是來自洛書。之後人們就在填纵横图的基础上，发明了一种数学游戏——重排九宫。又说大约在元朝时傳到歐洲。但是这里的说法经不起推敲。首先重排九宫游戏在中國历史上从来没有任何文献记载或实物证据。至于元朝传入西方，这恐怕更是作者的凭空想象。余俊雄是北京玩具协会益智玩具委员会主任，热衷于推广中国古典数学玩具。从2002年起，北京玩具协会和中国科技馆举办了中国古典数学玩具展，把华容道列入其中，使得谬误传播开[8]。
- 2002年崔樂泉著作《圖說中國古代遊藝》，介紹了中國自古傳統的智力遊戲七巧板、九連環，但排除華容道[9]。
- 2003年谈祥柏翻譯Elwyn R. Berlekamp、John Conway、Richard Guy在1982年合著《Winnings Ways:for your mathematical plays》，書名《稳操胜券》。書中引介了許多華容道的排法[10]。
- 2004年吴鹤龄在其著作《七巧板、九连环和华容道:中国古典智力游戏三绝》，認為「把華容道看做是從西方傳入以後本地化的產物，倒是比較合乎事實和邏輯的」。從無出現民國前的華容道玩具實體或文獻記載。
中國人之所以誤認华容道為其傳統遊戲，赋予这么悠久的历史，是因为它的故事背景出自於《三国演义》第五十回[1]。
解法
横刀立马布局最少的步數為 81 步，而且經電腦驗證過，已經不能再少。第一次有紀錄的 81 步走法是由 马丁·加德纳在 1964 年 2 月刊的《科学美国人》給出。在文章內他給了以下幾種類似華容道的遊戲的走法 (括號內是 Hordern 分類的編碼)：Pennant Puzzle (C19), L'Âne Rouge (C27d), Line Up the Quinties (C4), Ma's Puzzle (D1), Stotts' Baby Tiger Puzzle (F10).
變種解法
當方塊佈置不同時，最優解法可能相差甚遠。以下是一些不同佈局的示範圖。
表中的數字為最少步數，取自同濟大學數學建模協會的第 6 期會刊中的一篇文章，指出用電腦計算華容道一些不同佈局方式的最佳步數，其中如果 1×1 的方塊連續移動兩格只算一步。
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 横刀立馬: 81 | 横豎皆將: 81 | 守口如瓶之一: 81 | 守口如瓶之二: 99 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 層層設防之一: 102 | 層層設防之二: 120 | 三軍聯防: 65 (又名交錯堵道) |
堵塞要道: 40 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 水泄不通: 79 | 四路皆兵: 66 | 五虎攔路: 39 | 兵將連環: 75 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 插翅難飛: 62 | 齊頭並進: 60 | 兵分三路: 72 | 將擁曹營: 62 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 横馬當關: 83 | 前擋後堵: 42 | 兵擋將阻: 87 | 兵臨城下: 56 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 一路進軍 | 一路順風 | 兵臨曹營 | 雨聲淅瀝 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 桃花園中 | 捷足先登 | 圍而不殲 | 將守角樓 (又稱指揮若定) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 四將聯防 (又名四將連關) |
屯兵東路 | 比翼橫空 | 夾道藏兵 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
利用计算机逐个枚举开局排法并暴力搜索最少步数解法，验证得到的最优解需要步数最多的一种布局被命名为“峰回路转”，需要138步。
- 半瓶墨水. 所有布局 第 55 关 - 峰回路转 （中文简体）.
半瓶墨水注：已证实是二横最难，也是华容道最难得开局
以下为布局图形（左右对称的另一种情况本质相同）其中D单表1*1单块，H代表水平方向延伸的2*1块，V代表纵向延伸的1*2的块，B代表2*2的大块（曹操）
DDDV BBVV BBVV HHV DHH
變種
方塊名稱不同
- 另有一種在日本出現的變種，每塊方塊都使用將棋棋子名稱。
将棋版本的华容道
方塊排列不同
Pennant Puzzle
它還有很多名稱，例如 Dad's Puzzler 等等，由 L. W. Hardy 在 1909 年取得版權。它的玩法和華容道大致一樣，只是方塊排列和目的地位置有出入：
- 預設的方塊位置不同 (見右圖)，最大塊的正方形在左上角
- 除了 2x2 的正方形外，另外 8 塊分別為：兩塊 1x2，四塊 2x1，兩塊 1x1
- 出口在圍欄的左下角，不是在底部正中
目前已知最少需要 59 步完成遊戲。
電腦版本
最早出現的電腦版本是包含在Microsoft Windows 3.1 Game Pack內的其中一項小遊戲，需另外購置。
本遊戲在Gnome有一個版本，由Lars Rydlinge開發；在其他distro尚有其他版本。
方塊的形狀不同
日本有一個變種，是將其中一個大塊變成兩個兵，難度比原來的容易。 最近几年出现了“不动兵”、将大方块变成曲尺形的“异形”类布局或“蝶舞”类联动布局，难度比传统华容道大得多！
參見
- ^ 1.0 1.1 <《2000年来的那些游戏》 第2集 雅戏
- ^ 杜焕生. 《漫谈智力游戏华容道》. 中國: 宇航出版社. 1986-04 （簡體中文）.
- ^ http://www.g4g4.com/MyCD5/SOURCES/SOURCE2.DOC
- ^ U.S. Patent 1,017,752
- ^ An improved puzzle, and means therefor
- ^ 第十一屆電腦賽局發展學術研討會
- ^ 華容道簡史
- ^ “华容道”玩具不是中国人发明的
- ^ 圖說中國古代遊藝
- ^ 谈祥柏. 稳操胜券. 中國: 上海教育出版社. 2003-12-01. ISBN 753209220 请检查
|isbn=值 (帮助) （簡體中文）.
- 七巧板
- 三国演义
- 《七巧板、九连环和华容道:中国古典智力游戏三绝》，吴鹤龄编著，ISBN 7-03-013985-2
- 《漫谈智力游戏华容道》，杜焕生编著