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.

Suppose there's a minesweeper board like the following:

1 1 1
A B C

Where A, B, C is an unrevealed square which could contain a mine.

This can be represented with:

A + B = 1
A + B + C = 1
B + C = 1

Which can be easily solved to show that B = 1

Now, I hope I'm in the right stackexchange for this as I'm relatively amateur with maths, but is there such thing as an algorithm that can solve these types of equation relatively quickly and simply?

share|improve this question
    
You may find this useful: math.stackexchange.com/questions/42494/… –  Beni Bogosel Sep 9 '11 at 15:26
add comment

1 Answer 1

up vote 4 down vote accepted

Minesweeper belongs to the category of NP-complete problems (a type of ubiquitous but intractable combinatorial problem), and for general positions there is no known or suspected solution method that is fundamentally better than brute force search. The linear equations that encode a position have non-negative integer variables, or boolean 0-1 variables; they define instances of Integer Programming and Satisfiability respectively. Those too are well known NP-complete problems. So there is no real traction to be gained by encoding the problem this way, except for small cases where one can feed the position to SAT or integer program solvers.

http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

http://www.claymath.org/Popular_Lectures/Minesweeper/

(Added answer to question from the comments: )

How is Minesweeper even computable with scenarios like 1 1 A B (assuming this is an island)?

Minesweeper is usually formalized as a decision problem: is the scenario consistent with at least one placement of mines. If that problem were efficiently solvable then for every undetermined square S one could efficiently test whether Mined(S) or Empty(S) is inconsistent with the scenario. If Mined(S) is inconsistent then S must be Empty, and vice versa; if both are consistent then S is (at present) undetermined. Iteration of this process would be an algorithm for efficiently resolving all squares that are logically determined by the original scenario. Within deterministic playing algorithms this is perfect play.

share|improve this answer
    
How is Minesweeper even computable with scenarios like 1 1 A B (assuming this is an island)? –  Raphael Sep 9 '11 at 7:53
    
@Raphael: see update. It is not expected that the algorithm will guess in the case of multiple logically possible solutions. It is only required to resolve all logically resolvable squares. –  zyx Sep 9 '11 at 11:20
add comment

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.