2×n踩地雷一致性問題之研究

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.