Richard Kaye's Minesweeper Pages

Until recently, tiling problems were largely relegated to the domain of "recreational mathematics" (an obvious oxymoron to most non-mathematicians, but a pleonasm to true believers).
(Solomon W. Golomb, "Mathematics after forty years of the space age", Mathematical Intelligencer, Fall 99, 38-44.

Minesweeper is NP-complete!

For minesweeper addicts, this is either very good news, or very bad news (it depends on your point of view). My paper with the above title, which incidently goes to some lengths to explain what NP-completeness means and why it is important, has appeared in the Mathematical Intelligencer.

Since this paper appeared, my results have featured in Scientific American and in the press. For further discussion, with full references, please follow this link. You may find the section titled "So what's it all about?" helpful!

A companion paper, with some interesting Minesweeper configurations and puzzles is available here in PDF format. I have just set up a FAQ list concerning minesweeper and NP-completeness which is available here.

A PDF presentation on minesweeper that I have used on several occasions, including Open Days at Birmingham University and first given at the ASE meeting in Birmingham, Jan 3-5 2003, is also available here (PDF file, 300k). This talk contains some nice graphics, and interesting minesweeper configurations.

Infinite Minesweeper is Turing-complete!

"Infinite minesweeper" refers to a family of variations of the game with possibly different kinds of "mines", and different rules concerning them. It is "played" on an infinite grid rather than a finite one, but it nevertheless has something of the flavour of ordinary minesweeper. You can read about it and in particular how infinite minesweeper configurations can mimic arbitary computer programs in mt (slightly more technical) paper which is recently available in pdf format here.

I would welcome any suggestions, questions or comments or either of these papers and will endeavour to reply to all queries.

Minesweeper papers

These are my minesweeper papers, with the definitive latest version in PDF format where available.

• "Minesweeper is NP-complete", Mathematical Intelligencer, vol 22, number 2, pp9-15, 2000. Note: no electronic copy is available online.
• "Some Minesweeper Configurations". Published in Portugese in Boletim Sociedade Portuguesea de Mathemática, Janeiro 2007 (Número especial), Lisbon. ISSN 0872-3672. pp 181-189.
• "Infinite Versions of Minesweeper are Turing-complete". School of Mathematics preprint number 2000/15. University of Birmingham, 2000.

Minesweeper links

My other web pages:

• Minesweeper and NP-completeness
• My FAQ on minesweeper and NP-completeness

Here are a small number of external related minesweeper links I found and quite liked.

• The Authoritative Minesweeper, http://www.minesweeper.info/ by Damien Moore, including some articles as well as other news.
• Programmer's minsweeper, http://www.ccs.neu.edu/home/ramsdell/pgms/index.html, from John D. Ramsdell, who writes: "In this version of Minesweeper, the player supplies a Java program that implements a strategy for winning a Minesweeper game."
• Minesweeper strategies, at http://www.frankwester.net/winmine.html.

Other games

There are plenty of other games with interesting mathematics behind them; some of these may turn out to be NP-hard or NP-complete. I provide a couple of links to some of my favourites here. (Sorry: some of the links here are a bit old. I will update them someday soonish if I can.)

• King Albert is a patience (or "solitare") type of game played with nine columns of cards rather than seven, and much more skilful and enjoyable. (Many people will recognise similarities between certain moves in King Albert and the Towers of Hanoi puzzle.)
• Sokoban is another game where the solution is easy to verify but often difficult to spot. It is also ridiculously addictive.
• Try also the pages on "Mathematically Interesting Games" at http://www.math.toronto.edu/mathnet/.

Note: "Minesweeper" here refers to the game of that name which is provided with Microsoft's "Windows" operating system and is available in other versions on the web. (I do not have any connection with Microsoft and nothing here should be regarded as comment on any of Microsoft's products.)