Games & SimulationsProblem 7 of 11
Games & SimulationsIntermediate
Minesweeper
State PatternStrategy PatternObserver Pattern
Grid, mines, flood fill. The elegance is that every cell knows its neighbor-mine count at generation time — gameplay becomes pure state transitions.
Key Abstractions
Cell
One grid square. Holds mine-flag, adjacent-mine count, and reveal state.
Board
Grid of cells, mine layout, and reveal logic (flood fill for zero-adjacency)
MinePlacer
Strategy that places mines — random, fixed-seed, or first-click-safe
Game
Owns the board, status, and timer. Routes reveal/flag/chord actions. Declares win/lose.
Class Diagram
The Key Insight
Minesweeper's reveal logic looks like magic when someone clicks a zero-cell and half the board pops open. It's just BFS. Every cell with zero adjacent mines reveals its neighbors; if those are also zero, they cascade. A visited set (or the cell's own state transition) stops infinite loops. Eight lines of code.
Pre-computing adjacent-mine counts at generation time is the real win. The alternative — recounting neighbors on every reveal — means walking 8 cells per reveal, and on a 30x30 board with a cascade that can be 100+ cell reveals. Once-at-generation turns it into a single board walk, then O(1) per reveal.
First-click-safe is the detail that separates a good design from a working one. Placing mines after the first click, skipping the 3x3 window around the click, means the first move always opens up a useful area. Any commercial Minesweeper does this; most interview candidates miss it.
Requirements
Functional
- Configurable rows, columns, and mine count
- Reveal a cell; cascade through zero-adjacency neighbors
- Flag/unflag a hidden cell
- Track game status: playing, won, lost
- First click is always safe (never a mine)
Non-Functional
- O(1) per cell reveal after generation
- O(cells) memory for the board
- Reveal must be deterministic given a seed (testability)
- Board and Game should be separately testable
Design Decisions
Why precompute adjacent counts?
Adjacent-mine count is needed on every reveal. Recomputing means scanning 8 neighbors per click. Precompute at generation means scanning everything once, then O(1) per click thereafter. For cascading reveals (which can touch hundreds of cells), this is essentially the difference between a smooth UI and a janky one.
Why MinePlacer as a Strategy?
Tests want deterministic layouts. The first-click-safe rule wants a placer that knows the safe cell. A "chess-style" variant might want specific patterns. Strategy abstracts all of it — RandomMinePlacer for games, FixedMinePlacer for tests, SymmetricMinePlacer for puzzle modes.
Why lazy mine placement?
If mines are placed at board construction, the first click can hit a mine — game over at step one. Real Minesweeper delays placement until the first reveal and places mines away from the clicked cell. The lazy approach handles this naturally: no mines until the player clicks.
Why CellState.FLAGGED as a tristate?
Flags aren't involved in the win condition — they're a UI hint for the player. But a flagged cell shouldn't be revealable by click (prevents accidents). Making state an enum with three values captures all three behaviors (hidden-clickable, revealed, flagged-protected) in one field.
Why BFS instead of DFS for flood fill?
Either works. BFS is slightly safer for large cascades because it avoids deep recursion — Python's default recursion limit is 1000; a 40x40 board with one big zero-cluster could blow it. Iterative BFS with a deque has no such limit.
Interview Follow-ups
- "How would you save/load games?" Serialize the board (cell states, mine positions, adjacent counts) to JSON. Restore reconstructs
Boardwith the same state. SkipminesPlaced=false— use the loaded mines directly. - "What about chord clicks (click a revealed number to auto-reveal neighbors if flag count matches)?" New method
chord(r, c): if the revealed cell's number equals its flagged neighbors, reveal all non-flagged neighbors. - "How do you generate no-guessing boards?" Constraint solver — after placement, verify a logic-only solver can solve the board. If not, reroll. Expensive for large boards; typically done offline for puzzle packs.
- "How do you support a hint system?" The board internals already know mine positions. The hint service reveals one safe cell the player hasn't revealed yet — picks from
cells where !hasMine && state == HIDDEN.
Code Implementation
1 from __future__ import annotations
2 from abc import ABC, abstractmethod
3 from collections import deque
4 from dataclasses import dataclass
5 from datetime import datetime
6 from enum import Enum
7 import random
8
9
10 class CellState(Enum):
11 HIDDEN = "hidden"
12 REVEALED = "revealed"
13 FLAGGED = "flagged"
14
15
16 class GameStatus(Enum):
17 PLAYING = "playing"
18 WON = "won"
19 LOST = "lost"
20
21
22 @dataclass
23 class Cell:
24 row: int
25 col: int
26 has_mine: bool = False
27 adjacent_mines: int = 0
28 state: CellState = CellState.HIDDEN
29
30 def __str__(self) -> str:
31 if self.state == CellState.FLAGGED: return "⚑"
32 if self.state == CellState.HIDDEN: return "·"
33 if self.has_mine: return "*"
34 return str(self.adjacent_mines) if self.adjacent_mines else " "
35
36
37 class MinePlacer(ABC):
38 @abstractmethod
39 def place(self, board: "Board", safe_row: int, safe_col: int, count: int) -> None: ...
40
41
42 class RandomMinePlacer(MinePlacer):
43 """First-click-safe: avoid a 3x3 window around the first click."""
44
45 def __init__(self, rng: random.Random | None = None):
46 self._rng = rng or random.Random()
47
48 def place(self, board: "Board", safe_row: int, safe_col: int, count: int) -> None:
49 candidates = [
50 (r, c) for r in range(board.rows) for c in range(board.cols)
51 if not (abs(r - safe_row) <= 1 and abs(c - safe_col) <= 1)
52 ]
53 if count > len(candidates):
54 raise ValueError("Too many mines for board size")
55 picks = self._rng.sample(candidates, count)
56 for r, c in picks:
57 board.grid[r][c].has_mine = True
58 # Precompute adjacent counts once. O(rows*cols*8) — fast.
59 for r in range(board.rows):
60 for c in range(board.cols):
61 if board.grid[r][c].has_mine:
62 continue
63 board.grid[r][c].adjacent_mines = sum(
64 1 for n in board.neighbors(r, c) if n.has_mine
65 )
66
67
68 class Board:
69 DELTAS = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
70
71 def __init__(self, rows: int, cols: int, mine_count: int,
72 placer: MinePlacer | None = None):
73 if rows <= 0 or cols <= 0:
74 raise ValueError("rows and cols must be positive")
75 if mine_count >= rows * cols:
76 raise ValueError("Too many mines")
77 self.rows = rows
78 self.cols = cols
79 self.mine_count = mine_count
80 self.grid = [[Cell(r, c) for c in range(cols)] for r in range(rows)]
81 self._placer = placer or RandomMinePlacer()
82 self._mines_placed = False
83
84 def neighbors(self, r: int, c: int) -> list[Cell]:
85 out = []
86 for dr, dc in self.DELTAS:
87 nr, nc = r + dr, c + dc
88 if 0 <= nr < self.rows and 0 <= nc < self.cols:
89 out.append(self.grid[nr][nc])
90 return out
91
92 def reveal(self, r: int, c: int) -> list[Cell]:
93 """Reveal (r, c) and cascade through zero-adjacency cells. Returns cells newly revealed."""
94 if not self._in_bounds(r, c):
95 raise IndexError("out of bounds")
96
97 # Lazy mine placement — first click is always safe.
98 if not self._mines_placed:
99 self._placer.place(self, r, c, self.mine_count)
100 self._mines_placed = True
101
102 cell = self.grid[r][c]
103 if cell.state != CellState.HIDDEN:
104 return [] # already revealed or flagged; no-op
105
106 revealed: list[Cell] = []
107 if cell.has_mine:
108 cell.state = CellState.REVEALED
109 revealed.append(cell)
110 return revealed
111
112 # BFS flood-fill through zero-adjacency cells.
113 queue = deque([cell])
114 cell.state = CellState.REVEALED
115 revealed.append(cell)
116 while queue:
117 curr = queue.popleft()
118 if curr.adjacent_mines != 0:
119 continue
120 for n in self.neighbors(curr.row, curr.col):
121 if n.state == CellState.HIDDEN and not n.has_mine:
122 n.state = CellState.REVEALED
123 revealed.append(n)
124 queue.append(n)
125 return revealed
126
127 def flag(self, r: int, c: int) -> None:
128 if not self._in_bounds(r, c):
129 raise IndexError("out of bounds")
130 cell = self.grid[r][c]
131 if cell.state == CellState.REVEALED:
132 return # can't flag a revealed cell
133 cell.state = CellState.FLAGGED if cell.state == CellState.HIDDEN else CellState.HIDDEN
134
135 def all_safe_revealed(self) -> bool:
136 """Win condition: every non-mine cell is revealed."""
137 for row in self.grid:
138 for cell in row:
139 if not cell.has_mine and cell.state != CellState.REVEALED:
140 return False
141 return True
142
143 def _in_bounds(self, r: int, c: int) -> bool:
144 return 0 <= r < self.rows and 0 <= c < self.cols
145
146 def render(self, reveal_mines: bool = False) -> str:
147 lines = []
148 for row in self.grid:
149 parts = []
150 for cell in row:
151 if reveal_mines and cell.has_mine:
152 parts.append("*")
153 else:
154 parts.append(str(cell))
155 lines.append(" ".join(parts))
156 return "\n".join(lines)
157
158
159 class Game:
160 def __init__(self, rows: int, cols: int, mines: int, placer: MinePlacer | None = None):
161 self._board = Board(rows, cols, mines, placer)
162 self._status = GameStatus.PLAYING
163 self._started_at: datetime | None = None
164 self._finished_at: datetime | None = None
165
166 @property
167 def status(self) -> GameStatus: return self._status
168
169 @property
170 def board(self) -> Board: return self._board
171
172 def reveal(self, r: int, c: int) -> GameStatus:
173 if self._status != GameStatus.PLAYING:
174 return self._status
175 if self._started_at is None:
176 self._started_at = datetime.utcnow()
177 revealed = self._board.reveal(r, c)
178 for cell in revealed:
179 if cell.has_mine:
180 self._status = GameStatus.LOST
181 self._finished_at = datetime.utcnow()
182 return self._status
183 if self._board.all_safe_revealed():
184 self._status = GameStatus.WON
185 self._finished_at = datetime.utcnow()
186 return self._status
187
188 def flag(self, r: int, c: int) -> None:
189 if self._status != GameStatus.PLAYING:
190 return
191 self._board.flag(r, c)
192
193 def chord(self, r: int, c: int) -> GameStatus:
194 """Click-a-number to auto-reveal neighbors when the flag count matches.
195 Mis-flagging and then chording is a classic way to lose — by design."""
196 if self._status != GameStatus.PLAYING:
197 return self._status
198 if not self._board._in_bounds(r, c):
199 raise IndexError("out of bounds")
200 cell = self._board.grid[r][c]
201 if cell.state != CellState.REVEALED or cell.adjacent_mines == 0:
202 return self._status
203 flagged = sum(1 for n in self._board.neighbors(r, c) if n.state == CellState.FLAGGED)
204 if flagged != cell.adjacent_mines:
205 return self._status # no-op — not enough (or too many) flags
206 for n in self._board.neighbors(r, c):
207 if n.state == CellState.HIDDEN:
208 result = self.reveal(n.row, n.col)
209 if result == GameStatus.LOST:
210 return result
211 return self._status
212
213 def elapsed_seconds(self) -> float:
214 if self._started_at is None:
215 return 0.0
216 end = self._finished_at or datetime.utcnow()
217 return (end - self._started_at).total_seconds()
218
219
220 if __name__ == "__main__":
221 # Deterministic placement for the demo.
222 game = Game(5, 5, 5, placer=RandomMinePlacer(random.Random(7)))
223 print("Initial board (hidden):")
224 print(game.board.render())
225
226 game.reveal(0, 0)
227 print(f"\nAfter first reveal at (0,0) — status: {game.status.value}")
228 print(game.board.render())
229
230 # Flag a cell.
231 game.flag(2, 2)
232 print("\nAfter flagging (2,2):")
233 print(game.board.render())
234
235 # Reveal every non-mine cell to win.
236 for r in range(game.board.rows):
237 for c in range(game.board.cols):
238 cell = game.board.grid[r][c]
239 if not cell.has_mine:
240 game.reveal(r, c)
241 print(f"\nFinal status: {game.status.value}")
242 print(game.board.render(reveal_mines=True))
243 print(f"Elapsed: {game.elapsed_seconds():.3f}s")
244
245 # Chord: correctly flag neighbors then chord-click reveals the rest.
246 chord_game = Game(3, 3, 1, placer=RandomMinePlacer(random.Random(2)))
247 chord_game.reveal(0, 0) # lazy-places mines away from (0,0)
248 # Find a revealed number cell with exactly one mine neighbor.
249 target = None
250 for r in range(3):
251 for c in range(3):
252 cell = chord_game.board.grid[r][c]
253 if cell.state == CellState.REVEALED and cell.adjacent_mines == 1:
254 target = (r, c); break
255 if target: break
256 if target:
257 r, c = target
258 # Flag the one mine neighbor correctly.
259 for n in chord_game.board.neighbors(r, c):
260 if n.has_mine:
261 chord_game.flag(n.row, n.col)
262 break
263 before = sum(1 for row in chord_game.board.grid for cell in row
264 if cell.state == CellState.REVEALED)
265 chord_game.chord(r, c)
266 after = sum(1 for row in chord_game.board.grid for cell in row
267 if cell.state == CellState.REVEALED)
268 print(f"Chord revealed {after - before} new cell(s); status: {chord_game.status.value}")Common Mistakes
- ✗Checking 'all flags on mines' for the win condition. That forces the user to flag perfectly — not how the game works.
- ✗Placing mines at board creation. If the first click lands on a mine, the game ends before it starts — bad UX.
- ✗Revealing recursively without a visited set. Infinite loop on the first zero-cell click.
- ✗Storing only mine positions and recomputing counts per reveal. Slow and error-prone.
Key Points
- ✓Pre-compute adjacent-mine count once at board generation. Reveal becomes O(1) per cell.
- ✓Flood fill on reveal when adjacent count is 0 — BFS from the clicked cell through zero-cells.
- ✓First-click-safe: place mines *after* the first reveal and away from the clicked cell.
- ✓Win condition: all non-mine cells revealed, regardless of flags. Flags are just a UI hint.
- ✓Chord click: on a revealed number cell with matching flagged neighbors, auto-reveal the rest. Wrong flags → loss.
- ✓Timer starts on first reveal and stops on terminal status — clock doesn't tick before the player commits.