title: Generate a minesweeper board which doesn't need guessing
body: <p>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.</p>
  
  <p><a href="http://en.wikipedia.org/wiki/Minesweeper_%28video_game%29" rel="noreferrer">Wikipedia</a> mentioned:</p>
  
  <blockquote>
    <p>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. </p>
  </blockquote>
  
  <p>However, I cannot figure out the algorithm. </p>
  
  <p>Besides, in another StackOverflow question: <a href="https://stackoverflow.com/questions/1738128/minesweeper-algorithm">Minesweeper solving algorithm</a></p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>I doubt if this really works. It's well-known <a href="http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm" rel="noreferrer">solving minesweeper</a> is NP-complete. </p>
  
  <p>In summary, my questions are:</p>
  
  <ul>
  <li>How to generate a Minesweeper board which doesn't need any guessing?</li>
  <li>If we can, what's the concrete algorithm?</li>
  <li>Could we solve this problem in polynomial time deterministically? Is this problem NP-complete? How to prove it?</li>
  </ul>