Minesweeper

In 2000 it was proven that solving unknown values in minesweeper from known values is NP-complete. Some parts of this proof are available online. This sketch describes a polynomial conversion from the NP-hard problem of satisfiability to the minesweeper problem.

However two conditions must be met for a problem to be NP-complete, it must be NP-easy and NP-hard:

• NP-easy: There is a polynomial conversion of this problem to a problem in NP.
• NP-hard: There is a polynomial conversion of a problem in NP to this problem.

The NP-easy part of the proof can be sketched with SABR. First we generate objects to define the number of mines around each number, then we apply those objects to board-cells based on whether they are a corner, side or middle cell.

As the size of the board increases, causing the number of DesObj to also increase, the size of the CNF file increases at a polynomial rate.

generate | source | solution