(Versión en español disponible)

There must be few people that haven't heard about Minesweeper, a game that is available on most personal computers. It's a game that is likely to cause addiction, probably because once one gets used to it, the way that it's played is quite mechanic except for certain situations requiring a greater attention.

Here we will only give an outline of the rules; those who do not know them but are interested can try playing some games until getting the trick. Over a grid of covered cells there are a certain number of mines hidden. We can unveal each cell; if it hides a mine we lose the game immediately, otherwise the now uncovered cell tells us how many mines are there which surround it (counting the diagonals). If we're sure that a covered cell contains a mine, we can mark it to ease the search. We win the game if we uncover all of the cells that do not contain mines.

Though the usual gameplay is mechanic, there are a number of situations in which it's simply impossible to know how to continue. There are others in which resolving the situation is really difficult; for this reason there are puzzles such as the one in figure 1, a problem whose author is Richard W. Kaye. The cells that are unvealed but empty indicate that there's no mine around them, as is obvious in this case; this convention is preferred to putting a zero in its place in order to center the attention only in the relevant places.

Kaye's interest in Minesweeper is not just ludic. He's the author of a
paper, not available in Spain, showing how difficult it may become to find
out whether there is a mine in a certain position or not. To focus on the
problem, Kaye uses the approach of *consistency*, not just simple
gameplay: is a given board consistent, or not? Before going deeper on the
question let's first analyze what we're talking about. A board will be
consistent if it is possible to find a distribution of the hidden mines
such that the numbers in the uncovered cells are correct; it will be
inconsistent otherwise. Figure 2 shows
samples of consistent and inconsistent positions.

In figure 2a, if the hidden cell in the left contains a mine and the one in the right does not, clearly the numbers in the uncovered cells will tell the truth. Even though in any other case the numbers would not be coherent, there exists an actual combination of presence and absence of mines in the hidden cells satisfying all numbers; the fact that it exists is what makes the position consistent. That's not the case of figure 2b; any possible combination of presence or absence of mines in the covered cells will imply that at least one of the numbers in the uncovered cells is false (remember we're implicitly assuming that empty cells contain zeros, thus they have also to be accounted when determining consistency).

It's easy to understand the relationship between the consistency problem
and normal gameplay: the minesweeper playing programs know the placements
of the mines and show us values corresponding to them, that is, are always
consistent; on the other hand, in order to analyze consistency sometimes
the full board must be considered, because it's enough to find just one
cell that does not match the number of mines surrounding it to consider the
full board as inconsistent. In order to give a positive answer to the
consistency problem all one has to do is give a marked board in which all
uncovered cells show the exact number of marked cells surrounding them.
This part is actually very similar to normal gameplay, except that we don't
care about ambiguous situations as long as we can give one correct
placement of mines. Checking the solution is easy: it's enough to check the
number in every uncovered cell; as soon as we find one that does not match
the count of marked cells surrounding it we reject that solution as being
incorrect and the board *may* be inconsistent. But is it? How
difficult is to decide that?

What Kaye has proved is that the task of finding out whether a given board
is consistent or not is, in the general case, a problem whose difficulty
is at least the same as in the family of problems called NP-complete. It's
not easy to express the meaning of this in brief. To get a rough idea, this
means that if there exists an algorithm that resolves it, its *execution
time* is a function that grows with respect to the size of the problem
(the size of the board in the case of Minesweeper) at a rate bigger than
that of every polynomial function (for example, at an exponential rate).
This is not proven; anyone who finds otherwise, or finds that it's
necessarily that way with no other possibility, could earn **one million dollars**. This conjecture is known with the short name «P=NP?».

Kaye's proof is based in an amazing equivalence developed by himself: it's possible to build Minesweeper boards that are isomorphic (equivalent) to boolean functions with arbitrary inputs on whose output it depends whether the board is consistent or not. This is a satisfiabilty problem (SAT, for short) that is known to be NP-complete, so the general problem of Minesweeper consistency is NP-complete too.

To show the equivalence, Kaye builds Minesweeper configurations that are
themselves equivalent to the elements used when constructing logical
circuits. He builds logical entries, wires that can be bent and of course
logical gates. We can see in figure 3 what a logical input looks like; we've marked with flags the cells
that must *a priori* be mines in order for the configuration to
be consistent. The value that is given to x
(presence or absence of a mine) will determine the value of the rest of
covered cells in order to maintain consistency. The «conducting
wire» looks like pairs of hidden cells as shown in the figure, and
the signal propagates in the direction of the arrow.

By analyzing the figure, it becomes clear that for each pair of adjacent uncovered cells, in one of each there must be a mine and in the other it must not; furthermore, the relative position of the one containing the mine will always be the same and will depend on x. As a convention, if for each pair of adjacent cells in the «wire» the one with the mine is the later in the direction of the arrow (the ones marked with * in the diagram) we'll say that the wire holds a «logical 1»; otherwise it will be a «logical 0». According to this convention, a NOT gate can be represented with the configuration we see in figure 4, which toggles the state of zeros and ones.

The OR gate (figure 5), designed by Stefan Schwoon, is quite complex; however it's fundamental since with OR and NOT gates it's possible to build any logical circuit. This design simplifies the one used by Kaye in his proof; the universal gate he built was an AND but it was too big and complicated for this article. Anyone who is interested can find it together with other gates and elements (as the one to bend a wire) in a paper available in Kaye's Minesweeper page. Some of the configurations present in that paper are necessary for Kaye's formal proof, which of course takes care of all the subtle details.

Let's show an example of how to put this all together. Consider the
board in figure 6, corresponding to
the logic function
«NOT (x OR NOT
y)». The output is designed in
such way that in order for this configuration to be consistent the result
of the function must be a logical 1. What values should the inputs take in
order for this condition to be met? That's precisely the question in the
SAT problem. In this case, there *exists* an actual combination of
inputs such that the output is 1, thus the board *is* consistent.
However, this function is quite simple; for more complex functions it may
cost *much* time (even in the order of thousands of years) to find
out the answer with the algorithms that are available at present.

The reader may enjoy checking how, when giving x and y the appropriate values, a legitimate solution is effectively obtained (unique in this case), and that every other possible values for x and y lead to a contradiction in the numbers of the uncovered cells. The solutions to this problem and the one in figure 1 can be checked using the Minesweeper Designer program.

After writing the Minesweeper Designer program I could check the validity of the circuits herein. It also helped me checking that the OR gate by Stefan Schwoon has a subtle problem. There's exactly one cell that is marked as a mine but can't be deduced from the available data. A fixed version has been already provided by Kaye in a 2003 talk available in his Minesweeper page. My own fixed design will appear in the next article.

Michiel de Bondt, a Dutch researcher, is concerned about the role of the mine counter related to the NP-completeness of Minesweeper as a game. Kaye's specification didn't care about the counter, but De Bondt has created alternative versions of some gates with the property of having a constant number of hidden mines. His paper is available online; see the links section below.

De Bondt's designs also have a very interesting property: the circuit boards built from them consist just of covered cells and hidden mines; the mines which configure the circuit elements can be deduced given only a single cell with zero mines around (Kaye's definition of a board was a set of covered and uncovered cells, i.e. part of the guesswork is already done magically; Schwoon's OR gate design interpreted that a board was a set of uncovered, covered but unknown and covered but marked cells, thus taking it even farther than Kaye's one from a real game's board). With his designs, De Bondt takes Minesweeper's NP-completeness much closer to the actual game's gameplay. He has also explored circuit elements in hexagonal and triangular grids with success but he had to restrict to Kaye's definition of board because of the technical difficulty of these grids.

After the first version of this article was written, I've found that
demonstrations to prove the difficulty (in the technical sense) of certain
games are quite popular even before Kaye's article. Schwoon himself, in a
joint work with Markus Holzer, has proven that the game *Atomix* is even harder than
Minesweeper, since it belongs to a class named PSPACE-complete. We won't go
into further details about what that means since that exceeds the purpose
of this article. There are good books about complexity theory where to find
the meaning of these and other terms. Enough to say that NP-complete
problems are contained within PSPACE-complete problems.

Joseph C. Culberson has also proved that *Sokoban*, a block pushing game, is
PSPACE-complete. In a nutshell, his proof works by building a
Turing-equivalent machine using Sokoban constructs. In 1978 David
Lichtenstein and Michael Sipser proved that *Go*, a board game
originating in China, is PSPACE-hard when played in arbitrary-size
boards.

Using similar methods to Kaye's (construction of
logical circuit elements), Erich Friedman, professor of Mathematics at Stetson University, has proved that a
blocks game called *Cubic* (a variation of a commercial game called
*Puzznic*) also belongs to the NP-complete class. Friedman has also
proven the same for a game called *Spiral Galaxies*, a game that can
be played with pencil and paper, and *Pearl Puzzles*, this latter
one by quite different methods to Kaye's: using certain theorems from
graph theory. By even more complicated means, Erik D. Demaine, in a joint work with several other authors, prove the same about the
well-known *Tetris* and also about a very addictive game called
*Clickomania!*, also known as the *Same Game*. A version
called *Click*, written jointly by the «Rincón del Programador» webmaster and
me, is available for download.

Holzer had already proved that a game called *TANTRIX*, in its puzzle version, is NP-complete by Kaye's method. With a similar,
though more powerful, construct Gary W. Flake and Eric B. Baum prove that a sliding block game called *Rush Hour*, from Thinkfun (formerly Binary Arts), that I casually own,
is PSPACE-complete in its arbitrary-size version. Demaine, in a joint work
with Robert A. Hearn, gave a simpler alternative proof. In the same work there's also a
simplified proof for Sokoban by building logic blocks in the manner that
Flake and Baum did.

Other games proven hard that I know of are: *Checkers/Draughts*,
*Othello (Reversi)*, *Mastermind*, *Dots and
Boxes*, *Shanghai* (a.k.a. *Mahjongg Solitaire*),
*PushPush* and some variants, *Gravity*, *Instant
Insanity*, *Twixt* and *Corral Puzzles*.

In our previous article we asked the length of the shortest Brainfuck program that stores the number 111 in the first memory cell, leaving the rest set to zeros. Lola Cárdenas sent a 28-instruction program:

++++[>++++<-]>[<+++++++>-]<-

It's the shortest solution I know which sets the data pointer to zero, but that was not stated as a requirement. Juan José Martínez took advantage of that circumstance and sent the following 27-instruction program:

++++++[>++++++<-]>+[<+++>-]

Luis Cuesta sent another solution with 27 instructions, but his program assumes that a cell containing a zero can be decremented then incremented and obtain a zero. This is the case with most interpreters but not guaranteed.

+++++++[>++++<-]->[<++++>-]

With an 8-bit interpreter working modulo 256 an even shorter program can be written:

>-[<-->-------]<+

(17 instructions). The question about possibly shorter solutions on either of the three categories above (leaving the data pointer to zero, not leaving the data pointer to zero and taking advantage of 8-bit wrapping) is still open.

*Minesweeper Designer* (124,973 bytes),
written by the author of this article. The documentation is in an appendix in this page.

Richard W. Kaye's Minesweeper page:

http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm

An article by Ian Stewart about Kaye's work:

http://www.claymath.org/Popular_Lectures/Minesweeper/

A Java program (with source) to automatically solve Minesweeper boards,
though not always successfully. Its author invites other programmers to
implement their strategy in Java.

http://www.ccs.neu.edu/home/ramsdell/pgms/

Michiel de Bondt has written a very interesting paper about
Master Mind and Minesweeper that can be read here (in gzipped
PostScript format):

http://www.math.ru.nl/onderzoek/reports/rep2004/rep04_18.ps.gz

A page by David Eppstein about the complexity of some games:

http://www.ics.uci.edu/~eppstein/cgt/hard.html

Directory of technical articles, many of them available in PDF and
PostScript formats. It holds most of the bibliography used to write the
Complements section.

http://citeseer.ist.psu.edu/

Articles that can be found there, among others:

Sokoban is PSPACE-complete (Joseph C. Culberson)

Spiral Galaxies Puzzles are NP-complete (Erich Friedman)

Pearl Puzzles are NP-complete (Erich Friedman)

Corral Puzzles are NP-complete (Erich Friedman)

Pushing Blocks in Gravity is NP-hard (Erich Friedman)

The Game of Cubic is NP-complete (Erich Friedman)

PushPush and Push-1 are NP-hard in 2D (Erik D. Demaine, Joseph O'Rourke)

PushPush is NP-hard in 3D (Joseph O'Rourke)

In Erik D. Demaine's page about combinatorial games there are various
articles used as bibliography about Tetris, Clickomania, Phutball, Sliding
Blocks (Rush Hour, Sokoban), etc.

http://theory.lcs.mit.edu/~edemaine/games/

The personal pages of the authors which are linked within the text also contain in many cases articles published by them.

A book about solvability of many games. I have not read it; it's
apparently a collection of papers similar to the ones presented here.

More Games of No Chance

A page dedicated to Minesweeper as a game. Among the downloads there are
several programs to play Minesweeper, some of them with grids different
from the usual square grid (e.g. hexagonal).

http://www.minesweeper.info/

Here's a Java version of Minesweeper with which can be played online:

http://www.hut.fi/~mantell/Minesweeper.html

If the Java version dows not work, the one in the following link can be
played online with any browser, though in a quite awkward way.

http://www.linc.or.jp/~hamano/game/minesweeper.html

Sliding Blocks puzzle page. Most of them are playable via a Java applet.
Rush Hour, mentioned in the text, is there among others.

http://www.puzzleworld.org/SlidingBlockPuzzles/default.htm

Another page with a Rush Hour-like game in Java:

http://www.rhymezone.com/games/bb/

The game of Cubic is similar to Puzznic but has no mobile blocks.

http://www.agon.com/doodle/four.html

The game of *Click* written by Lola Cárdenas and Pedro Gimeno (in
Spanish):

http://rinconprog.metropoliglobal.com/Programas/Juegos/Click.php

A game mostly identical to Click can be played online at the following
address (requires Java):

http://membres.lycos.fr/glsft/Click.php

Another one which just requires JavaScript:

http://www.jaure.net/click/

Those who are registered in *Yahoo!* can play many games online
against other players. Available games include *Go*, *Dots and
Boxes*, *Reversi*, *Checkers* and *Shanghai (Mahjongg
Solitaire)*.

http://games.yahoo.com/

Stanislav Busygin's page about NP-completeness.

http://www.busygin.dp.ua/npc.html

Clay Mathematics Institute page on the Millennium Prize problems:

http://www.claymath.org/millennium/

There are a couple of pages dedicated to solutions to the SAT problem.
Here's one:

http://www.cs.duke.edu/~mlittman/topics/sat.html

A page in Spanish about the SAT problem.

http://www.mor.itesm.mx/~jfrausto/Algoritmos/pagina_sat/Sat.htm

The purpose of the program is to give a tool for designing and testing Minesweeper configurations, mainly with the purpose of trying the ones shown in this article. Sadly just a Windows version is available at the moment, but if I receive enough petitions I can end up writing one for Linux.

The installation is very simple: just uncompress the file
**MineDsgn.zip** in any folder you like. The file
**MineDsgn.lng** must be in the same folder as
**MineDsgn.exe** for the translations to work. The program is
freeware and can be freely distributed as long as the full package is what
it is distributed.

At the start of the program an empty board is shown with the size we last used. It currently has two working modes: design mode, active by default, and test mode.

In design mode we can «paint» over the board; we do so by selecting the desired tool in the upper panel and using the left mouse button to draw. Inconsistent configurations are not allowed: in a cell we can't put a number greater than the total number of covered cells surrounding it, nor less than the total number of cells marked as mines. Covered cells have preference over uncovered, in the sense that if we alter a covered cell causing a change in the cells surrounding it, the cells that will be updated are the uncovered ones.

A double click with the left button over a cell will have the following effect: if it was covered it will be substituted by an uncovered one (with the minimum possible starting value), and vice versa.

With the right mouse button we can increment the number of the uncovered cells, or make it minimum if it already was the maximum. In the case of covered cells we will toggle them between marked and unmarked. When using the right mouse button this way, the tool corresponding to the cell's new state will be automatically selected so that we can go on painting with that tool.

There's an option called «Use (?) marks»; when it is active it causes that when pressing the right mouse button on a cell marked as a mine it becomes a question mark instead of being blank. Covered cells with a question mark behave the same as covered cells in blank; the question mark is just a sign to distinguish certain cells at the discretion of the designer.

This option will cause also that using the right mouse button over an uncovered cell it cycles between the least and the greatest possible and followed by a question mark. This question mark will be able to substitute any other number later when we test the board.

A rule when drawing is that when we start drawing in a covered cell, we will only be able to draw in covered cells until we release and press again the mouse button; similarly, when we start drawing in uncovered cells we only can draw in uncovered cells.

The options «Open configuration», «Save configuration» and «Save as...» work as expected. The «New board» option clears the current board and lets us work in a fresh one. For changing the size the option «Redimension board» can be used, but beware that the changes can not be reverted with the current version. The maximum board size in this version is 200×200.

In this mode we can uncover any cell that is covered but not marked, but keeping always the consistency. Every time it's invoked the designed board will be copied to a working board. The board resulting from the test can't be saved. The covered cells with question marks will behave exactly like the blank covered cells.

With the left mouse button we will uncover a covered cell; if it's necessarily a mine according to its uncovered neighbours, it will be marked as such instead of being uncovered. If it becomes uncovered, depending on the cells that surround it it will hold a number or a question mark. If it is surrounded only by covered cells marked as mines or by no covered cell at all, it will show a number; if there's a covered cell not marked as a mine around it, it will show a question mark, as the value of the covered cell (mine or not mine) is unknown but necessary to show an actual number. It can happen that when clicking on a covered cell it does not become uncovered nor marked. That's because it can't be a mine and it can't be a non-mine; that's to say that the position is inconsistent. If the sound option is active the left mouse click will cause a bell sound indicating that circumstance.

By double-clicking a cell its value will be restored to the value it had in design mode.

With the right mouse button a covered cell will toggle its state between marked or unmarked. As the result of marking a cell as a mine the uncovered cells around it that hold a question mark can become an actual number. This effect can also happen when uncovering a cell. It's possible that when trying to mark a cell as a mine it does not let us; that's because one or more of the surrounding uncovered cells already has maximum value and thus this cell can't hold a mine. This situation will cause also a bell if sound is active.

The middle mouse button is also very useful. If the mouse does not have a middle button, we can use instead the left and right buttons simultaneously (in that order). For repeated clicks you can use just the right button holding the left one pressed. The usage of the middle click is as follows: with the mouse pointer we point an uncovered cell holding a number that matches either the total number of covered cells surrounding this one, or the total number of cells marked as mines. When pressing the middle button on it the remaining covered cells will be either marked or removed correspondingly. As with the left mouse button, it's possible to hit an inconsistency (a cell that must and can't be a mine, at the same time) that will be noted with a bell if sound is active.

Even if it sounds very complicated, the usage is simpler than it looks. In case someone finds a bug please report it to parigalo@formauri.es.

**2003-01-22:**First version in Spanish.**2003-02-03:**Miscellaneous fixes and additions; English translation written.**2005-05-07:**Adaption to new web hosting. Some links fixed.

Copyright © 2003, 2005 Pedro Gimeno Fortea.

Special thanks must go to María Dolores Cárdenas for her help and support every time. The aesthetics in this page is due to her, as well as so many other details.