←back to thread

Minesweeper thermodynamics

(oscarcunningham.com)
206 points robinhouston | 3 comments | 01 Sep 25 16:14 UTC | HN request time: 0s | source
Show context
gregfjohnson ◴[04 Sep 25 03:36 UTC] No.45123258[source]▶
I hacked up a version of minesweeper that was “forgiving:” if there was no selection that was provably safe, it gave you a safe move. If you picked any square that was not provably a bomb, it would not be a bomb. Typically, as long as you don’t select a number of bombs equal to the number of squares , your first move is safe. I just extended that for the whole game. If you select N-1 bombs, you always win on the first move..
replies(8): >>45123401 #>>45124178 #>>45124382 #>>45124386 #>>45124449 #>>45124938 #>>45126205 #>>45126922 #
abetusk ◴[04 Sep 25 03:59 UTC] No.45123401[source]▶
Ha! This is NP-Complete, no? In practice, it probably doesn't matter but my bet is that there are some configurations that will take exponential time to see if the player should be "forgiven".
replies(3): >>45123447 #>>45123487 #>>45123970 #
1. OscarCunningham ◴[04 Sep 25 05:49 UTC] No.45123970[source]▶
Yeah, it's NP-complete to decide whether a cell in Minesweeper must be a mine: https://logic.pku.edu.cn/ann_attachments/np.pdf.

In practice I suspect a SAT solver would make quick work of the positions that actually appear in games.

replies(1): >>45124368 #
2. maggit ◴[04 Sep 25 06:58 UTC] No.45124368[source]▶
There was a Minesweeper on here that used a SAT solver, but I cannot find it at the moment. As I recall, it never had any issue with resolving the board quickly. I think it dynamically resolved where the mines would be as you played the game, and if you clicked a square that could be a mine, it would be a mine, except, I believe, when there were no open squares that were safe.

(Edit: Here it is! https://pwmarcz.pl/kaboom/ And the write-up: https://pwmarcz.pl/blog/kaboom/ )

This is similar in spirit to my take on the game: https://magnushoff.com/articles/minesweeper/

Unfortunately, not being familiar with SAT solvers, my implementation can grind to a halt in some configurations :)

replies(1): >>45126102 #
3. Gravityloss ◴[04 Sep 25 11:34 UTC] No.45126102[source]▶
I wonder if one learned to play faster with this kind of minesweeper.

I find in a lot of repetitive learning, you have a very noisy signal, you don't know if you succeeded because of luck or you did something right.

This variant takes out the luck part.