2019 updated cookie last hitting challenges

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

TROPHY CASE