N Puzzle (数字推盘游戏)

avatar
作者
筋斗云
阅读量:0

N Puzzle [数字推盘游戏]

puzzle /ˈpʌzl/:n. 谜,智力游戏,疑问,不解之谜,令人费解的事 vt. 迷惑,使困惑 

1. 15 Puzzle

https://en.wikipedia.org/wiki/15_puzzle

The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and more) is a sliding puzzle. It has 15 square tiles numbered 1 to 15 in a frame that is 4 tile positions high and 4 tile positions wide, with one unoccupied position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in numerical order (from left to right, top to bottom).
数字推盘游戏 (N Puzzle) 是一种最早的滑块类游戏,常见的类型有十五数字推盘游戏和八数字推盘游戏等,数字推盘也被称为数字华容道。

Named after the number of tiles in the frame, the 15 puzzle may also be called a 16 puzzle, alluding to its total tile capacity. Similar names are used for different sized variants of the 15 puzzle, such as the 8 puzzle, which has 8 tiles in a 3x3 frame.
八数字推盘又名重排九宫。

gem [dʒem]:n. (经切割打磨的) 宝石,难能可贵的人,风景优美的地方,美妙绝伦的事物 adj. (珠宝) 最佳品质的 v. 用宝石装饰 tile [taɪl]:n. 地砖,瓦片,(棋盘游戏的) 棋子 v. 铺瓦,铺地砖,贴瓷砖,平铺显示 mystic ['mɪstɪk]:n. 神秘主义者,潜修者 adj. 不可思议的,引起惊奇的,秘诀的,秘传仪式的 

在这里插入图片描述

Versions of the 15 puzzle include a different number of tiles, such as the 8-puzzle or 24-puzzle.
十五数字推盘游戏的板上会有十五个方块和一个大小相当于一个方块的空位,供方块移动之用。而八数字推盘游戏,为九宫格布局,有八个方块和一个空位。

2. N Puzzle

https://n-puzzle.baletskyi.me/

The N-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing.

The puzzle also exists in other sizes, particularly the smaller 8-puzzle. If the size is 3x3 tiles, the puzzle is called the 8-puzzle, and if 4x4 tiles, the puzzle is called the 15-puzzle named for the number of tiles and so on.

The object of the puzzle is to place the tiles in order by making sliding moves that use the empty space.

在这里插入图片描述

在这里插入图片描述

shuffle ['ʃʌf(ə)l]:n. 洗牌,拖着脚走,曳步舞 v. 拖着脚走,(笨拙或尴尬地) 把脚动来动去,坐立不安,洗 (牌) 

The N Puzzle is a classical problem for modeling algorithms involving heuristics.
寻找数字推盘游戏的一个解相对容易,但寻找最优解是一个 NP 困难问题。十五数字推盘的最优解至多有 80 步,而八数字推盘的最优解至多有 31 步。

References

[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

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!