Minesweeper LLD: Two Grids, One Flood, and a Merciful First Click

"Design Minesweeper." Everyone remembers the game — the cautious right-clicks, the glorious moment a single click rips open half the board. Few candidates notice that this question is really three questions stacked: a data-modelling question (what even is the board?), an algorithm question (that glorious cascade is a flood fill), and a sneaky product question (why does the first click never, ever lose?).

We'll answer all three, in that order, and walk out with the complete game — the one LLD where the most satisfying feature of your childhood turns out to be twelve lines of queue discipline.

Let's start nowhere near a computer

Picture a referee running the game on paper. She has two sheets. Sheet one, drawn before the game and never touched again: where every mine sits, and — precomputable from that — how many mines touch each square. Sheet two, updated constantly: which squares the player has opened, which they've flagged, and nothing else.

The player only ever sees sheet two. The referee only ever consults sheet one. Neither sheet ever changes the other's job.

That's the entire data model, and muddling it is the classic rookie failure: one grid with magic values like -1 for mine, -2 for flagged-mine, 9 for revealed… and every method becomes an archaeology dig. Truth and view are different facts with different lifetimes — give them different homes.

Where the two-sheet trick keeps showing up

• Every game with hidden information — Battleship, poker engines, fog-of-war — is a truth grid plus per-player view grids.
• It's the paywall on this very site: the full article (truth) and what an anonymous visitor receives (view) are computed separately on purpose.
• The flood fill is the same algorithm behind the paint-bucket tool, island-counting interview questions, and maze solvers — Minesweeper is the friendliest place to learn it.

Step 1 — Functional requirements (sentences first)

What the game must do, as plain sentences — the functional requirements.

• The board has R×C cells; M of them hide mines.
• Each safe cell knows how many of its eight neighbours are mines.
• Revealing a mine loses the game; revealing a zero also reveals its neighbours, cascading.
• A player can flag a hidden cell; flagged cells can't be revealed (or cascaded into).
• The game is won when every safe cell is revealed — flags are decoration.
• The first reveal is never a mine.

That second-to-last sentence trips people: you win by clearing, not by flagging. And the last one is a product rule with a delightful implementation, saved for the end.

Step 2 — Non-functional requirements

This is a single-process puzzle — no servers, no clock, no concurrency. So the non-functional requirements are about being right and fast on a big board, not about staying up under load:

• Correctness. Adjacency counts are exact; revealing a zero flood-fills its zero-region and the numbered border, stopping there; clicking a mine ends the game; you win the instant every non-mine cell is revealed — and not a click sooner.
• Performance. A reveal costs O(cells it actually touches), via flood fill — each cell visited once. No rescanning the whole board on every click.
• Extensibility. Board dimensions, mine count, and the first-click-safe rule are all parameters and seams, not constants baked into the logic.
• Testability. A seeded mine placement (the RNG is injected) makes any board reproducible, so a reveal is deterministic given the layout — which is the only reason the cascade is verifiable at all.

Listing them is the easy half; the design only earns them if it fulfills them. Here's the contract — each requirement and the mechanism that keeps it:

Every trade-off below is chosen to keep one of these.

Step 3 — Nouns → the two sheets

The referee's sheets, verbatim:

private final boolean[][] mine;       // sheet one: the truth…
private final int[][] adjacent;       // …precomputed once, frozen
private final View[][] view;          // sheet two: HIDDEN, REVEALED or FLAGGED
private int revealed;                 // the win counter
private Status status;                // PLAYING → WON / LOST

No Cell class (Tic-Tac-Toe's lesson holds), no magic numbers — View is an enum, and adjacent is computed once at placement, never per move. Counting neighbours on every render is the quiet performance bug interviewers fish for.

Which structure — and why. Two parallel grids, not one — and that split is the load-bearing choice, not a default. Separate mine/adjacent (truth) from view (what the player has touched) and you get correctness for free: the cascade reads truth and writes view, so neither field can corrupt the other. The adjacent grid is precomputed and frozen because that's performance — counts that change once at placement must never be recounted per click. And revealed is a plain int counter rather than a derived scan: win-detection becomes one comparison (revealed == safe cells) instead of an O(board) sweep, which keeps both correctness and performance honest. Each grid is the cheapest structure that earns one NFR.

Step 4 — The flood, with discipline

Click a 0 and the board unzips. The rule generating that magic is one sentence: a revealed zero recruits all its hidden neighbours; a revealed number just sits there. Numbers get revealed by the cascade — they're its walls, not its members.

The naive implementation recurses: reveal calls reveal on eight neighbours. It works — until a big board's empty region blows the call stack, which is precisely the follow-up your interviewer is holding. So flood like an adult, with an explicit queue:

private void floodReveal(int startRow, int startCol) {
    ArrayDeque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[] {startRow, startCol});
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1];
        if (view[r][c] == View.REVEALED) continue;   // the visited check — no infinite loops
        view[r][c] = View.REVEALED;
        revealed++;
        if (adjacent[r][c] == 0) {                   // only zeros recruit
            for (int dr = -1; dr <= 1; dr++)
                for (int dc = -1; dc <= 1; dc++) {
                    int nr = r + dr, nc = c + dc;
                    if (inBounds(nr, nc) && view[nr][nc] == View.HIDDEN) {
                        queue.add(new int[] {nr, nc});
                    }
                }
        }
    }
}

Two highlighted lines carry the whole algorithm: the visited check (a cell may be enqueued by several neighbours — process it once), and the recruitment rule (zeros expand, numbers don't). Notice flagged cells never enter the queue — the HIDDEN filter quietly honours the player's flags, exactly like the real game.

Step 5 — Win, lose, and the state machine

Losing is easy: reveal a mine, game over. Winning is the subtle one — it has nothing to do with flags:

public Status reveal(int row, int col) {
    if (status != Status.PLAYING) throw new IllegalStateException("game over: " + status);
    if (view[row][col] != View.HIDDEN) return status;     // flags & re-clicks: no-ops
    if (!minesPlaced) placeMines(row, col);                // ← the mercy rule, next section
    if (mine[row][col]) {
        view[row][col] = View.REVEALED;
        status = Status.LOST;
        return status;
    }
    floodReveal(row, col);
    if (revealed == rows * cols - mineCount) {
        status = Status.WON;                               // every SAFE cell open — flags irrelevant
    }
    return status;
}

One counter, one comparison. Tracking "are all mines flagged" instead is both wrong (you can win without placing a single flag) and racier to maintain — the revealed counter is the design.

Step 6 — The merciful first click

Here's the product secret: in real Minesweeper, the mines aren't placed until you click. The board you're staring at doesn't exist yet. Your first reveal happens, then mines are scattered — everywhere except the cell you clicked and its neighbours — and only then does the game proceed, guaranteeing your opening click lands on a satisfying cascade instead of a bomb.

private void placeMines(int safeRow, int safeCol) {
    int placed = 0;
    while (placed < mineCount) {
        int index = random.nextInt(rows * cols);           // injected — tests script this
        int r = index / cols, c = index % cols;
        boolean nearFirstClick = Math.abs(r - safeRow) <= 1 && Math.abs(c - safeCol) <= 1;
        if (mine[r][c] || nearFirstClick) continue;
        mine[r][c] = true;
        placed++;
    }
    computeAdjacency();
    minesPlaced = true;
}

And there's our old friend: random arrives through the constructor, third article running. In tests, a scripted random places mines exactly where the test wants them — which is the only reason the flood fill above is verifiable at all.

Step 7 — Trade-offs (each one keeping an NFR)

The last column is the discipline: every choice keeps one of the promises from Step 2 — that's what designing to the non-functional requirements looks like.

Growth — when the board gets large. The first knob is just the constructor: bigger rows/cols, more mines. Past that, the structures bend rather than break — a million-cell board swaps the boolean[][] for a bitset to shrink memory, while the iterative flood already kept the stack safe and placement stays O(mines). Nothing about the shape of the design changes; you make the contended thing (memory per cell) smaller, not the algorithm cleverer.

The complete implementation

package dev.fiveyear.minesweeper;
 
import java.util.ArrayDeque;
import java.util.Random;
 
public final class Minesweeper {
 
    public enum Status { PLAYING, WON, LOST }
 
    public enum View { HIDDEN, REVEALED, FLAGGED }
 
    private final int rows;
    private final int cols;
    private final int mineCount;
    private final Random random;
    private final boolean[][] mine;
    private final int[][] adjacent;
    private final View[][] view;
    private boolean minesPlaced;
    private int revealed;
    private Status status = Status.PLAYING;
 
    public Minesweeper(int rows, int cols, int mineCount, Random random) {
        if (rows < 2 || cols < 2) {
            throw new IllegalArgumentException("board too small");
        }
        if (mineCount < 1 || mineCount >= rows * cols - 9) {
            throw new IllegalArgumentException("mine count must leave room for a safe first click");
        }
        this.rows = rows;
        this.cols = cols;
        this.mineCount = mineCount;
        this.random = random;
        this.mine = new boolean[rows][cols];
        this.adjacent = new int[rows][cols];
        this.view = new View[rows][cols];
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                view[r][c] = View.HIDDEN;
    }
 
    /** Reveals a cell; flags and already-open cells are safe no-ops. */
    public Status reveal(int row, int col) {
        if (status != Status.PLAYING) {
            throw new IllegalStateException("game over: " + status);
        }
        requireOnBoard(row, col);
        if (view[row][col] != View.HIDDEN) {
            return status;
        }
        if (!minesPlaced) {
            placeMines(row, col);
        }
        if (mine[row][col]) {
            view[row][col] = View.REVEALED;
            status = Status.LOST;
            return status;
        }
        floodReveal(row, col);
        if (revealed == rows * cols - mineCount) {
            status = Status.WON;
        }
        return status;
    }
 
    public void toggleFlag(int row, int col) {
        if (status != Status.PLAYING) {
            throw new IllegalStateException("game over: " + status);
        }
        requireOnBoard(row, col);
        if (view[row][col] == View.HIDDEN) {
            view[row][col] = View.FLAGGED;
        } else if (view[row][col] == View.FLAGGED) {
            view[row][col] = View.HIDDEN;
        }
    }
 
    private void floodReveal(int startRow, int startCol) {
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] {startRow, startCol});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];
            if (view[r][c] == View.REVEALED) {
                continue;
            }
            view[r][c] = View.REVEALED;
            revealed++;
            if (adjacent[r][c] == 0) {
                for (int dr = -1; dr <= 1; dr++)
                    for (int dc = -1; dc <= 1; dc++) {
                        int nr = r + dr, nc = c + dc;
                        if (inBounds(nr, nc) && view[nr][nc] == View.HIDDEN) {
                            queue.add(new int[] {nr, nc});
                        }
                    }
            }
        }
    }
 
    private void placeMines(int safeRow, int safeCol) {
        int placed = 0;
        while (placed < mineCount) {
            int index = random.nextInt(rows * cols);
            int r = index / cols, c = index % cols;
            boolean nearFirstClick = Math.abs(r - safeRow) <= 1 && Math.abs(c - safeCol) <= 1;
            if (mine[r][c] || nearFirstClick) {
                continue;
            }
            mine[r][c] = true;
            placed++;
        }
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) {
                int count = 0;
                for (int dr = -1; dr <= 1; dr++)
                    for (int dc = -1; dc <= 1; dc++) {
                        if (inBounds(r + dr, c + dc) && mine[r + dr][c + dc]) count++;
                    }
                adjacent[r][c] = mine[r][c] ? -1 : count;
            }
        minesPlaced = true;
    }
 
    private boolean inBounds(int r, int c) {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }
 
    private void requireOnBoard(int r, int c) {
        if (!inBounds(r, c)) {
            throw new IllegalArgumentException("off the board: (" + r + ", " + c + ")");
        }
    }
 
    public Status status() {
        return status;
    }
 
    public View viewAt(int row, int col) {
        return view[row][col];
    }
 
    public int adjacentAt(int row, int col) {
        return adjacent[row][col];
    }
}

And the cascade you remember, on the referee's sheets:

Minesweeper game = new Minesweeper(4, 4, 2, new Random());
 
game.reveal(3, 0);    // first click: mines materialize elsewhere — never here.
                      // a zero region unzips: zeros open zeros, numbers wall it off
game.toggleFlag(0, 1);
game.reveal(0, 1);    // no-op — flags block reveals AND the cascade
game.toggleFlag(0, 1);
 
// keep revealing safe cells… the moment the LAST safe cell opens:
// status() == WON — flags were never part of the win condition

The interview corner

Clarify before you code: Is first-click safety required (and how wide — the cell, or its neighbours too)? Are flags capped at the mine count? Largest board we must support?

The follow-up ladder:

1. "Add chording." Clicking a satisfied number reveals its remaining hidden neighbours — one loop that reuses reveal, cascades included.
2. "A million-cell board." The iterative flood already saved the stack; for memory, bitsets replace the boolean grid, and placement stays O(mines).
3. "Boards solvable without guessing." Now you need a solver inside the generator loop — name constraint propagation, estimate the cost, and scope it as a v2. Knowing it's hard is the point.
4. "Add a hint button." Cells provably safe from satisfied numbers come free; full probability is exponential in the worst case — say it, offer the cheap tier.
5. "Multiplayer minesweeper." The two-grid split pays off: one truth grid on the server, a view grid per player — the design was client-server before anyone asked.

Mistakes that fail the round: one grid with magic values; recursive flood-fill that dies on the first big board; declaring victory when all mines are flagged.

Where to go from here

Pocket version: two grids with two lifetimes, a queue-driven flood with a visited check, win by counting reveals, and a board that doesn't exist until the first click.

• Add chording — clicking a satisfied number reveals its remaining neighbours; it's one loop reusing reveal, and a great exercise.
• The flood fill transfers directly — go count islands or bucket-fill pixels; the queue, the visited check and the recruitment rule are identical.
• Next in the queue: the Jackpot machine, where the randomness lesson meets actual money.

And that childhood moment when half the board flew open? An ArrayDeque, a visited check, and zeros recruiting zeros. Some magic survives the explanation — this one gets better.