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