15-puzzle

簡介

15 - 拼圖（英文：15-puzzle, 又名 Gem Puzzle，Boss Puzzle，Game of 15，Mystic Square，N-puzzle, etc）是一個滑塊類遊戲（英文：sliding puzzle）。滑塊方盤的長寬均為 \(4\times 4\) 個方塊，其中 15 個位置放序號打亂的方塊，剩下一個為空位。與空位同行或同列的方塊可以通過水平或垂直滑動來移動。拼圖的目標是按編號順序排列方塊。

15 - 拼圖常見別稱為 n - 拼圖，其中數字 \(n\) 指的是方盤中的方塊總數。15 - 拼圖的不同尺寸變體亦使用了類似的名稱，例如 \(8\) 拼圖指的是置於 \(3\times3\) 方盤中的 \(8\) 個方塊。但 \(15\) 拼圖也可以稱為 \(16\) 拼圖，此處的 16 指的是方塊容量。它的擴展問題有時也包括了 \(n \times m\) 的滑動方盤。

15 - 拼圖是涉及啓發式算法建模的經典問題。此問題的常見形式是曼哈頓距離和錯位方塊的數量計算，二者都是可接受啓發（英文：admissible heuristic），即它們永遠不會高估剩餘的移動次數，這確保了某些搜索算法（例如 A * 算法）的最優性。

註釋

滑塊遊戲 是一類在平面上滑動方塊以組成特定排列的智力遊戲。常見的滑塊遊戲包括數字拼圖、華容道和塞車時間。其中 15 - 拼圖是最古老的滑塊類遊戲，發明者是 Noyes Chapman，該遊戲風靡於 1880 年代。不像其它 tour 類的解謎遊戲，滑塊遊戲禁止任何一個方塊離開盤面，這個特性區別於重新排列類的解謎遊戲。

定義

給定一個 \(4 \times 4\) 的方盤，其中 \(15\) 個方塊隨意排列。我們需要將它按照序號排列成下圖所示的樣子。移動規則為每次只能交換空方塊和和其相鄰一個方塊的位置。常見問題為找到可解決此問題的最少步驟，計算錯位方位的個數，或找出是和否能得到最終的有序排列。

①②③④

⑤⑥⑦⑧

⑨⑩⑪⑫

⑬⑭⑮口

可解性證明

Johnson & Story (1879) 證明，如果 \(m\) 和 \(n\) 都至少為 \(2\)，則逆向適用於大小為 \(m\times n\) 的棋盤：通過從 \(m=n=2\) 開始對 \(m\) 和 \(n\) 進行歸納證明，所有偶數排列都是可解的。Archer (1999) 給出了另一個證明，基於通過漢密爾頓路徑定義等價類。

算法

尋找數字滑盤遊戲的一個解相對容易，但尋找 最優解 是一個 NP 困難 問題。15-Puzzle 的最優解至多有 80 步；而 8-Puzzle 的最優解至多有 31 步。

N-Puzzle 支持常見的基於圖的搜索算法，如廣度優先搜索和深度優先搜索，同樣我們也可以用 A * 搜索算法尋找最優解。啓發式函數 \(h(n)\) 可以是

放錯的方塊的數量。
所有放錯的方塊到各自目標位置的歐幾里得距離之和。
所有放錯的方塊到各自目標位置的曼哈頓距離之和。

羣理論

因為 15 塊的數字推盤遊戲組合可以由「3 循環」（英文：3-cycles）產生，所以可以證明 15 塊的數字推盤遊戲可以用交錯羣 \(A_{15}\) 表示。事實上，任何使用 \(2\times k-1\) 塊相同面積正方形方塊的數字滑盤遊戲皆可以以交錯羣 \(A_{2k-1}\) 表示。

習題

參考資料與拓展閲讀

15 puzzle - Wikipedia
jrdnjacobson,How to Solve the 15 Puzzle - instructables
Korf, R. E. (2000),"Recent Progress in the Design and Analysis of Admissible Heuristic Functions", in Choueiry, B. Y.; Walsh, T. (eds.), Abstraction, Reformulation, and Approximation (PDF), SARA 2000. Lecture Notes in Computer Science, vol. 1864, Springer, Berlin, Heidelberg, pp. 45–55, doi:10.1007/3-540-44914-0_3, ISBN 978-3-540-67839-7, retrieved 2010-04-26
Welcome to N-Puzzle - web demo

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用