數字推盤遊戲
數字推盤遊戲(n-puzzle)是一種最早的滑塊類遊戲,常見的類型有十五數字推盤遊戲和八數字推盤遊戲等,因其遊玩的方式與另一個推盤遊戲華容道類似,故數字推盤也常被稱為數字華容道。也有以圖畫代替數字的推盤遊戲。可能Noyes Palmer Chapman在1874年發明十五數字推盤[1],但Sam Loyd則在1891年也宣稱為其發明[2][3]。
八數字推盤(又名重排九宮)則同樣是Noyes Palmer Chapman在1870年代發明[4],並且馬丁·加德納在科學人尋求更快的解答[5]。也有人宣稱重排九宮是傳統中國遊戲,來自洛書,並且為華容道的祖先[6]。
構造编辑
數字推盤遊戲由一塊有凹槽的板和數個寫有數字的大小相同的方塊所組成。
十五數字推盤遊戲的板上會有十五個方塊和一個大小相當於一個方塊的空位(供方塊移動之用)。而八數字推盤遊戲,為九宮格佈局,有八個方塊和一個空位。
遊戲規則编辑
遊戲者要移動板上的方塊,讓所有的方塊順著數字的次序排列。
解法编辑
寻找數字推盤遊戲的一个解相对容易,但寻找最优解是一个NP困难问题。[7][8]十五数字推盘的最优解至多有80步[9];而八数字推盘的最优解至多有31步。
可以使用A*算法寻找最优解。h(n)(启发式策略)可以是[10]
- 放错的方块的数量,
- 所有放错的方块到各自目标位置的距离之和。
群表示编辑
因为15塊的數字推盤遊戲组合可以由「3循環」(3-cycles)产生,所以可以证明15塊的數字推盤遊戲可以用交錯群 表示[11]。事實上,任何使用 塊相同面積正方形方塊的數字推盤遊戲皆可以以交錯群 表示。
參考條目编辑
參考文獻编辑
- ^ COS 226 Programming Assignment 8 Puzzle. [2010-01-30]. (原始内容存档于2021-01-07).
- ^ Sam Loyd's Fifteen. [2010-01-30]. (原始内容存档于2021-01-07).
- ^ The 15 Puzzle by Jerry Slocum and Dic Sonneveld. [2010-01-30]. (原始内容存档于2021-01-07).
- ^ 8 puzzle. [2010-11-11]. (原始内容存档于2020-09-08).
- ^ The Eight Puzzle. [2010-01-30]. (原始内容存档于2021-01-07).
- ^ 橫刀立馬華容道. [2016-05-18]. (原始内容存档于2021-01-07).
- ^ Daniel Ratner; Manfred K. Warmuth. Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable. National Conference on Artificial Intelligence. 1986.
- ^ Ratner, Daniel; Warmuth, Manfred. The (n2−1)-puzzle and related relocation problems. Journal of Symbolic Computation. 1990, 10 (2): 111–137. doi:10.1016/S0747-7171(08)80001-6.
- ^ A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications (页面存档备份,存于互联网档案馆), Annals of Operations Research 90 (1999), pp. 45–63.
- ^ Stuart Russell; Peter Norving. 人工智能——一种现代方法. 人民邮电出版社. 2010: 84–85. ISBN 978-7-115-23227-4.
- ^ Beeler, Robert. The Fifteen Puzzle: A Motivating Example for the Alternating Group (PDF). https://faculty.etsu.edu/. East Tennessee State University. [2020-12-26]. (原始内容存档 (PDF)于2021-01-07).
🔥 Top keywords: Baike: 首页淚之女王Special:搜索不夠善良的我們2024年湯姆斯盃金智媛2024年優霸盃金秀賢 (男演員)春色寄情人破墓怪獸8號乘風2024城市猎人排球少年!!背着善宰跑习近平承欢记張敬軒排球少年!!角色列表九龍城寨之圍城逆天奇案2BABYMONSTER六四事件ILLIT許瑋甯李主儐末日愚者與鳳行朴成焄鈴木亮平BOYNEXTDOOR方皓玟周處除三害 (電影)馬陸李美淑Seventeen (組合)崔永元完全省錢戀愛手冊921大地震机动战士GUNDAM SEED FREEDOM第二十条搜查班長1958NewJeans迷宮飯中華民國中华人民共和国林依晨愛的迫降葬送的芙莉蓮幕府將軍 (2024年電視劇)田馥甄三体 (小说)Energy (組合)(G)I-DLE傅崐萁周雨彤Believe-為你架起的橋樑-無職轉生~到了異世界就拿出真本事~Hide (电视剧)劉偉健劍星日本特技玩家徐譽庭郭東延黃道十二宮寄生獸:灰色部隊賀軍翔2024年花蓮地震支配物种朴智恩 (編劇)半生緣 (電影)HYBE邊佑錫WIND BREAKER—防風少年—柯震東香港來自星星的你宁安如梦鄭靚歆尹普美毛泽东白鹿 (演員)無職轉生~到了異世界就拿出真本事~角色列表戀愛兄妹草榴社区我獨自升級安東尼·布林肯李现LE SSERAFIM金秀賢影視作品列表少年歌行臧芮軒三流之路满城尽带黄金甲金正蘭但願人長久 (電影)国际劳动节P站