Generate a minesweeper board which doesn't need guessing

miaout17 picture miaout17 · Nov 29, 2011 · Viewed 18.4k times · Source

I am designing a Minesweeper-like game (with modified rules), and I want to prevent player from guessing. My goal is: The generated board is with few revealed squares, and player can solve the entire puzzle without any guessing.

Wikipedia mentioned:

Some implementations of Minesweeper will set up the board by never placing a mine on the first square revealed, or by arranging the board so that the solution does not require guessing.

However, I cannot figure out the algorithm.

Besides, in another StackOverflow question: Minesweeper solving algorithm

Improvement: Run the solver alongside the generator, making sure that the puzzle has a unique solution. This takes some cleverness, and isn't done in most variants.

I doubt if this really works. It's well-known solving minesweeper is NP-complete.

In summary, my questions are:

  • How to generate a Minesweeper board which doesn't need any guessing?
  • If we can, what's the concrete algorithm?
  • Could we solve this problem in polynomial time deterministically? Is this problem NP-complete? How to prove it?

Answer

gone picture gone · Nov 29, 2011

The implementation of Minesweeper in Simon Tatham's Portable Puzzle Collection is guessing-free. (It's also MIT licensed, so you're free to copy his implementation if you so desire.)