user

Pete's Log: minesweeper is np-complete

Entry #456, Sun, September 24, 2000, 19:14 EST (Coding, Hacking, & CS stuff)
(posted when I was 22 years old.)
Rebecca Weber invited me to a math department graduate student seminar. The talk was titled "Minesweeper is NP-complete" and was pretty cool. It started out pretty funny, because I got to witness thirty-plus math grad students try to figure out how many pizzas to order for themselves. It was very amusing. The guy then began his talk. He first went over P, NP, and NP-completeness, then briefly talked about minesweeper. Then came the cool part: the proof that minesweeper is NP-complete. He defined the general minesweeper problem, and then, in the math/algorithms equivalent to a cool hack, reduced the boolean satisfiability (SAT) problem (which is NP-complete) to the general minesweeper problem. Basically, since all logic gates can be represented by AND and NOT, we show how to use minesweeper boards as logic circuits. First, the minesweeper wire (or identity circuit or whatever):
000000000000000
111111111111111
 1  1  1  1  1 
111111111111111
000000000000000

So what we do is the middle line is the one that matters. The first 1 in the middle line is the "input" 1 and the last 1 is the "output" 1. So we define false as left of the 1, and true as right of the 1. So if you work out, based on the rules of minesweeper, where the bombs are, the above minesweeper board just propogates a truth value. Next, a NOT gate:
00001110000
11112*21111
 1  3 3  1
11112*21111
00001110000

I won't bother trying to draw an AND gate, because it is obscenely large minefield, but basically, it was a cool presentation. minesweeper is np-complete.
Nobody has rated this entry.