Recently, two people emailed me asking the same question about my puzzle collection: they wanted to know how it's possible for Mines, my Minesweeper implementation, to guarantee that every grid can be solved without guesswork.

So I wrote up a longish answer to that question, and sent it to both people. And it seems like a waste not to post it here too.

Both
my correspondents were curious to know if there was some kind of
mathematical characterisation of a soluble Minesweeper grid. It's
certainly possible to *imagine* such a thing –

If
there were one of those, then Mines's generator would almost certainly
be a lot simpler. But I don't know of any rule of that kind; I very much
doubt that there's a fully general one (that leaves *every*
soluble grid still permitted). You very likely could come up with a rule
of that kind that errs on the side of caution, so that any pattern of
mines it lets through is soluble. But I think it would almost certainly
rule out a lot of legal grids that you didn't want ruled out: it would
constrain layouts far more than necessary, reducing variety of gameplay,
and worse still, constituting an extra hidden clue to the mine
positions for anyone who knows how the generator is working.

(Perhaps
there wouldn't be that many players who did know. But I'd be one of
them, and not very surprisingly, I care about keeping these puzzles fun
for *me* to play!)

So I didn't do anything like that. It's done in a completely different way.

The first part of the answer is: the code has to include an actual solver, which simulates a human playing the game, and performs the same types of deduction that the human can use, reliably and quickly. (Including tracking what the player does and doesn't know about the grid at a given moment, of course.)

That would be enough by itself to generate a guaranteed-

(All this thinking, of course, has to be delayed
until the user places the first mouse click, because solubility depends
critically on where you're starting from. It's very common that a grid
which can be solved starting from *this* empty square can't also be solved starting from *that* one, even if both starting points would open up an area of more than one square.)

But
my Mines doesn't stop there. There's another piece of machinery I put
in to try to do better than brute force, by making small *changes*
to the grid as the solver progresses. If the solver gets stuck part way
through solving the grid, I don't just throw the whole thing away and
try again from scratch. Instead, I rearrange mines in the parts of the
grid the solver hasn't opened up yet, so as to make sure at least one
new deduction can be made at the current frontier. So the solver gets to
make more progress, and if it gets stuck again, another modification
might be needed.

So the solving process proceeds, with the solver
and perturber taking turns on the grid. When it comes to an end, they've
managed to open up all the non-

The reason why not is because I don't make any effort to *completely* guarantee that the perturbations I make are safe, in the sense of *provably*
not introducing a problem somewhere else, or affecting a square that a
deduction has already made use of. There are probably things I *could* do along those lines, but I decided it wasn't necessary: it's enough that perturbing the grid like this *usually*
doesn't break solubility. (In that, if you do affect a square that a
deduction has already used, there will often be a replacement deduction
in the same area that can still be made, or some other way to get round
to the same place from a different angle.) So there's always a chance
that one of the tweaks to the grid will introduces a new blockage in the
course of removing another one. This is especially likely if something
has to be changed right at the *end* of the solving process: if
the last 2 or 4 squares have a problem that needs a mine moving out of
them, and there's no other covered square remaining to move it to, I
just have to pitch the mine randomly into the already-

So, if the solver gets all the way through the grid but it needed at least one perturbation along the way, then it's not *completely*
guaranteed that the grid is genuinely soluble. Therefore, at that
point, I run the solver again, from the same starting point, and see if
it can get all the way through *this* time without getting stuck!

If it can, *then*
we return the grid to the user; otherwise, we try again, making more
small random modifications in areas where things are blocked, and again,
simply *hoping* that we solve more problems than we create, so that the next run will go better.

The
very last resort, of course, is to give up completely and regenerate a
fresh grid from scratch. I've tried hard to avoid that in favour of
incremental modifications, but sometimes things do just keep going badly
and you have to pick a completely new starting point. My strategy for
that is: as long as each run of the solver requires fewer perturbations
to the grid, we consider that things are still improving, but if a run
through finds *more* problems than the previous run, we conclude that we're stuck in a local optimum with no clear path through to a working grid.

This is all very heuristic, of course. I didn't have rigorous reasons to be *sure*
this particular strategy would work. I just thought it was worth a try,
based on having tried similar things in other puzzles, using other
algorithms from this general class which I think of as ‘discrete but
imprecise’. The basic idea is that if you're trying to generate an
object satisfying a complicated constraint, then as long as the *checker*
is reliable, the code that generates candidates doesn't have to be:
it's OK for it to have a nonzero failure rate, as long as the failures
don't consume too much time. (In some puzzles that's achieved by going
very fast, so that it doesn't matter if you fail often; in others, by
taking great care to fail infrequently, at the cost of each attempt
taking longer. It all depends.)

In fact, this one turned out to
work so well that I was able to provide default settings with over twice
the mine density of the Windows standard ones, and the algorithm still
doesn't take too long before it finds a usable grid. That was actually a
complete surprise to me –