Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Interesting question. Though technically, minesweeper is not a combinatorial game, two of the techniques from that theory might come in useful here. The concept that moves in games are moves, and the concept of disjoint sum of games. So one might be able to identify the largest connected minesweeper games where perfect play is possible. –  Tobias Kildetoft Feb 5 '12 at 7:33
1  
Since you can encode logical gates on the minefield, decision Minesweeper is NP-complete (web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm), I would not expect anything better. –  sdcvvc Feb 5 '12 at 7:57
    
Ohh... interesting indeed. Thanks :) should post that as an answer. –  ldog Feb 5 '12 at 8:07

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
Well, yes, on an arbitrary large board. However, each finite instance is simpler than a Turing machine, so one might expect to solve easier... –  Paxinum Feb 5 '12 at 9:31
    
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. –  sdcvvc Feb 5 '12 at 9:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.