How do I solve this minesweeper algorithm?

1

n the popular Minesweeper game you have a board with some mines and those cells that don’t contain a mine have a number in it that indicates the total number of mines in the neighboring cells. Starting off with some arrangement of mines we want to create a Minesweeper game setup.

Example

For

matrix = [[true, false, false],
[false, true, false],
[false, false, false]]
the output should be

minesweeper(matrix) = [[1, 2, 1],
[2, 1, 1],
[1, 1, 1]]
Check out the image below for better understanding:

Input/Output

[time limit] 4000ms (js)
[input] array.array.boolean matrix

A non-empty rectangular matrix consisting of boolean values - true if the corresponding cell contains a mine, false otherwise.

Guaranteed constraints:
2 ≤ matrix.length ≤ 5,
2 ≤ matrix[0].length ≤ 5.

[output] array.array.integer

The rectangular matrix of the same size as matrix each cell of which contains an integer equal to the number of mines in the neighboring cells. Two cells are called neighboring if they share at least one corner.

2

Looks like a homework (or maybe interview) question. If you want help with a solution you’re working on, go ahead and share what you have and explain what problems you’re having with it.

1 Like
3

well, I don’t have much I know how to get positions of the bombs. But I don’t know how to effectively replace boolean values with appropriate number

const matrix = [[true, false, false],
[false, true, false],
[false, false, false]]

function minesweeper(arr) {
  var pairs = [];
  for(let i=0; i<arr.length; i++){
    for (let j=0; j<arr[i].length; j++){
      if(arr[i][j] === true) {
        pairs.push([i, j])
      }
    }
    console.log(pairs)
  }  
}


minesweeper(matrix)
4

Use a function to count which of all the neighbor squares are bombs. This is the number you’ll output when the player clicks. I would try this. If you don’t have any bombs in the neighborhood you just open all squares and check each one for bombs in the their neighbors (this could be done recursively I think)

1 Like
5

Update:

The challenge above requires you to consider the mines as normal cell values. They do not have a static value of 1 as what this diagram might lead you to believe:

To make this clear, look at this other example:

My response below is based on what I initially understood - mines have a special value of 1 - so it is not valid for this challenge. But it does provide some some sort of a clue about how you could approach and/or solve this problem. So with some modifications, you could use the response below to solve this problem.

It seems that you don’t want to create a Minesweeper AI. From what I understood:

  • You have been provided with a pre-arranged board with the mines spotted.
  • The numbered cells are omitted.
  • Your job is to fill the neighboring cells with the correct values.

I don’t know how to effectively replace Boolean values with an appropriate number

There are several ways to solve this problem. But you should consider the following:

  • There is a special value in the board output, the mine’s value; They should always be 1.
  • The mine’s radius of effect is 1. Whatever inside this radius will have an incremented value of n+1.

Let’s visualize this a bit:

  • Consider we have a given board of:
/*
[F, F, F]
[F, T, F]
[F, F, F]
*/
  • Any true value will have a static value of 1 – Let’s assign that as “X” for now –
    Anything else will have a base value of 0:
/*
[F, F, F]          [0, 0, 0]
[F, T, F]    =>    [0, X, 0]
[F, F, F]          [0, 0, 0]
*/
  • Each “X” (mine) has an AoE of 1. Therefore, if there is an “X” in the middle:
/*
[0, 0, 0]          [1, 1, 1]
[0, X, 0]    =>    [1, X, 1]
[0, 0, 0]          [1, 1, 1]

+1 to all surrounding cells. 
*/
  • Now let’s turn that “X” into its own static value; 1:
/*
[1, 1, 1]          [1, 1, 1]
[1, X, 1]    =>    [1, 1, 1]
[1, 1, 1]          [1, 1, 1]
*/
  • Done.

Let’s try this algorithm on the board you provided:

  • Step 1: Turn it into a usable board
/*
[T, F, F]          [X, 0, 0]
[F, T, F]    =>    [0, X, 0]
[F, F, F]          [0, 0, 0]
*/
  • Step 2: Working on mine(1,1)
/*
[X, 0, 0]          [X, 1, 0]
[0, X, 0]    =>    [1, X, 0]
[0, 0, 0]          [0, 0, 0]
*/
  • Step 3: Working on mine(2,2)
/*
[X, 1, 0]          [X, 2, 1]
[1, X, 0]    =>    [2, X, 1]
[0, 0, 0]          [1, 1, 1]
*/
  • Step 4: Turn the "X"s into 1s
/*
[X, 2, 1]          [1, 2, 1]
[2, X, 1]    =>    [2, 1, 1]
[1, 1, 1]          [1, 1, 1]
*/

There you go, the output requested.

Following this approach for each mine, you should get your correct numbered cells after several loops or so.

Now, this is a thoughtless method to solve this problem. A good knowledge of matrices and linear algebra could possibly provide a better solution which I can’t figure out. More and over, keep in mind there are some hurdles you will encounter while writing your code in which I am leaving them for you to figure out.

Tip: .map() will help.

Goodluck.

Here is my solution while writing this response since you solved it…

1 Like
6

ok I solved it, since the topic didn’t pick up a lot of interest if anyone is interested in the final solution:
here is the link

7

Oh awesome solution!

After looking at your code, It turns out there is no “special value” - you treated the mines as a normal cell which can be incremented based on other mines around it. (I perceived the diagram incorrectly)

The way I did it when I wrote my response considered the “mines” as a special value. Here is a repl using my algorithm. (It is incorrect and took a lot more lines!)

Thanks for sharing your solution!

1 Like
8

Well, I was trying to implement your idea but I found it much harder to implement than if I just go cell by cell and count what’s around them. You should have left the post. It wasn’t bad clue, there are just different approaches

9

I’ll try to come up with recursive solution but this seems pretty efficent

10

My algorithm will provide static mine values. Whereas the challenge requires you to consider them as normal cells. So my algorithm can be misleading for readers.

Oh my bad, the post could definitely provide initial clues. I will restore it and cite the difference.

1 Like
12

here is my approach using Java -

int[][] minesweeper(boolean[][] matrix) {
    
    int[][] result = new int[matrix.length][matrix[0].length];
    
    for(int i=0; i<matrix.length; i++){
        for(int j=0; j<matrix[i].length; j++){
            int sum =0;
            
            for(int x=i-1; x<= i+1 ; x++){
                for( int y=j-1; y<= j+1; y++){

                    if(x > -1 && y > -1 && x < matrix.length && y < matrix[0].length){
                        if( matrix[x][y] == true){
                            sum += 1;
                        }
                    }
                }
            }
            
            if(matrix[i][j] == true){
                result[i][j] = sum-1;                
            }else{
                result[i][j] = sum;  
            }
        }
    }
}