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.
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" 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.
These are my minesweeper papers, with the definitive latest version in PDF format where available.
My other web pages:
Here are a small number of external related minesweeper links I found and quite liked.
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.)
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.)