数字推盘游戏

✍ dations ◷ 2025-09-09 14:42:25 #玩具,智力游戏,NP完全问题

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

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

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

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

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

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

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

相关

  • 牛乳牛乳,俗称牛奶,是最古老的天然饮料之一。顾名思义,牛乳是牛的乳汁。在不同国家,牛乳也分有不同的等级,目前最普遍的是全脂、高钙低脂及脱脂牛乳。美国将牛乳按照脂肪含量分为五类
  • pbs.org公共广播电视公司(英语:Public Broadcasting Service),也译作“美国公共电视网”或“美国公共电视台”,是美国公共电台和电视台节目发行渠道。它是一家非盈利组织,同时也是在美国
  • 球子蕨球子蕨(学名:Onoclea sensibilis)为球子蕨科球子蕨属下的一个种。
  • 白念珠菌白色念珠菌(学名:Candida albicans)是一种能造成伺机性感染的酵母菌,常见于人类消化道与泌尿生殖道的菌群,约有四成至六成健康成人的口腔与消化道中都有白色念珠菌,平时与人体行片
  • 盛京将军盛京将军(满语:ᠮᡠᡴ᠋ᡩᡝ᠋ᠨ  ᡳᠵᡳᠶᠠᠩᡤᡳᠶᡡᠨ,穆麟德:mukden i jiyanggiyūn),全称“镇守盛京等处将军”,又称奉天将军,为清朝从一品武职。清朝设盛京驻防将军一人。其
  • 高射炮高射炮又称防空炮,指用以从地面向空中目标射击的火炮,高射炮的特征是炮管长、射击准确、射速高、通常可360度回转,射击角度大,主要对付空中目标,口径一般不超过128毫米。在导弹尚
  • 安徽名人馆坐标:29°33′54″N 106°32′50″E / 29.56500°N 106.54722°E / 29.56500; 106.54722安徽名人馆建于2009年,位于安徽省合肥市滨湖新区,是有关安徽历史、文化及著名人物的博
  • 希里尤尔希里尤尔(Hiriyur),是印度卡纳塔克邦Chitradurga县的一个城镇。总人口48772(2001年)。该地2001年总人口48772人,其中男性24959人,女性23813人;0—6岁人口5844人,其中男3021人,女2823人
  • 大海,大海《大海,大海》(英语:The Sea, the Sea)是爱尔兰女作家艾瑞斯·梅铎创作的一部小说,1978年获得布克奖。《大海,大海》讲述了一个自满的剧作家及导演,在开始写回忆录时被奇怪的执念纠
  • 蝇王《蝇王》(英语:)是威廉·高丁发表于1954年的寓言体长篇小说。小说讲述了一群被困在荒岛上的儿童在完全没有成人的引导下如何建立起一个脆弱的文明体系。最终由于人类内心的黑暗