Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106634
Title: 2×n踩地雷一致性問題之研究
On The Study of
Authors: 林順喜
Lin Shun-Shii
胡淑琼
Hu Shu-chiung
Keywords: 踩地雷
踩地雷一致性問題
有限狀態機
P
Minesweeper
Minesweeper consistency problem
finite automata
P
Issue Date: 2006
Abstract: 踩地雷是微軟作業系統上非常流行的一套單人電腦遊戲,自從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.
URI: http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=%22http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22GN0692470190%22.&%22.id.&
http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106634
Other Identifiers: GN0692470190
Appears in Collections:學位論文

Files in This Item:
File Description SizeFormat 
n069247019001.pdf43.78 kBAdobe PDFView/Open
n069247019002.pdf173.4 kBAdobe PDFView/Open
n069247019003.pdf170.41 kBAdobe PDFView/Open
n069247019004.pdf59.4 kBAdobe PDFView/Open
n069247019005.pdf35.42 kBAdobe PDFView/Open
n069247019006.pdf35.76 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.