Design Minesweeper
Grid generation, flood-fill reveal, flagging, and win/lose detection — a tidy board-game engine.
Problem Statement
Design the object model for Minesweeper, a grid game where cells may hide mines, show adjacent-mine counts, be revealed, or be flagged by the player. The engine must generate a board, place mines without duplicates, compute the 8-neighbor counts, and reveal cells according to classic Minesweeper rules.
The central interview challenge is the reveal flow: clicking a mine moves the game to LOST, clicking a numbered safe cell reveals only that cell, and clicking a zero-count safe cell triggers flood-fill to reveal the connected empty region plus its numbered boundary.
Keep the model UI-free. A console app, web client, or bot should call the same Game API and receive a state transition from IN_PROGRESS to either WON or LOST.
Business context
Minesweeper is a strong intermediate LLD problem because the class model is small but the correctness surface is non-trivial. Candidates must model cell state, board generation, a pluggable mine-placement policy, and a game state machine without mixing in rendering concerns.
Interviewers use it to test whether you can combine OOP boundaries with graph traversal. The flood-fill must be iterative or carefully guarded, flags must not corrupt reveal state, and the win condition must be based on all non-mine cells being revealed rather than on flag count guesses.
Functional Requirements
Create a rectangular board with positive row and column counts and a mine count smaller than the number of cells.
Place mines through a pluggable placement strategy, ensuring positions are unique and within board bounds.
Compute adjacent-mine counts using all eight neighboring directions around each non-mine cell.
Reveal a safe numbered cell without expanding beyond that cell.
Reveal an empty zero-count cell with BFS or DFS flood-fill, expanding through zero cells and revealing bordering numbered cells.
Reveal a mine as a losing move and transition the game from IN_PROGRESS to LOST.
Allow players to toggle flags on hidden cells and reject reveal attempts on flagged cells.
Declare WON when every non-mine cell has been revealed, regardless of how many flags are placed.
Reject reveals and flag changes after the game reaches WON or LOST.
Expose enough board state for a UI to render hidden cells, flags, revealed counts, mines after loss, and current game state.
Non-Functional Requirements
Flood-fill correctness
The reveal algorithm must visit each safe cell at most a small constant number of times, must not cross mines, and must stop expansion at numbered boundary cells.
Deterministic testability
Mine placement is injected through MinePlacementStrategy so tests can supply fixed positions while production can use random placement.
State-machine safety
Only IN_PROGRESS accepts player actions. A mine reveal moves to LOST and all safe cells revealed moves to WON; terminal states are sticky.
Encapsulation
Cell flags, revealed status, mine markers, and adjacent counts are changed only through Board and Cell methods, not by callers mutating raw arrays.
Scalability for large boards
Use iterative BFS instead of recursive DFS in the reference implementation so a large empty area does not overflow the Java call stack.
Requirement Clarification
QAre diagonal neighbors counted?
Yes. Adjacent-mine count uses all eight surrounding cells: horizontal, vertical, and diagonal neighbors within bounds.
QDoes the first click need to be guaranteed safe?
Not in the base design. The Strategy seam makes it easy to add first-click-safe placement later by passing the first coordinate into a specialized strategy.
QDoes placing all flags correctly win the game?
No. Flags are player annotations. The base win condition is that every non-mine cell is revealed; flags alone never change the game to WON.
QShould flood-fill use recursion?
Use BFS or iterative DFS for the implementation. Recursive DFS is fine to explain, but an interview-grade Java solution should avoid stack overflow on large empty boards.
QDo we need a GUI, timer, scoring, or persistence?
No for the core LLD. Keep the engine in memory and expose board state so UI, timer, leaderboard, and storage adapters can be added around it.
UML Class Diagram
Sequence Diagram
Entity Identification
Game
Aggregate root for one play session. It serializes player actions, delegates board operations, and owns the sticky state transition from IN_PROGRESS to WON or LOST.
Board
Owns the grid, validates coordinates, places mines through the strategy, computes adjacent counts, and implements iterative flood-fill reveal.
Cell
Represents one coordinate with mine, revealed, flagged, and adjacent-mine state. It rejects invalid local transitions such as flagging a revealed cell.
GameState
Enum-backed state machine. It exposes transition methods so terminal-state stickiness and safe-reveal behavior are centralized.
MinePlacementStrategy
Strategy interface for choosing mine positions. Random, fixed, first-click-safe, or difficulty-weighted placement can all implement the same contract.
RandomMinePlacementStrategy
Default production strategy. It samples unique flattened cell positions until the requested mine count is reached.
Design Patterns Used
GameState captures the state machine explicitly. Game asks the enum for transitions, so WON and LOST remain terminal and action validation is simple.
Board.create and Game.newGame centralize construction, validation, mine placement, and adjacent-count calculation. Callers do not assemble a half-built board.
MinePlacementStrategy separates board rules from mine generation. Tests can inject fixed positions while production injects RandomMinePlacementStrategy.
Step-by-Step Design
1Model cell state tightly
A Cell owns only local facts: coordinate, mine flag, reveal flag, player flag, and adjacent count. It rejects invalid transitions such as flagging after reveal.
public boolean reveal() { if (flagged) { throw new IllegalStateException("Cannot reveal a flagged cell"); } if (revealed) { return false; } revealed = true; return true; }2Create the board through a factory method
Board.create validates dimensions, asks the placement strategy for mine positions, sets mines, and computes all adjacent counts before returning a playable board.
public static Board create(int rows, int cols, int mineCount, MinePlacementStrategy strategy) { Board board = new Board(rows, cols, mineCount); Set<Integer> positions = strategy.placeMines(rows, cols, mineCount); board.placeMines(positions); board.computeAdjacentMineCounts(); return board; }3Compute counts once after mine placement
Each safe cell scans the eight neighbors once. Counts become immutable gameplay data until a new board is created.
private int countAdjacentMines(int row, int col) { int count = 0; for (Cell neighbor : neighborsOf(row, col)) { if (neighbor.isMine()) { count++; } } return count; }4Use iterative flood-fill for zero cells
Reveal starts at the clicked cell. Numbered safe cells stop immediately; zero cells enter a queue, reveal connected zero cells, and reveal the numbered boundary without expanding through it.
while (!queue.isEmpty()) { Cell current = queue.removeFirst(); current.reveal(); if (current.getAdjacentMines() != 0) { continue; } for (Cell neighbor : neighborsOf(current.getRow(), current.getCol())) { addZeroToQueueOrRevealBoundaryNumber(neighbor); } }5Keep game state transitions in Game
Board knows reveal mechanics, but Game decides what the reveal means. Mine click means LOST; all safe cells revealed means WON; otherwise remain IN_PROGRESS.
if (clickedMine) { state = state.afterMineReveal(); board.revealAllMines(); } else { state = state.afterSafeReveal(board.allSafeCellsRevealed()); }6Treat flags as annotations, not truth
A flag prevents accidental reveal of a hidden cell, but it does not prove a mine and it never drives the win condition. This prevents false wins from lucky flag placement.
Complete Java Implementation
Explanation of Every Class
GameState
Enum state machine with IN_PROGRESS, WON, and LOST. Transition helpers keep terminal states sticky and make Game read like a rule engine rather than a switch-heavy controller.
Cell
One grid square. It stores coordinates, mine status, reveal status, flag status, and adjacent count. Local invariant checks prevent revealing flagged cells and flagging revealed cells.
MinePlacementStrategy
Strategy interface for mine placement. Board construction depends on this abstraction, enabling deterministic tests and alternative placement policies without changing reveal logic.
RandomMinePlacementStrategy
Default production strategy. It samples flattened cell ids into a set, which naturally prevents duplicate mines while keeping placement independent of Board internals.
Board
Owns the matrix and all coordinate-sensitive rules: factory construction, mine validation, adjacent-count calculation, flag toggling, flood-fill reveal, win-condition support, and rendering-friendly text output.
Game
Session facade and state owner. It serializes public actions with synchronized, delegates mechanics to Board, and updates GameState after every reveal.
Dry Run
Sample input
4×4 board with fixed mines at flattened positions 0 and 1: mines at (0,0) and (0,1). Actions: flag (0,0), reveal (3,3), reveal (0,1).
| Step | Action | Board operation | Revealed cells | State | Why |
|---|---|---|---|---|---|
| 1 | create board | place mines and compute counts | 0 | IN_PROGRESS | Counts around the top-left mines are prepared before play. |
| 2 | toggleFlag(0,0) | mark hidden cell as flagged | 0 | IN_PROGRESS | Flags are annotations and do not affect the win condition. |
| 3 | reveal(3,3) | BFS flood-fill from a zero cell | safe zero region plus numbered boundary | IN_PROGRESS | Flood-fill reveals connected empty cells but stops at counts near mines. |
| 4 | reveal(0,1) | clicked mine | mine cell, then all mines | LOST | Mine reveal moves the state machine to the terminal loss state. |
| 5 | toggleFlag(2,2) | rejected | 0 | LOST | Terminal states reject further player actions. |
The important row is step 3: a zero cell reveal does not scan the whole board blindly. It performs a bounded graph traversal over adjacent safe zero cells and reveals only the numbered border needed by the UI.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| Board creation | O(R × C) | O(R × C) | Allocates every cell, places mines, and computes counts by checking up to eight neighbors per cell. |
| reveal numbered cell | O(1) | O(1) | A numbered safe cell reveals itself and stops. |
| reveal zero cell with flood-fill | O(R × C) worst case | O(R × C) worst case | An empty board can reveal every safe cell and queue a large connected component. |
| toggleFlag | O(1) | O(1) | Coordinate validation plus one local state flip. |
| win check | O(R × C) | O(1) | The simple implementation scans for hidden safe cells; a counter can make this O(1). |
R is row count and C is column count. Flood-fill is linear in the number of cells it reveals, which is optimal. If win checks become hot, maintain a hiddenSafeCells counter and decrement it by the number of newly revealed safe cells returned from Board.reveal.
Extensibility
First-click-safe mode
Delay mine placement until the first reveal and pass the first coordinate to a specialized MinePlacementStrategy that excludes that cell and optionally its neighbors.
Difficulty presets
Add a small factory around Game.newGame that maps beginner, intermediate, and expert presets to row, column, mine-count, and placement-strategy choices.
Undo or replay
Store reveal and flag commands as events. Because Board.reveal returns changed cells, replay logs can reconstruct visible state step by step.
Hints and solver support
Add a read-only analyzer that consumes Board snapshots. It should never mutate Cell directly; all gameplay changes still go through Game.
Alternative Designs
Recursive DFS reveal
Implement zero-cell expansion with a recursive helper that visits neighbors until no more zero cells remain.
Tradeoffs
The code is short, but a large empty board can overflow the Java stack. Iterative BFS is safer for production and interviews.
Counter-based win tracking
Keep hiddenSafeCells in Game or Board and decrement it by the count of newly revealed non-mine cells returned from reveal.
Tradeoffs
This makes win checks O(1), but the counter must stay exactly consistent with idempotent reveal calls and boundary reveals.
Immutable board snapshots
Expose immutable DTO snapshots instead of returning mutable Cell references to callers.
Tradeoffs
Cleaner API boundaries for a service, but more object allocation for every render or poll.
Common Mistakes
- ×
Winning when all mines are flagged instead of when all safe cells are revealed.
- ×
Letting flood-fill reveal mines or expand through numbered cells rather than stopping at the boundary.
- ×
Using recursive DFS without discussing stack overflow on large empty boards.
- ×
Forgetting to skip flagged cells during reveal, which makes flags useless as player protection.
- ×
Recomputing adjacent counts on every reveal instead of once after mine placement.
- ×
Allowing actions after WON or LOST, which breaks the state machine.
- ×
Hard-coding random mine placement inside Board so deterministic tests become awkward.
Follow-up Interview Questions
QHow would you guarantee the first click is safe?
Delay board finalization until the first reveal. Then call a placement strategy that excludes the first cell, and optionally all eight neighbors, before computing adjacent counts.
QHow do you avoid stack overflow during reveal?
Use an explicit queue or stack. The reference uses BFS with ArrayDeque, so the heap holds traversal state instead of the call stack.
QWhy is flagging not part of the win condition?
Flags are user guesses. A player can flag any hidden cell, including safe cells, so correctness must be based on revealed safe cells rather than annotations.
QHow would you make win checking O(1)?
Maintain a remaining hidden safe-cell counter. Board.reveal returns the newly revealed cells, and Game subtracts the safe-cell count after each reveal.
QWhere would a timer and leaderboard live?
Outside the core engine. A session service can start a timer when the first reveal succeeds and submit results after WON without changing Board or Cell.
Production Considerations
API boundary
Expose immutable board snapshots to clients instead of raw Cell objects so external code cannot mutate game state behind Game.
Concurrency
Serialize actions per game id. The Java sample synchronizes Game.reveal and Game.toggleFlag; a distributed service would use a row lock or per-game actor.
Fair randomness
Use a seedable random source for replayable games and store the seed with the game session for audits, debugging, and cheat investigation.
Persistence
Persist the mine layout, revealed cells, flags, state, and start time. Do not rely on recomputing a random board after restart.
Abuse prevention
Server-authoritative games should never send hidden mine positions to the client before loss or completion; send only visible snapshots.
What Interviewers Look For
Did you identify flood-fill as the core algorithmic risk and implement it without revealing mines?
Did you model IN_PROGRESS, WON, and LOST as explicit states with terminal-state guards?
Did you keep mine placement pluggable so tests can be deterministic?
Did you distinguish flags from reveal truth in the win condition?
Did you keep UI, persistence, timer, and leaderboard concerns outside the core engine?
Quiz
0/5 answered
1.When should Minesweeper transition to **WON**?
2.What should flood-fill do when it reaches a numbered safe cell?
3.Why inject **MinePlacementStrategy**?
4.What happens when a player tries to reveal a flagged hidden cell in this design?
5.Why prefer iterative BFS over recursive DFS for the reference implementation?
Practice Variants
First-click-safe Minesweeper
IntermediateDelay mine placement until the first reveal and ensure the first clicked cell is never a mine. For an advanced version, also keep its neighbors mine-free.
Counter-based win detection
BeginnerReplace the O(R × C) win scan with a remaining-safe-cells counter updated from Board.reveal results. Prove repeated reveals do not double-decrement it.
Multiplayer race mode
AdvancedLet multiple players reveal cells on the same board. Decide how to serialize actions, score safe reveals, and handle the first player who clicks a mine.
Flashcards
Cheat Sheet
Entities: Game, Board, Cell, GameState, MinePlacementStrategy, RandomMinePlacementStrategy.
Patterns: State for IN_PROGRESS/WON/LOST, Strategy for mine placement, Factory Method for board and game creation.
Core flow: reveal = validate state → check clicked mine → Board.reveal → update state → reveal all mines on loss or check safe completion.
Flood-fill rule: numbered safe cell reveals one cell; zero safe cell expands through zero neighbors and reveals numbered boundaries; flagged cells are skipped.
Win rule: all safe cells revealed. Flag count is not a source of truth.
Complexity: creation O(R×C), numbered reveal O(1), flood-fill O(R×C) worst case, flag O(1).
References
- BookHead First Design Patterns (State, Strategy, Factory Method) — Freeman & Robson
- DocsRefactoring Guru — State Pattern
- DocsCP-Algorithms — Breadth First Search