This is Part II of my post on image similarity in Python with perceptual hashing. In this post, we will use Spotify's Annoy library to perform nearest neighbors search on a collection of images to find similar images to a query image.

Read MoreLet'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.

- 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.

- depth-first search
- constraint propagation
- 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:

[(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.

- 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.

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 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.

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.

This is Part II of my post on image similarity in Python with perceptual hashing. In this post, we will use Spotify's Annoy library to perform nearest neighbors search on a collection of images to find similar images to a query image.

Read MoreKruskal's algorithm finds a minimum spanning tree in an undirected, connected and weighted graph. We will use a union-find algorithm to do this, and generate a random maze from a grid of points.

Read MoreJust in time for Valentine's day, create a puckering lips animation in D3 from an SVG path, using interpolations and .attrTween(). We will go through the steps from generating points from an SVG path, to interpolating lines in D3 to animate them.

Read More