---
# System prepended metadata

title: An experimental minsweeper implementation

---

# An experimental minsweeper implementation

Well, this article is relating to my last [article on tictactoe game](https://hackmd.io/@0xosas/S1uWnLChq) and this is because of similar logic being used.

### A Minsweeper Game

The objective of the game is to clear a board that contains hidden "mines" or "bombs" without detonating any of them, and they are randomly placed in a 9x9 grid (beginners level). On every right opeing there's a clue which indicate how many bombs are in the adjacent cells.

At any point, you can perform 2 actions:

- Marking a cell - marking or flagging a cell that you think might be a bomb
- Revealing a cell - revealing the cell. If it is an empty cell, then all of the surrounding empty cells will also be revealed. Revealing a cell containing a bomb is game over.

Once you have revealed all cells that do not contain a bomb, you win the game. Also before going forward it is recommended that you understand how to play Minesweeper practically! and also understand the concept of [bitwise operations](https://hackmd.io/@0xosas/B1H8OY03c) as this article would rely heavily on it.

### Planning

Given a grid of N rows and M columns to play the game, we'd represent this grid as bits. We'd denote each cell as an 7-bit integer and here is the data that'd be stored:

```
 0          0         0          0 0 0 0
---        ---       ---        ---------
 |          |         |             |
is-marked  is-bomd   is-revealed  cell-value

```

Note: We can use bitwise operations to extract or set relevant bits. The relevant masks would be defined later in this article.

By default, the game is played on a 9x9 grid and a maximum of 10 bombs. However, you can change these later and I'd include settings to easily make changes. As a brief guidline, the standard levels of Minesweeper are:

|          | Beginner | Intermediate | Expert
-----------|----------|--------------|--------
Grid size  | 9 x 9    | 16 x 16      | 16 x 30
Max bombs  | 10       | 40           | 90

So here is a visual example of a 9 x 9 grid and how it'd be represented in bits.

```
      0       1       2       3       4       5       6       7      8            0   1   2   3   4   5   6   7   8
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╔═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╗
      9      10      11      12      13      14      15      16     17          ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     18      19      20      21      22      23      24      25      26         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 1
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     27      28      29      30      31      32      33      34      35         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 2
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     36      37      38      39      40      41      42      43      44         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 3
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     45      46      47      48      49      50      51      52      53         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 4
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     54      55      56      57      58      59      60      61      62         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 5
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     63      64      65      66      67      68      69      70      71         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 6
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     72      73      74      75      76      77      78      79      80         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 7
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
                                                                                ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 8
                                                                                ╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝
```

So firstly, we need a way to generate a game and add bombs at random; and here is how we'd implement this in python.

I'd define certain constants which would be used through out this code.

```python=
DATA_SIZE = 7

BITMASK_VALUE = (1 << 4) - 1 # 0xf
BITSHIFT_IS_REVEALED = 4
BITSHIFT_IS_BOMB = 5
BITSHIFT_IS_FLAGED = 6

BITMASK_CELL = (1 << DATA_SIZE) -1 
```

And here defining a simple Minesweeper class to simply help hold some property variables and also making it easy to tweek. 

```python=
class Minesweeper:
    def __init__(self, rows, columns):
        self.rows = rows
        self.columns = columns
        self.data_size = 7     # 7 bits
        self.bits = self.rows * self.columns * self.data_size

        self.grid = 1 << (self.bits + 1) # 0b1000...000 to the `self.bits` zeros
        
```

## Placing Bombs

On getting this far, you might be able to picture some of the diagrams prevously drawn, in code. Though not the full picture yet but very soon you'd get it. Since evey game needs a bomb and clues, we'd need to generate these randomly. Here is how we'd implement it:

```python=
from random import randint

class Minesweeper:
    ...

    def placeBomb(self, grid):
        """Places a bomb in a random cell"""
        bomb_cell = randint(0, self.rows * self.columns)

        cell = (bomb_cell * self.data_size)

        # getting the value of the cell (7-bits)
        val = (grid >> cell) & BITMASK_CELL

        if (val >> BITSHIFT_IS_BOMB) & 1:
            grid = self.placeBomb(grid)
        else:
            # setting the bomb bit and adding it to the grid (setting the 6th bit)
            new_cell = (1 << BITSHIFT_IS_BOMB) << cell
            grid |= new_cell
        
        return grid    
    
    def new_game(self):
        for _ in range(10):
            self.grid = self.placeBomb(self.grid)
```

The function `placeBomb` places a bomb in a random cell. If you look closely you'd see a little recursion which makes sure that a bomb is place in a unique cell, since there is a possiblity of a random cell being generated more than once. So from the above code we can only generate a grid with bombs on it.

```
game = Minesweeper(9,9)
game.new_game()
game.print_game(debug=True) # function not added here

========== OUTPUT =============
 _  *  _  _  _  _  _  _  _ 
 *  _  _  _  _  _  _  _  * 
 *  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _ 
 _  _  _  _  *  _  _  _  _ 
 *  _  *  _  *  _  _  _  _ 
 _  _  _  _  _  *  _  _  _ 
 _  _  _  _  _  _  _  *  _


Note: * denotes a bomb. Also it'd be different if you run it since it is generated at random
```

## Adding Clues

Clues indicate how many bombs are in the adjacent cells. So we'd need to know the cells adjacent if a particular cell and also count how many of these cells are bombs. 

```
      Count all the mines in the 8 adjacent cells

      N.W  N  N.E
        \  |  /
         \ | /
    W----Cell----E
         / | \
        /  |  \
      S.W  S  S.E
```

Solving this problem is far simpilar using a 2d array since you can easily do math on the (row, col). Here each cell is represented differently, in other words each cell has an `id` like so:


```
0    1   2   3   4   5   6   7   8   

9   10  11  12  13  14  15  16  17

18  19  20  21  22  23  24  25  26

27  28  29  30  31  32  33  34  35

36  37  38  39  40  41  42  43  44

45  46  47  48  49  50  51  52  53

54  55  56  57  58  59  60  61  62

63  64  65  66  67  68  69  70  71

72  73  74  75  76  77  78  79  80
```

If we want the adjacent cells for cell `30` which from the above grid would look like:

```
TOP       | 20 | 21 | 22 |
          ----------------
SIDED     | 29 | 30 | 31 |
          ----------------
BOTTOM    | 38 | 39 | 40 | 

Adjacent cells would be [20, 21, 22, 29, 31, 38, 39, 40]
```

To get the top cells, We'd need to check if the current row isn't the first row since there is noting above the first row. Also you'd realize that the top cell is just the `current_cell - number_of_columns` in this case the top cell of `30` is `21` which is `30 - 9` and the bottom cell of `30` is `current_cell + number_of_columns` which in this case is `39`. You'd also realize that the diagonal cells are the cells by the sides of the top and bottom cell. So to get the top diagonals we'd just minus and add 1 to the top cell, also to get the bottom
diagonals we'd minus and add 1 to the bottom cell.

```
Psuedocode

# add top cells
adjacent_cells = []
if row > 1:
    top = current_cell - number_of_columns
    adjacent_cells.push(top)

    # add the sides
    adjacent_cells.push(top-1)
    adjacent_cells.push(top+1)

# Add the sides of the current cell
adjacent_cells.push(current_cell-1)
adjacent_cells.push(current_cell+1)

# add bottom cells

if row < number_of_rows:
    bottom = current_cell + number_of_columns
    adjacent_cells.push(bottom)

    # add the sides
    adjacent_cells.push(bottom-1)
    adjacent_cells.push(bottom+1)


Note: extra checks would be done to make sure the right cells are added.
for example a cell at the edge would only have one valid cell by it side instead of 2
```

Here I would define a property function that gets adjacent cells:

```python=
class Minesweeper:
    ...

    def adjacent_cells(self, pos, pos_row):
        adj_cells = []
        # top
        if pos_row > 1:
            t = pos - self.columns
            adj_cells.append(t)

            if t+1 < ((pos_row-1) * self.columns):
                adj_cells.append(t+1)

            if t-1 >= (((pos_row-1) * self.columns) - self.columns):
                adj_cells.append(t-1)      

        # sides
        if pos + 1 < (pos_row * self.columns):    
            adj_cells.append(pos+1)
        
        if pos - 1 > ((pos_row-1) * self.columns) - self.columns:    
            if pos -1 >= 0:
                adj_cells.append(pos-1)
        
        # bottom

        if pos_row < self.rows:
            b = pos + self.columns
            adj_cells.append(b)

            if b+1 < ((pos_row+1) * self.columns):
                adj_cells.append(b+1)

            if b-1 >= (pos_row * self.columns):
                adj_cells.append(b-1)     
        
        return sorted(adj_cells)

```

Now, I think you understand how the adjacent cells are gotten. We can now move forward with adding the clues.

```python=
class Minesweeper:
    ...

    def new_game(self):
        ...

        # the row of the current position
        pos_row = 1

        # p is the position here
        for p, y in enumerate(range(0, self.bits, self.data_size)):

            adj_cells = self.adjacent_cells(p, pos_row)
            bombs = 0
            cell = (p * self.data_size)
            val = (self.grid >> cell) & BITMASK_CELL # gets the data of the current cell position

            if (val >> BITSHIFT_IS_BOMB) & 1 == 0: # checks if the current position is a bomb
                # looping through each adjacent cells and increments
                # the bomb count if the cell is a bomb
                for pos in adj_cells:
                    pos_cell = (pos * self.data_size)
                    pos_val = (self.grid >> pos_cell) & BITMASK_CELL # gets the data of the current cell position

                    if (pos_val >> BITSHIFT_IS_BOMB) & 1:
                        bombs += 1

                if bombs:
                    # adds the amount of bombs in adjacent cells to the grid
                    new_cell =  bombs << cell
                    self.grid |= new_cell


            # incrementing the row onces it gets to the end of a row
            y += self.data_size
            if y % (self.columns * self.data_size) == 0:
                pos_row += 1
```

Running the current code here is what we have to far.

```
game = Minesweeper(9,9)
game.new_game()
game.print_game(debug=True) # function not added here

========== OUTPUT =============
_  _  _  _  _  _  _  _  _ 
_  _  1  1  1  _  _  _  _ 
2  2  2  *  2  2  1  1  _ 
*  *  2  2  *  2  *  1  _ 
*  3  1  1  1  2  1  1  _ 
2  3  1  1  _  _  _  _  _ 
*  3  *  1  _  _  _  _  _ 
*  3  1  1  _  _  _  _  _ 
1  1  _  _  _  _  _  _  _ 

Note: It'd be different every time you run it since it is generated at random
```

## Making Moves

I think the game is a little bit ready and it's not complete if a play can't make a move. So basically a player should be able to flag a cell and also reveal a cell. The functions here are just basically setting and checking bits. In this case of `flag` its setting the 7th bit.

```python=
class Minesweeper:
    ...

    def flag(self, pos):
        """Lets a play flag a cell or position"""
        
        cell = (pos * self.data_size)
        _flag =  (1 << BITSHIFT_IS_FLAGED) << cell
        self.grid |= _flag

    def reveal(self, pos):
        """Lets a play reveal a cell or position. Also
        raises an exception is a player reveals a cell with
        a bomb
        """

        cell = (pos * self.data_size)
        val = (self.grid >> cell) & BITMASK_CELL

        if (val >> BITSHIFT_IS_BOMB) & 1:
            raise Exception("Game ended: revealed a bomb")

        reveal =  (1 << BITSHIFT_IS_REVEALED) << cell
        self.grid |= reveal
```

The full code is [available on github](https://gist.github.com/0xosas/8e1ade6a1a0b4067ba00c0094577f776).

## Reference materials
[Final Project: Minesweeper](https://itp.uni-frankfurt.de/~mwagner/teaching/C_WS17/projects/Minesweeper.pdf)
[Assignment 1: minesweeper, MIPS minesweeper](https://cgi.cse.unsw.edu.au/~cs1521/21T3/assignments/ass1/index.html)
[Implementation of Minesweeper Game](https://www.geeksforgeeks.org/cpp-implementation-minesweeper-game/)
[How to program MineSweeper in Python](https://replit.com/talk/learn/How-to-program-MineSweeper-in-Python-fully-explained-in-depth-tutorial/9397)
[Optimized tic-tac-toe game in Solidity](https://hackmd.io/@0xosas/S1uWnLChq)
[Bit Operations](https://hackmd.io/@0xosas/B1H8OY03c)

-----

If you found this helpful, consider following me on Twitter [@0xosas](https://twitter.com/0xosas).