Cracking The Coding Interview Together – Problem 7.10: Minesweeper

At first glance, building a command-line Minesweeper game seems like a straightforward programming exercise: declare a 2D array, scatter a few random integers to represent mines, and print the output to stdout. However, as any experienced engineer knows, simple specifications often hide subtle design traps. As soon as you begin handling dynamic state updates, validating user inputs, and managing cascading zero-neighbor reveals without hitting a stack overflow, the challenge becomes clear.

Minesweeper is an exceptional interview question because it tests two core disciplines simultaneously: clean Object-Oriented Programming (OOP) architecture and algorithmic graph traversal. In this article, we will tackle Problem 7.10 from Cracking the Coding Interview. Together, we'll design and build a fully functional, production-ready, text-based Minesweeper game in Java—focusing on maintainability, scalability, and technical elegance.

Problem Statement

Our objective is to design and implement a text-based Minesweeper game playable in the terminal.

The operational requirements are as follows:

• Customizable Board: The game board should support variable dimensions (M * N) and a configurable number of hidden mines (B).
• Interactive Game Loop: The player can iteratively expose cells or toggle flags on suspected mine locations via command-line coordinates.
• Neighbor Counting: Exposing a cell that is adjacent to one or more mines reveals the exact count of adjacent mines (including diagonals, up to 8 neighbors).
• Cascading Unmasking: Exposing a cell with zero adjacent mines must automatically and recursively expose all contiguous non-mine neighboring cells until a boundary of numbered cells is reached.
• Win/Loss Conditions: Unearthing a mine results in an immediate game over. Exposing all non-mine cells results in victory.

Analyze the Problem Together

When approaching this problem in an interview setting, we must resist the urge to immediately write code inside a single monolithic class or main loop. Let's step back and deconstruct the game into its fundamental components.

At its core, a Minesweeper board is an undirected grid graph where each cell represents a vertex, and adjacent spatial steps form edges. Every cell maintains several pieces of state:

• Whether it contains a mine.
• Whether it is currently hidden, exposed, or flagged.
• The total count of adjacent mines.

The core algorithmic challenge lies in the zero-neighbor expansion. When a player clicks a blank cell, we must perform a graph traversal—either Depth-First Search (DFS) or Breadth-First Search (BFS)—to uncover all connected blank cells and their immediate perimeter. To prevent infinite recursion or redundant processing, we must maintain exact state tracking on every cell node.

Let's compare the naive approach against a modular object-oriented approach:

By opting for a clean Object-Oriented design, we decouple board state manipulation from the input/output console logic. This allows us to write robust unit tests for our traversal algorithms without worrying about mock terminal inputs.

Questions for the Interviewer

Before diving into architecture design, a senior engineer always clarifies scope and edge cases with the interviewer. Here are 4 critical questions you should ask:

• 1. Is First-Click Safety Required? In standard modern Minesweeper, the first cell clicked by a player is guaranteed to never be a mine. Should we defer mine placement until after the first click, or is pre-allocating mines at board generation acceptable? (For this solution, we will stick to pre-allocating mines during board creation to keep the core graph focus sharp, but we will discuss how to implement first-click safety.)
• 2. How Should Win Conditions Be Validated? Is victory defined as flagging all mines correctly, or revealing all non-mine safe cells? (Standard rules state victory occurs when every safe cell is exposed.)
• 3. What CLI Command Syntax Is Expected? How will the user specify actions? For instance, entering r 2 3 for reveal at row 2, column 3, and f 2 3 for flagging.
• 4. How Should Out-of-Bounds or Invalid Moves Be Handled? Should invalid input crash the program, or re-prompt the user gracefully?

Think About the Solution

Let's map out our system architecture into three cohesive components:

• Cell: The domain model encapsulating individual node state (`isMine`, `isRevealed`, `isFlagged`, `adjacentMines`).
• Board: The container managing the 2D matrix of `Cell` objects, mine distribution, neighbor counting, and the recursive flood-fill algorithm.
• Game: The orchestrator managing the interactive game loop, parsing CLI commands, rendering terminal views, and evaluating win/loss states.

Cascading Unmasking (Flood Fill Logic):
When `Board.reveal(r, c)` is invoked:

1. If coordinates are invalid or the cell is already revealed or flagged, return immediately.
2. Mark the cell as revealed.
3. If the cell is a mine, return a signal indicating game over.
4. If `adjacentMines > 0`, stop further propagation (we've hit a numbered boundary).
5. If `adjacentMines == 0`, iterate over all 8 adjacent neighbors and recursively invoke `reveal()` on each.

Write Code and Explain

Below is the production-ready Java implementation demonstrating clean separation of concerns and robust traversal handling.

import java.util.Random;
import java.util.Scanner;

public class Minesweeper {

    // ==========================================
    // 1. CELL CLASS (Domain Model)
    // ==========================================
    public static class Cell {
        private final int row;
        private final int col;
        private boolean isMine;
        private boolean isRevealed;
        private boolean isFlagged;
        private int adjacentMines;

        public Cell(int row, int col) {
            this.row = row;
            this.col = col;
            this.isMine = false;
            this.isRevealed = false;
            this.isFlagged = false;
            this.adjacentMines = 0;
        }

        public int getRow() { return row; }
        public int getCol() { return col; }
        public boolean isMine() { return isMine; }
        public void setMine(boolean mine) { isMine = mine; }
        public boolean isRevealed() { return isRevealed; }
        public void setRevealed(boolean revealed) { isRevealed = revealed; }
        public boolean isFlagged() { return isFlagged; }
        public void toggleFlag() { isFlagged = !isFlagged; }
        public int getAdjacentMines() { return adjacentMines; }
        public void setAdjacentMines(int count) { this.adjacentMines = count; }
    }

    // ==========================================
    // 2. BOARD CLASS (Business Logic & Graph Traversal)
    // ==========================================
    public static class Board {
        private final int rows;
        private final int cols;
        private final int totalMines;
        private final Cell[][] grid;
        private int unrevealedSafeCells;

        public Board(int rows, int cols, int totalMines) {
            this.rows = rows;
            this.cols = cols;
            this.totalMines = totalMines;
            this.grid = new Cell[rows][cols];
            this.unrevealedSafeCells = (rows * cols) - totalMines;

            initializeGrid();
            placeMines();
            calculateNeighborCounts();
        }

        private void initializeGrid() {
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    grid[r][c] = new Cell(r, c);
                }
            }
        }

        private void placeMines() {
            Random random = new Random();
            int minesPlaced = 0;
            while (minesPlaced < totalMines) {
                int r = random.nextInt(rows);
                int c = random.nextInt(cols);
                if (!grid[r][c].isMine()) {
                    grid[r][c].setMine(true);
                    minesPlaced++;
                }
            }
        }

        private void calculateNeighborCounts() {
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (!grid[r][c].isMine()) {
                        grid[r][c].setAdjacentMines(countMinesAround(r, c));
                    }
                }
            }
        }

        private int countMinesAround(int r, int c) {
            int count = 0;
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 && dc == 0) continue;
                    int nr = r + dr;
                    int nc = c + dc;
                    if (isValid(nr, nc) && grid[nr][nc].isMine()) {
                        count++;
                    }
                }
            }
            return count;
        }

        public boolean isValid(int r, int c) {
            return r >= 0 && r < rows && c >= 0 && c < cols;
        }

        // Uncovers a cell. Returns FALSE if mine detonated, TRUE otherwise.
        public boolean revealCell(int r, int c) {
            if (!isValid(r, c)) {
                System.out.println("Invalid coordinates!");
                return true;
            }

            Cell cell = grid[r][c];
            if (cell.isRevealed() || cell.isFlagged()) {
                return true; // Ignore already exposed or flagged cells
            }

            cell.setRevealed(true);

            if (cell.isMine()) {
                return false; // Game Over
            }

            unrevealedSafeCells--;

            // Recursive Flood Fill if zero adjacent mines
            if (cell.getAdjacentMines() == 0) {
                for (int dr = -1; dr <= 1; dr++) {
                    for (int dc = -1; dc <= 1; dc++) {
                        if (dr == 0 && dc == 0) continue;
                        int nr = r + dr;
                        int nc = c + dc;
                        if (isValid(nr, nc) && !grid[nr][nc].isRevealed()) {
                            revealCell(nr, nc);
                        }
                    }
                }
            }

            return true;
        }

        public void toggleFlag(int r, int c) {
            if (!isValid(r, c)) {
                System.out.println("Invalid coordinates!");
                return;
            }
            Cell cell = grid[r][c];
            if (!cell.isRevealed()) {
                cell.toggleFlag();
            }
        }

        public boolean isWon() {
            return unrevealedSafeCells == 0;
        }

        public void printBoard(boolean revealAll) {
            System.out.print("   ");
            for (int c = 0; c < cols; c++) {
                System.out.printf("%2d ", c);
            }
            System.out.println();

            for (int r = 0; r < rows; r++) {
                System.out.printf("%2d ", r);
                for (int c = 0; c < cols; c++) {
                    Cell cell = grid[r][c];
                    if (revealAll) {
                        if (cell.isMine()) System.out.print(" * ");
                        else System.out.printf(" %d ", cell.getAdjacentMines());
                    } else if (cell.isFlagged()) {
                        System.out.print(" F ");
                    } else if (!cell.isRevealed()) {
                        System.out.print(" . ");
                    } else if (cell.isMine()) {
                        System.out.print(" * ");
                    } else {
                        System.out.printf(" %d ", cell.getAdjacentMines());
                    }
                }
                System.out.println();
            }
        }
    }

    // ==========================================
    // 3. GAME CONTROLLER (CLI Interface)
    // ==========================================
    public static class Game {
        private final Board board;
        private boolean gameOver;

        public Game(int rows, int cols, int mines) {
            this.board = new Board(rows, cols, mines);
            this.gameOver = false;
        }

        public void start() {
            Scanner scanner = new Scanner(System.in);
            System.out.println("Welcome to Minesweeper!");

            while (!gameOver) {
                board.printBoard(false);
                System.out.println("Enter command (e.g., 'r 1 2' to reveal, 'f 1 2' to flag):");
                String action = scanner.next();
                int r = scanner.nextInt();
                int c = scanner.nextInt();

                if (action.equalsIgnoreCase("r")) {
                    boolean safe = board.revealCell(r, c);
                    if (!safe) {
                        gameOver = true;
                        System.out.println("\n BOOM! You landed on a mine. Game Over.");
                        board.printBoard(true);
                    } else if (board.isWon()) {
                        gameOver = true;
                        System.out.println("\n CONGRATULATIONS! You cleared all safe cells!");
                        board.printBoard(true);
                    }
                } else if (action.equalsIgnoreCase("f")) {
                    board.toggleFlag(r, c);
                } else {
                    System.out.println("Unknown command! Use 'r' or 'f'.");
                }
            }
        }
    }

    public static void main(String[] args) {
        // Launch a standard 8x8 game with 10 mines
        Game game = new Game(8, 8, 10);
        game.start();
    }
}

Code Walkthrough

• Encapsulated Cell State: Rather than relying on multi-dimensional primitive flags, every cell manages its internal state via explicit booleans and getters/setters.
• Targeted Initialization: placeMines() picks random grid locations until $B$ unique mines are placed. calculateNeighborCounts() pre-computes adjacent mine totals in a single pass before gameplay starts.
• Recursive Traversal (`revealCell`): When a cell with zero adjacent mines is clicked, the function recursively triggers `revealCell()` on all 8 surrounding cells. The exit conditions (`isRevealed() || isFlagged()`) act as base cases, preventing infinite loops or double processing.
• Optimized Win Tracking: Instead of scanning the entire grid after every single turn to check for victory, the `Board` tracks an `unrevealedSafeCells` integer counter. Decrementing this counter on every successful move allows $O(1)$ win evaluation.

Time & Space Complexity

Let's analyze the algorithmic performance of our Minesweeper implementation, where M is board height, N is board width, and B is total mine count.

• Board Initialization:
  • Time Complexity: $O(M \times N + B)$. Generating the grid takes $O(M \times N)$. Placing $B$ mines takes $O(B)$ on average. Pre-calculating neighbor counts takes $O(M \times N \times 8) = O(M \times N)$. Overall: $O(M \times N)$.
  • Space Complexity: $O(M \times N)$ memory allocated to hold the `Cell` array grid.
• Cell Reveal Operation (`revealCell`):
  • Time Complexity:
    • Single Numbered Cell: $O(1)$ constant time.
    • Cascading Zero-Fill: In the worst-case scenario (e.g., a board with zero mines), clicking a cell triggers a traversal across all cells on the board. Each cell is visited once. Time complexity is $O(M \times N)$.
  • Space Complexity: The call stack depth during recursive flood fill can reach up to $O(M \times N)$ in the worst case. (Note: In production with extremely large boards like $1000 \times 1000$, we can replace recursion with an explicit Queue-based BFS to avoid call stack overflow).
• Win Evaluation:
  • Time Complexity: $O(1)$ time, thanks to maintaining the stateful `unrevealedSafeCells` decrement counter.

Why This Problem Matters (The Senior Perspective)

In senior-level software engineering interviews, coding a working application is only half the task. Interviewers look for how you tie low-level implementation details to higher-level architecture and production resilience.

Here is how the principles in this problem translate to enterprise application design:

• Model-View-Controller (MVC) Pattern: Notice how our code strictly separates domain rules (`Board`/`Cell`), UI interaction (`Game`), and data visualization (`printBoard`). If tomorrow the product team asks to replace the CLI with a React frontend web client, we can re-use 100% of the `Board` and `Cell` core engines unchanged.
• Graph Flood Fill in Production: The zero-fill cascading logic is identical to algorithms used in industrial applications—such as image segment bucket-fill in graphics software, dynamic region-growing in computer vision, and network cluster discovery in distributed topologies.
• Concurrency & State Persistence: In a web-scale multiplayer backend (e.g., turn-based web games), multiple users might execute moves concurrently. Encapsulating state transitions within a `Board` object allows us to wrap operations in thread-safe atomic blocks or lock mechanisms easily. Serialization to JSON or persistent DB state also becomes effortless.

Final Thoughts

Minesweeper is a classic design interview question because it tests whether a developer can structure clean code while navigating graph search mechanics. By separating our data model from console I/O, writing modular methods, and optimizing win-check complexity, we transformed a simple command-line game into an extensible software project.

As an extra challenge for yourself: Try extending this codebase to support First-Click Safety (deferring mine distribution until after the initial move) or converting the recursive DFS inside revealCell() into an iterative BFS using an explicit ArrayDeque.

What engineering design questions would you like us to break down next? Happy coding, and we'll see you in the next deep dive!