GCJ – Minesweeper Master

Minesweeper Master, Qualification Round 2014

There are a couple of key insights necessary to solve this problem. We know how many mines there will be and the size of the board, and we want to find some board state that would clear all the empty squares at once. It doesn’t have to be a likely state, it just has to be a valid state given the board size and mine count. So we can rearrange the board at will to find a state that will work.

The first insight is that for the board to clear in one click, all the empty spaces must be contiguous. Because a square can’t cascade to a square it’s not next to, we have to bunch all the empty squares together in one region.

The second insight is that this empty region should be up against the corner. Suppose we have a 2 by 2 clear area in a 4 by 4 region with mines surrounding it. If the empty region is in the middle or on the side, like this,

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

then all of the empty squares are next to a mine and they won’t cascade. If the empty region is in the corner,

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

then the corner square is next to the edge of the board rather than mines and will cascade, and we can win in a single click. So not only should our empty region be in the corner, but the clicked square should always be the corner square. Other squares might be able to cascade, but the corner one definitely will if others could.

With these insights, it’s now a matter of figuring out how to build our empty region and how to tell if it will cascade properly.

To build it, first note that if we can fill up a whole row or whole column of the board with mines, then we should do so. We’ll start up with the empty region filling the whole board, fill the shortest whole row or whole column available with mines, and repeat until we don’t have enough mines to keep going. At that point, we’ll have an empty rectangular region with the clicked square in the corner and some uneven number of mines to keep placing. If we have no mines, then we’ve finished our board and found a good position. We just need to check and make sure that the corner will cascade. If it won’t, then the board position doesn’t work with a single click and won’t be possible.

If we do still have mines to place, we’ll start placing them along the sides kitty corner to the clicked corner, like so:

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

But we’re limited in how many we can place, because the rest of those rows and columns have to be cleared as well. We have to leave at least two empty squares at the edge of both the row and the column. With only a single empty square, the empty square next to it won’t cascade and we won’t clear the singleton:

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

So the most we can place is the length of the empty space plus the width of the empty space minus five – two for the row, two for the column, and one for the overlap. If the number of mines to place is less than this, then we do so and report the board position. If not, then it’s impossible. That, along with some careful outlining of edge cases, will solve the problem.

def solve_case(case):
    R, C, M = case
    free = R * C - M
    
    def write_board(board):
        d = {0:'.', 1:'c', 2:'*'}
        return '\n' + '\n'.join([''.join([d[n] for n in r])for r in board]) + '\n'
    
    board = np.zeros((R, C), dtype=int)
    board[0,0] = 1
    
    while min(R, C) <= M:
        if R < C:
            board[:,C-1] = 2
            C -= 1
            M -= R
        elif C <= R:
            board[R-1,:] = 2
            R -= 1
            M -= C
    
    def cascades(board, r, c):
        rows = [i for i in (r-1, r, r+1) if (i >= 0 and i < board.shape[0])]
        cols = [i for i in (c-1, c, c+1) if (i >= 0 and i < board.shape[1])]
        for r in rows:
            for c in cols:
                if board[r,c] == 2:
                    return False
        return True
    
    if M == 0:
        if cascades(board, 0, 0) or free == 1:
            return write_board(board)
        else:
            return "\nImpossible"
    
    if M > (R + C - 5):
        return "\nImpossible"
        
    if R <= 2 or C <= 2:
        return "\nImpossible"
        
    fill_num = min(M, R - 2)
    board[(R - fill_num):,C-1] = 2
    M -= fill_num
    
    fill_num = min(M, C - 3)
    board[R-1,(C - fill_num - 1):] = 2
    M -= fill_num
    
    return write_board(board)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s