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