華容道（英語：Klotski，來自波蘭文的klocki，意為木塊）是一種滑塊類遊戲，由放在方形盘中的10块方片拼成，目標是在只滑動方塊而不從棋盤中拿走的情況下，將最大的一塊移到底部出口。华容道最早起源于19世纪末20世纪初的波兰，而现在的最常见的4个1 × 1、 5个1 × 2以及一个2 × 2的这种搭配是由英国人John Harold Fleming 在1932年发明并申请的专利。全球各地都有一些华容道的爱好者研究者[1]。
塑膠製的華容道玩具
目录
1 玩法
2 歷史
2.1 在中國的流傳
3 解法
3.1 變種解法
4 變種
4.1 方塊名稱不同
4.2 方塊排列不同
4.2.1 Pennant Puzzle
4.3 電腦版本
4.4 方塊的形狀不同
5 應用
6 參見
7 参考文献
8 外部連結
玩法
编辑
像其他的种类的滑块游戏，在一个方形盒子内放置了大小不同的方块，一般是4x5大小。在这些方块中有特殊的一个（一般是最大的）必须被移动到设计好的指定地点。玩家不允许拿起方块，只可向平行或垂直的方向移动方块，常见的玩法是移動最少次數，或者用最少的時間來完成遊戲。
还有一种数字华容道，游戏目标是将数字按照从小到大的顺序排列，空格位于最后。一般有3×3、4×4、5×5大小，每个方格包含 1 到 n²-1 的数字，以及一个空格。只能通过将数字移动到相邻的空格位置来重新排列数字；当所有数字按顺序排列（1 到 n²-1），且空格在最后时，游戏获胜。
歷史
编辑
Lewis W. Hardy在1909年获得了名为智取奪旗（Pennant Puzzle）的专利，是華容道的前身，并被芝加哥的OK Novelty公司生产。[2]他还在1907-12-14申请了美国专利美國專利第1,017,752号并在1912-02-20通过[3]。
1932年，John Harold Fleming在英國申請專利（英國专利号411515），已與現代的華容道一模一樣，並也提供了橫刀立馬的解法[4]。
在中國的流傳
编辑
《科学消遣》（Science Pastime）是中國最早对于华容道游戏的记录之一，作者是一位中国教授姜长英，写于1949年。其称「估計它的歷史不過有幾十年。從前人的筆記中沒有發現有玩具華容道的記載。」[5]
40年代，华容道玩具在上海就很流行。50年代初期，上海地摊上有薄纸印制的华容道玩具出售。后来，上海文具店里也出售过木制的华容道玩具。60年代，上海玩具十四厂和上海长春塑料厂曾把华容道制作成塑料玩具，没有武將名字，只是薄的彩色塑料片，被命名为“船塢排檔”。
1943年，新四軍文化教員梁青從蘇北的人民群众那裡學會華容道，並將其在新四軍推廣。梁青還收集整理了華容道不同的佈局，並給每一個佈局都起了一個相應的名字。[6]
1956年8月号的《数学通讯》杂志上，在封面的小知识栏目中提出了“关羽放曹”游戏。1959年5月号和6月号的《辽宁画报》上也刊登了这个游戏，命名为“赶走纸老虎”。
1982年9月号《我们爱科学》杂志刊登數學家谈祥柏写的《华容道》。
1984年9月，在北京市少年宫，由《我们爱科学》杂志社和首钢带钢厂粉末冶金厂联合举办少年华容道计时比赛，完成横刀立马局的最少时间是15秒。
1985年1月5日，中国中央电视台在少年儿童节目里播放了《小游戏“华容道”》，由余俊雄供稿，介绍了华容道的规则和历史。
1987年，余俊雄在《独粒钻石和华容道——迷人的智力游戏》認為華容道是來自洛書。之後人們就在填纵横图的基础上，发明了一种数学游戏——重排九宫。又说大约在元朝时傳到歐洲。但是这里的说法经不起推敲。首先重排九宫游戏在中國历史上从来没有任何文献记载或实物证据。至于元朝传入西方，这恐怕更是作者的凭空想象。余俊雄是北京玩具协会益智玩具委员会主任，热衷于推广中国古典数学玩具。从2002年起，北京玩具协会和中国科技馆举办了中国古典数学玩具展，把华容道列入其中，使得谬误传播开。[7]
2002年著作《圖說中國古代遊藝》，介紹了中國自古傳統的智力遊戲七巧板、九連環，而無華容道[8]。
2003年谈祥柏翻譯Elwyn R. Berlekamp、John Conway、Richard Guy在1982年合著《Winnings Ways:for your mathematical plays》，書名《稳操胜券》。書中引介了許多華容道的排法[9]。
2004年吴鹤龄在其著作《七巧板、九连环和华容道：中国古典智力游戏三绝》，認為「把華容道看做是從西方傳入以後本地化的產物，倒是比較合乎事實和邏輯的」。從無出現民國前的華容道玩具實體或文獻記載。
中國人之所以誤認华容道為其傳統遊戲，赋予这么悠久的历史，是因为它的故事背景出自於《三国演义》第五十回。[10]
解法
编辑
横刀立马布局最少的步數為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 （页面存档备份，存于互联网档案馆）
將擁曹營: 72 （页面存档备份，存于互联网档案馆）
橫馬當關: 83 （页面存档备份，存于互联网档案馆）
前擋後堵: 42 （页面存档备份，存于互联网档案馆）（又名前擋後阻）
兵擋將阻: 87 （页面存档备份，存于互联网档案馆）
兵臨城下: 54 （页面存档备份，存于互联网档案馆）
一路進軍: 58 （页面存档备份，存于互联网档案馆）
一路順風: 39 （页面存档备份，存于互联网档案馆）
兵臨曹營: 34 （页面存档备份，存于互联网档案馆）
雨聲淅瀝: 47 （页面存档备份，存于互联网档案馆）
桃花園中: 70 （页面存档备份，存于互联网档案馆）
捷足先登: 32 （页面存档备份，存于互联网档案馆）
圍而不殲: 62 （页面存档备份，存于互联网档案馆）
將守角樓: 70 （页面存档备份，存于互联网档案馆）（又名指揮若定）
巧過五關: 34 （页面存档备份，存于互联网档案馆）
屯兵東路: 71 （页面存档备份，存于互联网档案馆）
比翼橫空: 28 （页面存档备份，存于互联网档案馆）
峰迴路轉: 138 （页面存档备份，存于互联网档案馆）
利用计算机逐个枚举开局排法并暴力搜索最少步数解法，验证得到的最优解需要步数最多的一种布局被命名为 “峰迴路轉”，需要138步。
部分取自“同濟大學數學建模協會的第6期會刊”的布局只有名稱及最佳步數，而無布局圖，如: 五虎攔路、兵將連環等；經查找原參考書籍“獨立鑽石和華容道”取得其原布局圖。[11]。
變種
编辑
方塊名稱不同
编辑
在第二次世界大戰時期的日本出現了排列幾乎一模一樣，但是方塊名稱改變了的遊戲，名稱為「箱入り娘」。其中最大的方块称为“娘”（女儿），其他的方块也相应的以家庭成员来命名。 日本的“箱入り娘”
另有一種在日本出現的變種，每塊方塊都使用將棋棋子名稱。 将棋版本的华容道
方塊排列不同
编辑
Pennant Puzzle
编辑
Pennant Puzzle / Dad's Puzzler
它還有很多名稱，例如Dad's Puzzler等等，由L. W. Hardy在1909年取得版權。它的玩法和華容道大致一樣，只是方塊排列和目的地位置有出入：
預設的方塊位置不同（見右圖），最大塊的正方形在左上角
除了2x2的正方形外，另外8塊分別為：兩塊1x2，四塊2x1，兩塊1x1
出口在圍欄的左下角，不是在底部正中
目前已知最少需要59步完成遊戲。
電腦版本
编辑
最早出現的電腦版本是包含在微軟為Windows 3.X開發的娛樂包的其中一項小遊戲，需另外購置。
本遊戲在Gnome有一個版本，由Lars Rydlinge開發；在其他distro尚有其他版本。
方塊的形狀不同
编辑
日本有一個變種，是將其中一個大塊變成兩個兵，難度比原來的容易。
最近几年出现了“不动兵”、将大方块变成曲尺形的“异形”类布局或“蝶舞”类联动布局，难度比传统华容道大得多。
應用
编辑
有些立體停車場利用華容道的原理任意移動車子，使車主能夠在一樓不必開車上下樓找車位就能停車和取車。但是當停車場樓層多且車流量大時，可能因為移動車子步驟多而增加等待時間。
參見
编辑
倉庫番
七巧板
三国演义
《七巧板、九连环和华容道:中国古典智力游戏三绝》，吴鹤龄编著，ISBN 978-7-03-013985-6
《漫谈智力游戏华容道》，杜焕生编著
参考文献
编辑
^ 杜焕生. 《漫谈智力游戏华容道》. 中國: 宇航出版社. 1986-04 （中文（简体））.
^ 存档副本. [2008-07-08]. （原始内容存档于2007-10-26）.
^ U.S. Patent 1,017,752
^ An improved puzzle, and means therefor
^ 第十一屆電腦賽局發展學術研討會. [2010-01-29]. （原始内容存档于2019-11-22）.
^ 華容道簡史
^ “华容道”玩具不是中国人发明的. [2010-01-30]. （原始内容存档于2020-01-14）.
^ 崔樂泉. 《圖說中國古代遊藝》. 臺灣: 文津出版社. 2003-04-01. ISBN 9789576687037 （中文（臺灣））.
^ 谈祥柏. 《稳操胜券》. 中國: 上海教育出版社. 2003-12-01. ISBN 7532092208 （中文（中国大陆））.
^ 《两千年来的那些游戏》第2集 雅戏. [2022-05-22]. （原始内容存档于2022-07-05）.
^ 郭正誼, 余俊雄. 《獨立鑽石和華容道──迷人的智力遊戲》 (PDF). 中國: 氣象出版社. 1987-06: 122 [2022-07-18]. ISBN 7-5029-0005-5. （原始内容 (PDF)存档于2022-05-31） （中文（中国大陆））.
外部連結
编辑
同濟大学數學建模協會第6期會刊中有關華容道電腦解法的文章
國立臺灣師範大學資訊教育系的魏仲良、林順喜有關華容道電腦解法的文章 （页面存档备份，存于互联网档案馆）
黃志華關於華容道的研究 （页面存档备份，存于互联网档案馆）
谜一样的源头·华容道 （页面存档备份，存于互联网档案馆）
滑板遊戲博物館 （页面存档备份，存于互联网档案馆）（英文）
Gnome Klotski （页面存档备份，存于互联网档案馆） （英文）
游戏发芽网的在线的华容道游戏，可动态回放过关记录
在线的华容道最短路径求解程序
华容道online game[永久失效連結]
华容道各种玩法研究
滑块游戏世界
華容道遊戲與解法 （页面存档备份，存于互联网档案馆）
华容道算法的JavaScript快速实现 （页面存档备份，存于互联网档案馆）