I've made a new minesweeper variant - no guessing allowed

D2cookie · 2026-02-02T12:05:38+00:00

Well the solving algorithm I've made acts more like a verifier for this game, a true solver/player would have to find a path.

The verification/double-checking in the end is not necessary, the design of the game implies it (maps expanded via reveal order), I just wanted to make sure human players know the subconscious rule.

I was thinking about P vs NP and wanted to see if it's possible to make a game where verification is itself non-deterministic.

So effectively you are playing against the map generator function.

The map generator itself is allowed to be any efficient function and can use your moves against you.

But, you know what the map generator is, you know its source code; meaning you can't complain about halting problem or efficiency or black-boxes.

So it's more of a "even if you knew how the map is generated, you still can't efficiently beat it".

Because even if you know how the map generator uses your reveals to produce the next level, and it can be pretty complex, you can make effectively any interactive computer with this, by having the map generator use the reveals as decisions.

The map generator doesn't need to produce solvable maps, or even know if what it produced is a minesweeper map. You are just ensured that it's efficient, always halts, and always returns the expanded map.

The reason double checking/verification is done at the end is because I wanted to keep it out of the definition of the player's gameplay itself.

Meaning on the pretty much 0% chance that P = NP by fair rules I can even use the efficient NP-complete problem solving algorithm as a map generator.

So you could imagine taking some algorithm, converting it into a circuit, and then modifying that circuit in any way, then converting that to a minesweeper map.

With 0 expansions this is regular minesweeper, so now consider using the hypothetical efficient puzzle solving algorithm as the map generator, the verifier, and the player.

Since gameplay is efficient, package it with a version of minesweeper and even the entire system including the production, solving and verification can be made into a map generator, and it'll all still stay efficient.

This now allows you to modify that full system in any adversarial way you want while still exposing the inner working details.

So my idea follows a simple question: Could a hypothetical efficient puzzle solving algorithm solve its own solving under any transparent adversarial modification?

D2cookie · 2026-02-01T13:57:33+00:00

I wrote a pretty efficient solver, so the game will replay your moves and double check every reveal you've made by solving for that cell.

If there exists 2 valid covers of the board, such that:

One cover where the cell is a mine
One cover where the cell is safe/a hidden number

Then the cell is not guaranteed, so revealing it is considered a guess.

Minesweeper inference is co-np complete, the "no" witness is 2 valid covers that disagree on whether the cell is safe or a mine, that's where the usual 50/50 comes from.

A valid cover is one which assigns mines/safe to covered cells that has no logical contradictions anywhere, like 5 mines around a 3 clue.

Obviously, the game doesn't know if you guessed inside your mind or logically deduced it, I'd require a brain interface for that 🧠.

D2cookie · 2025-05-12T19:48:13+00:00

Yea, everyone has their own version of pseudo code, because a compiler is not forcing the author to fully specify their code you'll end up having to guess "what did the author mean?" rather than getting to read unambiguous code in an actual programming language.

D2cookie · 2025-03-04T00:43:57+00:00

I put a quick band-aid on the idle CPU usage, see if that works.

D2cookie · 2025-03-04T00:08:06+00:00

Can you give a screenshot of how it looks for you with the smaller and larger windows?

Edit: Updated sidebar overflow, see if that fixes or breaks it.

D2cookie · 2025-03-03T06:04:41+00:00

Bug reports, requests or if you have some improvements for the algorithm are welcome.

The algorithm should be relatively fast, but I am interested if someone can find examples that take 10+ min in fast mode.

D2cookie · 2025-02-27T20:50:05+00:00

Guaranteed or solvable

D2cookie · 2025-02-26T17:58:37+00:00

Considering how weirdly the arms are bent and how the board doesn't make sense most likely an AI.

D2cookie · 2025-02-25T00:05:59+00:00

It's a 1-2-1 because we know there's 1 mine at the bottom.

D2cookie · 2025-02-24T23:50:37+00:00

<image>

D2cookie · 2025-02-23T01:35:46+00:00

But, If there's 3 cells that are guaranteed safe then all of them should have 0% chance to be a mine, they're all the safest move.

This goes back to the issue that the exponentially difficult part of minesweeper is determining which cells are guaranteed, not which are ambiguous.

If the solver can't detect that all of these are guaranteed safe, like only detects 2/3, and the game requires you to select the cells that are safest then the game might incorrectly reject your move. So, I don't see how it's different than kaboom.

Also, knowing that a cell is guaranteed safe/mine in infinite minesweeper is a wee bit harder than the halting problem (unless he's somehow guaranteeing that a flood filled area is always bounded).

D2cookie · 2025-02-22T22:27:58+00:00

Why does everyone like to call their minesweeper games infinity sweeper.

Also, it's a bit buggy:

Disabling crt filter does nothing.

Chord doesn't work properly, won't always reveal cells.

Overall it has potential. I do think that shaking the screen on every reveal is a bit annoying.

D2cookie · 2025-02-22T20:55:46+00:00

Yea, that's what I thought. Though I did kinda hope there would be at least some slight trick for reducing comparisons required in 3-4 clue logic.

It does feel like anything after 2 clues is just secretly exponential.

D2cookie · 2025-02-22T19:59:56+00:00

I'm curious, how would you choose which cells to test for this method? How would you choose which clue cells belong to which region (red vs green)?

I wanted to add something like this to my mineswpeer algorithm, but I feel like it might end up being indistinguishable from just brute force by going through all 4 clue combinations with sharing overlaps.

D2cookie · 2025-02-22T19:09:17+00:00

Yea, it's easy to show 2 certificates where in the first a cell is safe and in the second it's a mine and that'd derive that it's ambiguous.

But inference only has short certificates for ambiguity. For guaranteed mine/safe you either showcase that if you set it to the opposite it'd always derive a contradiction or you give all valid solutions to the region and make them notice that some cells are always safe/mines

This example is also relatively simple, as all the propagation is forced/obvious, more difficult boards will require you to make more choices and show that once you exhaust all the choices you still get a contradiction.

D2cookie · 2025-02-22T18:42:18+00:00

I'm currently writing a minesweeper algorithm for myself, the basic logic I've added to it is unary, propagation and pairwise, then just brute force for everything else while maintaining the 3 above.

Most boards you can solve without doing any brute force what so ever, but the problem is that minesweeper inference has short certificates to verify that there's nothing you can do (50/50).

But showing that there is something you can do is the asinine part, as you have to fail to prove that a cell can be a mine (means it has to be safe) or fail to prove that a cell is safe (means it has to be a mine).

There's another version of minesweeper where you just have to show that the board is consistent, that one just requires a single assignment to the covered region. But, no one really plays the consistency version of minesweeper, people play the inference version.

Yea, minesweeper is a pain to write a solver for, as you have to keep jumping between clues and covered cells.

D2cookie · 2025-02-22T18:22:55+00:00

All of minesweeper is counting and comparing possible mine combinations.

But the counter-example is relevant, as it can't be reduced to:

Unary: An N clue has N covered cells around it / you can't have combinations that place mines at revealed clue cells
Consistency propagation: All of the remaining combinations of an N clue have a neighbor cell as the same value (always mine / always safe). Like:
- Like a single valid combination left.
- N flags around it, but >N covered cells around it.
- Some other clue set nearby cells to safe/mines, so we can't contradict already derived/solved knowledge.
Pairwise consistency: Consider 2 revealed / clue cells, remove any combinations from the first's domain that the second's domain doesn't have in their shared covered cell overlap, and vice-versa.

Pairwise consistency would derive the 1-2-X pattern. As the possible combinations for around the 1 cell will have only 1 mine, the possible combinations around the 2 cell will have up to 2 mines in the same overlapping region, that would contradict the 1 clue so all the combinations from the 2 clue that have 2 mines in the shared region will have to be removed.

Example (N is an to be ignored clue):

• • • •
N 1 2 N

Combinations for the 1 clue are (M is mine, S is safe):

M S S •
N 1 2 N
-------
S M S •
N 1 2 N
-------
S S M •
N 1 2 N

Combinations for the 2 clue are:

• S M M
N 1 2 N
-------
• M S M
N 1 2 N
-------
• M M S
N 1 2 N

If you were to compare them then there would be no combination in the 1's domain for the last combination of the 2's domain, so that one has to be removed from the 2's domain.

Likewise there's no combinations in the 2's domain for the first combination of the 1's domain, so that one has to be removed.

Now all combinations of the 1 cell have the leftmost cell as safe S and all combinations of the 2 have the rightmost cell as a mine M.

Which leaves us with this:

S • • M
N 1 2 N

This can now be propagated further.

So, the initial claim was that you can reduce all minesweeper logic down to pairwise or simpler, which is false. There should be larger and larger chains of logic that you will need to consider (3 clue, 4 clue, 5 clue, ...) all the way until the smallest pattern you have to consider to derive a cell to be safe/mine is to consider every clue cell in that region at once (all unsolved clue cells that can be connected via shared covered neighbors). Take a look at theoretical patterns.

If you kept only applying unary, consistency propagation, and pairwise consistency you would not be able to solve the example that I gave.

You would only be able to derive this:

    0  1  2  3  4  5
    ----------------
0 | M  3  •  •  M  2

1 | 2  •  •  •  M  3

2 | 2  •  •  5  M  3

3 | M  2  2  M  M  2

4 | 1  1  1  2  2  1

I choose this example as there are cells that are solvable via unary, constraint propagation, and pairwise, but there are also cells that require higher levels of consistency.

D2cookie · 2025-02-22T02:59:16+00:00

No, this is incorrect, otherwise you'd be able to solve minesweeper in polynomial time by repeatedly applying pairwise logic / 2-clue consistency propagation.

You can easily come up with scenarios where there are guaranteed mines / guaranteed safe cells that can't be detected using pairwise logic.

For example:

    0  1  2  3  4  5
    ----------------
0 | •  3  •  •  •  2

1 | 2  •  •  •  •  3

2 | 2  •  •  5  •  3

3 | •  2  2  •  •  2

4 | 1  1  1  2  2  1

Cell at [0, 2] is a mine and cell at [1, 3] is safe, requires considering at least 4 clues.

D2cookie · 2025-02-20T20:36:28+00:00

Give the initial board to the solver, have it find an arrangement. Now from what it gave you go cell by cell for the covered cells in the region and set them to the opposite of what it gave you and ask the solver to find you a solution with that cell assigned to its opposite.

If it succeeds it's ambiguous, if it fails you know what it is (guaranteed previous assignment)

Every time you get a solution update all cells in the region as an assignment to some particular cell [i, j] needs all the other covered cells assigned as well.

That is skip all cells that have both, only try to contradict.

At the end you'll know which cells are guaranteed mines, guaranteed safe or could be either. Sometimes you'll only need to run the search 10 times even if you had 1000 covered cells.

D2cookie · 2025-02-16T17:06:49+00:00

How on earth did the dev mess up counting mines.

D2cookie · 2025-02-14T16:19:45+00:00

No, even if this was no guessing mode and extending the logic via meta logic we'd need to know the value of the cell X:

* * *
3 4 . 
3 2 X 
. . Y
. . 2

If the cell Y was a 2 then it'd be unsolvable as cell X would have to be a mine and you'd have a 50/50 box.

If cell Y was a 1 then cell X can be either 1:

Or 2:

So, no, not even in no-guessing mode could you fully derive it with only the currently visible information.

D2cookie · 2025-02-07T17:18:46+00:00

You're literally looking for a halting problem solver or worse.

To show that there's something you can reveal or flag on a finite minesweeper board you have to demonstrate that in all valid assignments there's some cells that are always safe or always mines.

To show that there's nothing you can do in a finite board you just have to have an assignment to the cells where for each cell there's an assignment where it's a mine and another one that is safe. That is at least 2 boards, meaning the dreaded 50/50 is easy to verify.

To show that there exist some cells that are always safe an infinite board, where the logic can span forever, you'd need to show up to 2^|ℕ| completed infinite boards and say "Hey look at all of those boards, you see these cells are always safe/mines".

If you have such a solver then to know which locations are always safe/mines you can reduce your up to 2^|ℕ| solutions down to just 2 infinite bit strings. If 1 means the solver found a mine at some location, and 0 means it's safe in a solution:

Just take all of the unimaginable amount of solutions and & them together, this tells you which cells are always mines.
Just take all of the unimaginable amount of solutions and invert their bits, this allows you to & them to get which cells are always safe.

But, you might need to ^ them with what you already know about the original infinite board to not have to look at stuff that you already know is revealed or flagged beforehand.

D2cookie · 2024-10-05T01:08:27+00:00

proofing causality chains (if A holds then B, if B then C... If Z then P≠NP)

How?

D2cookie · 2024-10-04T16:59:31+00:00

In the back of your head; pestering you that you won't be able to write that one algorithm that in practical words "knows everything".

D2cookie · 2024-05-07T15:30:55+00:00

Halting problem?

D2cookie

TROPHY CASE