研究生: |
王怡人 |
---|---|
論文名稱: |
Light Up遊戲一致性問題之研究 |
指導教授: | 林順喜 |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2007 |
畢業學年度: | 95 |
語文別: | 中文 |
論文頁數: | 39 |
中文關鍵詞: | Light Up 、一致性問題 |
論文種類: | 學術論文 |
相關次數: | 點閱:147 下載:7 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
Light Up(點燈遊戲)是一個從日本發跡並已推廣至世界各地,造成相當流行的一種“paper-and-pencil puzzles”類型的遊戲,在2005年時由Brandon McPhail證明了Light Up一致性問題 -- 「給定一個Light Up的盤面,判定此盤面是否存在合理的解?」的難度是NP-complete。目前探討本議題的相關論文並不多,因此在本論文中,首先提出了將盤面縮小至一維的盤面,並發現一維的Light Up盤面能夠在線性時間內以一個決定性的有限狀態機(DFA)判斷出盤面是否一致,即1×n Light Up一致性問題複雜度為P。
接著我們將Light Up盤面限定為一個2×n的盤面,即一個二維的盤面但其中一個維度限制為2,發現這個問題同樣地能被克服。我們設計了一個有限狀態機,同樣能在線性時間內判斷出一個2×n Light Up盤面是否一致,即2×n Light Up一致性問題複雜度亦為P。
[1] M. A. Arbib, Theories of Abstract Automata, Prentice-Hall, Englewood Cliffs, N. J., 1969.
[2] M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979.
[3] B. P. McPhail, “The complexity of puzzles: NP-completeness results for Nurikabe and Minesweeper,” Undergraduate Thesis, Reed College, 2003.
[4] B. P. McPhail, “Light Up is NP-complete,” The Division of Mathematics and Natural Sciences, Technical report, Reed College, 2005.
[5] M. L. Minsky, Computation-Finite and Infinite Machines, Prentice Hall, Englewood Cliffs, New Jersey, 1967.
[6] M. Sipser, Introduction to the Theory of Computation, Second Edition, Course Technology, 2005.
[7] S. Takahiro, The Complexities of Puzzles, Cross Sum, and their Another Solution Problems (ASP), Undergraduate Thesis, The University of Tokyo, 2001.
[8] N. Ueda and T. Nagao, “NP-completeness results for NONOGRAM via parsimonious reductions,” Technical report, Tokyo Institute of Technology, 1996.
[9] T. Yato, “On the NP-completeness of the Slither Link Puzzle,” In IPSJ SIGNotes ALgorithms, pages 25–32, 2000.
[10] T. Yato, Complexity and Completeness of Finding Another Solution and its Application to Puzzles, Master’s thesis, The University of Tokyo, 2003.
[11] The Light Up Puzzle website, http://www.puzzle-light-up.com/.
[12] The Wikipedia website, http://en.wikipedia.org/wiki/Light_Up.