As you will no doubt realise, I get a lot of emails on this subject. Whilst I value this correspondence greatly, I find it almost impossible to reply to every one. To save time and energy, I've started a FAQ on Minesweeper and the "P=NP"? question, and will update this list whenever possible. (It is currently in a fairly rudimentary state!). Any comments or contributions to this FAQ will be most welcome.

**A:** Please click here.

**A:** The paper was published in the
*Mathematical Intelligencer* (Springer Verlag, New York)
Volume 22 number 2 (Spring 2000 ), pages 9--15. Its title is
"Minesweeper is NP-complete".

**A:** I don't think you can. Try a library.

**A:** There are some other papers you may like on
this web site including a PDF presentation on
minesweeper and a companion PDF paper entitled Some minesweeper configurations.

**A:** There are quite a lot of textbooks and
research monographs in these areas. A quick trawl of amazon (for
example) will bring up a few. A few that I liked include Garey and
Johnson "Computers and Intractability", Hopcroft and Ullman
"Introduction to Automata Theory, Languages and Computation",
Papadimitriou "Computational Complexity", and Gibbons "Algorithmic
Graph Theory". But there are many others, some putting a different
slant on the problems.

If anyone knows of goods web sites concerning NP-completeness, I would be interested to know, and will give links to them here.

**A:** Garey and Johnson give a few of these: most
of the ones they consider turn out to be NP-hard (at least) but may
not in fact lie in NP themselves. Some are even PSPACE-complete,
which is presumed (but not known to be) even harder than
NP-complete problems.

Familiar examples include the game of Draughts (also called "Checkers"!) on an arbitrarily large board: this is known to be PSPACE-hard, but not known to be in NP; The Japanese game of "Go" is also PSPACE-hard but not known to be in NP. Another nice example is of crossword-puzzle generation. This (suitably formulated) turns out to be NP-complete.

One correspondent asked me about battleships. As I understand "battleships", the question concerns whether it is possible to place a collection of "ships" on a square grid avoiding certain squares which have already been tested and found to be vacant. It is clearly in NP, and also contains the bin-packing problem as a special case, so is also NP-complete.

**A:** This is a question one can ask about any
particular rectangular grid with the squares decorated by numbers
0--8, mines, or left blank. It asks: is there a configuration of
mines in the grid that would result in the pattern of symbols one
sees (according to the usual Minesweeper rules)?

The word "problem" here may be misleading. Think of it as a specification for an algorithm or computer program. There are certainly computer programs that meet this specification. (For instance, one can simply search through all possibilities, though this may take rather a long time to do!)

The classes P and NP are certain classes of such problems (or specifications) with yes/no answers like this, and reformulating Minesweeper in terms of such a specification helps greatly in its analysis. By my result, the "P=NP"? question is equivalent to the question of whether there is a polynomial time algorithm that meets the specification in the Minesweeper Consistency Problem.

**A:** The letter n is typically used in complexity
theory to denote the *length* of the input. One possibility is
to code the input as a string of symbols from a finite alphabet, or
even as a string of binary digits. Then n is the length of this
string. (This is OK provided you choose a "sensible" natural coding
that does not have a lot of redundant information.)

For most "sensible" codings, the n just given is (within a
polynomial) the same as the number of squares in the input
configuration. For this reason, I usually think of n as the total
number of squares, since the distinction really doesn't matter as
we are only looking for algorithms that are (in time taken)
*polynomial in n*. Similarly, if there are of the order
sqrt(n) unknown squares (as is typical in my configurations in the
paper i wrote) then "polynomial in n" and "polynomial in sqrt(n)"
are essentially the same, so it's OK to think of n as the number of
unknown squares if you prefer.

**A:** As far as I know, the answer is no, but I
would be delighted to hear otherwise.

In principle, any of the literally hundreds of NP-complete problems may give a way to settle the "P=NP?" question (whichever way it goes). Many of them have been studied, but there is no success to date (to my knowledge!)

**A:** For the definitive answer, see the Clay
Institute's pages. But to be brief, you must either prove that P=NP
or prove that P is not equal to NP, and do it in such a way to
satisfy the mathematical community. (I.e., write a paper and
publish it in a refereed journal, so your paper will have to be
checked carefully by certain anonymous referees.)

**A:** You will need to either show that there is
no polynomial-time algorithm that solves the Minesweeper
Consistency Problem, or else find an algorithm that solves it in
time p(n) for some fixed polynomial p(x) where n is the number of
squares in the input configuration *and prove that your algorithm
always returns the correct answer in this amount of time*. Many
algorithms I see work very nicely in most cases, but do not always
guarantee to give an answer.

**A:** This request is quite common, and I have to
be very careful here as I only have a polynomial-bounded amount of
time!

Because of pressures of time and my other commitments at work I
have to say I am *not* interested in approximate algorithms or
"practical algorithms that work most of the time". (Such algorithms
are no help with P=NP? anway.) Please read the following very
carefully, as I can only discuss your work with you if it falls
into my area of interest and expertise. Please make sure that a
long discussion will not be simply a time-waster, and that it is
possible to communicate effectively.

If, having read this, you are absolutely sure your work is within the area of interest I outline, and you understand all the issues concerning the problem as discussed on these pages, we can discuss it further.

Firstly, I am interested in algorithms that solve what I call the "Minesweeper Consistency Problem". (See above.) In some sense this is equivalent to the problem of how to play Minesweeper "perfectly". But please address the Minesweeper Consistency Problem, not a different one. In particular your algorithm needs to be able to work on a r by s board FOR ANY VALUES OF r,s. A practical implementation of the algorithm will have time and space constraints due to the machine being used, but the algorithm itself must not have any such constraints.

Here, I will use the letter n for the product rs, i.e., the number of squares on the board. Obviously n varies with the particular input and must NOT be regarded as "constant".

Now, I believe it is possible to come up with algorithms that work in most cases, *especially* for cases generated "randomly". I am NOT interested in these, only in algorithms that work in all cases, and work in all cases in polynomial time. This means that, for your algorithm A there are constants a and b such that:

for any input I to A with n squares

- if I is "consistent" the algorithm returns the "yes" value taking no more than n^a + b units of time.

- if I is not "consistent" the algorithm returns the "no" value taking no more than n^a + b units of time.

Time can be measured as the number of single additions, multiplications or single machine-code instructions on a typical microprocessor. So, to multiply together two 8 bit integers to get a 16-bit integer is one step. But to multiply two integers with n bits each, or to find a determinant of an n x n matrix if you wish to do this, takes an amount of time that varies with n (and will depend on the paricular method you propose to use).

I want to emphasise that, to be of relevance to P=NP? and to be of interest to me, your algorithm A must ALWAYS return a correct answer in the time given. I am not interested in algorithms that sometimes, albeit very infrequently, give incorrect answers or no answers at all. (These algorithms may be of practical use, but are not helpful for the P=NP? problem, and are not of interest for my research.)

Also, please note that randomly generated test data usually gives a VERY POOR indication of the performance of the algorithm. What is much more interesting is a precise (mathematical) argument saying why the algorithm always produces the correct answer in some given time bound

In electronic form, no. One way to build test cases is to build logic circuits in Minesweeper using the ideas from my original paper. I'm sorry I can't be more specific on this question. If any one has such a collection of data it could be interesting.

**A:** I don't know the answer to either of these!
For an NP-completeness result one would have to formulate a
decision problem in terms of an arbitrarily large pack of cards,
and I don't even know how one should do this.

**A:** Sokoban is a really nice puzzle game
invented, apparently, by Hiroyuki Imabayashi in 1982. See http://www.games4brains.de/sokoban_history.htm
for more information. It was proved to be PSPACE-complete by Joseph
Culbertson ('Sokoban is PSPACE-complete' http://web.cs.ualberta.ca/~joe/Abstracts/TR97-02.html).
PSPACE-complete problems are generally regarded as being even
harder in complexity that NP-complete problems (though the question
"NP=PSPACE?" is also open and seems very hard too).

**A:** Many other games may also be NP-complete or
NP-hard. Let me know if you spot anything interesting.

**A:** Problems around "P=NP?" come up in many
places, notably in the study of computability, computational
complexity, and for a more practical side, combinatorial
optimization. It is also possible to study algorithms in particular
subjects such as graph theory, other branches of combinatorics, and
also in number theory.

My own interest in these questions arose from an interest in the logical foundations of number theory where computational complexity questions are really very close. My PhD students have all studied nonstandard models of arithmetic or analysis in some form or other, and I don't feel I can take on postgraduate students outside these areas. (But I have other colleagues—some in Birmingham—who are interested in supervising students in combinatorial optimization.) To do a PhD you would certainly have to look a lot wider than just Minesweeper! (But there may be possibilities for Birmingham maths students to do a final-year project in some area associated with Minesweeper and NP. If you qualify and are interested, please discuss it with me.)

Thanks to: Frank Reffel for information and useful contributions regarding this page.

To Richard Kaye's main minesweeper
page.

To Richard Kaye's home page