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.

Bailee

Each mine should just increment every neighbor cell that isn't a mine. – Hypercriticism

that solves for all the ones .. but what about 3 and 4 . how will i incorporate those digits . if the way i parse only works for single ones – Bailee

possible duplicate of Minesweeper algorithm – Chalcocite

@boltcock i did go thru that thread and its more focused towards on solver than maker – Bailee

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!

Kirchhoff

This would increment on top of mines already placed, so you'd want mines to be represented by a number that was negative enough that it wouldn't get incremented up to zero, like mine = -20. Then, every negative number is a mine. – Nasal

i dont have problem placing the mines , but how to i get generate those numbers which are clues to identify the mines ? i aint have ne idea on that – Bailee

the algorithm will place the numbers giving the identity of the mines – Kirchhoff

Great answer and great demo. I would add a few suggestions for demo. 1) To avoid "First click game-over": At start of game, add 1 extra mine to grid (if user requests 10 mines, make 11 mines). Then on first click (only): if it is a mine just (quietly) remove that mine. and adjust the counts in nearby cells. if it's NOT a mine just select a random mine and (quietly) remove that mine and adjust the counts in its nearby cells. Then, expose the board where the user clicked and proceed with the game as normal. 2) Add some way to "mark" mines (left-click or shift-click...). ---> – Paleontology

---> 3) Remove "alert" box at end of game. It is an annoyance to have to clear it each time to start new game. Instead, add message on window (or on non-modal overlay), that is cleared when starting a new game. 4) One more thing: You have a "404 error" message on your demo page (I understand the humor). But the text "404 Error - Page Not Found" in the page "Title" is confusing. – Paleontology

Thanks for the suggestions. I have thought about removing the alert, yes. I'll make that change soon! About the first point and the 1 extra mine, it would actually be a better idea to just generate the mine field once the user have selected the first square (i.e. marking that cell as unselectable), it would actually make things less redundant, so the first selection will always guarantee an empty cell. Finally, the "404" title is because I don't want to have a site at the root of my domain, so I generated these "errors" and this demo is one of the few so far (with more coming in the future). – Kirchhoff

Minesweeper game demo link is a 404 – Entrammel

@Entrammel just refresh a few times :) I need to fix this. – Kirchhoff

Answer 2

You just seed the mines and after that, you traverse every cell and count the neighbouring mines.

Or you set every counter to 0 and with each seeded mine, you increment all neighbouring cells counters.

Planetarium

Answer 3

A Strong Algorithm

Here is an implementation of a MineSweeper algorithm. This algorithm takes into account some conditions while generating the map, and also performs a solver algorithm to make sure that the generated map has at least one possible solution.

The implementation of this example is too long to be posted as a code, so it will be explained with some examples to allow others to replicate it in the desired programing language. In this example, python was used.

The main loop

First of all, we need to create a main loop where an arbitrary number of map generation attempts will be performed, including the solver algorithm validation at the end of each one. This loop will have a max_fails limit to make sure it does not remain as an infinite loop. Note that we are going to use more inherit loops later, and all of them must have their own limits set.

A fail is counted when a mine placement attempt failed or the generated map has no possible solution. With this method, we can try generating maps dynamically, regardless of how large map generation attempts were or how many were done. It always will stop attempting map generations if max_fails is reached. This means that if the grid is small, a lot of attempts could be done before reaching the limit, on the other hand, if the grid is large, then a small number of attempts could be done. We could define the max_fails limit also dynamically according to the area of the grid, allowing to larger grids more time execution if needed.

Also here, we should define the number of mines, this could be done dynamically using the area of the grid or using a difficulty variable... Or both at once!

mines = int((height * width)//(15 - difficulty))

max_fails = 500 #<- This could be defined dynamically using exponential functions.

possible_solution_found = False
fails = 0
while not possible_solution_found and fails < max_fails:

1. Grid Generation

We need to create a matrix representation of the grid, generally, within given dimensional values. This could be done by creating a list of lists representation of a matrix just by iterating over these dimensional values. First on the Y-axis, creating the row list, and then on the X-axis, adding a 0 value to the row list.

It is a good idea to create a copy of the matrix to work as a register. Instead of adding a 0 value to each cell, we need to add the position of each cell. It could be, for example, a tuple of the coordinates. (x, y)

The register is useful to later optimize the random choosing process of mine placement, this will prevent failing twice on the same cell.

matrix = list()
matrix_register = list()
for row_index in range(height):
    row = list()
    row_register = list()
    for cell_index in range(width):
        row.append(0)
        row_register.append((cell_index, row_index))
    matrix.append(row)
    matrix_register.append(row_register)

2. Mines placement

1. Loop

• Here we should start the loop where mine placement attempts will be done. This loop should end if no more mines have to be placed or if the max_fails limit is reached.

total_mines = mines
while total_mines > 0 and fails < max_fails:
    # subtract 1 to total_mines each time a mine is placed correctly.

2. Randomly choosing

• Now, we need to randomly choose one cell to be placed as mine. If you did implement it, you should choose the cell from the register matrix and, whether it was successfully set as mine or not, remove it. This makes it impossible to choose again a cell that is already a mine or will never be a mine. Otherwise, if you did not implement the register matrix, then just choose randomly from the main matrix. But be aware that this will increase the failed attempts and make the algorithm less performant.

• Note that, if you opt for implementing the register matrix, you also have to catch exceptions that will occur when the register matrix remains empty.

• Before continuing, we should make sure the chosen cell is not already a mine.

• If you are building the algorithm on a live game, then probably you may want to add some additional features. For example, you should do the choosing process and the following steps after the player actually clicks some cell at the beginning of the game. This allows you to make sure that the player does not click a mine as it first click. Also, if you want, you could make sure that the player does its first click on an empty cell, allowing a good start. Those are some examples of real-time game additional features that make your game better, more responsive, and funnier. In this case, we do not use these features because we are building just a generator for general purposes, for example, a Discord bot minigame.

In this example, register matrix is used:

try:
    row_choice: list = random.choice(matrix_register)
except IndexError:
    # No more mines can be placed!
    break

cell_coordinates: dict = random.choice(row_choice)

row_index = cell_coordinates[0]
column_index = cell_coordinates[1]

value = matrix[row_index][column_index]

3. Evaluation of conditions

• Now that we choose a cell to be placed as mine, we need to evaluate if that cell is valid to be a mine or not. In this case, we will evaluate two main conditions, the number of surrounding valid empty cells and if all contiguous mines are still valid if the chosen cell was to be placed as a mine.

• To do these evaluations, we need to be able to access the surrounding cells of a given cell (The 8 cells that surround it). This can be done by calculating the range of the surrounding cells. To do so, we need to calculate the top left cell and bottom right cell of the range. This has to be done correctly, if not, could end up in index error. One implementation of this could be checking on what position is the given cell. For example, if the given cell is not at the first row of the matrix, we can set the top_left_y as one less position from the Y-axis coordinate of the given cell, if it is, then top_left_y should be the same as the Y-axis coordinate of the given cell. This can be done for the four directions, top_left_x, top_left_y, bottom_right_x and bottom_right_y.

top_left_x = column_index
top_left_y = row_index
bottom_right_x = column_index
bottom_right_y = row_index

if column_index >= 1:
    top_left_x -= 1

if row_index >= 1:
    top_left_y -= 1

if column_index <= width-2:
    bottom_right_x += 1

if row_index <= height -2:
    bottom_right_y += 1

for y in range(top_left_y, bottom_right_y +1):
    for x in range(top_left_x, bottom_right_x +1):

• Surrounding valid empty cells: This first condition will evaluate if the chosen cell has in its surroundings (this means the 8 cells that surround it) at least an arbitrary number of valid empty cells, in this example, at least three, but you can set the number as your wish. A valid empty cell is one that is surrounded by at least an arbitrary number of empty cells, in this example, at least four, but you can set the number as your wish. So basically, we iterate over the empty cells that surround the chosen cell and, recursively, iterate over their surrounding empty cells. This recursion is done only one time, this means that we do not check if the empty cells that surround the empty cell that we are checking are also valid. For example, one valid empty cell has four surrounding empty cells, but these empty cells do not have other four surrounding empty cells so they could not be valid, but we do not check that. For performance reasons, when the desired number of both, surrounding valid empty cells and their surrounding empty cells, is reached, no more iterating to search valid empty cells should be done, as we already fulfilled the condition. If the chosen cell position does not have enough Surrounding valid empty cells, then is discarded as invalid to be placed as a mine.

• All contiguous mines are still valid: This second condition will evaluate if all contiguous mines do still valid in the case where the chosen cell was placed as a mine. This condition should be checked in the same iteration as Surrounding valid empty cells. But here is a difference, this condition will be evaluated recursively until a mine_concatenation_limit or all mines will still be valid. In this case, mine_concatenation_limit is set as three, which means that there should never be more than three mines together, but you can set the number as your wish. When we evaluate this condition, we check again the Surrounding valid empty cells condition for every mine concatenated. If one mine is invalid, then the chosen cell is discarded as invalid to be placed as mine.

• If all conditions are fulfilled, then we can place the chosen cell as a mine. If not, we add one to the counter of failed attempts.

4. Leaving the loop

• Once we exit the loop, we need to check why. If all mines were placed, then we can continue. If not, then we should start over again, restarting the loop, to try again. This will repeat until a correct map generation of mines is done or max_fails is reached.

3. Completing the map

• Now that we have a correct map generation of mines, we should complete it by adding the numbers that surround all mines and give information about their position to the player. This can be done by iterating all the cells again, and on each cell that is a mine, add 1 to the current value of each surrounding cell if it is not a mine. This will end up with a map with mines and all their surrounding cells with numbers of how many are.

for y in range(top_left_y, bottom_right_y +1):
    for x in range(top_left_x, bottom_right_x +1):

        # If the coordinates x & y are the mine cell itself...
        if x == column_index and y == row_index:
            continue

        # Value of the surrounding cell.
        value = matrix[y][x]

        # If the surrounding cell does not contain a mine...
        if value != -1:
            matrix[y][x] += 1

4. Running the validator

• Now that we finished our map, we need to make sure that it has at least one possible solution. Although we place the mines following certain conditions, this is not enough to make sure that the map has at least one possible solution. These conditions help us to make the positioning of the mines more distributed, fun to play, and also, increases the possibilities of the map to has at least one possible solution. If the solver is not able to solve the generated map, then we start again, note that we are still on the main loop. If the solver actually solves the generated map, then we exit the main loop and prepare to either payload or update our game or whatever.

Validator

The validator will not be explained as it is a separate algorithm, but at least will resume it for those who want to know how we did it.

Our validator const of two parts. The logical operations and the matrix operations.

• Logical operations: First, the validator uses logical operations to simplify and solve most of the cases. This normally will end up with the game almost finished. But if an complex case is found, the validator switches to using matrix operations for that case.

• Matrix operations: Uses matrices and maths (Solve a system of linear matrix equations) to determine which cells could be mines or not, if the case is too complex, it could end using prediction and approximations (least-squares solution to a system of linear matrix equations). In the case of using prediction, if the algorithm fails and "loses the game", then the solver determines that the generated map does not have at least one possible solution. The matrix operations are way less flexible than logical operations, but are also way faster computationally and better in the most complex cases.

Summary

This is a good way to build a strong and performant algorithm, that takes into account some conditions and makes some verifications to make sure that the generated MineSweeper map is not only possible to solve, but also funny and challenging. This implementation generates the map dynamically, allowing a lot of configurations, such as difficulty or execution time for the algorithm. This algorithm is very flexible; useful either for small games of grids with areas of literally 9 cells, and also strong and performant against immense and huge grids with areas of thousands of thousands of cells.

If you have any questions, feel free to ask!

Tornado

Answer 4

If you want to place m mines on N squares, and you have access to a random number generator, you just walk through the squares remaining and for each square compute (# mines remaining)/(# squares remaining) and place a mine if your random number is equal to or below that value.

Now, if you want to label every square with the number of adjacent mines, you can just do it directly:

count(x,y) = sum(
  for i = -1 to 1
    for j = -1 to 1
      1 if (x+i,y+j) contains a mine
      0 otherwise
)

or if you prefer you can start off with an array of zeros and increment each by one in the 3x3 square that has a mine in the center. (It doesn't hurt to number the squares with mines.)

This produces a purely random and correctly annotated minesweeper game. Some random games may not be fun games, however; selecting random-but-fun games is a much more challenging task.

Lodicule

i can create the grid and use any random function to place the mines , but the challenge lies ahead , it when i try associating the numbers with those mines , i aint have an idea on how to go about doing them . – Bailee

I provided pseudocode (without bounds checking) that does exactly that. (Pay attention to the sum--you add up 9 values that are either 1 or 0 depending on whether there's a mine there.) – Lodicule