数字推盘游戏

✍ dations ◷ 2025-04-03 12:44:50 #玩具,智力游戏,NP完全问题

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

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

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

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

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

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

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

相关

  • 二长岩二长岩是一种中性深成岩,岩性介于正长岩和闪长岩之间,碱性长石和斜长石的含量相等,含有30%的深色矿物,如果石英含量超过5%,不到20%,则称为石英二长岩,二长岩如果没有深入低壳而喷出
  • 廖正豪廖正豪(1946年3月30日-),台湾政治人物及法学家,中华民国台湾嘉义县人。毕业于国立台湾大学法律系,曾任台湾省政府官员、行政院副秘书长、中华民国法务部部长。胞兄是廖正雄,曾任六
  • 红门川河红门川河是北京地区的一条河流,为潮河的支流。发源于河北省兴隆县黄门子村,先后流经密云县3个乡,在邓家湾汇入潮河。全长20.5公里。沿途有达峪沟、碰合寺、龙门沟等10多条小支
  • 碳酸氢锂碳酸氢锂,化学式: LiHCO 3 {\displaystyle {\text{LiHCO}}_{3
  • 草麻黄草麻黄(学名:)为麻黄科麻黄属下的一个种。
  • 尹勋尹勋,字伯元,河南郡巩县(今河南省巩义市西南)人,东汉政治人物。伯父尹睦为司徒,兄尹颂为太尉,宗族多是担任政府要职,孝廉出身、曾任邯郸令、尚书令。在汉桓帝诛大将军梁冀时,勋参建大
  • 献贞王后献贞王后(헌정왕후,?-992年)皇甫氏,是高丽的第五代君主景宗的第四王妃,亦是高丽显宗之母。献贞王后是王旭(后追崇为戴宗)之女,为宣义王后柳氏所生,也是成宗王治和献哀王后之妹。嫁给堂
  • 湖南国货陈列馆湖南省国货陈列馆湖南长沙现存最大的民国时期建筑,地处黄兴路与蔡锷路之间的中山路。1930年由欧阳淑设计,张连生承建。湖南省国货陈列馆是旧长沙的标志性建筑和长沙商业文化的
  • 布永的戈弗雷布永的戈弗雷(布庸的的戈弗雷,Godefroy de Bouillon,约1060年-1100年7月18日,耶路撒冷),下洛林公爵(1087年-1100年在位,称戈弗雷四世),布永伯爵(1076年-1096年在位)和第一次十字军的将
  • 缅甸文学缅甸文学有始于蒲甘碑铭的说法,蒲甘时期著名的碑铭有《妙齐提碑》(《亚扎古曼碑》)等。有一千年历史的缅甸文学,其内容主要是诗歌。这是因为缅甸语言的独特性,使它的韵律感很强。