Complexity of minesweeper with restricted number

We consider the Minesweeper consistency problem (is a given partially completed board consistent with some mine placement?) when the set of numbers that may appear on a Minesweeper board is restricted. First, we analyze the possible sets of numbers that could exist in legal rectangular Minesweeper boards, proving either possibility or impossibility for 509 of the 512 subsets of {0, 1, 2, 3, 4, 5, 6, 7, 8} (leaving 3 subsets as open problems), and thus make conclusions on the relations among some restricted-set Minesweeper consistency problems. We prove either inclusion in P or NP-completeness for the restricted-set Minesweeper consistency problem for 134 of the 512 subsets of the set of numbers above. In particular, we show that {0,1}-Minesweeper consistency is NP-complete, while {0}-Minesweeper consistency and {1}-Minesweeper consistency are in P. We also suggest a few more dimensions in which the Minesweeper consistency problem could be analyzed.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Wu, Ray Hua

Advisor dc:contributor.advisor

• Erik D. Demaine.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/119557

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/119557