Minesweeper is NP-complete!
Richard Kaye’s work on Minesweeper is a lot of fun to read. He first proved that Minesweeper is NP-complete (though the article in The Mathematical Intelligencer isn’t available online, unfortunately), and has a very neat paper that demonstrates some logic circuits in the game (the AND gate is truly impressive). I suspect that his latest paper, “Infinite versions of minesweeper are Turing complete“, is even more interesting, but I don’t know enough about the area to properly appreciate it.