Minesweeper

Have you played minesweeper before? Well, I believe yes, everyone has played that game during our childhood. But not everyone knows the logic behind that awesome game. Stay with me for this post and believe me I will make it simpler for you and you are going to love it.

Let’s begin!

In minesweeper game, there are three types of cells, i.e., flagged (the cells containing mine or bomb), covered cells which are clickable, uncovered cells which are already exposed.

At first, we can click on any random cell, and if unfortunately it is a mine, your game is over. If the clicked cell has a number on it, it denotes that this cell has at most these many mines surrounding it.

Possible neighbors of a cell

There are eight neighbors for a cell

Cell at position (x,y) in the grid and surrounding neighbors

Let’s take an example of a cell that has a number on it.

Central cell has number 1 on it, that means it has at least and at most one mine in it’s surrounding neighbors.
This can be a possible mine position and it represents a possible correct grid
As the cell has 1 on it, that means there is only one mine adjacent to it, but here two mines are shown. So, this is not possible. This is incorrect grid.

Similarly, example of two cells having a number on them.

This is valid. Both cells can have only 1 surrounding mine and this mine is adjacent to both the mines.
This is invalid. Both cells can have only 1 surrounding mine but here both cells are having two adjacent mines in the neighbors.

Now, I think you might have understood the logic behind minesweeper game. Suppose, you are given one click position and you have to explore the cells of minesweeper game as much as possible.

Problem statement (Source — Leetcode)

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

If a mine (‘M’) is revealed, then the game is over — change it to ‘X’.

If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.

If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.

Return the board when no more squares will be revealed.

Depth First Search — Self explanatory code

//all the possible 8 directions around a cell
private static int[] xdir = new int[]{-1, 1, -1, 1, -1, 1, 0, 0};
private static int[] ydir = new int[]{0, 0, -1, -1, 1, 1, -1, 1};
//checking if the adjacent position is a valid position or not
private boolean isValid(int newRow, int newCol, int rows, int cols){
return newRow>=0 && newRow<rows && newCol>=0 && newCol<cols;
}

Function to update the board after the click

//function to update the board based on the click
public char[][] updateBoard(char[][] board, int[] click) {
int rows = board.length;
int cols = board[0].length;

//if the click position is revealed or unrevealed mine, change it to revealed mine i.e. X and return the board as the game is over
if(board[click[0]][click[1]]=='M' || board[click[0]][click[1]]=='X'){
board[click[0]][click[1]] = 'X';
return board;
}

//if the click position has an unrevealed cell, find the number of mines adjacent to it
int mines = 0;
for(int i=0; i<8; i++){
int newRow = click[0]+xdir[i];
int newCol = click[1]+ydir[i];

if(isValid(newRow, newCol, rows, cols) && board[newRow][newCol]=='M'){
mines++;
}
}

//if there is at least one mine adjacent to current click position, then update the board click position with the number of adjacent mines
//and in such case we won't explore any further from current cell according to problem constraint and just return

if(mines>0){
board[click[0]][click[1]] = Character.forDigit(mines, 10);
return board;
}

//if there is no adjacent mine to the current click position, then mark this cell as revealed black cell
board[click[0]][click[1]] = 'B';

//explore the adjacent valid unexplored cells which don't have mine - DFS from current click position for all the valid cells
for(int i=0; i<8; i++){
int newRow = click[0]+xdir[i];
int newCol = click[1]+ydir[i];

if(isValid(newRow, newCol, rows, cols) && board[newRow][newCol]=='E'){
updateBoard(board, new int[]{newRow, newCol});
}
}

//return the final board
return board;
}

Complexity Analysis

Time Complexity: O(m*n) in worst case, where m is the number of rows and n is the number of columns. We are performing DFS on the grid from the click position

Space Complexity: O(m*n) stack space for recursion

Guys I really hope that you find this article valuable! If still, you have any queries, you can surely discuss them in the comment section below.

Thanks a lot for devoting your time to this blog.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store