Let's play Minesweeper in Python...
You can find the code for this post here.
The animation was created with Matplotlib.
We're going to solve Minesweeper as a constraint satisfaction problem.
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.
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.
The animation that you just saw is an intermediate puzzle with a 16x16 board and 40 mines.
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:
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:
[(4,0),(4,1),(4,2),(5,2),(6,2),(6,1),(6,0),(5,0)]
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:
[1,0,0,0,1,0,0,0]
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.
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.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.
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.
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.
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's constraints are a subset of square two, so we can subtract them from square two, and also decrement the constant of square two.
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.
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.
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.
Let me know if you've developed your own Minesweeper solver, and what techniques you used!
If you have questions or comments, write them below or feel free to reach out on Twitter @LVNGD.
Starting out with general purpose computing on the GPU, we are going to write a WebGPU compute shader to compute Morton Codes from an array of 3-D coordinates. This is the first step to detecting collisions between pairs of points.
Read More
In this post, I am dipping my toes into the world of compute shaders in WebGPU. This is the first of a series on building a particle simulation with collision detection using the GPU.
Read More
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.
Read More