數字推盤遊戲
數字推盤遊戲（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）.