# How we make Minesweeper puzzles

There are of course, two types of Minesweeper puzzles. The perhaps most well-known is the classic game that shipped with older versions of Windows, and unavoidably involves some degree of guessing. The second type (and the type we are talking about), is the logic-based pen-and-paper version. This version doesn't involve any guessing, but instead asks you to arrive at the solution from careful analysis of the clues.

## Minesweeper solver

It doesn't matter what type of puzzle we are dealing with, the first consideration is always the solver. These are the steps our solver will go through,

1. We look at each clue in turn, and count the number of mines around that cell. If we have the specified number of mines for that clue, we will mark all the other neighbours with a cross, i.e. these cells cannot be mines. We also look to see if all the remaining surrounding cells have to be mines, i.e. if we have a clue of 4, we already have 1 mine, and another 3 undecided cells, then these 3 undecided cells must be mines as well.

Note that when we first start the puzzle, this step will catch all the clues with a value of '0'.

2. The first step of the solver is quite straightforward, but the second step is much more involved. We look at each unsatisfied clue (i.e. those that don't have their full complement of mines yet). We look at all of the possible combinations for those unsatisfied clues, and look for any common elements across all those combinations.

We may find that a particular clue has 6 possible combinations for the remaining mines, for example, but only 3 of those don't cause a conflict with other clues. For all 3 valid combinations, they might all have a mine in one particular cell, or one particular cell might be empty for all valid combinations.

3. The third step takes the second step a little further. The third step also looks at each combination in turn, but also applies the first 'easy' solve step to each combination. If a contradiction (i.e. a grid that can't be solved, or is invalid) is found, then we can discard that combination.

It is important to note here that we only move to the second step when the first step no longer gives us any results. Likewise, we will only move to the third step when the second step stops giving us results. We repeat this process until we have a solution.

Our solvers drive the overall 'feel' of our puzzles - we feel very strongly that if a solver uses a generic Computer Science 'efficient' algorithm (the backtracking algorithm is a firm favourite), then that will give puzzles that are not very satisfying to solve. This is why most of our solvers will solve a puzzle in the same you or I would solve a puzzle.

Minesweeper is no different here. It might look on the surface that our solver is applying some kind of brute force algorithm here, but actually, we have only codified how you or I solve minesweeper puzzles, i.e. we will look at clues and try by a process of elimination to place a single mine or empty cell.

## Minesweeper generator

Now we have our Minesweeper solver, our generator follows these steps,

1. We start with a blank grid, and insert a number of mines in to the grid at random. We aim to cover around a third of the grid with mines, with a little bit of random variability.
2. The second step is to insert clues for every cell that doesn't contain a mine. This guarantees that we will trivially have a minesweeper puzzle we can solve.
3. We now look at each clue in turn, and see if the puzzle remains solvable (with a unique solution) if we were to remove that clue.

That's it! It's quite common for our solvers to be the most complicated part of generating any type of puzzle, but this is especially true of Minesweeper puzzles!