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. 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.
Complements
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.
Solutions to the problems
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.
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 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/
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 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.
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. 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.
Test mode
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.
Revision history of this page
- 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.