Strategies of Minesweeper

Minesweeper is a logic puzzle video game genre generally played on personal computers. I strongly recommand the game chocolate sweeper. As explained in the preview page
We made up such Minesweeper into a "perfect" puzzle game. I use "perfect" to mean that no guesses are required to solve puzzles, or even more strictly, no guesses are allowed. Only the squares (means "chocolate cubes" in this game) that are certainly safe can be uncovered (eaten).

I am going to give an example of how it works. You can try my example online. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │   │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 17

1. Obvious mine

Since Gc is 1, it is clear that Fd is a mine.

Since Fd is a mine, Fe must be safe. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │   │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 16

2. Exclusion

Note that
     Ea + Eb = 1 since Fa is 1;
     Ea + Eb + Ec = 1 since Fb is 1;
Thus Ec is safe.

Note that
     Hf + Gf = 1 since He=1;
     Hf + Gf + Ff = 1 since Ge=2;
Thus Ff is safe. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │   │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 16

3. Exercises

Exercise: now, prove Db, Dc, Dd are all safe. (Hint: consider Fc and Ec)

It turns out 
     b   c   d
  ─┼───┼───┼───┼─
D  │ 2 │ 1 │ 2 │ 
  ─┼───┼───┼───┼─

Exercise: now, prove Cb, Cc, Cd are all safe. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │   │ 2 │ 1 │ 1 │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │   │ 2 │ 1 │ 2 │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │   │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 16

4. Inequality

Note that
     Ed + Ee <= 1, since Fe is 2.
This implies
     De + Ce >= 1, since Dd is 2.
But
     De + Ce <= 1, since Cd is 2.
This means all the "="'s are achieved. So
     Ed + Ee = 1, De + Ce = 1.

It follows that Ef and Gf are safe (so Hf is a mine); BC, Bd, Be are safe (so Bb is a mine). 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │   │ # │ 2 │ 3 │ 3 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │   │ 2 │ 1 │ 1 │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │   │ 2 │ 1 │ 2 │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │ 3 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │ 2 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │ # │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 14

5. Exercise

Prove that Ba is safe. (Hint:
     Ea + Eb = 1
     Da + Ca = 1
     Da + Ca + Ba = 1 ) 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │   │   │   │   │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │ 2 │ # │ 2 │ 3 │ 3 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │   │ 2 │ 1 │ 1 │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │   │ 2 │ 1 │ 2 │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │ 3 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │ 2 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │ # │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 14

6. Intersection

Consider Ac + Ad
     Ac + Ad != 2 since Bc is 2
     Ac + Ad != 0 since Bd is 3
This implies Ac+Ad=1, so Ab is safe and Ae and Ce are mines. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │   │ 3 │   │   │ # │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │ 2 │ # │ 2 │ 3 │ 3 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │   │ 2 │ 1 │ 1 │ # │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │   │ 2 │ 1 │ 2 │   │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │ 3 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │ 2 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │ # │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 12

7. Do trivial things

Now,
Aa and Ac are mines;
Ad, Ca are safe;
Da is a mine;
De is safe. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │ # │ 3 │ # │ 2 │ # │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │ 2 │ # │ 2 │ 3 │ 3 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │ 2 │ 2 │ 1 │ 1 │ # │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │ # │ 2 │ 1 │ 2 │ 4 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │ 3 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │ 2 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │ # │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 9

8. Exercise

Now, show Df and Dg are mines, Gg is safe. (Hint: consider Ee+Eg+Fg)

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │ # │ 3 │ # │ 2 │ # │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │ 2 │ # │ 2 │ 3 │ 3 │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │ 2 │ 2 │ 1 │ 1 │ # │   │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │ # │ 2 │ 1 │ 2 │ 4 │ # │ # │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │ 3 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │ 2 │ 3 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │ # │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 7

9. Do trivial things

As a result,
Cf is a mine (Ed+Ee=1).
Af, Bf are safe. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │ # │ 3 │ # │ 2 │ # │ 1 │ 1 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │ 2 │ # │ 2 │ 3 │ 3 │ 3 │ 3 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │ 2 │ 2 │ 1 │ 1 │ # │ # │ 5 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │ # │ 2 │ 1 │ 2 │ 4 │ # │ # │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │ 3 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │ 2 │ 3 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │ # │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 6

10. Exercise

Prove that Ch is a mine. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │ # │ 3 │ # │ 2 │ # │ 1 │ 1 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │ 2 │ # │ 2 │ 3 │ 3 │ 3 │ 3 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │ 2 │ 2 │ 1 │ 1 │ # │ # │ 5 │ # │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │ # │ 2 │ 1 │ 2 │ 4 │ # │ # │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │ 3 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │   │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │ 2 │ 3 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │ # │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 5

11. The number of mines

There rest 5 mines, but
     Ea + Eb = 1,
     Ed + Ee = 1,
     Ah + Bh = 1,
     Fg + Fh + Gh + Hg + Hh = 2.
So Eg, Eh, Dh are safe. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │ # │ 3 │ # │ 2 │ # │ 1 │ 1 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │ 2 │ # │ 2 │ 3 │ 3 │ 3 │ 3 │   │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │ 2 │ 2 │ 1 │ 1 │ # │ # │ 5 │ # │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │ # │ 2 │ 1 │ 2 │ 4 │ # │ # │ 2 │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │   │   │ 2 │   │   │ 3 │ 2 │ 1 │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │ 0 │ 0 │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │ 2 │ 3 │ 2 │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │ # │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 5

12. The rest is easy

The rest is easy. 

    a   b   c   d   e   f   g   h   
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
A │ # │ 3 │ # │ 2 │ # │ 1 │ 1 │ 1 │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
B │ 2 │ # │ 2 │ 3 │ 3 │ 3 │ 3 │ # │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
C │ 2 │ 2 │ 1 │ 1 │ # │ # │ 5 │ # │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
D │ # │ 2 │ 1 │ 2 │ 4 │ # │ # │ 2 │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
E │ # │ 2 │ 2 │ 2 │ # │ 3 │ 2 │ 1 │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
F │ 1 │ 1 │ 2 │ # │ 2 │ 1 │ 0 │ 0 │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
G │ 0 │ 0 │ 1 │ 1 │ 2 │ 2 │ 3 │ 2 │
  ├───┼───┼───┼───┼───┼───┼───┼───┤
H │ 0 │ 0 │ 0 │ 0 │ 1 │ # │ # │ # │
  └───┴───┴───┴───┴───┴───┴───┴───┘
Rest: 0

13. Finished!

We are done.

home