Design Minesweeper

01The design, in the six-step framework

1. Requirements and use cases

This one comes from Google's own Tech Dev Guide: design a play method given a matrix, with attention to placing mines without duplicates, the state of a cell, and the recursive reveal. Those three topics are the outline of the answer.

• A game is created with a height, a width and a mine count, with mines at distinct cells.
• A player reveals a cell: a mine loses; a number shows the mines around it; a zero opens the whole connected empty region and its numbered border.
• A player flags or unflags a hidden cell; a flagged cell cannot be revealed by accident.
• The game is won when every non-mine cell is revealed. Flags are not required.
• The first reveal is safe: mines are placed after it, avoiding that cell.
• A caller can read what the player may see, with mines hidden until the end.

Out of scope: timers, high scores, guess-free board generation. Constraints: mine placement is O(cells) with no retry loop, so a dense board cannot stall; the flood fill must not overflow the call stack on a large board (a 1000×1000 empty board is a million frames of recursion); generation takes a seeded random source so tests are exact.

2. Core entities and relationships

• CellState: hidden, flagged, or revealed; the small state machine each cell moves through.
• MineField: the immutable truth: mine locations and adjacency counts.
• MinePlacer: an interface that builds a mine set; the random version avoids a safe cell, and a fixed version serves tests.
• Game: the player's view (per-cell state) plus the status; it owns reveal and flag.

The game composes its mine field, created on the first reveal. The placer is aggregated and injected. Keeping the truth (MineField) apart from what the player has seen (states) is what makes it impossible for a view to leak a mine.

3. Interfaces and key methods

import random
from enum import Enum
from typing import Iterator, Protocol, Set, Tuple

Cell = Tuple[int, int]

class CellState(Enum):
    HIDDEN = "#"
    FLAGGED = "F"
    REVEALED = "."

class Status(Enum):
    READY = "ready"        # no mines placed yet
    PLAYING = "playing"
    WON = "won"
    LOST = "lost"

class MinePlacer(Protocol):
    def place(self, height: int, width: int, count: int, safe: Cell) -> Set[Cell]:
        """Exactly `count` distinct cells, excluding `safe`."""

class MineField:
    def is_mine(self, cell: Cell) -> bool: ...
    def count(self, cell: Cell) -> int:
        """Mines among the up to eight neighbours."""
    def neighbours(self, cell: Cell) -> Iterator[Cell]: ...

class Game:
    def reveal(self, row: int, col: int) -> Status:
        """Open a hidden cell; a zero opens its whole region; flagged cells are ignored."""
    def toggle_flag(self, row: int, col: int) -> None:
        """Hidden to flagged and back; revealed cells are ignored."""
    def view(self) -> list:
        """Rows of what the player may see; mines appear only after a loss."""

Invariants: mines are distinct and never include the first revealed cell; safe_left equals the non-mine cells not yet revealed, so a win is exactly safe_left == 0; a revealed cell never goes back to hidden; after the game ends, no state changes.

4. Design patterns and the choices behind them

Distinct mines by sampling, not retrying

The force: "pick a random cell, retry if taken" has no bound, and it slows badly as the board fills. random.sample draws distinct items directly, in the manner of a partial Fisher-Yates shuffle, in O(count) picks over a list of candidates. Every placement of that size is equally likely, and the safe cell is simply left out of the candidates. Be ready to write the shuffle by hand if asked: for i from 0 to count, swap position i with a random position at or after i.

An explicit stack rather than recursion

The force: the guide calls it a recursive reveal, and recursion reads nicely, but one empty region can be the whole board. An explicit stack does the same flood fill, in O(cells) time, and cannot overflow. Mark a cell revealed when it is pushed, not when it is popped, so no cell enters the stack twice. Only zero cells expand, so the numbered border is opened and stops the spread. This is the flood fill from modeling boards and grids.

Cell state as a small machine

A cell moves hidden to flagged and back, and hidden to revealed, and never leaves revealed. Three values in an enum with those transitions enforced in reveal and toggle_flag is the state idea at its smallest; a class per state would be absurd here. The game's own status has the extra READY value, because mines do not exist until the first reveal.

Sparse, shared cell data

Storing a full Cell object per square wastes memory on a big board, since nearly every cell starts identical. The states dictionary stores only cells that differ from hidden, and enum members are single shared objects. That is the flyweight instinct: share what is identical, and store only what varies. Adjacency counts are computed on demand from the mine set, in at most eight lookups each. The return values keep the method design simple: an illegal or pointless reveal is ignored, not an error, because a player clicking a revealed cell is normal. A scripted placer gives the exact boards unit tests need.

5. Core flow and code

1. reveal bounds-checks and returns if the game is over or the cell is flagged or revealed.
2. On the first call it asks MinePlacer.place with the cell as safe and builds the MineField.
3. A mine sets the status to lost.
4. Otherwise the flood fill runs from the cell: reveal, and if the count is zero, push hidden neighbours.
5. Each revealed safe cell decrements safe_left; at zero the game is won.

class RandomPlacer:
    def __init__(self, rng: random.Random) -> None:
        self.rng = rng
    def place(self, height: int, width: int, count: int, safe: Cell) -> Set[Cell]:
        candidates = [(r, c) for r in range(height) for c in range(width) if (r, c) != safe]
        return set(self.rng.sample(candidates, count))

class FixedPlacer:
    def __init__(self, mines: set) -> None:
        self.mines = set(mines)
    def place(self, height: int, width: int, count: int, safe: Cell) -> Set[Cell]:
        return set(self.mines)

class MineField:
    def __init__(self, height: int, width: int, mines: set) -> None:
        self.height, self.width = height, width
        self.mines = frozenset(mines)

    def is_mine(self, cell: Cell) -> bool:
        return cell in self.mines

    def neighbours(self, cell: Cell) -> Iterator[Cell]:
        r, c = cell
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if (dr or dc) and 0 <= nr < self.height and 0 <= nc < self.width:
                    yield (nr, nc)

    def count(self, cell: Cell) -> int:
        return sum(1 for n in self.neighbours(cell) if n in self.mines)

class Game:
    def __init__(self, height: int, width: int, mine_count: int, placer: MinePlacer) -> None:
        if not 0 < mine_count < height * width:
            raise ValueError("need at least one mine and one safe cell")
        self.height, self.width, self.mine_count = height, width, mine_count
        self.placer = placer
        self.field = None
        self.states: dict = {}                 # absent means HIDDEN
        self.safe_left = height * width - mine_count
        self.status = Status.READY

    def _state(self, cell: Cell) -> CellState:
        return self.states.get(cell, CellState.HIDDEN)

    def _start(self, cell: Cell) -> None:
        mines = self.placer.place(self.height, self.width, self.mine_count, cell)
        self.field = MineField(self.height, self.width, mines)
        self.status = Status.PLAYING

    def reveal(self, row: int, col: int) -> Status:
        cell = (row, col)
        if not (0 <= row < self.height and 0 <= col < self.width):
            raise ValueError("off the board")
        if self.status in (Status.WON, Status.LOST) or self._state(cell) is not CellState.HIDDEN:
            return self.status
        if self.field is None:
            self._start(cell)
        if self.field.is_mine(cell):
            self.status = Status.LOST
            return self.status
        self._open(cell)
        return self.status

    def _open(self, start: Cell) -> None:
        self.states[start] = CellState.REVEALED
        self.safe_left -= 1
        stack = [start]
        while stack:
            cell = stack.pop()
            if self.field.count(cell):
                continue                      # numbered cells stop the spread
            for n in self.field.neighbours(cell):
                if self._state(n) is CellState.HIDDEN:
                    self.states[n] = CellState.REVEALED
                    self.safe_left -= 1
                    stack.append(n)
        if self.safe_left == 0:
            self.status = Status.WON

    def toggle_flag(self, row: int, col: int) -> None:
        cell = (row, col)
        if self.status in (Status.WON, Status.LOST):
            return
        state = self._state(cell)
        if state is CellState.HIDDEN:
            self.states[cell] = CellState.FLAGGED
        elif state is CellState.FLAGGED:
            del self.states[cell]

    def view(self) -> list:
        rows = []
        for r in range(self.height):
            out = ""
            for c in range(self.width):
                cell, state = (r, c), self._state((r, c))
                if self.status is Status.LOST and self.field.is_mine(cell):
                    out += "*"
                elif state is CellState.REVEALED:
                    n = self.field.count(cell)
                    out += str(n) if n else "."
                else:
                    out += state.value
            rows.append(out)
        return rows

if __name__ == "__main__":
    g = Game(3, 3, 1, FixedPlacer({(2, 2)}))
    assert g.reveal(0, 0) is Status.WON            # the flood fill opens every safe cell
    assert g.view() == ["...", ".11", ".1#"]
    g2 = Game(2, 2, 1, FixedPlacer({(1, 1)}))
    assert g2.reveal(0, 0) is Status.PLAYING       # a numbered cell does not spread
    assert g2.reveal(1, 1) is Status.LOST
    assert g2.view() == ["1#", "#*"]

6. Extensions, concurrency and what interviewers probe

• "How do you place mines without duplicates?" Sampling or a partial shuffle. Explain why rejection sampling degrades: with 90 percent mines, the last picks need about ten tries each.
• "Why not recursion?" Depth equals the size of the empty region, which can be every cell. Mention the recursive version first if it reads better, then say why you changed it.
• "Chord click" (reveal the neighbours of a satisfied number). A method that checks flags around a cell and calls reveal on the rest; the state machine is untouched.
• "First reveal should open a region." Also exclude the neighbours of the first cell; the placer takes a set of safe cells instead of one.
• Concurrency: a shared board needs a lock around reveal, because safe_left and states must change together. MineField is immutable and needs none.
• Common mistake: revealing a cell when it is popped rather than pushed, so it is counted twice and safe_left goes wrong; and letting the flood fill open flagged cells, which it must skip.

02Where this question was reported

• peterchen.xyz · From Google Tech Dev Guide: design play(); mine placement without duplicates, cell state, recursive reveal