查看“︁數字推盤遊戲”︁的源代码

[[File:Batgirl.gif|thumb|9數字推盤遊戲解法]]
[[File:Great presidential puzzle2.jpg|thumb|《總統推盤遊戲》：彩色平版印刷的插圖顯示共和黨參議員羅斯科·康克林在玩推盤遊戲。盤中的方塊包括格蘭特、舍曼、蒂爾登和布萊恩等共和黨總統候選人。推盤遊戲模仿了著名的十五數字推盤遊戲]]
'''數字推盤遊戲'''（n-puzzle）是一種最早的[[滑塊類遊戲]]，常見的類型有十五數字推盤遊戲和八數字推盤遊戲等，因其遊玩的方式與另一個推盤遊戲[[華容道 (遊戲)|華容道]]類似，故數字推盤也常被稱為'''數字華容道'''。也有以圖畫代替數字的推盤遊戲。可能Noyes Palmer Chapman在1874年發明十五數字推盤<ref>{{Cite web |url=http://www.cs.princeton.edu/courses/archive/spr09/cos226/assignments/8puzzle.html |title=COS 226 Programming Assignment 8 Puzzle |access-date=2010-01-30 |archive-date=2021-01-07 |archive-url=https://web.archive.org/web/20210107214810/https://www.cs.princeton.edu/courses/archive/spr09/cos226/assignments/8puzzle.html |dead-url=no }}</ref>，但Sam Loyd則在1891年也宣稱為其發明<ref>{{Cite web |url=http://www.cut-the-knot.org/pythagoras/fifteen.shtml |title=Sam Loyd's Fifteen |access-date=2010-01-30 |archive-date=2021-01-07 |archive-url=https://web.archive.org/web/20210107214858/http://www.cut-the-knot.org/pythagoras/fifteen.shtml |dead-url=no }}</ref><ref>{{Cite web |url=http://www.cut-the-knot.org/books/Reviews/The15Puzzle.shtml |title=The 15 Puzzle by Jerry Slocum and Dic Sonneveld  |access-date=2010-01-30 |archive-date=2021-01-07 |archive-url=https://web.archive.org/web/20210107221311/http://www.cut-the-knot.org/books/Reviews/The15Puzzle.shtml |dead-url=no }}</ref>。

八數字推盤（又名'''重排九宮'''）則同樣是Noyes Palmer Chapman在1870年代發明<ref>{{Cite web |url=http://gamescrafters.berkeley.edu/games.php?puzzle=8puzzle |title=8 puzzle |access-date=2010-11-11 |archive-date=2020-09-08 |archive-url=https://web.archive.org/web/20200908122350/http://gamescrafters.berkeley.edu/games.php?puzzle=8puzzle |dead-url=no }}</ref>，並且[[馬丁·加德納]]在[[科學人]]尋求更快的解答<ref>{{Cite web |url=http://www.mathematische-basteleien.de/15puzzle.htm |title=The Eight Puzzle |access-date=2010-01-30 |archive-date=2021-01-07 |archive-url=https://web.archive.org/web/20210107214901/http://www.mathematische-basteleien.de/15puzzle.htm |dead-url=no }}</ref>。也有人宣稱重排九宮是傳統中國遊戲，來自[[洛書]]，並且為華容道的祖先<ref>{{Cite web |url=http://www.cctv.com/program/kxlc/20030903/101220.shtml |title=橫刀立馬華容道 |access-date=2016-05-18 |archive-date=2021-01-07 |archive-url=https://web.archive.org/web/20210107214844/http://www.cctv.com/program/kxlc/20030903/101220.shtml |dead-url=no }}</ref>。

[[File:15-puzzle.svg|thumb|right|十五數字推盤遊戲。]]

== 構造 ==

數字推盤遊戲由一塊有凹槽的板和數個寫有數字的大小相同的方塊所組成。

十五數字推盤遊戲的板上會有十五個方塊和一個大小相當於一個方塊的空位（供方塊移動之用）。而八數字推盤遊戲，為[[九宮格]]佈局，有八個方塊和一個空位。

== 遊戲規則 ==

遊戲者要移動板上的方塊，讓所有的方塊順著數字的次序排列。

== 解法 ==
寻找數字推盤遊戲的一个解相对容易，但寻找[[最佳化|最优解]]是一个[[NP困难]]问题。<ref>{{cite conference | title=Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable | author=Daniel Ratner | year=1986 | conference=National Conference on Artificial Intelligence | coauthors=Manfred K. Warmuth}}</ref><ref name=ratner+warmuth>{{cite journal|last=Ratner|first=Daniel|coauthors=Warmuth, Manfred|title=The (n<sup>2</sup>−1)-puzzle and related relocation problems|journal=Journal of Symbolic Computation|year=1990|volume=10|issue=2|pages=111–137|doi=10.1016/S0747-7171(08)80001-6}}</ref>十五数字推盘的最优解至多有80步<ref>A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, [http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf The parallel search bench ZRAM and its applications] {{Wayback|url=http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf |date=20171111193526 }}, ''Annals of Operations Research'' '''90''' (1999), pp. 45–63.</ref>；而八数字推盘的最优解至多有31步。
<!-- 这几句话我不懂，就不翻译了。
or 43 multi-tile moves;<ref>[http://cubezzz.dyndns.org/drupal/?q=node/view/223 "The Fifteen Puzzle can be solved in 43 "moves""]. Domain of the Cube Forum</ref>

 the 8-puzzle always can be solved in no more than 31 single-tile moves or 24 multi-tile moves (integer sequence [http://oeis.org/A087725 A087725]).
-->

可以使用[[A*算法]]寻找最优解。h(n)（[[启发式算法|启发式策略]]）可以是<ref>{{cite book | title=人工智能——一种现代方法 | publisher=人民邮电出版社 | author=Stuart Russell | year=2010 | pages=84-85 | isbn=978-7-115-23227-4 | coauthors=Peter Norving}}</ref>
# 放错的方块的数量，
# 所有放错的方块到各自目标位置的距离之和。

==群表示==
因为15塊的數字推盤遊戲组合可以由「3循環」（3-cycles）产生，所以可以证明15塊的數字推盤遊戲可以用[[交錯群]]<math>A_{15}</math>表示<ref>{{cite web |last1=Beeler |first1=Robert |title=The Fifteen Puzzle: A Motivating Example for the Alternating Group |url=https://faculty.etsu.edu/beelerr/fifteen-supp.pdf |website=https://faculty.etsu.edu/ |publisher=East Tennessee State University |access-date=2020-12-26 |archive-date=2021-01-07 |archive-url=https://web.archive.org/web/20210107214840/https://faculty.etsu.edu/beelerr/fifteen-supp.pdf |dead-url=no }}</ref>。事實上，任何使用<math>2 \times k - 1</math>塊相同面積正方形方塊的數字推盤遊戲皆可以以[[交錯群]]<math>A_{2 k - 1}</math>表示。

==參考條目==
*[[旋轉方塊]]
*[[魔方群]]

==參考文獻==

{{reflist}}


[[Category:玩具]]
[[Category:智力游戏]]
[[Category:NP完全问题]]