簡易檢索 / 詳目顯示

研究生: 胡淑琼
Hu Shu-chiung
論文名稱: 2×n踩地雷一致性問題之研究
On The Study of
指導教授: 林順喜
Lin, Shun-Shii
學位類別: 碩士
Master
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2006
畢業學年度: 94
語文別: 英文
論文頁數: 32
中文關鍵詞: 踩地雷踩地雷一致性問題有限狀態機P
英文關鍵詞: Minesweeper, Minesweeper consistency problem, finite automata, P
論文種類: 學術論文
相關次數: 點閱:172下載:10
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 踩地雷是微軟作業系統上非常流行的一套單人電腦遊戲,自從Richard Kaye在2000年證明了踩地雷問題是NP-complete之後,近年來有許多學者投入這方面的研究。Meredith Kadlac提出了一維的踩地雷遊戲,並証明了一維踩地雷一致性問題(One-dimensional Minesweeper Consistency Problem)是非常容易處理的,且可以用一個決定性的有限狀態機(DFA)來判斷一個一維踩地雷的盤面是否一致。我們將此一致性問題延伸至2×n踩地雷盤面上,2×n踩地雷是二維的,但其中一個維度被限定為2。我們發現這個問題也是可克服的,我們成功的設計了一個有限狀態機,其可在線性時間內解出2n踩地雷一致性問題,因此,我們證明了2×n踩地雷一致性問題的複雜度亦為P。

    Minesweeper is a popular single-player game included with Windows operating systems. Since Richard Kaye proved that Minesweeper is NP-complete in 2000, it has been recently studied by many researchers. Meredith Kadlac had showed that one-dimensional Minesweeper consistency problem is regular and can be recognized by a deterministic finite automata. We extend the consistency problem to 2×n Minesweeper, which is two-dimensional but with its one dimension restricted to 2. We find that this problem is also tractable and design a finite automata which can solve 2n Minesweeper consistency problem in linear time. Hence, we are able to show that 2×n Minesweeper consistency problem is also in P.

    TABLE OF CONTENTS Chapter 1 Introduction 1 1.1 Motivation and Theoretical Background 1 1.2 Overview and Contribution 2 1.3 Organization of this thesis 5 Chapter 2 Literature Reviews and Fundamentals 6 2.1 Minesweeper Consistency Problem is NP-Complete 6 2.2 The One-dimensional MCP 9 2.3 The 2×n MCP 12 Chapter 3 NFA for 2×n MCP 14 3.1 Input Symbols 14 3.2 Representation for 2×n MCP NFA 16 Chapter 4 Simplified NFA and DFA for 2×n MCP 25 Chapter 5 Finding Consistent Configurations 29 Chapter 6 Conclusion Remarks 31 6.1 Conclusions 31 6.2 Future work 31 References 33

    [1] Raphaël Collet., 2004, "Playing the Minesweeper with Constraints," Second International Mozart/Oz Conference, pp. 251-262.
    [2] R. Donner, C. Johnson., "Minesweeper,"
    http://www.planat-minesweeper.com/download.php
    [3] M. Kadlac., 2003, "Explorations of the Minesweeper Consistency Problem," Proceedings of the Research Experiences for Undergraduates Program in Mathematics, Oregon State University, pp. 78-126.
    [4] R. Kaye., 2000, "Minesweeper is NP-Complete," The Mathematical Intelligencer, 22(22) pp. 9-15.
    [5] R. Kaye., 2000, "Some Minesweeper Configurations,"
    http://web.mat.bham.ac.uk/R.W.Kaye/minesw/
    [6] R. Kaye., "Richard Kaye’s Minesweeper Website,"
    http://web.mat.bham.ac.uk/R.W.Kaye/minesw/
    [7] Pedro Gimeno Fortea., "Minesweeper Designer v0.1 beta."
    http://www.formauri.es/personal/pgimeno/compurec/Minesweeper.php

    [8] B. P. McPhail., 2003, "The Complexity of Puzzles: NP-Completeness Results for Nurikabe and Minesweeper," Senior Thesis, Reed College.

    [9] J. Palumbo., 2003, "The P Vs NP Problem, NP Completeness, and Minesweeper," http://www.math.rutgers.edu/~greenfie/currentcourses/sem090/pdfstuff/palumbo.pdf

    [10] J. D. Ramsdell., "Programmer's Minesweeper,"
    http://www.ccs.neu.edu/home/ramsdell/pgms/
    [11] M. Sipser., 2005, Introduction to the Theory of Computation, Second Edition, Course Technology.
    [12] T. A. Sudkamp., 2005, Languages and Machines: An Introduction to the Theory
    of Computer Science, 3rd Edition, Addison-Wesley, pp. 672.

    [13] I. Stewart, , "Ian Stewart on Minesweeper,"
    http://www.claymath.org/Popular_Lectures/Minesweeper/

    [14] C. Studholme, 2005, "Minesweeper as a Constraint Satisfaction Problem,"
    http://www.cs.toronto.edu/~cvs/Minesweeper/

    [15] F. Wester, 2005, "The Minesweeper Page," http://www.frankwester.net/winmine.html

    [16] The Wikipedia website,
    http://en.wikipedia.org/wiki/Main_Page

    QR CODE