Computational Recreations

Minesweeper and logical circuits

(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.

Figure 1: Minesweeper puzzle. Where are the hidden mines?
Figure 1: Minesweeper puzzle.

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.

Figure 2: Consistency examples: (a) Consistent position; (b) inconsistent position.
a.
Figure 2a: Consistent position.
b.
Figure 2b: Inconsistent position.

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.

Figure 3: Logical input and conducting wire in a «Minesweeper circuit».
Figure 3: Logical input and conducting wire.

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.

Figure 4: NOT gate.
Figure 4: NOT gate.

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.

Figure 5: OR logical gate: z = x OR y.
Figure 5: OR logical gate.

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.

Figure 6: Logical function NOT (x OR NOT y). Is this board consistent?
Figure 6: Consistency problem.

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.

Complements

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.

Solutions to the problems in the previous article

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.

Links

About Minesweeper logic circuits

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

About other games proved hard

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

Some games mentioned in the text that are available online

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/

About NP-completeness and the million dollar prize

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

Appendix: Minesweeper Designer documentation

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.

Design 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.

Test mode

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.

Revision history of this page

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.

This page aims to be valid XHTML