The complexity of Minesweeper and strategies for game playing
Kasper Allan Pedersen · 2004
To determine whether a Minesweeper configuration is consistent was proved NP-complete by Kaye. Here the complexity of Minesweeper is investigated and three game playing strategies are developed. The two decision problems: “Does a configuration have a unique solution?” and “Is a given move safe?” are proved complete in DP, and the problem of counting the number of solutions to a configuration complete in #P. Three Minesweeper strategies are presented, the best of which uses probability estimates to assist in guessing when required. This strategy is capable of winning 25% of games at expert level. The strategies are implemented in a framework developed specifically for automated Minesweeper playing.