数字推盘游戏

数字推盘游戏（n-puzzle）是一种最早的滑块类游戏，常见的类型有十五数字推盘游戏和八数字推盘游戏等，因其游玩的方式与另一个推盘游戏华容道类似，故数字推盘也常被称为数字华容道。也有以图画代替数字的推盘游戏。可能Noyes Palmer Chapman在1874年发明十五数字推盘^[1]，但Sam Loyd则在1891年也宣称为其发明^[2][3]。

9数字推盘游戏解法

《总统推盘游戏》：彩色平版印刷的插图显示共和党参议员罗斯科·康克林在玩推盘游戏。盘中的方块包括格兰特、舍曼、蒂尔登和布莱恩等共和党总统候选人。推盘游戏模仿了著名的十五数字推盘游戏

八数字推盘（又名重排九宫）则同样是Noyes Palmer Chapman在1870年代发明^[4]，并且马丁·加德纳在科学人寻求更快的解答^[5]。也有人宣称重排九宫是传统中国游戏，来自洛书，并且为华容道的祖先^[6]。

十五数字推盘游戏。

构造

数字推盘游戏由一块有凹槽的板和数个写有数字的大小相同的方块所组成。

十五数字推盘游戏的板上会有十五个方块和一个大小相当于一个方块的空位（供方块移动之用）。而八数字推盘游戏，为九宫格布局，有八个方块和一个空位。

游戏规则

游戏者要移动板上的方块，让所有的方块顺著数字的次序排列。

解法

寻找数字推盘游戏的一个解相对容易，但寻找最优解是一个NP困难问题。^[7][8]十五数字推盘的最优解至多有80步^[9]；而八数字推盘的最优解至多有31步。

可以使用A*算法寻找最优解。h(n)（启发式策略）可以是^[10]

1. 放错的方块的数量，
2. 所有放错的方块到各自目标位置的距离之和。

群表示

因为15块的数字推盘游戏组合可以由“3循环”（3-cycles）产生，所以可以证明15块的数字推盘游戏可以用交错群${\displaystyle A_{15}}$表示^[11]。事实上，任何使用${\displaystyle 2\times k-1}$块相同面积正方形方块的数字推盘游戏皆可以以交错群${\displaystyle A_{2k-1}}$表示。

参考条目

• 旋转方块
• 魔方群

参考文献

1. COS 226 Programming Assignment 8 Puzzle. [2010-01-30]. （原始内容存档于2021-01-07）.
2. Sam Loyd's Fifteen. [2010-01-30]. （原始内容存档于2021-01-07）.
3. The 15 Puzzle by Jerry Slocum and Dic Sonneveld. [2010-01-30]. （原始内容存档于2021-01-07）.
4. 8 puzzle. [2010-11-11]. （原始内容存档于2020-09-08）.
5. The Eight Puzzle. [2010-01-30]. （原始内容存档于2021-01-07）.
6. 橫刀立馬華容道. [2016-05-18]. （原始内容存档于2021-01-07）.
7. 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 (帮助)
8. Ratner, Daniel; Warmuth, Manfred. The (n²−1)-puzzle and related relocation problems. Journal of Symbolic Computation. 1990, 10 (2): 111–137. doi:10.1016/S0747-7171(08)80001-6. 引文使用过时参数coauthors (帮助)
9. 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.
10. Stuart Russell; Peter Norving. 人工智能——一种现代方法. 人民邮电出版社. 2010: 84–85. ISBN 978-7-115-23227-4. 引文使用过时参数coauthors (帮助)
11. Beeler, Robert. The Fifteen Puzzle: A Motivating Example for the Alternating Group (PDF). https://faculty.etsu.edu/. East Tennessee State University. [2020-12-26]. （原始内容存档 (PDF)于2021-01-07）.