Algorithmic Approaches to Playing Minesweeper

Abstract

This thesis explores the challenges associated with designing a Minesweeper solving algorithm. In particular, it considers how to best start a game, various heuristics for handling guesses, and different strategies for making deterministic deductions. The paper explores the single point approach and the constraint satisfaction problem model for playing Minesweeper. I present two novel implementations of both of these approaches called double set single point and connected components CSP. The paper concludes that the coupled subsets CSP model performs the best overall because of its sophisticated probabilistic guessing and its ability to find deterministic moves.