数字推盘游戏

✍ dations ◷ 2025-09-15 21:30:43 #玩具,智力游戏,NP完全问题

数字推盘游戏(n-puzzle)是一种最早的滑块类游戏,常见的类型有十五数字推盘游戏和八数字推盘游戏等。也有以图画代替数字的推盘游戏。可能Noyes Palmer Chapman在1874年发明十五数字推盘,但Sam Loyd则在1891年也宣称为其发明。

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

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

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

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

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

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

相关

  • hCG人绒毛膜促性腺激素(英语:Human chorionic gonadotropin,简写为hCG)是一种糖蛋白激素,由胎盘的滋胚层细胞分泌,主要功能是刺激黄体,有利于雌激素和黄体酮持续分泌,以促进子宫蜕膜形
  • 阑尾切除手术阑尾切除术(appendectomy),是切除阑尾的手术。因阑尾位在盲肠附近,以往知道阑尾的人较少,因此也会误称割盲肠。一般病人会进行阑尾切除术的原因是因急性阑尾炎而相当疼痛,因此阑尾
  • 巴儿速孛罗巴儿速孛罗(蒙古语:Барсболд;1490年-1531年),清朝译作巴尔斯博罗特,蒙古大汗,达延汗的第三子,封为济农。达延汗本来指定长子图鲁博罗特的长子博迪为继承人。然而,在1517年达延
  • 缪天瑞缪天瑞(1908年-2009年8月31日),男,浙江瑞安人,中国音乐学家、音乐教育家、音乐翻译家、音乐编辑家,中国现代律学奠基人。被誉为“中国音乐期刊之父”。其著作《律学》一书对律学学
  • FooBillard 是免费的OpenGL台球游戏。首先支持Linux,有人移植到Mac OS X和Windows。拥有真实的物理引擎和AI,几种模式:是自由软件,遵循GPLv2其有趣的功能包括:
  • 南洲站2号线广佛线2号线广佛线南洲站是广州地铁二号线及广佛地铁的换乘站,位于广州海珠区南洲路东晓南路口南侧的地底,邻近海珠客运站。于2010年9月25日启用。南洲站共设有三层,地面
  • 东方诗集《东方诗集》(les Orientales)是法国作家维克多·雨果于1829年1月所出版的诗集。在该本诗集,作者雨果歌颂了希腊人民的民族解放运动。全集有41首诗,其中36首于1828年创作,诗中所
  • 相川茉穗相川茉穗(1999年3月26日-)日本神奈川县出身的歌手。原为早安家族所属团体ANGERME(前称S/mileage)的成员。血型为A型,身高为163公分,代表色为绿色。已于2017年12月31日宣布从ANGERME
  • 凯·贝利·哈奇森凯·贝利·哈奇森(英语:Kay Bailey Hutchison,1943年7月22日-),美国共和党籍政治人物,原德克萨斯州联邦参议员。哈奇森出生于德州加尔维斯敦,1962年毕业于德克萨斯州大学奥斯汀分校
  • 社会性懈怠社会惰化(英语:social loafing)也叫社会干扰、社会致弱、社会懈怠,是一个社会心理学术语,指群体一起完成一件工作时,每个成员所付出的努力会少于单独完成工作时的总和的现象。法国