This makes me wonder:
Is there a strategy such that it can consistently solve every minesweeper configuration?
I always assumed that the 50/50 guess was unavoidable on some maps but I don't know if that's true.
Is there a strategy such that it can consistently solve every minesweeper configuration?
I always assumed that the 50/50 guess was unavoidable on some maps but I don't know if that's true.
From all the commentary however, it's pretty clear that the answer is no.
+------
| 1
| 2
| 1 2 M
+------
| M 1
| M 2
| 1 2 M
+------
| M 1
| M 2
| 1 2 M
If you assume that you have knowledge of the 5 outside squares of a 3x3 corner (and any neighbors outside of that 3x3 corner) and that you know how many mines are left, you won't be able to fill in the rest without guessing 4.14% of the time on an Expert board. The most common failures are either three three-mine cases like the one illustrated here (0.440% likelihood each) or one of 16 four-mine cases (0.115% likelihood each). Given that there are four corners on the board, that sends your failure rate to at least 15.572% (actually higher, because you don't always know how many mines are left in one corner without clearing the other three).
If you want to fail fast, figure out if you have symmetry in the corners first.
- Can every minesweeper board be solved without guessing?
No:
1 ?
1 ?
Yes. Just enumerate all combinations of mine/not-mine for every hidden cell, and look at all the boards that match the exposed clues. If there is a square that is never a mine, click it. If there isn't, the board requires guessing.
- Is there an efficient algorithm to do the above?
Most likely not. Minesweeper as a decision problem ("is there any solution to these given clues") is NP-complete. http://simon.bailey.at/random/kaye.minesweeper.pdf
One of those problems I always wanted to work on on my own, knowing that someone somewhere probably had a much better solution.
The creator wrote an explanation here: http://mrgris.com/projects/minesweepr/
This will be so useful for actually helping me understand how Minesweeper works - theoretical explanations just make my eyes glaze over more often than not.