Foundations Path

Reach beyond the basics of coding with these carefully curated resources for newer programmers who have already completed 1-2 computing courses. You’re at an exciting point and we want to support you however and wherever you’re learning!

View all sequences

Practice testing and debugging first

Put your problem-solving skills (and everything you know about algorithms, data structures, and dynamic programming) to the test as you work to create your own version of the game Minesweeper for this former Google interview question.

Take the challenge

Google

The Challenge

Implement Minesweeper

Minesweeper is a game where the objective is correctly identify the location of all mines in a given grid. You are given a uniform grid of gray squares in the beginning of the game. Each square contains either a mine (indicated by a value of 9), or an empty square. Empty squares have a number indicating the count of mines in the adjacent squares. Empty squares can have counts from zero (no adjacent mines) up to 8 (all adjacent squares are mines).

If you were to take a complete grid, for example, you can see which squares have mines and which squares are empty:

Copied
0  0  0  0  00  0  0  0  01  1  1  0  01  9  1  0  01  2  2  1  00  1  9  1  00  1  1  1  0

The squares with "2" indicate that there 2 mines adjacent to that particular square.

Gameplay starts with a user un-hiding a square at random. If the square contains a mine, the game ends. If it is a blank, the number of adjacent mines is revealed.

Exposing a zero means that there are no adjacent mines, so exposing all adjacent squares is guaranteed safe. As a convenience to the player, the game continues to expose adjacent squares until a non-zero square is reached.

For example, if you click on the top right corner you get this ('-' means hidden):

Copied
0  0  0  0  00  0  0  0  01  1  1  0  0-  -  1  0  0-  -  2  1  0-  -  -  1  0-  -  -  1  0

Please write functions to construct the playing field given the size and number of mines.

Note: You can suppose that you have a Matrix class that looks like this:

C++ Copied
template<typename T> class Matrix {   void resize(int rows, int cols);   T& at(int row, int col);   int rows();   int cols(); }; 

Or, if your language supports an idiomatic way to express matrices, you may use that instead. The goal is to expose safe squares correctly, not demonstrate facility with matrix classes or arrays.

Learning objectives

This question gives you the chance to practice using Java to design and use a simple class, implement an appropriate search algorithm, and use if-then. It also touches on leveraging work that’s already done.

Solution explained, commentary

The most effective solutions consider and include the following:

Simple class

This question definitely points towards designing a simple class.

Create an array with the specified number of mines at the beginning and use a random shuffle.

If mines occupy more than half of the cells, randomize empty cells instead of mines.

If for NxN you need M mines then:

1) if M < NxN/2 then randomly pick spots and if empty place mines. At worst, the chance of picking a mine rather than empty cell is 50% so we need 2M tries.

2) if M > NxN/2 try step 1 assuming that all cells are mined and we are trying to free up (NxN - M) spots. So in the extreme example above, it takes almost one try

What is the right way to report a problem if the requested number of mines is larger than the number of available squares?

Some other important learnings from this question:

There are various ways to solve it. For the initialization, you might choose to place mines and increment neighbors in one loop, or place mines and then iterate over all fields and count the mines in the neighborhood.

A common error is to struggle to see the structure of the problem and make gigantic if clauses when looking at neighboring fields, instead of writing a simple for loop.

An important part of this question is figuring out a way to place the mines. The most naive implementation is to pick two random numbers (row and column) and place a mine there, but this will cause the board to have less mines than expected if the same coordinates are picked twice. Re-trying if the picked coordinates already have a mine fixes the immediate problem, but will take a very long time for cases such as a 100x100 board with 9999 mines.

Code snippet for solution

Here's one solution posted on GitHub:

https://gist.github.com/dgossow/d28083522608771e1c65f49822820ba9

A further solution:

Another clever and simple solution, here expressed in Python. The idea is to adjust the probability of placing the mine as we iterate over the table.

Python Copied
remaining_mines = M remaining_cells = N for i in range(0, N):   chance = float(remaining_mines) / remaining_cels   if random.uniform(0., 1.) < chance:     place_mine(i)     remaining_mines -= 1   remaining_cells -= 1