What's the algorithm behind minesweeper generation

Question

Well I have been through many sites teaching on how to solve it, but was wondering how to create it. I am not interested much in the coding aspects of it, but wanted to know more on the algorithms behind it. For example, when the grid is generated with 10 mines or so, I would use any random function to distribute itself across the grid, but then again how do I set the numbers associated to it and decide which box to be opened? I couldn't frame any generic algorithm on how would I go about doing that.

Answer 1

Perhaps something in the lines of :

grid = [n,m]   // initialize all cells to 0
for k = 1 to number_of_mines
   get random mine_x and mine_y where grid(mine_x, mine_y) is not a mine
   for x = -1 to 1
      for y = -1 to 1
         if x = 0 and y = 0 then
            grid[mine_x, mine_y] = -number_of_mines  // negative value = mine
         else 
            increment grid[mine_x + x, mine_y + y] by 1

That's pretty much it...

** EDIT **

Because this algorithm could lead into creating a board with some mines grouped too much together, or worse very dispersed (thus boring to solve), you can then add extra validation when generating mine_x and mine_y number. For example, to ensure that at least 3 neighboring cells are not mines, or even perhaps favor limiting the number of mines that are too far from each other, etc.

** UPDATE **

I've taken the liberty of playing a little with JS bin here came up with a functional Minesweeper game demo. This is simply to demonstrate the algorithm described in this answer. I did not optimize the randomness of the generated mine position, therefore some games could be impossible or too easy. Also, there are no validation as to how many mines there are in the grid, so you can actually create a 2 by 2 grid with 1000 mines.... but that will only lead to an infinite loop :) Enjoy!