3
$\begingroup$

It should be fairly obvious that it is impossible to solve a minesweeper game without at least one guess, but beyond that, is there any way to characterize sufficient and necessary conditions to then win a minesweeper game with subsequent perfect play?

In fact, I am more interested in figuring out what are the necessary conditions to arrive at a win in minesweeper.

  • 0
    Ohh... interesting indeed. Thanks :) should post that as an answer.2012-02-05

1 Answers 1

5

Decision version of Minesweeper is NP-complete, because it is possible to encode logic gates on the minefield (reference). So one should not expect any nice criteria that determine solvability of a given field.

  • 0
    It is possible, but I would not expect this; it would be similar to finding a fast SAT algorithm for, say, maximally 100 variables. I strongly doubt there is a nice one, although you can theoretically enumerate all possible inputs.2012-02-05