研究生: |
胡淑琼 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 |
論文種類: | 學術論文 |
相關次數: | 點閱:209 下載:10 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
踩地雷是微軟作業系統上非常流行的一套單人電腦遊戲,自從Richard Kaye在2000年證明了踩地雷問題是NP-complete之後,近年來有許多學者投入這方面的研究。Meredith Kadlac提出了一維的踩地雷遊戲,並証明了一維踩地雷一致性問題(One-dimensional Minesweeper Consistency Problem)是非常容易處理的,且可以用一個決定性的有限狀態機(DFA)來判斷一個一維踩地雷的盤面是否一致。我們將此一致性問題延伸至2×n踩地雷盤面上,2×n踩地雷是二維的,但其中一個維度被限定為2。我們發現這個問題也是可克服的,我們成功的設計了一個有限狀態機,其可在線性時間內解出2n踩地雷一致性問題,因此,我們證明了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 2n Minesweeper consistency problem in linear time. Hence, we are able to show that 2×n Minesweeper consistency problem is also in P.
[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