(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. Once one gets used to it, the way that it's played is quite mechanical except for certain situations requiring a greater attention.

Here we will only give an outline of the rules; if you do not know them but are interested, you can try playing some games. There are a certain number of mines hidden in a grid of covered cells. We can uncover each cell; if it hides a mine we lose the game immediately, otherwise the now uncovered cell tells us how many mines there are surrounding it (counting the diagonals). If we're sure that a covered cell contains a mine, we can mark it as such 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 mechanical, 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 uncovered and have no number in them indicate that there's no mine around them, as is obvious in this case; this convention is preferred over putting a zero in its place, facilitating focussing the attention only on the relevant places.

Kaye's interest in Minesweeper is not just ludic. He's the author of a
paper 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
understand 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 if there can't
possibly be one. Figure 2 shows samples
of consistent and inconsistent positions.

In figure 2a, if the hidden cell on the left contains a mine and the one on 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 incorrect (remember we're implicitly assuming that empty cells have zero mines around, thus they also have to be taken into account 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, they 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 correct 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 placement of
mines that causes the numbers to be correct. That's the main difference
between a consistency problem and gameplay. Checking whether a given
combination of mines is a solution to the consistency problem 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
combination as not being a solution and the board *may* be
inconsistent. But is it? How difficult is it 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 makes it belong to the family of problems called NP-complete. This means that it has two properties. The first one is that, given a solution, it's possible to verify it quickly; the formal definition of what we call here «quickly» is «in an amount of time that can be bound by a polynomial on the size of the problem». This property is stated by saying that the problem is in NP. The second one is that all problems in NP can be quickly (for the same definition of «quickly») reduced to it. This property is called NP-hardness. The first property imposes an upper bound on the difficulty of the problem; the second property imposes a lower bound.

«Reduced» is the keyword here. Reducing a problem to another means that every instance of the first problem can be stated in terms of the second problem, such that finding a solution to the second problem implies that we have a solution for the first one as well.

No one has found a general way to solve any particular NP-complete problem quickly,
for yet the same definition of «quickly». Even though algorithms exist
that solve *most* instances of a problem quickly, there are a few that can't be
solved quickly with the currently existing algorithms. Were a quick
(polynomial time) algorithm to solve every instance of one NP-complete problem found,
that would have very important implications. The same would happen if a
proof that it's impossible was found. It's so important, that there's a
prize of one million dollars
for whoever proves it one way or the other. This conjecture is known with
the short name «P=NP?».

It's trivial to show that a solution to the Minesweeper consistency problem requires a verification time that isn't larger than a polynomial on the instance's size. In this case, the size of an instance of the problem is given by the size of the playing grid, and a solution is just a configuration of present or absent mines. As we've explained earlier, verifying it just consists of going cell by cell, counting how many mines it is surrounded by and checking whether the count matches the number in the cell. That requires a time to verify that is linear on the number of cells, therefore the Minesweeper consistency problem is in NP.

The difficult part is showing that it is also NP-hard. Kaye's proof works by reducing a known NP-complete problem to a Minesweeper consistency problem. This is a commonly used shortcut: in order to prove that a problem is NP-hard, it suffices to show that any particular problem known to be NP-complete can be reduced to it; it isn't necessary to show that every problem in NP can be reduced to it. Kaye's choice is the boolean satisfiability problem, abbreviated SAT, known to be NP-complete. He proves that it is possible to build Minesweeper configurations that represent boolean functions with unknown inputs and an output of 1, making the board consistent only if the corresponding boolean function is satisfiable (i.e. if there exists a combination of inputs for which the formula results in an output of 1).

To this end, Kaye builds Minesweeper configurations that are
themselves equivalent to some elements used when constructing logical
circuits. He builds logical inputs, wires that can turn 90°
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 configured as shown in the
image, and the signal propagates in the direction of the arrow.

When analyzing the figure, it becomes clear that for each pair of adjacent covered cells, in one of them there must be a mine and in the other there 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 latter 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. Can a certain combination of inputs
result in that value? 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, therefore the board *is* consistent.
In this case such a combination is unique, but it doesn't need to be so.

The reader may enjoy checking how, when giving x and y the appropriate values, a legitimate solution is effectively obtained. Since it is unique in this case, the inputs can also be found by playing normally, going backwards from the output. Every other possible values for x and y that are not the solution would 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.

The example function given is quite simple; for more complex functions it may
cost *a lot* of time, even in the order of thousands of years, to find
out the answer with the algorithms that are available at present. For
example, some classical hash functions such as MD5 can be represented as
boolean functions. It is possible to create a giant Minesweeper
configuration that computes the MD5 compression function. Finding a preimage
(an input that results in a given hash) can be reduced to the problem of
finding a solution that satisfies the SAT problem for that particular instance;
the security of the hash relies partly on the inherent difficulty of solving
general NP-complete problems.

After writing the Minesweeper Designer program I could check the validity of the circuits presented. It also allowed me to find out 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 in relation 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 another 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 uncovered cells marked with numbers, and covered 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 and marked, covered but unknown and covered but known-to-be-mine 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 proof much closer to the actual game's gameplay. He has also explored circuit elements in hexagonal and triangular grids successfully, but he had to restrict his definition of a board to Kaye's in these cases (i.e. allowing cells to be uncovered in advance), due to the technical difficulty of these grids.

After the first version of this article was written, I found that
demonstrations to prove the difficulty (in the technical sense) of certain
games are quite popular even before Kaye's article. De Bondt shows in
the same paper mentioned that Master Mind is NP-complete.
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.

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 and several other authors prove the same about the
well-known *Tetris* and also about a very addictive game called
*Chain Shot!*, also known as *SameGame*. 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 happen to 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*.

**2017 Update:** Since the next article was not published,
here are the solutions to the problems in this article as well:

- Solution to Kaye's 6x6 grid puzzle. Blue cells represent the cells that were previously covered and unmarked.
- Solution to the circuit given. Blue cells represent cells that were previously covered and unmarked. Due to Schwoon's OR gate design problem, this solution is only unique assuming you're not allowed to unmark a mine and clear it; otherwise there are two other possible solutions that keep consistency.
- Alternative design for an OR gate where all marked mines can be deduced.

(End update)

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 leaves the data pointer at position 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 without lifts/elevators.

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 and study their consistency. Sadly just a Windows version is available at the moment, but if I receive enough petitions I may port it to Linux. (2017 update: Since it was originally written in Delphi and Lazarus is now quite up-to-speed with it, there's a Lazarus version available that works on Linux with GTK2. Email me if interested.)

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. Attempting to do so will automatically clamp the number to keep it in range. Covered cells have precedence over uncovered, in the sense that if we alter a covered cell and that causes a change in the cells surrounding it, the cells that will be updated are the uncovered ones.

A double click with the left button on 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 in 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. In both cases, the tool corresponding to the cell's new state will be automatically selected so that we can paint with it.

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 that are blank; the question mark is just a sign to distinguish certain cells at the discretion of the designer.

This option will also cause that when using the right mouse button on an uncovered cell, it cycles between the least and the greatest possible followed by a question mark. This question mark will stand for any other number later when we test the board.

A rule when drawing is that when we start drawing on a covered cell, we will only be able to draw on covered cells until we release and press again the mouse button; similarly, when we start drawing on uncovered cells we can only draw on 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.

There's no copy/paste or undo/redo feature implemented.

In this mode we can uncover any cell that is covered but not marked, but always keeping local 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 attempt to 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, it will contain either a number or a question mark, depending on whether the number can be determined from the cells that surround it or not. It can happen that when clicking on a covered cell it stays the same. That means that 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.

When double-clicking a cell, its state or value will be restored to the one 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 can't be a mine or a non-mine, at the same time); that will be noted with a bell if sound is active.

Even if it may sound 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.**2017-06-22:**Revision of the text to fix several factual errors.

Copyright © 2003, 2005, 2017 Pedro Gimeno Fortea.

Special thanks 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.