Minesweeper & P!=NP

You’ve probably heard about Vinay Deolalikar’s proof that P != NP. Are you confused about what it means? Ian Stewart has a nice explanation which involves minesweeper.

Minesweeper is actually an interesting little game to implement. It was very popular back when the first workstations were new. Here’s a link to Tom Anderson’s early version on comp.sources.games. We ported it to several of the different workstations we used at the time. It was particularly popular with Chris’ coworkers at Intermetrics. In addition to being a good example for learning the basics of a UI framework and graphics library, there are some interesting bits in coding up the hint command.
Ian’s article gives you a good idea of some of the complexity which is hiding in this simple little game. Go check it out here.