If we’re gonna get fuzzy, let’s be discrete - Up close and personal with a Minesweeper solver

In 1992, Microsoft released Minesweeper alongside Windows 3.1. We can only imagine the purpose Microsoft originally intended, but most of us know Minesweeper as the worst Cookie Clicker clone ever designed. We’d fire it up and click all over the board until the smiley face turned sad (and dead). Sometimes we’d get pretty far; sometimes wide swaths of the board opened up, and we knew we were probably some kind of genius, fated to discover new physics, or a way to recycle sewage into edible food. Well, until sad face appeared again, boredom grew to disdain, and Chip’s Challenge twinkled its eyes at ya.

I grew to love Minesweeper in my final year of grade school. Because I’d fallen deep into computers from a young age, my high school, hesitating not a single second seizing opportunities to hire less IT staff to foster curiosity, assigned half my day to PC Support, where on occasion I’d be asked to fix a computer. Otherwise, I played a lot of Minesweeper. (And, of course, those LAN multiplayer Halo and Quake 3 demos #millenials)

The rules of Minesweeper are pretty simple. At the start of the game, the board contains a number of mines – this number is displayed prominently. Each cell either contains a mine, or doesn’t. When you click a cell, it reveals either a mine, in which case:

Enough talk – more pretty pictures. Well, more pictures, at least.

In the first picture, there is a number 1 which has only a single neighbour. By the rules of the game, this neighbour must contain a mine. We flag it, so we remember not to click it.

That was the only place where the obvious choice of action is derived entirely from a single number. We’ve gotta get clever to continue. And so we shall!

Numbers that share neighbours also share information – like, if neighbour X is a mine, it may mean neighbours Y and Z cannot contain mines, and are safe for the clicking. Which, you guessed it, we can take advantage of.

The topmost number 1 touches both neighbours highlighted in blue. Since this #1 means only one of its neighbours has a mine, we can infer that if we knew the location of the mine, the other neighbours could safely be clicked. The same applies to the 1 below it at (2, 1), whose neighbours are highlighted in orange.

See the single orange neighbour not overlapped by the blue? If we were to assume a mine was there, it would mean those two blue neighbours contained 0 mines, safe for the clicking. So we click them. Now the topmost #1 touches no cells, leaving no place for its single mine. Of course, this means the #1 pops out of existence, appearing spontaneously in the bank account balance of some fortunate soul (or Shia LaBeouf’s, setting off a chain of events culminating in the attempted assassination of the US president). Or, we end up clicking a mine and losing the game. It all depends on how strange you believe the universe is.

For the sake of the exposition, we’ll adhere to Occam’s razor, and assume clicking both of the blue-shaded cells leads to certain death. Since we’re forced to click both blues if we flag the orange, we know we can’t flag it without certainly dying. We’ve gotta do the other thing… what was it? …uh, Clicking? Yeah.

This same logic can lead us to flagging a cell, instead of clicking.

Taking it one step further, we can combine information from multiple cells to expose less obvious solutions. In the next example, the #1’s at the bottom left portion touch all but a single neighbour of the #3. We know both of those #1’s combined provide two mines, leaving one mine of #3 unaccounted for. We infer the mine’s location must be in the only neighbour #3 doesn’t share with the #1’s.

Note: cells shaded blue have been right-clicked, and red-shaded cells have been left-clicked.

Using only this rule, we can get pretty far. Much of the time, a single move can open up the board.

That is, until those moves run out.

Well, there is one other general strategy we missed. Our previous strategies relied on one number completely containing all the neighbours of another number. There are some cases where only partial overlap is decisive enough to uncover Deep Truths™ of the board.

The three blue-shaded cells contain exactly one mine. Another way of putting it is: the blue-shaded cells contain a maximum of one mine. This is true, even for the cells overlapping the green – since there is a maximum of one mine, we can effectively treat the two overlappers as a single cell. This leaves only one other place for green’s remaining mine: the bottommost greenie. We flag it, and the board opens up again… at least for a bit.

And then there were no more strategies. Finito. Good day, sir!

Well, of course, no more strategies except for the other ones, which we’ll take a look at next time, before finally accepting the futility of our situation and graphing grasping at straws to milk the board for all she’s worth.

Bonus win gif for you beautiful readers.

We'd love to hear your thoughts. Find us on Twitter, LinkedIn or write in to hello@perchsecurity.com

Next: Kovter Research and Analysis