Friday, June 19, 2009

Minesweeper puzzle

I trust most of you have seen minesweeper before? If not, then this puzzle will go right over your head.

Where should you click in order to maximize your chances of winning?

In case you didn't know, the number 4 in the upper left represents the number of unmarked mines remaining.

See the solution

Anonymous said...

square (5,1)

miller said...

I assume you meant first row, fifth column from the lower left. Nope!

Eduard said...

There are 8 over 4 = 70 possibilities to set the 4 mines one 8 possible places.
35 of those are forbidden because of the visible hints.
In the remaining 25 cases (5,1) and (6,1) are the most frequently occupied places (18 times).
Two solutions?
Notation: (column, row) from lower left.

Eduard said...

Other consideration:

(4,3) is least frequent (4 times) in the 25 "remaining"cases. If (4,3) has a mine then I have to try further only 4 cases.
Hence (4,3) is optimal.

Secret Squïrrel said...

Given that the objective is to maximise your chances of winning, and that clicking on a mine results in you not winning, I think that the best strategy for this example is to click on the square least likely to contain a mine.

Intuitively I had thought, like the first answerer, that this would be the centre square of the bottom row (5,1). However, there is a 50% chance of it having a mine. The square with the lowest probability is (4,3), directly under the highest "3". The chance of it having a mine is 25%. I did consider that it might be a slightly better strategy to click on the 2nd best squares - (4,1) & (4,2) at 37.5% each - if they would lead to complete analysis of the remaining squares if you survived, but they don't.

If you click on (4,3) and survive (75% chance), the revealed number will allow you to infer where the other mines are, unless it's "4" (37.5%). In that case, you can only deduce that there is a mine to the immediate right. The remaining three mines must be in a V-shape within the lower six squares, either upright or inverted (v or ^), with equal probability.

So, clicking on (4,3) and assuming you don't make an error, your overall chances are:

1-click instant death - 25%
2-click delayed death - 18.75%
Survival - 56.25%

miller said...

There seems to be disagreement about how many possible cases there are. Is it 8 or 25? (Hint: neither)

Lucien said...

There are 5 cases: (O=mine, X=no mine)

XO
OXO
XOX

XO
XXO
OOX

XO
OOX
XXO

XO
XOX
OXO

OX
XOO
XOX

So, (4,3) is the best place to click.

Eduard said...

My last count has 10 possible cases.
(4,3) stays the favorite.

xo
xox
oox

ox
xoo
xxo

xo
oox
xox

xo
oxo
xxo

xo
xxo
oxo

to Lucien's list.

Secret Squïrrel said...

When you take into account all of the available information (numbers indicating how many mines are in the surrounding 8 squares) then, as Lucien has stated, there are only 5 possible configurations.

However, their chance of occurring are not equal. Using Lucien's notation and order, their probabilities are as follows:

XO
OXO
XOX 12.5%

XO
XXO
OOX 12.5%

XO
OOX
XXO 25%

XO
XOX
OXO 25%

OX
XOO
XOX 25%

Eduard said...

Sorry. I have have seen ma error.

Secret Squïrrel said...

Gah! I started my calculation of probabilities with a false premise. There must be a mine in one of the 2 squares in the RH column and I assigned a probability of 50% to both and merrily proceeded from there (hence the chances all being related to powers of 2, if I'd started from the left they'd have been powers of 3).

However these probabilities are not independent of those for the other mine positions. Taking each of the 5 cases as equally likely, (4,3) now has a survivability of 80% - I've gained 5%!

So my recalc'd odds are:

1-click instant death - 20%
2-click delayed death - 20%
Survival - 60%

miller said...

Lucien and Secret Squirrel have got it!

There exists an alternate solution which gives the same chance of survival.

Secret Squïrrel said...

Yes, of course. (6,1) has a 60% chance of being mine-free. If you survive, there must also be mines at (5,1) and (6,2). The number revealed (2 or 3) will tell you whether there is also a mine at (5,2). If there is, then the 4th mine is at (4,3) and if not, you can safely click on (4,3) to see whether there is a mine at (4,2). If not, it will be at (4,1). The 4th is at (5,3) in either case.

(4,1) and (4,2) also have a 60% chance of being mine-free but their revealed numbers (which would be "3" and "5" respectively) will not prevent you from having to make a second guess, thus reducing your survival chances below 60%.