Re: Minesweeper game is NP-complete, CNN says


Subject: Re: Minesweeper game is NP-complete, CNN says
From: Johan Ovlinger (johan@ccs.neu.edu)
Date: Fri Nov 03 2000 - 09:39:06 EST


Discussed on slashdot and kuro5hin. Bascially, the game itself is not
NP complete (as it is easy to set up boards that require chance to
solve, even if the first click is guaranteed not to kill you) but
rather the decision of whether a partially revealed board is
consistent with any configuration of mines. You basically have to
resort to exhaustive search.

More precisely, he found a way to encode 3sat into the problem:
configurations of mines that correspond to AND OR and NOT.

Johan



This archive was generated by hypermail 2b28 : Fri Nov 03 2000 - 09:39:22 EST