My Analysis of Mine Sweeper Algorithms

minesweeper.png

By Laker N.
Age 14
Palo Alto, CA

CodeWars is an online collection of programming challenges ranked by difficulty. It’s community driven, meaning that, though the problems require thinking, they are satisfying to complete. One problem on CodeWars that caught my attention was “Mine Sweeper” by the user myjinxin2015, a prolific creator and the second highest holder of honor, gained by solving and making the site’s code challenges. “Mine Sweeper” is a kyu 1 code challenge, the hardest on the site. (Kyu, or difficulty, ranges from 1 to 8, with 8 as the easiest and 1 as the hardest.)

Despite its ranking, I’ve always liked the idea of Minesweeper. “Mine Sweeper,” however, didn’t involve programming the game; “Mine Sweeper” is kyu 1, because the task is to program an algorithm to solve Minesweeper. Specifically, given a board configuration with a number of the squares identified, fill in the rest.

Though the problem intrigued me, I was at a loss for how to attack it. After some brainstorming, however, I came up with a rule my algorithm could apply to a board configuration to solve unknown squares. If a square has as many empty tiles around it as it needs mines to fulfill its number, then all surrounding squares are mines. If a square needs no more mines, then all unknown surrounding tiles are safe. In code, I assigned each tile the number of mines needed to satisfy its number minus the number of mines already flagged around it. This number I called the tile’s working number. For example, a tile with the number three and two flagged mines around has a working number of one: any unknown tiles around it can act as though it only needs one mine. With working numbers, a tile with number five, three mines flagged around it, and two remaining unknown tiles knows to flag all surrounding unknown tiles. I call the first rule Easy Logic, because most Minesweeper players rely on it before thinking harder.

The code for EasyLogic is split into three functions: one to find tiles who need to flag all surrounding mines, one to find tiles who need to open all surrounding tiles, and one to combine them.

About half of Minesweeper games can be solved with only Easy Logic. A fraction of games, however, evolved into configurations Easy Logic couldn’t untangle. I knew Easy Logic would still be integral to my solution, but I was going to need something more.

The second rule I came up with was significantly more complicated to implement. I call it Contradiction Search. Contradiction Search looks at unknown tiles around known tiles one by one and pretends they are mines. It then applies the rules of Easy Logic to flag mines until one of two outcomes is reached. Either no conclusions can be drawn, or a contradiction is reached. A contradiction is when, as a result of the unknown test tile being a mine, logic indicates that there must be safe tiles in a location. These same safe tiles that must exist if the test tile is a mine deprive another tile of enough mines. The contradiction shows one of the premises must be incorrect; Easy Logic doesn’t fail, so the incorrect premise is that the test tile is a mine. Therefore, the test tile must be safe.

The following image is the comment in the code to explain Contradiction Search.

laker3.png

A simple example of a contradiction is in a 3x2 board in which the bottom row has three ones. See the image for a visual. If Contradiction Search checks the top left square, Easy Logic dictates that, because the middle one has satisfied its one mine requirement, all other surrounding squares are safe. That means that the top middle and top right squares are safe. This, however, deprives the bottom right one of its mine: the two possibilities it had (top middle and top right) are both safe. This is a contradiction and proves that the top left square is safe.

With Easy Logic and Contradiction Search in hand, my algorithm could now solve the majority of Minesweeper boards. Almost all games they failed to solve were unsolvable, meaning there are two or more possibilities, and there is no information to distinguish them. The simplest example of an unsolvable position is a 2 by 1 board with one mine. There is no information that tells whether the mine is in the left square or the right square. To solve the board, a player would need to guess.

In practice, Contradiction Search requires much more computation than Easy Logic. Consequently, to solve boards, the algorithm applies Easy Logic as many times as it can. Either it solves the game or it gets stuck. If Easy Logic gets stuck, I repeatedly run Contradiction Search and Easy Logic again until the algorithm comes out of the rut. If Contradiction Search fails to find anything, chances are the board is unsolvable.

A live demo for this algorithm along with an implementation of Minesweeper on which to use it can be found at www.arongil.com/minesweeper. For those who wish to play it, left click to uncover a square and right click to flag or unflag a mine. The buttons to apply any of the three rules discussed are in the bottom left.