Solving Minesweeper Rules

Have you ever played the Minesweeper game included in your operating system? It is basically a game where you locate the mines by looking at the numbers. Most people found it impossible therefore ignoring it. However, Minesweeper is such a great game. You must learn how to solve minesweeper by learning the following rules of solving:

Notations used:

  • \bold{M} is the set of all squares with mines.
  • \bold{A}_{x, y} is the set of squares (A)round (x, y) of the Minesweeper board A.
  • |A| means the number of elements in a set.
  • \overline{A} means the number of mines in a set, it is defined as: \overline{A} = |A \cup \bold{M}|
    This notation only apply in the scope of this document.
  • Please learn set theory before reading this article: http://en.wikibooks.org/wiki/Discrete_Mathematics/Set_theory.

The Nothing Rule

\overline{A} = 0, A \cup \bold{M} = \{\}

This rule is very simple, if A has no mines, all of the squares in A are safe to be clicked. That is why all squares around an empty square (an opened square without any numbers) are opened automatically.

The Equality Rule

|A| = \overline{A}, A \subseteq \bold{M}

If the number of squares in the set A equals the number of mines of A, then all squares in A are mines. For example:

1 2
1 3 ?
2 ? ?

As we can see, \overline{\bold{A}_{1, 1}} is 3. How can the 3 mines distributed? 3 mines to 3 squares, means all squares in there are mines. Therefore, \bold{A}_{1, 1} \subseteq \bold{M}.

The Subset Rule

A \subset B, C = B - A, \overline{C} = \overline{B} - \overline{A}

This is the most useful rule in Minesweeper solving. If the squares in A (strict) subsets B, and C is the set difference between B and A, then the number of mines in C is the number of mines in B minus the number of mines in A.

Here is the proof by example:

1 2 3
1 ? 3 ?
2 3 6 ?
3 ? ? ?

By using the Equality Rule on \bold{A}_{2, 2}, all “?”s are mines. What if we use the Subset Rule on \bold{A}_{2, 1} and \bold{A}_{2, 2}:

\bold{A}_{2, 1} \subset \bold{A}_{2, 2}, C = \bold{A}_{2, 2} - \bold{A}_{2, 1}, \overline{C} = \overline{\bold{A}_{2, 2}} - \overline{\bold{A}_{2, 1}} = 3,

By the Equality Rule, all squares in \bold{A}_{2, 1} C are mines, which is consistent to the result over the Equality Rule under \bold{A}_{2, 2}.

Example Case

Now let’s look at an example puzzle, found and analyzed on Wikipedia. We are not going to use the coordinates, instead, letters and variables are used.

1 2 3
1 1 a
2 1 2 b
3 c d e

First, scan through the numbers and we can let A = \{a, b\}, B = \{a, b, c, d, e\}, C = \{c, d\} while \overline{A} = 1, \overline{B} = 2, \overline{C} = 1.

Because A \subset B, then by using the Subset Rule: D = B - A = \{c, d, e\}, \overline{D} = \overline{B} - \overline{A} = 2 - 1 = 1

Notice C \subset D, then we apply the Subset Rule again: E = D - C = \{e\}, \overline{E} = \overline{D} - \overline{C} = 1 - 1 = 0. By the Nothing Rule, e is not a mine.

By using the rules above, you can implement an automated Minesweeper solver. See http://github.com/SHiNKiROU/Minesweeper.

Here is the Minesweeper solving algorithm in pseudocode:

class Set {
  Coordinate[] elements;
  int mines;
  Set(Coordinate[], int);
  bool strictSubset(Set);
  Set diff(Set);
}
 
solveMinesweeper(board) {
  sets = [ ];
  // gather information
  for (square in board.squares) {
    if (square.isNumber()) {
      sets.add(new Set(square.around(), square.number))
    }
  }
 
  // apply the Subset Rule
  changed = true;
  while (changed) {
    for (set1 in sets) {
      for (set2 in sets) {
        if (set1 != set2 && set1.strictSubset(set2)) {
          sets.add(new Set(set2.diff(set1), set2.mines - set1.mines));
        }
      }
    }
  }
 
  // apply the Nothing and Equality rule
  for (set in sets) {
    if (set.mines == 0) {
      board.dig(set.elements);
    } else if (set.mines == set.elements.length) {
      board.mark(set.elements);
    }
  }
}

Tags: , ,

This entry was posted on Friday, April 16th, 2010 at 16:25and is filed under Computer Games, Math. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Solving Minesweeper Rules”

  • Dave Says:
    November 8th, 2010 at 13:39

    Excellent, this is a great logical breakdown of an automated method. I’ve seen some automated cheat methods online which use image processing to pull back a tile count and then determine which tiles can be clicked. I’m wondering how they compare with this set of rules.

    I wrote a simple beginner-level minesweeper game, I’m wondering if it’s possible or useful to write an online minesweeper solver…

    Reply
  • STIMpacks Says:
    September 9th, 2010 at 14:35

    very fun game! for windows vista there is a “easter egg” that makes you think even more. this game is very simple but none of my friends know how to play it?

    watch this:
    http://www.youtube.com/watch?v=-CH-Kx2sl9c

    Reply

Leave a Reply