華容道

華容道，英文稱 Klotski (來自波蘭語的 klocki，意指木塊)，是一種滑塊遊戲，由放在方形盘中的10块方片拼成，目標是在只滑動方塊而不從棋盤中拿走的情況下，將最大的一塊移到底部出口。

[编辑] 玩法

最大的一块代表曹操，其余九块分别代表关羽、张飞、赵云、马超和黄忠及4个小兵。各方块的起始位置可以根据开局不同有变化，但传统的摆法是将曹操置于方盘上方的中间，周围围绕着五虎将和小兵。游戏的玩法是移动这10块方块，将代表曹操的一块移动到最下方中间的空位。

一般玩法分兩種：移動最少次數，或者用最少的時間來完成遊戲。

[编辑] 故事

故事源于《三国演义》中“诸葛亮智算华容，关云长义释曹操”的故事，指赤壁之戰曹操兵敗被迫逃走，最後到華容道時關羽顧念舊情，網開一面讓曹操離去。正因為這個故事，所以華容道有時又稱為捉放曹。

[编辑] 歷史

不少人都認為华容道是一种古老的中国智力游戏，不過沒有任何實質證據支持，不論是考古學還是古籍都沒有。反而不是源自中國的證據卻有很多。

據姜長英在他所著《科學思維鍛煉與消遣》說，「估計它的歷史不過有幾十年。從前人的筆記中沒有發現有玩具華容道的記載」；最早記載華容道的，就是他自己在1949年出版的另一本書《科學消遣》(找不到出版紀錄)。

另一本有記載華容道的是許蒓舫的《數學漫談》(華義印刷，1952年3月出版)，給出了 100 步的解法。

[编辑] 解法

最少的步數為 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 的方塊連續移動兩格只算一步。

[编辑] 變種

[编辑] 方塊名稱不同

• 在第二次世界大戰時期的日本出現了排列幾乎一模一樣，但是方塊名稱改變了的遊戲，名稱為「箱入り娘」。

• 另有一種在日本出現的變種，每塊方塊都使用將棋棋子名稱。

[编辑] 方塊排列不同

[编辑] Pennant Puzzle

Pennant Puzzle / Dad's Puzzler

它還有很多名稱，例如 Dad's Puzzler 等等，由 L. W. Hardy 在 1909 年取得版權。它的玩法和華容道大致一樣，只是方塊排列和目的地位置有出入：

1. 預設的方塊位置不同 (見右圖)，最大塊的正方形在左上角
2. 除了 2x2 的正方形外，另外 8 塊分別為：兩塊 1x2，四塊 2x1，兩塊 1x1
3. 出口在圍欄的左下角，不是在底部正中

目前已知最少需要 59 步完成遊戲。

[编辑] 電腦版本

[编辑] 參見

• 七巧板
• 三国演义

[编辑] 外部鏈結

• 同濟大学數學建模協會第 6 期會刊中有關華容道電腦解法的文章
• 國立臺灣師範大學資訊教育系的魏仲良、林順喜有關華容道電腦解法的文章