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.)
The obvious puzzle is, given partial information about a configuration, to determine the status of all the unknown squares, which either have a mine or do not. In the diagrams of play, a square is marked with a question mark if its status is unknown, with a number if it is known and empty, but is next to the given number of mines, and blank if it is known and empty and not next to any mines.
Note a peculiarity of the program. If you choose to declare that an unknown square is actually minefree, and it is, then the program will replace the question mark by a blank or a number, depending on whether it has 0 or nonzero immediate mine neighbors. If the number of mine neighbors is zero, then it will also immediately replace the question marks on those neighbors by their status. Any of these neighbors which also has 0 mine neighbors will in turn be processed in this way. Sometimes a single move can reveal a great deal of information.
Puzzle 1:
?|1| | |1|?|?
-+-+-+-+-+-+-
?|2| | |1|2|?
-+-+-+-+-+-+-
?|1| | | |2|?
-+-+-+-+-+-+-
?|2| | | |1|?
-+-+-+-+-+-+-
?|1|1|1|1|2|?
-+-+-+-+-+-+-
?|?|?|?|?|?|?
Puzzle 2:
?|?|?|?|?|?
-+-+-+-+-+-
?|2|2|2|2|?
-+-+-+-+-+-
?|2| | |2|?
-+-+-+-+-+-
?|2| | |2|?
-+-+-+-+-+-
?|2|2|2|2|?
-+-+-+-+-+-
?|?|?|?|?|?
Puzzle 3: Given any partial configuration, what possibilities are there? Can there be no solution, one, or several ways of filling in the missing values? On a 6 by 6 board, for instance, what is the LEAST amount of information (number of cells that are given) that will allow you to determine the rest of the board? What is the most amount of information you can give for which there are still at least two solutions? What is a configuration which cannot have a solution?
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.