Sun, 2005-07-03 01:14 — Uwe Hermann

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

## 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.