# Resource Library

Below you can find all of the different resources in the Guide: practice problems, former Google interview questions, online courses, videos, and more.

##### 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  0``0  0  0  0  0``1  1  1  0  0``1  9  1  0  0``1  2  2  1  0``0  1  9  1  0``0  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  0``0  0  0  0  0``1  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:

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.

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.

Copied
````import random``kMine = 9``class Matrix():``  def __init__(self, T):``    self.elem_type = T``  def resize(self, rows, cols):``    self.data = [self.elem_type() for _ in range(rows * cols)]``    self.rows, self.cols = rows, cols``  def at(self, row, col):``    return self.data[row * self.cols + col]``  def rows(self):``    return self.rows``  def cols(self):``    return self.cols``class MineField():``  class Spot():``    def __init__(self):``      self.value = 0``      self.visible = False``  def _spot(self):``    return self.Spot()``  def __init__(self, rows, cols, num_mines):``    self.matrix = Matrix(self._spot)``    self.matrix.resize(rows, cols)``    self.rows, self.cols = rows, cols``    if num_mines > rows * cols:``      print("Too many mines")``    mine_list = [i < num_mines for i in range(rows * cols)]``    random.shuffle(mine_list)``    print(mine_list)``    for index, is_mine in enumerate(mine_list):``      if not is_mine:``        continue``      row, col = index // cols, index % cols``      self.matrix.at(row, col).value = kMine``      for i in range(-1, 2):``        for j in range(-1, 2):``          if row + i < 0 or row + i >= rows or col + j < 0 or col + j >= cols:``            continue``          if self.matrix.at(row + i, col + j).value == kMine:``            continue``          self.matrix.at(row + i, col + j).value += 1``  def OnClick(self, row, col):``    if row < 0 or row >= self.rows or col < 0 or col >= self.cols:``      return False``    spot = self.matrix.at(row, col)``    if spot.visible:``      return False``    spot.visible = True``    if spot.value == kMine:````      print("Boom!!!!

")````      return True``    if spot.value != 0:``      return False``    self.OnClick(row - 1, col)``    self.OnClick(row, col - 1)``    self.OnClick(row + 1, col)``    self.OnClick(row, col + 1)``    return False``  def Print(self, show_hidden=False):``    for i in range(self.rows):``      for j in range(self.cols):``        ch = '.'``        if self.matrix.at(i, j).visible or show_hidden:``          ch = self.matrix.at(i, j).value``        print(ch, end=' ')``      print()``    print()``    print()``if __name__ == '__main__':``  mine_field = MineField(12, 10, 7);``  mine_field.Print(True);``  mine_field.OnClick(5, 2);``  mine_field.Print();``  mine_field.OnClick(2, 6);``  mine_field.Print();``  mine_field.OnClick(9, 3);``  mine_field.Print();``  mine_field.OnClick(0, 0);``  mine_field.Print();``  mine_field.OnClick(3, 5);``  mine_field.Print();`    ```
``#include <cstdlib>``#include <vector>``#include <iostream>``#include <utility>``template<typename T>``class Matrix {`` public:``  void resize(int rows, int cols) {``    data_.resize(rows * cols);``    rows_ = rows;``    cols_ = cols;``  }``  T& at(int row, int col) {``    return data_.at(row * cols_ + col);``  }``  int rows() const { return rows_; }``  int cols() const { return cols_; }`` private:``  std::vector<T> data_;``  int rows_ = 0;``  int cols_ = 0;``};``constexpr int kMine = 9;``using std::min;``using std::max;``class MineField {`` private:``  struct Spot {``    int value = 0;``    bool visible = false;``  };``  Matrix<Spot> field;`` public:``  MineField(int rows, int cols, int num_mines) {``    field.resize(rows, cols);``    const int sum = rows * cols;``    if (num_mines > sum) {``      std::cout << "Too many mines!" << std::endl;``      num_mines = sum;``    }``    // Fulfill all spot preparing random shuffle.``    for (int i = 0; i < sum; i++) {``      field.at(i / cols, i % cols).value = i < num_mines ? kMine : 0; ``    }``    // Random shuffle.``    for (int i = 0; i < min(num_mines, sum - 1); i++) {``      int j = i + (rand() % (sum - i));``      std::swap(field.at(i / cols, i % cols), field.at(j / cols, j % cols));``    }``    // Calculate value for each spot.``    for (int row = 0; row < rows; row++) {``      for (int col = 0; col < cols; col++) {``        if (field.at(row, col).value != kMine) {``          continue;``        }``        for (int i = max(0, row - 1); i <= min(rows - 1, row + 1); i++) {``          for (int j = max(0, col - 1); j <= min(cols - 1, col + 1); j++) {``            if ((i != row || j != col) && field.at(i, j).value != kMine) {``              field.at(i, j).value++;``            }``          }``        }``      }``    }``  }``  bool OnClick(int row, int col) {``    if (row < 0 || row >= field.rows() || col < 0 || col >= field.cols()) {``      return false;``    }``    if (field.at(row, col).visible) { return false; }``    field.at(row, col).visible = true;``    if (field.at(row, col).value == kMine) { ``      std::cout << "BOOM!" << std::endl << std::endl;``      return true; ``    }``    if (field.at(row, col).value != 0) { return false; }``    OnClick(row - 1, col);``    OnClick(row + 1, col);``    OnClick(row, col - 1);``    OnClick(row, col + 1);``    return false;``  }``  void Print(bool show_hidden) {``    for (int i = 0; i < field.rows(); ++i) {``      for (int j = 0; j < field.cols(); ++j) {``        if (field.at(i, j).visible || show_hidden) {``          std::cout << field.at(i, j).value << " ";``        } else {``          std::cout << ". ";``        }``      }``      std::cout << std::endl;``    }``    std::cout << std::endl;``  }``};``int main() {``  srand(1);``  MineField mine_field(8, 11, 7);``  mine_field.Print(true);``  mine_field.OnClick(5, 1);``  mine_field.Print(false);``  mine_field.OnClick(2, 6);``  mine_field.Print(false);``  mine_field.OnClick(9, 3);``  mine_field.Print(false);``  mine_field.OnClick(0, 0);``  mine_field.Print(false);``  mine_field.OnClick(3, 5);``  mine_field.Print(false);``  return 0;``}`    `