Evaluation
The reduction from SAT (a NP-Complete problem) to Minesweeper showed that Minesweeper is NP-Complete. This is a very interesting result as it shows the complexity of a game that at first glance appears to be simple.
What we found clever was the author's ability to turn a group of booleans into SAT, which we know is NP-Complete.
We found no major flaws. However, Kaye’s proof only reduces SAT to Minesweeper to show that Minesweeper is NP-Complete. We are able reduce other NP-Complete problems to Minesweeper which are easier to follow, such as the 3COLOR problem:
Main takeaway
This showed us that Minesweeper is actually a well developed game! There are different difficulty levels and easy rules to grasp. Never the less, even an expert can have difficulty. Kaye successfully solved the problem by deriving Minesweeper into a known NP-Complete problem (SAT). The paper was originally published in 2000, which led the path to explaining how other puzzle games are NP-Complete and allowed other puzzle game developers to consider the mechanisms of Minesweeper to develop their game to be more challenging. In total, we are now more aware of the logic of Minesweeper!