踩地雷是微軟作業系統上非常流行的一套單人電腦遊戲，自從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.

[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