Minesweeper Puzzle in Python in 66 Lines and Its Solution with Probabilistic Algorithm
The idea to write this article came after reading the article Implementation of Minesweeper in 100 Lines of Pure Ruby. Firstly, it seemed to me that 100 lines of code were too much for such a simple game in mechanics. I could have written a more compact solution in pure C. Secondly, the implementation is not entirely correct: in the original game, you cannot lose on the first move, moreover, the first open cell should not have a mine in the neighboring cells.
In addition to implementing the puzzle itself, it would be interesting to write an algorithm that solves it. To do this, we will create a probabilistic algorithm that copes well with this.
Let's define the requirements
Before we start writing code, let's set out the implementation requirements:
The program is a console version of the Minesweeper puzzle. The game field is printed to stdout, columns and fields are numbered, and the console is cleared of previous data at each step.
When launched, the program takes as arguments the field size (width and height) and the number of mines. By default, without passing arguments, a 10×10 playing field with 10 mines is created.
Control is performed by passing commands to standard input (stdin) in the format
row col.You can't lose on the first move, i.e. the cell chosen on the first move must not contain a mine. Also, the neighboring cells must not contain mines.
Victory is counted when all unmined cells on the playing field are revealed, defeat – when the player reveals a cell with a mine. The last move displays the corresponding message about victory or defeat and a completely open playing field.
It is necessary to implement an algorithm for solving the puzzle. At each step, the program prints the current state of the game with accompanying reference information.
The requirements turned out to be quite formal; in the implementation itself, I will not strive for a minimum number of lines of code, but will try to maintain a balance between compactness, readability, and performance.
Designing the implementation
To begin with, it would be good to understand what “Minesweeper” is from the point of view of game logic. The basis of the game is a two-dimensional field of arbitrary size, the cells of which can contain mines. When the game starts, all the cells are closed, the player's task is to open all the cells that do not contain mines and not “blow up”. When a cell is open, a counter appears in its place, indicating the number of mines in neighboring cells. If there are no mines around a cell, all neighboring cells are automatically revealed. Based on this information, the player must decide which cell to open next.
So, we need to store the state of all the cells of the playing field. Each cell can be:
open or closed
to contain or not to contain a mine
know the number of mines in neighboring cells
Since our primary goal is to write a compact algorithm, we can consider two options for storing the cell state: a structure with the corresponding fields, or a single byte of data into which we encode all states.
Data structure
class Cell:
def __init__(self):
self.is_mine = False
self.revealed = False
self.adjacent_mines = 0Everything is intuitive here: three fields for each characteristic, easy to read and work with. Only 5 lines of code.
One byte per cell
If necessary, we can encode the cell state in just one byte. Although it will be more difficult to understand, the rules are as follows:
Negative numbers from -1 to -9 will represent closed unmined cells, where the absolute value of the number minus one indicates the number of adjacent mines.
Positive numbers from 1 to 9 will represent open cells.
A value of 0 will indicate a cell with a mine.
Since opening a mine cell will be considered the final step, we do not need to distinguish between open or closed mined cells.
I will choose the option with storing the state in one byte. It remains to determine in which data structure we will store the field state. The first thing that comes to mind is, of course, a two-dimensional array. However, there is an alternative – a flat list, and Python is simply the king of lists, so no two-dimensional arrays.
Let's write code
Let's declare a class Minesweeperits fields and methods:
class Minesweeper:
def __init__(self, rows, cols, mines):
self.size = rows * cols
self.rows = rows
self.cols = cols
self.mines = mines
self.board = [-1] * (self.size) # Инициализация значениями -1
self.first_step = True
def play(self):
pass
def place_mines(self, safe_row, safe_col):
pass
def print_board(self, reveal_mines=False):
pass
def get_neighbors(self, idx):
pass
def reveal(self, idx):
passThe constructor takes the field size and the number of mines as arguments, and initializes the cell list with the value -1. This value corresponds to a closed cell with zero adjacent mines. To do this, we simply multiply the list of one element by the number of elements needed.
To work with a flat list we need the following simple formulas.
Index of an element by its two-dimensional coordinates:
index = row * cols + colColumn of an element by its index:
col = index % colsString of an element by its index:
row = index // colsKnowing this, we can write a method to get neighboring cells by cell index:
def get_neighbors(self, index):
# Вычисляем строку и столбец из индекса
row = index // self.cols
column = index % self.cols
# Инициализируем список для хранения индексов соседних клеток
neighbors = []
# Проходим по всем возможным соседям
for i in range(row - 1, row + 2): # r - 1, r, r + 1
for j in range(column - 1, column + 2): # c - 1, c, c + 1
# Проверяем, чтобы не выйти за пределы поля
if 0 <= i < self.rows and 0 <= j < self.cols:
# Проверяем, чтобы не добавить саму клетку
if i != row or j != column:
# Вычисляем индекс соседа и добавляем его в список
neighbor_index = i * self.cols + j
neighbors.append(neighbor_index)
return neighborsIt turned out to be quite verbose. Python has many tools for convenient work with lists, including their generation. There is a so-called list comprehensionsit's not the same as the usual ones generators. The difference is that generators create sequences of values as needed (lazily), while list comprehensions create and store them in memory immediately. It is easy to distinguish a generator from a list comprehension: the generator expression is enclosed in parentheses, while list comprehensions are enclosed in square brackets.
def get_neighbors(self, idx):
r, c = divmod(idx, self.cols)
return [i * self.cols + j for i in range(r - 1, r + 2) for j in range(c - 1, c + 2)
if 0 <= i < self.rows and 0 <= j < self.cols and (i != r or j != c)]Please note that we have transferred all cycles and conditions without changes.
It's time to implement the method of placing mines on the playing field. Here, too, we cannot do without list generators:
def place_mines(self, safe_row, safe_col):
def count_mines(idx):
return sum(1 for ni in self.get_neighbors(idx) if self.board[ni] == 0)
safe = set(self.get_neighbors(safe_row * self.cols + safe_col) + [safe_row * self.cols + safe_col])
possible = [(i, j) for i in range(self.rows) for j in range(self.cols) if (i * self.cols + j) not in safe]
list(map(lambda pos: self.board.__setitem__(pos[0] * self.cols + pos[1], 0), sample(possible, self.mines)))
self.board = [-1 * (count_mines(idx) + 1) if cell != 0 else cell for idx, cell in enumerate(self.board)]Let's take a look at what's going on here:
First, we need to define a safe zone. The method takes the coordinates of a safe cell, gets a list of its neighbors, and creates a list of cell indices safein which we will not place mines.
The next line generates a list of cell indices possiblein which a mine can be placed. To do this, we generate a list of indices of all cells on the playing field that are not in the safe zone.
Now it's time to place mines. We agreed earlier that the cell containing the mine takes on the value 0. To select N random elements of the list, we use the function random.sample. This is a standard library function. random takes as argument any iterable sequence of elements and a number that specifies the number of unique elements to be selected from the passed sequence. We use mapto apply the lambda function to all elements of the list, and listto map did all the work.
Next we need to count the number of mines in the neighboring cells. To do this, we use the list generator again and for each element of the existing list we check whether the cell is a mine (the value is zero) and count the mines in the neighboring cells.
Now that the game board is ready, we can move on to writing the game loop.
Method play must process user input, place mines on the first move, open cells, check for victory and defeat conditions. We will have the most lines of code.
def play(self):
while True:
print("\033[H\033[J", end="") # очищаем терминал
self.print_board()
try:
row, col = map(int, input("Enter row and column (0-9): ").split())
assert 0 <= row < self.rows and 0 <= col < self.cols
except (ValueError, AssertionError):
print("Invalid input. Please enter numbers between 0 and 9.")
continue
idx = row * self.cols + col
if self.first_step:
self.place_mines(row, col)
self.first_step = False
if self.board[idx] == 0:
print("You hit a mine! Game Over.")
self.print_board(reveal_mines=True)
break
self.reveal(idx)
if all(cell >= 0 for cell in self.board):
print("Congratulations! You've cleared the minefield.")
self.print_board(reveal_mines=True)
breakThe winning condition is very simple: the values of all cells on the board must be greater than or equal to zero.
In the method revealwhich opens a cell, we have two options for implementation. Since if the opened cell does not contain any mines in the neighborhood, we need to open all neighboring cells, recursion comes to mind. However, we should be careful with this, since with a large playing field and low density of mines, we can easily reach the maximum recursion depth. By default, the recursion depth in Python is limited to 1000 calls. An alternative would be to use a stack, in which we will put the indices of the cells to be opened:
def reveal(self, idx):
stack = [idx]
while stack:
current_idx = stack.pop()
self.board[current_idx] = abs(self.board[current_idx])
if self.board[current_idx] - 1 == 0:
stack.extend(ni for ni in self.get_neighbors(current_idx) if self.board[ni] < 0)At the beginning, we add the index of the transferred cell to the stack, which is represented by a list. Then, while there are elements in the stack, we get them. To consider the cell open, we remove the sign from its value. If there are no mines around, we add neighboring cells to the stack.
It remains to implement the method that prints the playing field.
def print_board(self, reveal_mines=False):
max_col_digits = len(str(self.cols - 1))
max_row_digits = len(str(self.rows - 1))
print(" " * (max_row_digits + 2) + " ".join(f"{i:>{max_col_digits}}" for i in range(self.cols)))
for i in range(self.rows):
row = ['X' if reveal_mines and value == 0 else
str(abs(value) - 1) if reveal_mines and value < 0 else
'*' if value <= 0 else str(value - 1)
for value in (self.board[i * self.cols + j] for j in range(self.cols))]
print(f"{i:>{max_row_digits}}: " + " ".join(f"{cell:>{max_col_digits}}" for cell in row))The method takes a parameter reveal_mineswhich determines whether the positions of mines on the field will be revealed. To ensure that columns and rows are aligned regardless of their number, the number of digits in the row and column numbers is counted. This data is used to insert the required number of spaces.
The first line displays the header with column numbers: " " * (max_row_digits + 2) creates a starting indent, then the column numbers are printed using f-strings.
Next, in the loop, for each row, a list of the displayed cell values is generated using a list generator:
If
reveal_mines is Trueand the cell contains a mine, it is excretedX.If
reveal_mines is Truebut the cell is not opened, its value is displayed.If the cell is not opened, an empty line is displayed.
In all other cases, the cell value (the number of mines in adjacent cells) is displayed.
All that remains is initialization and launch:
if __name__ == "__main__":
rows, cols, mines = (int(arg) for arg in sys.argv[1:]) if len(sys.argv) > 1 else (10, 10, 10)
game = Minesweeper(rows, cols, mines)
game.play()The program expects three arguments: number of rows, columns, and min. If no arguments are passed, default values are used.
At this point, the implementation of the game itself is complete, and the entire code fits into just 66 lines!
Here is the full code listing:
import sys
from random import sample
class Minesweeper:
def __init__(self, rows, cols, mines):
self.size = rows * cols
self.rows = rows
self.cols = cols
self.mines = mines
self.board = [-1] * self.size
self.first_step = True
def play(self):
while True:
print("\033[H\033[J", end="") # очищаем терминал
self.print_board()
try:
row, col = map(int, input("Enter row and column (0-9): ").split())
assert 0 <= row < self.rows and 0 <= col < self.cols
except (ValueError, AssertionError):
print("Invalid input. Please enter numbers between 0 and 9.")
continue
idx = row * self.cols + col
if self.first_step:
self.place_mines(row, col)
self.first_step = False
if self.board[idx] == 0:
print("You hit a mine! Game Over.")
self.print_board(reveal_mines=True)
break
self.reveal(idx)
if all(cell >= 0 for cell in self.board):
print("Congratulations! You've cleared the minefield.")
self.print_board(reveal_mines=True)
break
def print_board(self, reveal_mines=False):
max_col_digits = len(str(self.cols - 1))
max_row_digits = len(str(self.rows - 1))
print(" " * (max_row_digits + 2) + " ".join(f"{i:>{max_col_digits}}" for i in range(self.cols)))
for i in range(self.rows):
row = ['X' if reveal_mines and value == 0 else
str(abs(value) - 1) if reveal_mines and value < 0 else
'*' if value <= 0 else str(value - 1)
for value in (self.board[i * self.cols + j] for j in range(self.cols))]
print(f"{i:>{max_row_digits}}: " + " ".join(f"{cell:>{max_col_digits}}" for cell in row))
def place_mines(self, safe_row, safe_col):
def count_mines(idx):
return sum(1 for ni in self.get_neighbors(idx) if self.board[ni] == 0)
safe = set(self.get_neighbors(safe_row * self.cols + safe_col) + [safe_row * self.cols + safe_col])
possible = [(i, j) for i in range(self.rows) for j in range(self.cols) if (i * self.cols + j) not in safe]
list(map(lambda pos: self.board.__setitem__(pos[0] * self.cols + pos[1], 0), sample(possible, self.mines)))
self.board = [-1 * (count_mines(idx) + 1) if cell != 0 else cell for idx, cell in enumerate(self.board)]
def get_neighbors(self, idx):
r, c = divmod(idx, self.cols)
return [i * self.cols + j for i in range(r - 1, r + 2)
for j in range(c - 1, c + 2)
if 0 <= i < self.rows and 0 <= j < self.cols and (i != r or j != c)]
def reveal(self, idx):
stack = [idx]
while stack:
current_idx = stack.pop()
self.board[current_idx] = abs(self.board[current_idx])
if self.board[current_idx] - 1 == 0:
stack.extend(ni for ni in self.get_neighbors(current_idx) if self.board[ni] < 0)
if __name__ == "__main__":
rows, cols, mines = (int(arg) for arg in sys.argv[1:]) if len(sys.argv) > 1 else (10, 10, 10)
game = Minesweeper(rows, cols, mines)
game.play()Now you can launch the game:
Puzzle solving algorithm
Now that we have created a compact and efficient implementation of Minesweeper in Python, it is time to develop an algorithm to automatically solve the puzzle. In this part of the article, we will create a probabilistic algorithm that will find safe moves and solve the puzzle, minimizing the risk of a mine explosion.
The heuristic solution algorithm is based on probabilistic and logical inferences. Here is a general approach to its implementation:
Start by opening a random cell.
Evaluate the opened cells and compare the number of adjacent unopened cells with the number of mines in the neighborhood.
If the number of adjacent undiscovered cells is equal to the number of mines in the neighborhood, mark them with a flag as mined.
If the number of adjacent flagged cells is equal to the number of mines in the neighborhood, reveal the remaining adjacent cells as guaranteed safe and return to step 2.
If the field configuration does not allow one to find guaranteed safe cells, conduct an analysis of the probability of mines in unexposed cells based on information about the number of mines around exposed cells.
Open the cell with the lowest probability of containing a mine. If the cell is safe, go to step 2. If the cell contains a mine, the game is lost.
If the number of uncovered cells is equal to the number of mines remaining on the board, the game is won.
Now let's move on to implementation: let's create a class MinesweeperSolverextending the base class Minesweeper.
class MinesweeperSolver(Minesweeper):
def __init__(self, rows, cols, mines):
super().__init__(rows, cols, mines)
self.probabilities = [0] * self.size
self.flagged = [False] * self.size
self.place_mines(int(rows / 2), int(cols / 2))
self.reveal(int(rows / 2 * cols + cols / 2))In the constructor, we initialized the lists for storing probabilities and flags, and immediately opened the first cell. The central cell was chosen for this, since it usually provides the most information about the state of the field.
A method that analyzes the state of the field and opens cells:
def analyze_and_reveal(self):
to_reveal = []
self.probabilities = [0] * self.size
flag_placed = False
for idx, cell in enumerate(self.board):
if cell <= 1: # клетка не раскрыта или по соседству 0 мин
continue
unrevealed_neighbors = [n for n in self.get_neighbors(idx) if self.board[n] <= 0]
flag_neighbors_count = sum(self.flagged[n] for n in self.get_neighbors(idx))
# если количество мин вокруг равно значению клетки то помечаем соседей флагом
if cell - 1 == len(unrevealed_neighbors):
for un_idx in unrevealed_neighbors:
if not self.flagged[un_idx]:
self.flagged[un_idx] = True
flag_placed = True
for un_idx in unrevealed_neighbors:
# если соседняя клетка не помечена флагом
if not self.flagged[un_idx]:
if cell - 1 == flag_neighbors_count and un_idx not in to_reveal:
# если количество помеченных флагом клеток вокруг равно значению клетки
# добавляем ее в список для раскрытия
to_reveal.append(un_idx)
# подсчитываем вероятность клетки быть заминированной на основании ее значения
# и количества нераскрытых и не помеченных флагом клеток вокруг
self.probabilities[un_idx] += (cell - 1) / (len(unrevealed_neighbors))
if to_reveal:
# открываем гарантированно безопасные клетки
print("Reveal safe cells:", [divmod(safe_idx, self.cols) for safe_idx in to_reveal])
list(map(self.reveal, to_reveal))
elif flag_placed:
# если безопасных клеток нет, но какая-то клетка была помечена флагом, следует проанализировать доску снова
return True
else:
# находим клетку с минимальной вероятностью быть заминированной и пытаемся открыть
probably_safe = (i for i, p in enumerate(self.probabilities) if p > 0 and not self.flagged[i])
idx = min(probably_safe, key=lambda i: self.probabilities[i], default=None)
if idx is not None:
print("Try reveal:", divmod(idx, self.cols), self.board[idx])
if self.board[idx] == 0:
return False
self.reveal(idx)
else:
return False
return TrueMethod solve in the loop calls analyze_and_reveal and analyzes the conditions of victory and defeat:
def solve(self):
while (not_failed := self.analyze_and_reveal()) and not all(cell >= 0 for cell in self.board):
self.print_board()
if not_failed:
print("Congratulations! You've cleared the minefield.")
else:
print("Auto-solver hit a mine! Game Over.")
The algorithm turned out to be quite simple, and it can be improved, for example, using the method Monte Carlo. To evaluate how well the current implementation copes with solving the puzzle, I propose to conduct a benchmark. To do this, we will test configurations with a field size of 10×10 and the number of mines from 10 to 35. We will conduct 5000 iterations for each configuration and calculate the percentage of successful solutions. The results can be visualized using matplotlibhaving constructed a graph of the dependence of the percentage of successful solutions on the number of min.
Test code:
if __name__ == "__main__":
tries = 5000
success_rates = []
mine_counts = range(10, 36)
for m in mine_counts:
rows, cols, mines = (int(arg) for arg in sys.argv[1:]) if len(sys.argv) > 1 else (10, 10, m)
stat = 0
for i in range(tries):
solver = MinesweeperSolver(rows, cols, mines)
stat += solver.solve()
success_rate = stat / tries * 100
success_rates.append(success_rate)
print(m, success_rate)
# Построение графика
plt.figure(figsize=(8, 4))
plt.plot(mine_counts, success_rates, marker="o")
plt.title('Success Rate of Minesweeper Solver')
plt.xlabel('Number of Mines')
plt.ylabel('Success Rate (%)')
plt.ylim(0, 100)
plt.grid(True)
plt.show()
Result:
The results were quite good. The standard 10×10 configuration with 10 mines is solved successfully in about 95% of cases. For configurations with 20 mines, the probability of successful solution is about 30%, and with 30 or more mines, the algorithm no longer copes. However, the Monte Carlo method can improve the results, so for those who read the article to the end, I offer a challenge: implement an algorithm that solves the Minesweeper puzzle using the Monte Carlo method or another method that shows better results than the current one!
The project code is available at GitHub.
