數字推盤遊戲
9數字推盤遊戲解法
《總統推盤遊戲》：彩色平版印刷的插圖顯示共和黨參議員羅斯科·康克林在玩推盤遊戲。盤中的方塊包括格蘭特、舍曼、蒂爾登和布萊恩等共和黨總統候選人。推盤遊戲模仿了著名的十五數字推盤遊戲
數字推盤遊戲（n-puzzle）是一種最早的滑塊類遊戲，常見的類型有十五數字推盤遊戲和八數字推盤遊戲等。也有以圖畫代替數字的推盤遊戲。可能Noyes Palmer Chapman在1874年發明十五數字推盤[1]，但Sam Loyd則在1891年也宣稱為其發明[2][3]。
八數字推盤（又名重排九宮）則同樣是Noyes Palmer Chapman在1870年代發明[4]，並且馬丁·加德納在科學人尋求更快的解答[5]。也有人宣稱重排九宮是傳統中國遊戲，來自洛書，並且為華容道的祖先[6]。
十五數字推盤遊戲。
目录
1 構造
2 遊戲規則
3 解法
4 參考
構造
數字推盤遊戲是由一塊有凹槽的板和數個寫有數字的大小相同的方塊所組成。
十五數字推盤遊戲的板上會有十五個方塊和一個大小相當於一個方塊的空位（供方塊移動之用）。而八數字推盤遊戲，為九宮格佈局，有八個方塊和一個空位。
遊戲規則
遊戲者要移動板上的方塊，讓所有的方塊順著數字的次序排列。
解法
寻找數字推盤遊戲的一个解相对容易，但寻找最优解是一个NP困难问题。[7][8]十五数字推盘的最优解至多有80步[9]；而八数字推盘的最优解至多有31步。
可以使用A*算法寻找最优解。h(n)（启发式策略）可以是[10]
- 放错的方块的数量，
- 所有放错的方块到各自目标位置的距离之和。
參考
^ COS 226 Programming Assignment 8 Puzzle
^ Sam Loyd's Fifteen
^ The 15 Puzzle by Jerry Slocum and Dic Sonneveld
^ 8 puzzle
^ The Eight Puzzle
^ 橫刀立馬華容道
^ Daniel Ratner; Manfred K. Warmuth. Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable. National Conference on Artificial Intelligence. 1986. 引文使用过时参数coauthors (帮助)
^ Ratner, Daniel; Warmuth, Manfred. The (n2−1)-puzzle and related relocation problems. Journal of Symbolic Computation. 1990, 10 (2): 111–137. doi:10.1016/S0747-7171(08)80001-6. 引文使用过时参数coauthors (帮助)
^ 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.
^ Stuart Russell; Peter Norving. 人工智能——一种现代方法. 人民邮电出版社. 2010: 84–85. ISBN 978-7-115-23227-4. 引文使用过时参数coauthors (帮助)
