4 ms·

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

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".

alain_gilbert 1y ago
I made winsweeper, which will move the mine if there is no safe tile left for you to discover. https://github.com/alaingilbert/winsweeper https://github.com/alaingilbert/winsweeper
mcmoor 1y ago
Yeah I've debugged another game that attempted this and this system resulted in the game lagging as hard sometimes.
OscarCunningham 1y ago
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 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.
- maggit 1y ago
  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/ https://pwmarcz.pl/kaboom/ And the write-up: https://pwmarcz.pl/blog/kaboom/ https://pwmarcz.pl/blog/kaboom/ ) This is similar in spirit to my take on the game: https://magnushoff.com/articles/minesweeper/ https://magnushoff.com/articles/minesweeper/ Unfortunately, not being familiar with SAT solvers, my implementation can grind to a halt in some configurations :)
  - Gravityloss 1y ago
    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.

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".

alain_gilbert 1y ago

I made winsweeper, which will move the mine if there is no safe tile left for you to discover. https://github.com/alaingilbert/winsweeper https://github.com/alaingilbert/winsweeper

mcmoor 1y ago

Yeah I've debugged another game that attempted this and this system resulted in the game lagging as hard sometimes.

OscarCunningham 1y ago

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 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.

maggit 1y ago
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/ https://pwmarcz.pl/kaboom/ And the write-up: https://pwmarcz.pl/blog/kaboom/ https://pwmarcz.pl/blog/kaboom/ ) This is similar in spirit to my take on the game: https://magnushoff.com/articles/minesweeper/ https://magnushoff.com/articles/minesweeper/ Unfortunately, not being familiar with SAT solvers, my implementation can grind to a halt in some configurations :)
- Gravityloss 1y ago
  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.