Friday, July 10, 2009

Minesweeper solution

See the original puzzle

There are five different mine arrangements which are consistent with the given minesweeper board. See here: Spoiler alert!

Each of five arrangements is equally likely.* So if we want to maximize our chances of winning, we should first try the square which is least likely to contain a mine. The upper left unknown has only a 1/5 chance of containing a mine, so we might pick that. If it turns out to be a 3 or a 5, then we can figure out the rest of the mines from there. If it turns out to be a 4, then we'll have to guess one more square. Let's just guess the square below it. In total, we have a 3/5 chance of surviving.

*The reason for this is that we are assuming that all arrangements are equally likely at the beginning of the game. As we click more squares, we prune the possibilities, but never do we make any of the remaining possibilities more likely than others.

We know there is no way to improve on this survival rate, because if we picked any other square first, we would already have at least a 2/5 chance of dying.

However, there is one alternative strategy which matches the 3/5 survival rate. If we pick the lower left right unknown, there is a 2/5 chance of dying. If we survive and it is a 3, then we can deduce the rest of the mines. If we survive and it is a 2, then we know that the upper left unknown is clear, and we can use the number there to deduce the rest of the mines.

2 comments:

Secret Squïrrel said...

Hi miller
Thx for the puzzles and musings. For the 2nd option I think you mean lower right unknown.

miller said...

Right you are. Thanks!