Minesweeper is NP-complete!
This article argues that Minesweeper belongs to the class of NP-Complete problems (see “Complexity Classes P and NP” in Wikipedia to brush up on P and NP).
My result in the Mathematical Intelligencer states that a decision problem which I like to call “the Minesweeper Consistency Problem” and which is exactly equivalent to the problem of playing the minesweeper game, is yet another one of these NP-complete problems.
For the current discussion, it suffices that the problem of simply detecting which squares are or are not mines is equivalent to the Minesweeper Consistency Problem, and the fact that it is NP-complete means, for Minesweeper fans, that their favourite game can be seen as being right at the cutting edge of mathematical research. There are two possible viewpoints one might take on this.
The more “sober” viewpoint is that the NP-completeness of Minesweeper shows that Minesweeper really is a rather good game. The fact that it is NP-complete means that it is very difficult to spot when it is possible to clear a square safely in full knowledge that that square is clear, and when some guessing is required. In fact, even if you are told in advance that guessing is not required, it may still be difficult to decide what squares to clear. In some sense, when you play the game you cannot be expected to do much better than the hundreds of very good mathematicians who have worked on the P=NP? question for many many years.
