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

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

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

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 cellprivate 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 notprivate 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 clickpublic 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.

--

--

More from TRICK THE INTERVIEWER

Programming interview is the one where the interviewer will make all possible attempts to trick you. Trick the interviewer this time! :)