5 ms·
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 unavo
by iaw 10y ago
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.
- drchickensalad 10y agoIt's very simply provable that there exist configurations you must guess in, even if weighted.
- mod 10y agoIt's not possible, no. The guessing is not a part of every layout, but often it is. See the board positions in this blog post: http://nothings.org/games/minesweeper/ http://nothings.org/games/minesweeper/
- inlined 10y agoThe proof seems pretty easy to reduce with a smaller example: there are 17 mines. One cluster is in a 3x3 box and another is in a hollow 3x3 box. Which is which?
- Pxtl 10y agoConsider the basic state - the minesweeper board is built around your first move. If your first move is not a void, but has one or more adjacent mines, all you see to start is a single open square with a number. At that point you're already making a guess. Even if it's a 1, you're guessing about your next move.
- saghm 10y agoNot to mention that the first move itself is a guess. I'm not sure about all variants, but certainly on the classic Windows minesweeper there were times that my first click was a bomb.
- nicholaides 10y agoYou would think that if you clicked a bomb first, the app would regenerate the board until it made one where the place you clicked was not a bomb.
- ATsch 10y agoSome games do this, some don't some only actually generate the field once you click the first box.
- ygra 10y agoThe behaviour towards the user is the same, though: The first click never results in a bomb. Everything else is an implementation detail, although not placing bombs until after the first click is probably the easiest approach to ensure it.
- M4v3R 10y agoThat was definitely not possible on Windows XP version of Minesweeper, they would regenerate the board if you clicked on a bomb in the background and used that one instead.
- saghm 10y agoOh, really? I guess I was just misremembering things. Thanks for correcting me here! (not sarcastic, genuinely happy to be corrected when I remember things wrong)
- Drdrdrq 10y agoIt was definitely not like that on Win98.
- saghm 10y agoDefinitely not like what the parent said, or what I said? Maybe I'm remembering that rather than XP
- iaw 10y agoI was thinking that past a certain threshold of moves the probability of clicking a mine in most strategies will drop to zero, the question I had was if there were a specific strategy where that probability would never increase past 0. From all the commentary however, it's pretty clear that the answer is no.
- derf_ 10y agoConsider the following configuration (where --- is the wall and M == known mine): +------ | 1 | 2 | 1 2 M If you know there are three mines here, including the marked one, this is either +------ | M 1 | M 2 | 1 2 M or +------ | M 1 | M 2 | 1 2 M There's no way to ever get more information to resolve the ambiguity without guessing, and the mine probability in every square is 50%. This (or simple variants) is the most common late-game failure case. Similar symmetries can also occur on edges, and (though more rarely) even in the middle of the field. 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.
- mhils 10y agoNot for normal minesweeper, but there are always-solvable variants: http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/mines.html http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/mines...
- ballenf 10y agoI'm sure someone's maxed the strategy, but playing I would always try to figure out when I got to those forced-guess situations which click had the lowest probability of being a mine. I.e., there were squares that you knew were 1/2 or 1/3 chance, you knew how many total unrevealed mines and number of unrevealed squares. So you could calculate the odds on any given square. One of those problems I always wanted to work on on my own, knowing that someone somewhere probably had a much better solution.
- Hussell 10y agoThere's a minesweeper solver which works out all the probabilities of uncertain squares. http://mrgris.com/projects/minesweepr/demo/player/ http://mrgris.com/projects/minesweepr/demo/player/ The creator wrote an explanation here: http://mrgris.com/projects/minesweepr/ http://mrgris.com/projects/minesweepr/
- i336_ 10y agoThis implementation shows you where the mines are! 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.
- jmtame 10y agoI think it would depend on a few things: the size of the grid, how many bombs there are, and whether the board uses the rule of "the first click is guaranteed not to be a mine."
- orasis 10y agoNo. some configurations can be solved perfectly but as you get to higher mine density it becomes probabilistic.
- kmod 10y agoThere 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? 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 http://simon.bailey.at/random/kaye.minesweeper.pdf