Here’s what I never liked about the game Minesweeper: It’s a puzzle game, but there’s a huge element of luck in it. Solving small boards is relatively easy, but the problem is that you’ll inevitably and frequently get into states where it’s impossible to deduce where the mines are, and you have to just take a //step// into a risky unknown area, a click of faith, as it were. You can probably use probability to figure out where there’s less likely to be a mine, and I bet that’s an aspect in solving more puzzles, but I’m sure (although I never spent any inordinate amounts of time playing the game) that when you get “stuck” and need to take that blind leap of faith and you hit a mine after spending lots of time trying to open up and solve a large board, that that’s rather frustrating. That’s pretty much why I never bothered to play the game (and so I found other outlets for boredom). So wouldn’t it be nice if you could play Minesweeper without running into those ambiguous scenarios?

I wrote a [http://mh-z.com/misc/minesweeper2.html minesweeper solver] a while back, which generates a random board and then simulates all the steps it’d take a person to solve the board. The solver algorithm takes advantage of the configuration of mines it’s already detected and explores all possibilities, and if it’s possible to deduce that a particular spot is definitely free of mines or definitely a mine, even if that deduction would take many layers of reasoning, the program does get to that point. That’s about all it does for the moment; writing the program was just a fun exercise (in response to an interview question) that took about a day.

So the next step, which I thought about long ago but never really had the inclination to implement before having a conversation last weekend about it, would be to build a version of Minesweeper you can actually play which generates boards that are solvable. Here’s how I’d do it:

The aforementioned solver generates a random board, steps on an initial square, then tries to solve the rest of the board. When it gets into an ambiguous scenario which would require guessing, it just gives up. Given that I can generate a random board and see if it’s fully solvable or ends in ambiguity, I can just keep on trying, with different random boards, until I hit upon one which the solver can solve. Then we know you’ll be able to solve it, too, knowing you can’t get stuck — you may run into tricky puzzles based on configurations of mines, but you’ll be able to puzzle it out, like Sudoku.

Maybe that’s why games like Sudoku are popular these days — there’s guaranteed to be a solution, always a definite next step, even though it can be very tricky for us humans to find. A tough Sudoku puzzle where you weren’t sure whether a solution existed would be pretty frustrating.

One factor I need to consider is that the solvability of the board depends on where you initially step, and your first step could itself be directly on a mine. So I could either try to simulate the experience of “real” minesweeper by generating a board around you after you step (guaranteeing that the first step is a safe spot) and guaranteeing solvability from that point, or I could automatically open up a random square as the first step — this is where you’re standing now, your safe ground from which to explore and open up the rest of the board. In keeping with the theme of not having to guess, I’m leaning towards the second option; this would also make it simpler to solve a saved puzzle.

Also, I originally implemented the solver itself in JavaScript, so generating dynamic random puzzles can be done by your browser, without putting any load on a server. I need to “thread” the JS, though, since generating (i.e., repeatedly attempting to solve different random mine configurations in) a puzzle is slow, depending on its size and the number of mines. (I could use the generation time as a metric for how difficult a puzzle would be for a human player to solve.) Updates as I go.