數字推盤遊戲

數字推盤遊戲（n-puzzle）是一種最早的滑塊類遊戲，常見的類型有十五數字推盤遊戲和八數字推盤遊戲等，因其遊玩的方式與另一個推盤遊戲華容道類似，故數字推盤也常被稱為數字華容道。也有以圖畫代替數字的推盤遊戲。可能Noyes Palmer Chapman在1874年發明十五數字推盤，但薩姆·勞埃德則在1891年也宣稱為其發明。

八數字推盤（又名重排九宮）則同樣是Noyes Palmer Chapman在1870年代發明，並且馬丁·加德納在科學人尋求更快的解答。也有人宣稱重排九宮是傳統中國遊戲，來自洛書，並且為華容道的祖先。


 構造 

數字推盤遊戲由一塊有凹槽的板和數個寫有數字的大小相同的方塊所組成。

十五數字推盤遊戲的板上會有十五個方塊和一個大小相當於一個方塊的空位（供方塊移動之用）。而八數字推盤遊戲，為九宮格佈局，有八個方塊和一個空位。

 遊戲規則 

遊戲者要移動板上的方塊，讓所有的方塊順著數字的次序排列。

 解法 
寻找數字推盤遊戲的一个解相对容易，但寻找最优解是一个NP困难问题。十五数字推盘的最优解至多有80步A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications , Annals of Operations Research 90 (1999), pp. 45–63.；而八数字推盘的最优解至多有31步。

可以使用A*算法寻找最优解。h(n)（启发式策略）可以是
 放错的方块的数量，
 所有放错的方块到各自目标位置的距离之和。

 15-14問題 

薩姆曾經在19世紀末提出懸賞，獎勵能解決在4×4數字推盤遊戲15和14對調的人1,000美元（2024年折合通貨膨脹為34,996美元），直至最後無人解決。

群表示
因为15塊的數字推盤遊戲组合可以由「3循環」（3-cycles）产生，所以可以证明15塊的數字推盤遊戲可以用交錯群表示。事實上，任何使用塊相同面積正方形方塊的數字推盤遊戲皆可以以交錯群表示。

參考條目
旋轉方塊
魔方群

參考文獻

Category:玩具
Category:智力游戏
Category:NP完全问题