The Oz Minesweeper

Raphaël Collet

Try it out: OzMine

The link above launches the Oz Minesweeper as an Oz applet. You need version 1.3.0 or later to be installed on your system. In order to launch the application with a single click, you have to enable Oz applets in your internet browser. Consult the Mozart Installation Manual if necessary.

The source files are packed in OzMine.zip. To build the application, unpack the file, enter the directory OzMine, and run make (for the executable), or make oza (for the applet).

I have submitted a paper to the Second International Mozart/Oz Conference MOZ2004. The paper describes how I used constraint programming to implement a solver for the game. Using constraint programming is appropriate, since the Minesweeper is NP-complete (by Richard Kaye).

The game

This application looks like the usual minesweeper game. The playing field is a grid of squares, each of which may hide a mine. The total number of mines is given when the game starts. The objective is to find out where they are located. The rules are:

1. You uncover a square by clicking on it. If you explode a mine, the game is over. Otherwise, the number in the square gives the number of adjacent mines.
2. You mark a square as a mine by clicking on it with the right button of your mouse. This helps to visualise your knowledge about the field.
3. You win the game when all the non-mined squares have been uncovered. To help you, a counter in the window indicates the number of remaining squares to be uncovered.

The digital assistant

This application is definitely more than the usual minesweeper game. It provides a digital assistant, which consists in several inference engines and one search engine. The digital assistant is based on techniques from the field of constraint programming, for which Oz has valuable support. As it is capable of solving a nontrivial problem, the digital assistant can be called ``intelligent''.

The inference engines are controlled by the checkbuttons on the right of the mine field. When active, they augment the knowledge about the hidden mine field. The user interface shows this in the squares. Safe positions are marked with a dash (-) until they are played. Mine positions are marked with a black circle, suggesting a bomb. OzMine currently provides four inference engines.

Autoplay

This is not strictly speaking an inference engine. This module automatically uncovers the squares that are known to be safe. Its purpose is to be used in conjunction with the other inference engines.

Zero propagation

This module implements the following inference rule: if a square is uncovered and shows a ``0'', then all the squares around it are safe. It is the simplest form of intelligence for this game. Usual implementations of the game never provide more than this.

Binary Constraints

This module post Oz propagators that correspond to the information shown by the game. It considers the hidden mine field as a binary matrix, where the value 1 reflects the presence of a mine. If a square is uncovered and shows number k, a propagator is created for the equation x1 + ... + xn = k, where the xi's are the matrix entries corresponding to the neighbors of the uncovered square.

Set Constraints

This one improves the latter, by adding redundant constraints to the problem. It creates propagators that constrain subterms in the equation shown above. Every subterm corresponds to the number of mines in a set of squares. Several propagators can thus share information about groups of squares.

The Search engine is triggered by the user, and basically solves the whole problem. It considers all the possible mine fields, and computes their mean. This mean value gives a probability for each square to be mined. The probabilities are shown on the board as filled rectangles. The precise value for a square is shown below the search button when the user places the mouse cursor on the square.

Actually the search engine does not compute all the solutions of the problem. This is simply impossible. For instance, a 10x10 field with 20 mines has 5.36x10²⁰ solutions when the game starts! It first reformulates the problem, using similar techniques to the Set Constrains engine above, and solves this new problem. It has much less variables, and much less solutions. Details are given in the paper.