Minesweeper is NP-complete

KMines screenshot

In the year 2000, Richard Kaye published a paper in which proved that Minesweeper is NP-complete. He has some very nice slides which demonstrate how the proof works.

Later, he also proved that Infinite Minesweeper is Turing-complete (PDF).

I'm so waiting for some kid to solve the P=NP problem by playing minesweeper...

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Tetris

That's pretty cool! There have been a lot of similar studies of whether or not it's possible to play Tetris forever (assuming you're really good!) There are a couple of ways you can be forced to lose. For example, if you got a long long sequence of identical Z-shaped pieces then eventually you'd be forced to leave a hole in the opposite corner without clearing your previous hole, and if this keeps happening, you'd lose. So if you played for a really long time and your random-number generator were perfect (and gravity naive) then you'd eventually lose.

In reality this won't happen in most versions of Tetris because the pseudo-random number generator is a linear congruential generator and won't deal such a sequence. There are also issues with how naive gravity is in the game's engine, and even on a system where this could occur, the probability at any given time that you will be dealt such a sequence is 1 in (7/2)^150 (approximately 1 in 4 x 10^81.)

It'd be neat if someone collected a bunch of these problems and made a math book that taught math through games. :-)

-random planet.debian reader / math grad student

David Eppstein has a nice

David Eppstein has a nice page called Combinatorial Game Theory as well as a huge Computational Complexity of Games and Puzzles list. Many of the games listed there are NP-complete or even PSPACE-complete.

The Annotated List of Selected NP-complete Problems and the Complexity Zoo list even more problems (not resticted to games and puzzles) and their complexity.

HTH, Uwe.

P=NP

You mean P=NP, not N=NP...

Yes.

Oops, you're right, of course. I fixed that, thanks.

Uwe.