Re:Cracking Minesweeper with Z3 SMT Solver
by kmod on Sunday March 05, 2017 @08:01PM
(#13799975)
There are a couple questions here:
- Can every minesweeper board be solved without guessing?
No:
1 ?
1 ?
- If a minesweeper game doesn't require guessing, is there an algorithm that can determine the next move?
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?
- Can every minesweeper board be solved without guessing?
No:
- If a minesweeper game doesn't require guessing, is there an algorithm that can determine the next move?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