数字推盘游戏

✍ dations ◷ 2025-07-08 17:37:52 #玩具,智力游戏,NP完全问题

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

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

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

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

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

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

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

相关

  • 庞贝氏症庞贝氏症(英语:Pompe disease),又称为酸性麦芽糖酵素缺乏症(acid maltase deficiency, AMD)或糖原贮积症第二型(glycogen storage disorder, GSD; glycogenosis II),是一种罕见疾病,成
  • T7 RNA聚合酶T7 RNA聚合酶(英语:T7 RNA Polymerase)是一种RNA聚合酶,分子量约99kDa。专门催化5'→3'方向的RNA形成过程。T7RNA聚合酶具有高度启动子专一性,且只会转录T7噬菌体中位于T7启动子
  • 方豪方豪(1910年9月15日-1980年12月20日),字傑人,后改杰人,笔名芳庐,绝尘,圣老。浙江杭县人,原籍浙江诸暨。中国现代天主教神父、历史学家。出生于基督教圣公会家庭,1920年1月9日,全家改信
  • 宁夏军区中国人民解放军宁夏军区,是中国人民解放军现属中央军委国防动员部的一个省级军区,管辖范围为宁夏回族自治区。主席(党、国)副主席(党、国)委员(党、国)军种: 陆军  海军  空军  火
  • 伊莱贾·伍德伊莱贾·乔丹·伍德(英语:Elijah Jordan Wood,1981年1月28日-)是一位美国男演员,代表作品的知名角色有《指环王电影三部曲》的主角佛罗多·巴金斯。银幕初登作为《回到未来2》(1989
  • 核桃市核桃市(英文:Walnut)中文又音译为沃尔纳特,是一座位于美国加利福尼亚州洛杉矶郡、富裕而宁静的城市,素有“小瑞士”之美誉,经常名列全美最宜居小城市及最适合抚养小孩的城市。核桃
  • 伊拉克北部内战伊斯兰国取得初期胜利伊拉克叙利亚伊朗支持:伊拉克库尔德斯坦伊斯兰国伊拉克伊斯兰军伊拉克复兴党支持者战役及冲突事件大规模攻击外国势力介入伊斯兰国的群体灭绝伊斯兰国的
  • 豪情四海《豪情四海》(英语:)是1991年的美国犯罪电影,由巴瑞·李文森执导。内容讲述黑帮Bugsy Siegel与Virginia Hill(英语:Virginia Hill)之间的关系。华伦·比提、安纳·贝宁主演。由Jame
  • 中国传媒大学出版社中国传媒大学出版社是中华人民共和国的一家出版社,成立于1985年,社址位于北京市,由中华人民共和国教育部主管,中国传媒大学主管主办。1985年,北京广播学院出版社成立。2004年9月
  • 韩国联合通讯社韩国联合通讯社,又译联合通讯社,简称韩联社、YNA,是韩国的官方通讯社,也是韩国最大的通讯社。韩联社的总部在首尔,为韩国的报纸、广播、电视和其他媒体提供新闻。韩联社与65家非