A million dollar prize for playing the computer game Minesweeper!
Well, it’s almost true. Recently the Clay Mathematical Institute offered a million dollar prize for the solution to a mathematical question (P versus NP Question) and this problem is equivalent to the Minesweeper consistency problem.
The P versus NP Question is not new, but is very topical, as it is linked to algorithm efficiency. Roughly speaking, NP problems appear to be unsolvable in real time. However, once you have a solution, verification is fast. For instance, if you want to break the encryption code RSA (see Infinity 1 issue) by factoring a large number n, then the number of operations required grows exponentially, (like an for some constants a). However, it is quick to check that n is the product of its factors.
Similarly, if you were a travelling salesman visiting n cities (see Infinity 10 issue), as the number of cities grows large, the number of calculations used to find the shortest path grows at least exponentially. Simple algorithms, like those used to sort alphabetically a list of n names, only require n2 operations. So if n = 600 the sort will be executed in less than a 1/3 of a second. However, if an algorithm requires 2n operations and if n = 600 it would take approximately 10247 years and you will be waiting a long time!
The tantalising question is, can we find more efficient algorithms which only take a polynomial number of operations (na for some a). Algorithms solved in polynomial time are relatively fast and termed P algorithms, hence P versus NP.
Recently, the Minesweeper consistency problem was shown to be an NP problem. Minesweeper is a bit like Battleships, except that instead of sinking ships you avoid mines. You start with a blank grid and under some of the squares there are mines. The object of the game is to locate all the mines without uncovering them and being blown up. The first square you uncover is guesswork, but if you aren’t blown up you receive information about how many neighbouring squares (including diagonal neighbours) contain mines. If the uncovered square contains an 8 you know all neighbouring squares contain mines. If it contains a 3 you must try to figure out which three squares contain mines. For instance, suppose you have uncovered the squares shown in the competition below. Can you see where the mines are? If so you win! Try it and see.
However you can also dream up partial grids which can never occur. See if you can show that the following grid is inconsistent and therefore can never occur; i.e. there is no possible arrangement of mines that fit.
0 00 00 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 The challenge in the Minesweeper Consistency Problem is to determine whether a given Minesweeper grid is logically consistent. You must find an algorithm for a computer to test the consistency of any given Minesweeper grid. If it runs in polynomial time, or you can prove that no such algorithm exists, then you are rich!
[Ian Stewart, Million-Dollar Minesweeper, Scientific American, October 2000,
p 80.
Richard Kaye, Minesweeper is NP-complete, The mathematical Intelligencer, Spring 2000, Vol 22, No 2, p 9.]
