華容道 (遊戲)
華容道(英語:Klotski,來自波蘭文的klocki,意為木塊)是一種滑塊類遊戲,由放在方形盤中的10塊方片拼成,目標是在只滑動方塊而不從棋盤中拿走的情況下,將最大的一塊移到底部出口。華容道最早起源於19世紀末20世紀初的波蘭,而現在的最常見的4個1 × 1、 5個1 × 2以及一個2 × 2的這種搭配是由英國人John Harold Fleming 在1932年發明並申請的專利。全球各地都有一些華容道的愛好者研究者[1]。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/NTPC-SHJH_HuaRongDao_2013-06.jpg/220px-NTPC-SHJH_HuaRongDao_2013-06.jpg)
玩法
編輯像其他的種類的滑塊遊戲,在一個方形盒子內放置了大小不同的方塊,一般是4x5大小。在這些方塊中有特殊的一個(一般是最大的)必須被移動到設計好的指定地點。玩家不允許拿起方塊,只可向平行或垂直的方向移動方塊,常見的玩法是移動最少次數,或者用最少的時間來完成遊戲。
歷史
編輯- 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年代,上海玩具十四廠和上海長春塑料廠曾把華容道製作成塑料玩具,沒有武將名字,只是薄的彩色塑料片,被命名為「船塢排檔」。
- 1956年8月號的《數學通訊》雜誌上,在封面的小知識欄目中提出了「關羽放曹」遊戲。1959年5月號和6月號的《遼寧畫報》上也刊登了這個遊戲,命名為「趕走紙老虎」。
- 1982年9月號《我們愛科學》雜誌刊登數學家談祥柏寫的《華容道》。
- 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
編輯它還有很多名稱,例如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快速實現 (頁面存檔備份,存於網際網路檔案館)