March 30, 2006
Minesweeper
About a year ago the guys in the office and I went on a little minesweeper kick and I discovered that while I'm usually pretty good at analytical problems, I was definitely missing something with Minesweeper. I played enough to where I just memorized patterns and guessed if I didn't recognize something. I could clear the board quickly, but if I didn't guess it would take me forever. I pretty much relied on guessing to get good times - and guessing that much means that half (or more) of the time I'd have to start over. For the most part you don't have to guess in Minesweeper. There are times that you do, but they don't come up that often, aside from the first few clicks. That got me wondering about how systematic minesweeper is, and what algorithms have been developed to solve it.
So after a few weeks of Minesweeper, I went searching and found out there's a lot of interesting stuff about the game. The Wikipedia minesweeper page has a ton of info, and I'll mention some of it. For starters you can see what the world records are and watch 'videos' at Planet Minesweeper. The best players in the world have combined times of 50-60 seconds for beginner, expert, and intermediate. The current leader has times of 1, 10, and 39 seconds at the three levels, Which is insane. The 1 second beginner time is just a random thing. If you play enough beginner minesweeper games you'll eventually hit one that clears instantly. You can watch some of the minesweeper videos if you don't believe that people can move their mouse that fast. (You need to get a codec linked on that page).
What got me interested again today was an article I read on the NP-completeness of Minesweeper. (You can brush up on P vs. NP at wikipedia) The above article references the journal article which first proved that Minesweeper was equivalent to existing NP-complete problems. Richard Kaye (the original author) developed minesweeper grids that were equivalent to the building blocks of logic - gates and wires, like AND, OR, and NOT. I thought this was pretty neat. (Click on the links 1 and 3 spots above this one to see some of the gates) Since the problem of determining the output of a set of gates/wires for any input is an NP-complete problem, the transformation shows that Minesweeper is also NP-complete. An efficient (polynomial time) Minesweeper solver would solve all other NP-complete problems in polynomial time. That includes prime factorization (modern cryptography), the traveling salesman problem, graph coloring problem, among others. In other words it would be one of the biggest discoveries in math in a long time, and it would have practical implications. So I guess I won't find a Minesweeper solver anytime soon.
(Footnote: There are Minesweeper solvers, just not any that work in polynomial time)