CS geeks who love Minesweeper will be pleased to learn that Minesweeper is an NP-complete problem.
The rest of you… well, um, I can beat Expert in under five minutes! Once in a while, even!
Minesweeper 1, polynomial time algorithms 0
Sorry, the comment form is closed at this time.
I’ve just posted an AI on my website, haven’t though about NP-completeness since it solves expert in 1 second
Interesting article though.
Comment by Joco — February 22, 2007 @ 2:23 am
Neat-o! You’ve basically taken two insights I always stumble upon when playing Minesweeper and found a way to deal with them in an algorithm efficiently, which is pretty cool.
You might be interested in the Minesweeper NP-complete FAQ, also posted on the site. There’s a question that clears up what exactly is meant by Minesweeper being an NP-complete problem and why it’s possible to find practical algorithms for solving Minesweeper games despite the NP-complete classification.
Comment by Wesley — February 22, 2007 @ 2:35 pm