News for hackers. Stuff that matters.
Re:1M Cell Minesweeper by tromp on Wednesday October 14, 2020 @05:53AM (#24774886)
I wonder if it's possible to generate a minesweeper on the fly, where you are guaranteed to never have to guess.

And if so, if you can make the generation efficient (polynomial time).

I should have asked that in the Pure Skill Minesweeper thread [1], but only thought of it more recently.

[1] https://news.ycombinator.com/item?id=24181772

Re:1M Cell Minesweeper by lemagedurage on Wednesday October 14, 2020 @06:42AM (#24775141)
Yes, guaranteed solvable minesweeper variants exist. https://www.chiark.greenend.org.uk/%7Esgtatham/puzzles/js/mi...

"The first square you open is guaranteed to be safe, and (by default) you are guaranteed to be able to solve the whole grid by deduction rather than guesswork. (Deductions may require you to think about the total number of mines.)"

I don't know about the runtime though.

Re:1M Cell Minesweeper by tromp on Wednesday October 14, 2020 @07:00AM (#24775226)
It would be really cool if the algorithm is able to generate all possible instances that can be solved purely by deduction.

I do wish that it allowed me to pick a higher fraction of mines. I found the pure skill minesweeper a lot more challenging (and therefore satisfying) when I increased the fraction from 20% (30 mines on 10x15) to 33.3% (50 mines).

Re:1M Cell Minesweeper by lemagedurage on Wednesday October 14, 2020 @07:06AM (#24775264)
Under "Type..." -> "Custom" you can choose board size and amount of mines. What a timesink!
Re:1M Cell Minesweeper by wasyl on Wednesday October 14, 2020 @06:20AM (#24775042)
You might find this interesting, not exactly generating a minesweeper without guesses but close https://pwmarcz.pl/blog/kaboom/
Re:1M Cell Minesweeper by Narishma on Wednesday October 14, 2020 @06:17AM (#24775027)
I'm pretty sure the minesweeper from the Portable Puzzle Collection generates guaranteed winnable boards without having to guess.
Re:1M Cell Minesweeper by codetrotter on Wednesday October 14, 2020 @06:32AM (#24775096)
Impossible, because the first move in any game of minesweeper will always be a guess :^)
Re:1M Cell Minesweeper by offlineguy on Wednesday October 14, 2020 @07:01AM (#24775233)
Original minesweeper ensures that the first move is never a mine.