Minesweeper is a game that comes with the Microsoft Windows operating system. A rectangular grid is displayed. A specific number of mines have been laid in the grid. Each cell can contain one or no mines. In the Microsoft version, you are also told the total number of mines, although this is not an essential feature of the game.
You start the game with no information. You pick a cell, and if it's mined, you die. If there are immediate neighbors of the cell which are mined, then the number of such cells shows up. Otherwise, that cell shows up as cleared, and since you know that no neighbor contains a mine, each of those neighbors is also uncovered. The uncovering continues recursively, until reaching a cell that is not mined, but has a mined neighbor. This results in a cleared region with a border of cleared cells, each of which lists the number of its 8 neighbors that contain a mine. Your task is to locate the mines.
Essentially, you carry out your task by stepping bravely on new squares, thus establishing they are clear and getting new information, and by planting marker flags on squares that you have determined contain a mine. Of course, you fail by stepping on an mined square, or by finishing the game with an unmined cell incorrectly marked as mined. (This latter event cannot happen in the Microsoft version. You can't finish the game until there are exactly as many flagged cells as there are mines.)
There are two interesting questions. The first is, obviously, given a configuration, can you determine where a mine is, and how? For example, consider the following arrangement:
?|1| | |1|?|?
-+-+-+-+-+-+-
?|2| | |1|2|?
-+-+-+-+-+-+-
?|1| | | |2|?
-+-+-+-+-+-+-
?|2| | | |1|?
-+-+-+-+-+-+-
?|1|1|1|1|2|?
-+-+-+-+-+-+-
?|?|?|?|?|?|?
Can you determine the arrangement in this problem?
?|?|?|?|?|?
-+-+-+-+-+-
?|2|2|2|2|?
-+-+-+-+-+-
?|2| | |2|?
-+-+-+-+-+-
?|2| | |2|?
-+-+-+-+-+-
?|2|2|2|2|?
-+-+-+-+-+-
?|?|?|?|?|?
A second, less obvious, question is, given a configuration, can you determine if it is legal, that is, that it could arise from some arrangement of mines in the uncleared cells.
The second question is a consistency question, and might seem to be of interest only to someone who is designing a mine puzzle. But in fact, if we can answer the consistency question, then we can solve the puzzle, and identify cases where the puzzle is not solvable. Suppose we want to know if there is a mine in a given uncleared cell. Then we can ask whether the configuration that includes all our current knowledge, plus a mine in the given cell, is consistent. If not, there can't be a mine there. If it is consistent, there may be a mine there. But if the puzzle is solvable, there must be an uncleared cell for which the consistency test will report that there can't be a mine there.
I give up, let me see the solution.
Back to the puzzle page.