数字推盘游戏

✍ dations ◷ 2025-11-16 19:07:09 #玩具,智力游戏,NP完全问题

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

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

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

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

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

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

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

相关

  • 联邦安全会议副主席俄罗斯联邦安全会议(俄语:Совет Безопасности Российской Федерации,缩写СБ РФ)是一个直属于俄罗斯联邦总统的组织,主要任务在于为总统
  • 吴培亨吴培亨(1939年-),上海人,中国超导电子学家,南京大学教授。1939年生于上海。1961年毕业于南京大学物理系。现任南京大学超导电子学研究所所长,兼中国电子学会超导电子学分会主任。20
  • 布仑斯惕酸酸碱质子理论,又称布仑斯惕-劳里酸碱理论(英语:Brønsted–Lowry acid–base theory),是丹麦化学家约翰内斯·尼古劳斯·布仑斯惕和英国化学家托马斯·马丁·劳里于1923年各自独
  • 詹姆斯·帕金森詹姆斯·帕金森(英语:James Parkinson,1755年4月11日-1824年12月21日)是一位英国医生,地质学家,古生物学家,社会活动家。1755年出生于伦敦肖迪奇,1784年被伦敦市法团任命为外科医师。
  • 月亮和六便士《月亮和六便士》 是威廉·萨默塞特·毛姆的一本小说,以第一人称通过对中心人物查尔斯·思特里克兰德心灵的描述,展现一个中年英国股票经纪人如何突然扔下妻子和孩子去追寻成
  • 女性参政权女性参政权(英语:Women's suffrage,Woman suffrage),又称妇女参政权,意指在民主社会中,允许女性拥有平等参与选举投票以及担任候选人的政治权利。在人类历史的多数时期中,女性大多都
  • 台北市私立景文高级中学台北市私立景文高级中学(Taipei Jingwen High School),位于台北市文山区,附近有政治大学、世新大学、台湾戏曲学院、台北市立动物园。与台北市立文山特殊教育学校有教学合作关系
  • 奥伯恩岑湖坐标:49°26′55″N 10°27′16″E / 49.4485°N 10.4545°E / 49.4485; 10.4545奥伯恩岑湖(德语:Obernzenner See),是德国的湖泊,位于该国东南部,由巴伐利亚州负责管辖,处于艾施河
  • 肖恩·伊万斯肖恩·伊万斯(Shaun Evans,1980年3月6日-)是英国演员,家族来自北爱尔兰,或译“尚恩·伊凡斯”。他最著名的作品是在独立电视台电视剧《摩斯探长前传》出演摩斯(Morse)角色。
  • 奴隶丛书奴隶丛书,由鲁迅编印的一套文学丛书。奴隶丛书共出三种,分别为叶紫的《丰收》、萧红的《生死场》和萧军的《八月的乡村》。1935年,该书以“奴隶社”名义出版。《丰收》共收录了