In 2000, Richard Kaye published a proof that shows that Minesweeper is NP-complete and determines whether a given grid of uncovered, correctly flagged, and unknown squares, has an arrangement of mines that is possible within the rules of the game. The argument is constructive, consisting of a method to quickly convert any Boolean circuit into such a grid that is possible if and only if the circuit is satisfiable; membership in NP is established by using the arrangement of mines as a certificate. If, however, a minesweeper board is already guaranteed to be consistent, solving it is not known to be NP-complete, but interestingly it has been proven to be co-NP-complete.

Kaye also proved that an infinite minesweeper game is Turing complete.

​

The following is a link to his essay: http://simon.bailey.at/random/kaye.minesweeper.pdf