Minesweep.rs - an oxidized no guess Minesweeper

an implementation of Minesweeper that guarantees that boards are solvable without having to guess

icon

 GitHub    Demo    Simon Tatham's Blog

About

The original version of Minesweeper in Windows XP does not guarantee that every board is solvable, meaning you can end up in a situation where you have to make a random guess to proceed. This implementation aims to generate boards that can be solved using logical deductions alone, inspired by Simon Tatham’s implementation of the same idea. While I referred to his excellent blog for guidance, the implementation is my own.

We achieve this by running a solver that applies the same deductions a human player would. Whenever the solver gets stuck, we run a “perturber” that moves one or more mines around, allowing the solver to make at least one new deduction. We repeat this process until the board is guaranteed to be solvable. I’ve gone into more detail about the approach in the accompanying post.

Solving a Minesweeper board is NP-complete (Kaye, 2000). However, for the standard board sizes (and quite a bit more), we can run the perturb-solve loop fast enough (<1s) that it’s basically unnoticeable. We can of course only do this after the first click, since the start position decides the state of the board.

Some quick benchmarks on time taken to build a solvable board, sampled across a 1000 random boards.

DifficultyMine DensityMedianP99
Beginner (10×10, 10)10%0.05ms0.16ms
Intermediate (16×16, 40)15.6%0.21ms0.77ms
Expert (30×16, 99)20.6%1.24ms4.08ms
Master (30×20, 200)33.3%6.04ms24.7ms
benchmark only (30×20, 400)66.6%41.5ms175ms

Personal Notes

This was my first time actually using Rust to build something, and I can definitely see the appeal. It feels like a nice modern language with all the syntactic sugar and is fast too. On the project, this has been on my to-do list for the longest time, and I’m glad I finally have my very own solvable Minesweeper!

Another benefit of building it in Rust is that it compiled to WASM with little to no effort at my end. And thanks to that, I can offer to you a live working demo right here on this page.

Demo

The WebAssembly build of minesweep.rs is available at /demos/minesweeper, and in the iframe below.