N Puzzle（数字推盘游戏）：从传统游戏到算法研究

N Puzzle（数字推盘游戏）：从传统游戏到算法研究

引用

CSDN

1.

https://blog.csdn.net/chengyq116/article/details/140504548

数字推盘游戏（N Puzzle）是一种经典的滑块类游戏，最早可以追溯到19世纪。游戏的目标是通过滑动方块，将打乱的数字顺序重新排列成正确的顺序。这种游戏不仅考验玩家的空间想象力和逻辑思维能力，而且在计算机科学领域，特别是算法研究中，N Puzzle也是一个重要的研究对象。

1. 15 Puzzle

15 Puzzle（也被称为Gem Puzzle、Boss Puzzle、Game of Fifteen、Mystic Square等）是一种滑动拼图游戏。它由15个编号为1到15的正方形瓷砖组成，这些瓷砖被放置在一个4x4的框架中，其中有一个空位。与空位在同一行或同一列的瓷砖可以通过水平或垂直滑动的方式移动。游戏的目标是将瓷砖按照数字顺序（从左到右，从上到下）排列。

这种游戏也被称为16 Puzzle，暗示其总容量为16个瓷砖（包括空位）。类似的名称也用于不同大小的变体，例如8 Puzzle，它有8个瓷砖在一个3x3的框架中。

八数字推盘又名重排九宫。

2. N Puzzle

N Puzzle（也称为Gem Puzzle、Boss Puzzle、Game of Fifteen、Mystic Square等）是一种滑动拼图游戏，由随机排列的编号正方形瓷砖组成，其中有一个瓷砖缺失。游戏的目标是通过滑动瓷砖来将它们按顺序排列。

这种拼图还存在其他尺寸的版本，特别是较小的8 Puzzle。如果尺寸为3x3瓷砖，则称为8 Puzzle；如果是4x4瓷砖，则称为15 Puzzle，以此类推。

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

参考文献

1. Yongqiang Cheng,https://yongqiang.blog.csdn.net/
2. The 15 Puzzle, Fifteen Puzzle, 14-15 Puzzle, Boss Puzzle,https://www.mathematische-basteleien.de/15puzzle.htm
3. N-Puzzle,https://tristanpenman.com/demos/n-puzzle/
4. Implementing A-star(A*) to solve N-Puzzle,https://algorithmsinsight.wordpress.com/graph-theory-2/a-star-in-general/implementing-a-star-to-solve-n-puzzle/
5. 8-puzzle,https://www.cnblogs.com/magic-sea/p/12081180.html