started at . submit by
solve 1d minesweeper quickly, please. I'm in a predicament! how hard could it be? submissions can be written in any language.
minesweeper is a-- do you really not know? minesweeper is a logic puzzle game where you clear a grid of tiles, some of which are hidden mines, by revealing 1 time at a time: if you reveal a mine, you lose. you are aided by numerical hints that appear on each revealed tile, telling you exactly how many of the neighbouring tiles are mines. the game is usually played in 2 dimensions. technically, it works the same with any number. it doesn't even have to be a grid; any graph could be used to represent the "neighbouring" relation.
today we will be playing on a line.
there are but 2 visible states for a minesweeper tile during the course of play:
-)0, 1, or 2) signalling how many neighbouring tiles are minesgiven a line of these tiles ("board"), our goal will be to determine a good one to reveal; one that hopefully isn't a mine.
you may see a problem. let's pretend we've survived the first reveal, and we see this:
- - 1 - -
uh-oh. there's no solution here, no safe tile to reveal. or is there? if we knew that the board only had 1 mine on it, we'd know that both tiles on the edge have to be safe, since the single mine on the board has to be next to the 1. so we can reveal either of these, and be done:
- - 1 - -
^ ^
that's trick #1. the number of mines on the board ("mine count") is always known, and we can use that information to make deductions. but what about when we can't? take a look at this board with 5 mines in total:
- - - 1 0 1 - - 1 - -
? ? * * ? ? ?
the location of 2 of the mines is clear, but the rest could be anywhere! what should we do?
...yeah, you know where this is going. time for trick #2: get out the / signs, because where we're going, we need probability. the way to maximize our chances of survival is to choose whichever tile is the least likely to be a mine, since we'll be seeing few guaranteed safe tiles on our journey.
let's see: ½ of the two tiles neighbouring the isolated 1 are mines, and ⅔ of the remaining three unknowns are mines also. so the tiles next to the 1 are safer here. we can do either of these, right?
- - - 1 0 1 - - 1 - -
^ ^
right... well, no. not right. we need trick #3 here as well. yes, the chance of either of these two tiles being a mine is 50%. but think about the future! this is minesweeper, not minefair. the game won't cut us a break just because we were forced to guess. our goal is to clear the board, and optimizing our chances of doing so requires upping our game!
imagine we reveal the left option, and it's clear. we already know there's 1 mine next to it, so we're guaranteed to see this:
- - - 1 0 1 - 1 1 - -
? ? * * * ?
we're forced to take a 33/66 on one of the tiles. if we're right, we win, and if we're wrong, we lose. all in all, we end up with a ⅙ chance of winning because of the two guesses we made having ½ and ⅓ chances to survive respectively. but what if we had made a different choice?
if we reveal the right option instead, things look better for us. we might see this:
- - - 1 0 1 - - 1 1 -
? ? * * * *
since our click revealed more information, we now only have another 50/50 to make. there's a ⅙ chance of winning this way as well. (½ on the first guess, ⅔ that the number it reveals is a 1, and ½ for the subsequent next guess.) so what makes this way better? well, what if we saw this instead?
- - - 1 0 1 - - 1 0 -
* * * * * _
holy wow! there's a ⅙ chance again of this scenario occurring that immediately solves the board without having to make another guess. adding those probabilities together, we end up with a ⅓ chance of winning the game if we reveal the right option, twice that of revealing the left option. so there is in fact only 1 correct solution to the problem: we should reveal this tile.
- - - 1 0 1 - - 1 - -
^
or at least there would be only 1 correct solution if it wasn't for trick #4. it's not actually necessary to reveal one of the safest tiles. in this case, we do effectively the exact same thing if we reveal the rightmost tile, so we can do that as well:
- - - 1 0 1 - - 1 - -
^ ^
more complicated than you expected, right? your challenge, given a board and mine count, is to find one of the tiles to reveal for the best chance to clear the board. as any language is allowed, there is no fixed API.
some more examples of boards and correct solutions:
2 | - - - -
^ ^ ^ ^
1 | 0 1 - -
^
4 | - - - 1 - - -
^ ^ ^ ^
2 | - - - 1 - - -
^ ^
4 | - - 1 - - -
^ ^ ^ ^
3 | - - - 1 - 2 -
^
4 | - - 2 - - 1 1 - 1 0
^
1 entry has been received so far.