We're going to solve Minesweeper as a constraint satisfaction problem.
What is Minesweeper?
Minesweeper is a single-player puzzle game that you may have played on a computer at some point.
In the last post, we generated random Minesweeper boards in Python - check that out here if you haven't yet.
As you can see in the animation, it starts out with all of the squares covered, and you play the game by uncovering squares.
The goal is to not uncover a square that contains a mine, so if you've identified a square that likely contains a mine, you can flag it so that you remember to avoid uncovering it.
Two possibilities when you uncover a square:
The square contains a mine, and the game ends because you lost.
It is a numbered square between 0 (zero) and 8 - we'll call this number the square's constant.
If you uncover all of the squares except for any mines, you win the game.
So the goal is to figure out where the mines are and avoid uncovering them.
It is often possible to solve easier puzzles simply by using logic to determine where the mines are located and which squares are safe to uncover.
With more difficult puzzles, you will sometimes have to resort to guessing if you find yourself left with covered squares that are equally likely to be mines or safe squares.
Beginner - the board ranges from 8x8 to 10x10, with 10 mines.
Intermediate - the board ranges from 13x15 to 16x16, with 40 mines.
Expert - the board is 30x16, with 99 mines.
The animation that you just saw is an intermediate puzzle with a 16x16 board and 40 mines.
Algorithms used in this solver
depth-first search with backtracking.
Using these algorithms - constraint propagation in particular - we can mimic the logic human players would use to play Minesweeper.
After getting as far as we can with logic, we will use depth-first search with backtracking to guess new squares to uncover.
A constraint satisfaction problem has a few parts:
A set of variables.
A set of constraints on these variables that must be satisfied.
A set of values that can be assigned to the variables.
The variables are the board squares, which each contain either a mine or a constant between 0 and 8.
In most Minesweeper boards, squares with a 0 constant will be shown as blank, and constants above zero will have the number displayed in the square.
In Minesweeper, the constant number of a square is equal to the number of mines in adjacent squares.
I am assuming that the board is consistent, meaning that the numbers on the board do indicate the true number of adjacent mines.
The yellow square at (5,1) has a constant of 2, indicating that there are 2 mines in adjacent squares.
The asterisks are mines.
This square's constraints list would look like:
A Minesweeper square either is a mine, or is not a mine (i.e. a safe square), which we can represent with ones and zeros, and are the values that we can assign to each square.
So each square in the board will be assigned a value of 1 if it is a mine, and a value of 0 if it is safe.
The corresponding values to the list of constraints of (5,1) look like this:
The values of the adjacent neighbors to (5,1) must add up to its constant value of 2.
This is the constraint that is imposed on each variable.
If we try to assign an extra mine to one of the neighbors of (5,1), that would violate the constraints.
A valid solution will be a configuration of 0s and 1s assigned to each variable that does not violate any variable's constraints.
The board is a 2-D matrix.
Each variable is represented by a Square class, which has a list of constraints Square.constraints that starts out as a list of board coordinate points (x,y) of adjacent neighboring squares.
The class MinesweeperSolver maintains a list MinesweeperSolver.moves of these Square objects that get added and subtracted from it as the game goes on.
A Square object also contains information about its constant and its value, where the value is initialized to None.
There are actually two attributes for the constant: Square.constant and Square.original_constant.
The original constant never changes, but as we will see shortly, the constant value will be altered.
This solver starts off using depth-first search. The first square the player picks to uncover is added to a queue of squares to uncover MinesweeperSolver.squares_to_probe.
When we uncover a square, it will either show a mine or a number.
If the square has a zero constant number, then the solver continues to uncover adjacent squares until it is left with a perimeter of squares with non-zero constants.
In this graphic, the gray squares are covered squares.
If we started off uncovering the bottom left square - blank squares have a zero constant - it would continue to uncover adjacent squares until we are left with this perimeter.
As new squares are uncovered, they are marked as safe and added to MinesweeperSolver.moves.
Marking a square as safe or a mine is where constraint propagation comes in.
When we determine that a square is definitely a mine or definitely safe, we can remove that square from each of its adjacent neighbors list of constraints.
If we've determined that the square is a mine, we will also decrement the constant value of each of its adjacent neighbors by one.
The constant value is decremented because we've identified one mine, so now we have one fewer mine to identify in the remaining constraints of that square - this is what I was referring to earlier about having two attributes for the constant.
If you're playing the computer game version of Minesweeper, this is where you would flag a square that is definitely a mine.
After we've done this, each square's constraints list will only contain unknown adjacent squares.
Next we can examine the squares in MinesweeperSolver.moves to see if we can figure out any of the unknowns from their constraints.
When we look at each square in MinesweeperSolver.moves, and its list of constraints, there are two logical conclusions that we can possibly come to.
1. All of the constraints are mines
If a square has a constant value that is equal to the number of constraints in its list, then we know that these constraints must be mines.
The starred square at (1,3) has to be a mine.
We know the value of all of the other neighbors of square (2,4), so they would all have been removed from its list of constraints when we marked them as safe.
Square (2,4)'s constant is 1, and square (1,3) would be the only square left in its constraints list, so square (1,3) must be a mine.
2. All of the constraints are safe
On the other hand, if the square's constant value has been reduced to zero (meaning all neighboring mines have been identified), but its constraints list is not empty, then we can be sure that the leftover constraints are all safe.
If we marked the starred square (1,3) as a mine, we would decrement the constants of its neighbors by one, which includes square (0,4).
That would decrease square (0,4)'s constant from one to zero, and its constraints list would still contain the uncovered square at (0,3), so that square would have to be safe.
Once we have reduced a square's constraints to an empty list, and its constant to zero, we have satisfied the constraints on that square and can remove that square from MinesweeperSolver.moves.
Compare pairs of constraints
After we've reduced the constraints as much as possible in the previous step, there may still be some non-empty constraints in MinesweeperSolver.moves.
We can try to further reduce these by comparing pairs of constraints.
If one constraint is a subset of another, then we might be able to further reduce them.
For example, if we had the following scenario comparing two squares and their constraints.
(note: this is a fake example and not taken from the board in the example graphic from earlier)
Square one with constant 1, and constraints [(0, 1), (1, 1)]
Square two with constant 1 , and constraints [(1, 0), (1, 1), (0, 1)]
Square one's constraints are a subset of square two, so we can subtract them from square two, and also decrement the constant of square two.
Square one with constant 1, and constraints [(0, 1), (1, 1)]
Square two with constant 0 , and constraints [(1, 0)]
And now square two's constant has been reduced to zero, so we know that the remaining constraint, square (1,0) is safe to uncover.
Backtracking search to try to guess the next move to make
Finally, we might get to a point where there are no more covered squares that are obviously safe or obviously mines, but we haven't won or lost the game yet.
MinesweeperSolver.moves is not empty, so we will look at the unknown constraints for each square in this list, and conduct an exhaustive search to find all solutions for the rest of the squares that would not violate constraints.
The solutions are just permutations of a list of 0s and 1s, with a value for each of the remaining squares, and however many mines we have left to identify will be the number of 1s in the list, with the rest being 0s.
Then each solution is checked to make sure that assigning those values to the squares does not violate any constraints.
After that, we look at all of the solutions generated, and if there are any squares that are safe in all solutions, or mines in all solutions, then we will start with those to either uncover or flag them and continue on with the game.
In some cases there might not be any obvious safe squares or mines, and we would just take a random guess of the next square to uncover.
Minesweeper algorithms + Improvements
There are lots of improvements we could make on this solver!
We could use probability to try to figure out the best squares to uncover, based on where mines likely are.
If we uncover a square that has a 1 constant, and uncover a square that has a 2 constant, the next guess might be to uncover a neighbor of the square with the 1 constant since there is a lower chance of uncovering a mine than if we uncovered a neighbor of the square with a 2 constant.
Or if we know that the mines are evenly distributed over the board, we could use a heuristic when guessing new squares to uncover that would compute a probability for each remaining covered square based on the number of mines left and where the known mines are.
Finding the Lowest Common Ancestor of a pair of nodes in a tree can be helpful in a variety of problems in areas such as information retrieval, where it is used with suffix trees for string matching. Read on for the basics of this in Python.
This blog post walks through the process of writing a fragment shader in GLSL, and using it within the three.js library for working with WebGL. We will render a visually appealing grid of rotating rectangles that can be used as a website background.
Streaming can be a great way to transfer and process large amounts of data. It can help save space and/or time, if the data uses a lot of memory, or if you want to start processing or visualizing the data as it comes in.