数字推盘游戏
数字推盘游戏（n-puzzle）是一种最早的滑块类游戏，常见的类型有十五数字推盘游戏和八数字推盘游戏等，因其游玩的方式与另一个推盘游戏华容道类似，故数字推盘也常被称为数字华容道。也有以图画代替数字的推盘游戏。可能Noyes Palmer Chapman在1874年发明十五数字推盘[1]，但Sam Loyd则在1891年也宣称为其发明[2][3]。
八数字推盘（又名重排九宫）则同样是Noyes Palmer Chapman在1870年代发明[4]，并且马丁·加德纳在科学人寻求更快的解答[5]。也有人宣称重排九宫是传统中国游戏，来自洛书，并且为华容道的祖先[6]。
构造[编辑]
数字推盘游戏由一块有凹槽的板和数个写有数字的大小相同的方块所组成。
十五数字推盘游戏的板上会有十五个方块和一个大小相当于一个方块的空位（供方块移动之用）。而八数字推盘游戏，为九宫格布局，有八个方块和一个空位。
游戏规则[编辑]
游戏者要移动板上的方块，让所有的方块顺着数字的次序排列。
解法[编辑]
寻找数字推盘游戏的一个解相对容易，但寻找最优解是一个NP困难问题。[7][8]十五数字推盘的最优解至多有80步[9]；而八数字推盘的最优解至多有31步。
可以使用A*算法寻找最优解。h(n)（启发式策略）可以是[10]
- 放错的方块的数量，
- 所有放错的方块到各自目标位置的距离之和。
群表示[编辑]
因为15块的数字推盘游戏组合可以由“3循环”（3-cycles）产生，所以可以证明15块的数字推盘游戏可以用交错群表示[11]。事实上，任何使用块相同面积正方形方块的数字推盘游戏皆可以以交错群表示。
参考条目[编辑]
参考文献[编辑]
- ^ COS 226 Programming Assignment 8 Puzzle. [2010-01-30]. （原始内容存档于2021-01-07）.
- ^ Sam Loyd's Fifteen. [2010-01-30]. （原始内容存档于2021-01-07）.
- ^ The 15 Puzzle by Jerry Slocum and Dic Sonneveld. [2010-01-30]. （原始内容存档于2021-01-07）.
- ^ 8 puzzle. [2010-11-11]. （原始内容存档于2020-09-08）.
- ^ The Eight Puzzle. [2010-01-30]. （原始内容存档于2021-01-07）.
- ^ 橫刀立馬華容道. [2016-05-18]. （原始内容存档于2021-01-07）.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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）.