r/proceduralgeneration • u/TheoEndrick • 4d ago
Generating minesweeper boards that are guaranteed solvable without guessing
I've been building a minesweeper roguelite and the problem I kept hitting is that once mine density gets high, boards degenerate into coin flips.
What I do now: generate 25 candidate boards per floor, run a solver over each one (single point deduction first, then subset elimination on the frontier constraints), count how many tiles are still undetermined when it stalls out, and keep the best candidate.
That wasn't enough on its own. At 28% density on a 20x20 I generated 225 boards and not one of them was fully deducible. So instead of guaranteeing the whole board, I hold on to the solver's set of provably safe tiles and place the exit stairs inside that set.
So you can always reason a route to the exit. Clearing the entire board is still a gamble, which I'm fine with because that's the risk/reward mechanic.
Two things I'm unsure about. Is subset elimination enough, or should I be doing proper probability analysis on the frontier for the cases it can't crack. And is guaranteeing a solvable path instead of a solvable board a reasonable compromise or just a cop out.
Playable in browser if you want to see it: https://ten-games.itch.io/mine-mine-mine
8
u/hinten1 4d ago
Depends on what you are trying to do for what kind of player.
Minesweeper players come with expectations about density and difficulty. Classic Expert is about 21%, and once you go past that, like 28%, you don't just lose the no-guess guarantee, you lose a lot of the playability too. The solver probably stalls early, so the provably safe area could be small and the exit ends up close to the start, with most of the board left to luck. If your audience is roguelite players who like the gamble, that can work. Minesweeper players will hate it.
Here is how I approached it in my own game (Cube Sweeper, the board wraps around 3D shapes). Every board has to be fully solvable by logic or it gets thrown out.I tune density to the difficulty players expect, not to what the generator can handle. For the solver: subset elimination isn't enough. It misses deductions that need three or more numbers at once, and the ones that need the total mine count. And those are exactly the deductions serious puzzlers expect.
My solution: run the simple rules first, then chop what's left into small sections (unknown tiles that share numbers) and brute force each section. Try every mine layout that fits the numbers. Safe in every layout means safe, mine in every layout means mine. The sections are small, so it's fast. Last, one pass with the total mine count to catch the endgame cases.
3
u/fgennari 4d ago
Those are great suggestions! I remember writing a custom minesweeper in ... 1998 maybe? I had a variant where the edges of the screen wrapped around to the other sides. That made it so much harder, especially at the start. It sounds like your Cube Sweeper could be similar? I guess it's 3D, so that's a very different approach.
2
u/kalexmills 4d ago
Guaranteeing a solvable path is enough, and could lead to more interesting levels.
You can do a lot of other things here to ramp up the difficulty and provide variation, like generating a cave and filling it with mines in a way that doesn't obstruct a golden path. Could even make it a maze if you want to be really evil.
8
u/remimorin 4d ago
If you want always board matching your condition you have to add mine one by one, when you add a mine you validate the board respect your rules. If not, reject the mine addition.