Minesweeper master from Google Code Jam(2014) Qualification round

Question

This is a problem from Google Code Jam qualification round (which is over now). How to solve this problem?

Note: If you have a different method from the ones discussed in answers, please share it so we can expand our knowledge of the different ways to solve this problem.

Problem Statement:

Minesweeper is a computer game that became popular in the 1980s, and is still included in some versions of the Microsoft Windows operating system. This problem has a similar idea, but it does not assume you have played Minesweeper.

In this problem, you are playing a game on a grid of identical cells. The content of each cell is initially hidden. There are M mines hidden in M different cells of the grid. No other cells contain mines. You may click on any cell to reveal it. If the revealed cell contains a mine, then the game is over, and you lose. Otherwise, the revealed cell will contain a digit between 0 and 8, inclusive, which corresponds to the number of neighboring cells that contain mines. Two cells are neighbors if they share a corner or an edge. Additionally, if the revealed cell contains a 0, then all of the neighbors of the revealed cell are automatically revealed as well, recursively. When all the cells that don't contain mines have been revealed, the game ends, and you win.

For example, an initial configuration of the board may look like this ('*' denotes a mine, and 'c' is the first clicked cell):

*..*...**.
....*.....
..c..*....
........*.
..........

There are no mines adjacent to the clicked cell, so when it is revealed, it becomes a 0, and its 8 adjacent cells are revealed as well. This process continues, resulting in the following board:

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

At this point, there are still un-revealed cells that do not contain mines (denoted by '.' characters), so the player has to click again in order to continue the game.

You want to win the game as quickly as possible. There is nothing quicker than winning in one click. Given the size of the board (R x C) and the number of hidden mines M, is it possible (however unlikely) to win in one click? You may choose where you click. If it is possible, then print any valid mine configuration and the coordinates of your click, following the specifications in the Output section. Otherwise, print "Impossible".

My Tried Solution:

So for the solution, you need to make sure that each non-mine node is in a 3x3 matrix with other non-mine nodes, or a 3x2 or 2x2 matrix if the node is on an edge of the grid; lets call this a 0Matrix. So any node in a 0Matrix have all non-mine neighbors.

Firstly, Check whether less mines are required, or less empty nodes

if(# mines required < 1/3 of total grid size)
    // Initialize the grid to all clear nodes and populate the mines
    foreach (Node A : the set of non-mine nodes)
        foreach (Node AN : A.neighbors)
            if AN forms a OMatrix with it's neighbors, continue
            else break;
        // If we got here means we can make A a mine since all of it's neighbors 
        // form 0Matricies with their other neighbors
    // End this loop when we've added the number of mines required

else
    // We initialize the grid to all mines and populate the clear nodes
    // Here I handle grids > 3x3; 
    // For smaller grids, I hard coded the logic, eg: 1xn grids, you just populate in 1 dimension

    // Now we know that the # clear nodes required will be 3n+2 or 3n+4
    // eg: if a 4x4 grid need 8 clear nodes : 3(2) + 2

    For (1 -> num 3's needed)
        Add 3 nodes going horizontally
        When horizontal axis is filled, add 3 nodes going vertically
           When vertical axis is filled, go back to horizontal then vertical and so on.

    for(1 -> num 2's needed)
        Add 2 nodes going horizontally or continuing in the direction from above
        When horizontal axis is filled, add 2 nodes going vertically

For example, say we have an 4x4 grid needing 8 clean nodes, here are the steps:

// Initial grid of all mines
* * * *
* * * *
* * * *
* * * *

// Populating 3's horizontally
. * * *
. * * *
. * * *
* * * *     

. . * *
. . * *
. . * *
* * * *    

// Populating 2's continuing in the same direction as 3's
. . . *
. . . *
. . * *
* * * *        

Another Example: 4x4 grid with 11 clear nodes needed; output:

. . . .
. . . .
. . . *
* * * * 

Another Example: 4x4 grid with 14 clear nodes needed; output:

// Insert the 4 3's horizontally, then switch to vertical to insert the 2's
. . . .
. . . .
. . . .
. . * *  

Now here we have a grid that is fully populated and can be solved in one click if we click on (0, 0).

My solution works for most cases, but it didn't pass the submission (I did check an entire 225 cases output file), so I'm guessing it has some problems, and I'm pretty sure there are better solutions.

Answer 1

Algorithm

Let's first define N, the number of non-mine cells:

N = R * C - M

A simple solution is to fill an area of N non-mine cells line-by-line from top to bottom. Example for R=5, C=5, M=12:

c....
.....
...**
*****
*****

That is:

• Always start in the top-left corner.
• Fill N / C rows with non-mines from top to bottom.
• Fill the next line with N % C non-mines from left to right.
• Fill the rest with mines.

There are only a few special cases you have to care about.

Single non-mine

If N=1, any configuration is a correct solution.

Single row or single column

If R=1, simply fill in the N non-mines from left-to-right. If C=1, fill N rows with a (single) non-mine.

Too few non-mines

If N is even, it must be >= 4.

If N is odd, it must be >= 9. Also, R and C must be >= 3.

Otherwise there's no solution.

Can't fill first two rows

If N is even and you can't fill at least two rows with non-mines, then fill the first two rows with N / 2 non-mines.

If N is odd and you can't fill at least two rows with non-mines and a third row with 3 non-mines, then fill the first two rows with (N - 3) / 2 non-mines and the third row with 3 non-mines.

Single non-mine in the last row

If N % C = 1, move the final non-mine from the last full row to the next row.

Example for R=5, C=5, M=9:

c....
.....
....*
..***
*****

Summary

It is possible to write an algorithm that implements these rules and returns a description of the resulting mine field in O(1). Drawing the grid takes O(R*C), of course. I also wrote an implementation in Perl based on these ideas which was accepted by the Code Jam Judge.

Answer 2

This is my code. I solved taking different cases like if number of rows=1 or number of columns=1 or if number of mines=(r*c)-1 and few other cases.

The position on the layout to click is placed at a[r-1][c-1]('0' indexed) every time.

For this question I had given few wrong attempts and every time I kept finding a new case. I eliminated few cases in which solution is not possible using goto and let it jump to end where it prints out impossible. A very simple solution(Indeed can be said a brute force solution since I coded for different cases possible individually). This is an editorial for my code. And on github.

Answer 3

There is a more general solution to this problem that passes both the small and large test cases. It avoids having to think of all the special cases, it doesn't care what the dimensions of the board are and doesn't require any back tracking.

ALGORITHM

The basic idea is start with a grid full of mines and remove them starting from cell {0, 0} until there are the correct number of mines on the board.

Obviously there needs to be some way to determine which mines to remove next and when it is impossible to remove the correct number of mines. To do this we can keep an int[][] that represents the board. Each cell with a mine contains -1 and those without mines contain an integer which is the number of mines adjacent to the cell; the same as in the actual game.

Also define the concept of a 'frontier' which is all non-mine cells that are non-zero i.e. those cells with mines adjacent.

For example the configuration:

c . *
. . *
. . *
* * *

Would be represented as:

 0  2 -1
 0  3 -1
 2  5 -1
-1 -1 -1

And the frontier would contain the cells with values: 2, 3, 5, 2

When removing the mines the strategy is:

• Find a cell in the frontier that has the same value as the remaining number of mines to remove. So in the example above if we had 5 more mines to remove, the cells with value 5 on the frontier would be chosen.
• Failing that chose the smallest frontier cell. So either of the 2's in the example above.
• If the value of the chosen cell is greater than the number of mines left to remove then it's impossible to build this board, so return false.
• Else remove all mines surrounding the chosen frontier cell.
• Repeat until the correct number of mines are present on the board - the constraints of the problem have been met.

In java this looks like:

// Tries to build a board based on the nMines in the test case
private static boolean buildBoard(TestCase t) throws Exception {
    if (t.nMines >= t.Board.rows() * t.Board.cols()) { 
        return false;
    }
    // Have to remove the cell at 0,0 as the click will go there
    t.Board.removeMine(0, 0);
    while (!t.boardComplete()) {
        Cell c = nextCell(t);
        // If the value of this cell is greater than what we need to remove we can't build a board
        if (t.Board.getCell(c.getRow(), c.getCol()) > t.removalsLeft()) {
            return false;
        }
        t.Board.removeNeighbourMines(c.getRow(), c.getCol());
    }

    return true;
}

// Find frontier cell matching removals left, else pick the smallest valued cell to keep things balanced
private static Cell nextCell(TestCase t) {
    Cell minCell = null;
    int minVal = Integer.MAX_VALUE;
    for (Cell c : t.Board.getFrontier()) {
        int cellVal = t.Board.getCell(c.getRow(), c.getCol());
        if (cellVal == t.removalsLeft()) {
            return c;
        }
        if (cellVal < minVal) {
            minVal = cellVal;
            minCell = c;
        }
    }
    if (minCell == null) {
        throw new NullPointerException("The min cell wasn't set");
    }
    return minCell;
}

PROOF / INTUITION

Firstly a board is defined as valid if it can be solved by a single click, even if there is only one cell on the board where this click can occur. Therefore for a board to be valid all non-mine cells must be adjacent to a cell with value 0, if this is not the case the cell is defined as unreachable. This is because we know with certainty that all cells adjacent to a 0 cell are non mines, so they can be safely revealed and the game will do it automatically for the player.

A key point to prove for this algorithm is that it is always necessary to remove all the mines surrounding the smallest frontier cell in order to keep the board in a valid state. This is quite easy to prove just by drawing out a board (such as the one above) and picking the lowest value cell (in this case the top right 2). If only a single mine is removed then the board would not be valid, it would be in either of these two states:

 0  1  1
 0  2 -1
 2  5 -1
-1 -1 -1

or

 0  1 -1
 0  2  2
 2  5 -1
-1 -1 -1

which both have unreachable cells.

So it is now true that always choosing the smallest frontier cell will keep the board in a valid state and my first instinct was that continuing to choose these cells would go through all valid states, however this is not correct. This can be illustrated by a test case such as 4 4 7 (so there are 9 non-mine cells). Then consider the following board:

 0  2 -1 -1
 2  5 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

Continuing to chose the smallest frontier cell may result in the algorithm doing the following:

 0  2 -1 -1
 0  3 -1 -1
 0  3 -1 -1
 0  2 -1 -1

Which means it is now impossible to remove just a single mine to complete the board for this case. However choosing a frontier cell that matches the number of remaining mines (if one exists) ensures that the 5 would have been chosen resulting in a 3x3 square of non-mines and a correct solution to the test case.

At this point I decided to give the algorithm a try on all test cases in the following range:

0 < R < 20
0 < C < 20
0 ≤ M < R * C

and found that it managed to correctly identify all the impossible configurations and build what looked like sensible solutions to the possible configurations.

Further intuition behind why choosing the frontier cell with the same value as the remaining number of mines (should it exist) is correct is that it allows the algorithm to find configurations for solutions requiring an odd number of non-mines.

When originally implementing this algorithm I was intending on writing heuristics that built the non-mine area in a square arrangement. Considering the 4 4 7 test case again it would end-up doing this:

 0  0  2 -1
 0  1  4 -1
 2  4 -1 -1
-1 -1 -1 -1

notice how we now have a 1 on the frontier which would ensure the final cell removed completed the square to give:

c . . *
. . . *
. . . *
* * * *

This would mean the heuristics change slightly to:

• Pick the smallest frontier cell
• In the case of a tie, pick the first cell added to the frontier list

This could be implemented by keeping a FIFO queue of frontier cells, but I quickly realised that it is trickier than it first seems. This is due to the fact that the values of the frontier cells are interdependent and so care needs to be taken to keep the collection of frontier cells in the correct state and also not to use the cells value in any kind of hash value etc. I'm sure this could be done, but upon realising that just adding the extra heuristic to pick any cells with values equal to the remaining removals worked, this seemed liked the easier approach.

Answer 4

I used search with backtracking, but I could solve only the small input.

Basically the algorithm starts with the board full of mines and tries to remove the mines in a way that the first "click" would solve the board. The catch is that to allow a "click" to expand to another cell, the expansion will come from another cell that must have all other neighbor cells cleared too. Sometimes, to expand to another cell you would need to remove other mines and end up with less mines than required. The algorithm will backtrack if it reaches such a position.

Maybe it is simpler to do the opposite. Start with an empty board and add each mine in a way that would not prevent the "expansion" of the initial click.

The full Python code is below:

directions = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1,  -1],  [1, 0],  [1, 1],
]

def solve(R, C, M):
    def neighbors(i, j):
        for di, dj in directions:
            if 0 <= (i + di) < R and 0 <= (j + dj) < C:
                yield (i + di, j + dj)

    def neighbors_to_clear(i, j, board):
        return [(ni, nj) for ni, nj in neighbors(i, j) if board[ni][nj] == "*"]

    def clear_board(order):
        to_clear = R * C - M - 1
        board = [["*" for _ in range(C)] for _ in range(R)]
        for i, j in order:
            board[i][j] = "."
            for ni, nj in neighbors_to_clear(i, j, board):
                to_clear -= 1
                board[ni][nj] = "."
        return board, to_clear

    def search(ci, cj):
        nodes = []
        board = []
        to_clear = 1
        nodes.append((ci, cj, []))
        while nodes and to_clear > 0:
            i, j, order = nodes.pop()
            board, to_clear = clear_board(order)
            neworder = order + [(i, j)]
            if to_clear == 0:
                board[ci][cj] = "c"
                return board
            elif to_clear > 0:
                for ni, nj in neighbors_to_clear(i, j, board):
                    board[ni][nj] = "."
                    nodes.append([ni, nj, neworder])

    for i in range(R):
        for j in range(C):
            board = search(i, j)
            if board:
                for row in board:
                    print "".join(row)
                return

    print "Impossible"
    return

T = int(raw_input())
for i in range(1, T + 1):
    R, C, M = map(int, raw_input().split(" "))
    print("Case #%d:" % i)
    solve(R, C, M)

Answer 5

my strategy was very similar to yours and I passed both small and large. Did you think about cases below?

• R * C - M = 1

• There is only one row

• There are only two rows

---

I flipped R and C when R > C.

Answer 6

I separated this into two initial special cases, then had a general algorithm. The tl;dr version is to build a square of blank spaces from the top left. Similar to other answers, but with fewer special cases.

Special cases

Case 1

Only 1 blank space. Just click in the top left corner and finish.

Case 2

2 or 3 blank spaces, with a grid that is not either Rx1 or 1xC. This is impossible, so we fail early.

Algorithm

Always click in the top left corner. Start with a 2x2 blank square in the top left (we have at least 4 blanks). Now we need to add the remaining blanks. We then expand the square along one edge then the other, until we have no more blank spaces.

Example of blanking order:

C  2  6 12
1  3  7 13
4  5  8 14
9 10 11 15

Impossible case

Note that when beginning a new edge, we must place at least two blank spaces for this to be valid. So if we have only one blank to place, then this must be invalid (unless our edge has length one). My logic looked like this:

if maxEdgeLength > 1 and remainingBlanks == 1:
    print('Impossible')
    return

However, we could have left off the end of the last edge, which would give us two blanks now. Of course we can only leave off the last blank if the last edge was more than 2 blanks long!

My logic for this special case looked like this:

if remainingBlanks == 1 and lastEdgeSize > 2:
    mineMatrix[lastBlank] = '*'
    blanks += 1