A nice introduction to both algorithmic and probabilistic aspects of the Minesweeper can be found in this B. Sc. thesis “Algorithmic Approaches to Playing Minesweeper” by David J. Becerra from Harvard.

Some advanced studies exploring different algorithms and their relation to probabilistic models of the Minesweeper can be seen in the paper “Optimistic Heuristics for MineSweeper” by O. Buffet, Ch.-Sh. Lee, W. Lin, O. Teytaud,

What does all of this beautiful mathematics says to a passionate gamer? Namely, what would be a good algorithm for solving the puzzle, and is the solution computationally hard?

In fact, the minesweeper is one of the classical board puzzles based on algebras of binary variables. Algorithmic solutions to these problems are typically sought with the use of integer linear programming. Unlike simple linear programming, integer programming problems are typically NP-hard. This is true even for binary integer programming where variables can only be 0 or 1 rather than arbitrary integers.

This transforms into the fact that, in its general formulation, the minesweeper is indeed algorithmically NP-complete. However, there is an argument that, if the minesweeper board is already known to be consistent, solving it is only guaranteed to be co-NP-complete, and might be (or not be) NP-complete.

And here is the raining defending Minesweeper world rekord holder Kamil Muranski performs his skillful play. Not sure if his brain is using integer linear programming or not ðŸ™‚