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

Syndicate content