簡易檢索 / 詳目顯示

研究生: 王怡人
論文名稱: 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。

    摘要......................................................II Abstract.................................................III 第一章 緒論................................................1 第一節 前言.................................................1 第二節 問題定義.............................................3 第三節 文獻探討.............................................9 第四節 論文組織.............................................9 第二章 相關研究探討........................................10 第一節 Light Up 一致性問題..................................10 第二節 Light Up 一致性問題為NP-complete.....................11 第三節 1×n與2×n LCP........................................14 第三章 1×n 的Light Up一致性問題............................17 第一節 符號定義............................................17 第二節 1×n LCP之DFA........................................17 第四章 2×n 的Light Up一致性問題............................23 第一節 符號定義............................................23 第二節 2×n LCP之NFA狀態介紹.................................25 第三節 2×n LCP之NFA狀態轉換表...............................31 第四節 簡化2×n LCP之NFA狀態轉換表............................36 第五節 2×n LCP屬於P........................................36 第五章 結論...............................................38 第一節 結論................................................38 第二節 未來方向............................................38 參考著作...................................................40

    [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.

    QR CODE