No-guess Minesweeper: making every board solvable by reasoning alone

There are two ways to lose at Minesweeper, and they are not the same kind of thing:

• You missed something. That is on me; start another board.
• You had to guess. The position reached a point where every deductive step was exhausted and the rest was a coin flip.

The second one is why people stop playing. “No-guess” is not a difficulty setting — it is the precondition for treating the game as a game of skill.

The definition has to be exact

Be precise here, or the implementation drifts:

A board is no-guess if and only if there exists a path from the first click to a win where every step uses only deductive reasoning.

Note “there exists a path”, not “no branch ever requires a guess”. The latter is far stronger and throws away many perfectly good boards.

There is a subtler constraint too: the solver may only use information the player can see. If it peeks at the answer to decide “this cell is a mine”, the boards it accepts are solvable from god’s view and unsolvable from the player’s. They pass the check and are worthless.

The obvious approach: generate, solve, retry

loop:
  place mines at random
  open a safe starting cell
  if the solver can finish the board: return it
  else: retry

That is rejection sampling. It is correct, simple, and on small boards entirely adequate — at low mine density the first attempt usually passes.

What looks bad is the tail. Bigger boards and higher densities drop the hit rate fast, and you occasionally retry dozens or hundreds of times. If placing mines is O(n), the worst case is O(n × retries), and retries have no upper bound.

The cheaper approach: repair instead of restart

Rather than regenerating the whole board, fix the cell that forces a guess:

1. Generate a board, run the solver
2. When it stalls, collect the unknown cells that no deduction can resolve
3. Pick one, move its mine or open it (which also changes the information around it)
4. Solve again; only restart from scratch if a few rounds of this fail

Changing one cell is usually far cheaper than regenerating a whole board. In practice most stalls need one or two mines moved.

How far the solver has to go

This is the one genuinely judgement-dependent part. Deduction has three tiers:

Tier	Technique	Coverage
1	Direct counting: remaining mines around a cell equal its unknown neighbours → all mines; equal zero → all safe	Most positions
2	Subset and difference: A’s unknown set is a subset of B’s → the difference is all mines or all safe	A large batch
3	Local enumeration: enumerate unknown frontier cells up to some size and find cells identical across every solution	Most of the rest

Tier 2 is the generalisation of the classic “1-2-1” and “1-2-2-1” patterns. Those patterns are not rules; they are special cases of this tier.

Tier 3 is the dividing line. It is still mathematically deterministic (if a cell is a mine in every solution, it is a mine), but the compute goes up, and “enumeration size” becomes a knob: too loose and generation slows down, too tight and boards get mislabelled as requiring a guess.

I settle on tier 2 plus small-scale enumeration. Tiers 1 and 2 cover most positions, enumeration eats most of what is left, and the extra pass rate from going further is tiny for the compute it costs.

The first click

An easily overlooked but critical detail: the first click must be safe.

The standard trick is to place mines after the first click, or to clear the first cell and its eight neighbours. That solves two things at once:

• The player cannot die on move one — purely a feel problem
• The opening immediately contains numbers, which means it immediately contains information. Otherwise the first move is pure randomness and the no-guess premise never held to begin with

What no-guess actually changes

It does not make the game easier. Difficulty is still board size and mine count.

What it changes is where the randomness sits: from “luck decides the outcome” to “the shape of the position”. You still lose, but you lose to “I did not see that” rather than “nobody could have seen that”.

That is the point for me. Whether a game is worth playing repeatedly comes down to whether a loss can be attributed to your own judgement.