Reveal Minesweeper

Tags

Reveal Minesweeper

Category

Recursion

Difficulty

Medium

Problem Statement

Given a 2D grid representing a minesweeper board and a click position (row, col), reveal the cell at that position. If the cell contains a mine, mark it as revealed and the game is over. If the cell is empty and has no adjacent mines, recursively reveal all adjacent cells. If the cell has adjacent mines, reveal it and display the count of adjacent mines. Return the updated board.

Intuition

Minesweeper reveal follows a flood-fill pattern. When a cell with zero adjacent mines is clicked, it triggers a cascade that reveals all connected cells until cells with adjacent mines form a boundary. This is a natural application of BFS or DFS: expand outward from the clicked cell, stopping expansion at cells that border mines.

Approach

  1. If the clicked cell is a mine, mark it as revealed (e.g., "X") and return.
  2. Count the number of adjacent mines around the clicked cell.
  3. If the count is greater than 0, set the cell to that count and return (do not recurse).
  4. If the count is 0, mark the cell as revealed (e.g., "H" for hidden becomes "-" for revealed empty), then recursively reveal all 8 adjacent cells that have not been revealed yet.
  5. The recursion naturally stops at boundary cells that have adjacent mines.

Pseudocode

function revealMinesweeper(board, row, col):
    if board[row][col] == "M":  // mine
        board[row][col] = "X"
        return board

    reveal(board, row, col)
    return board

function reveal(board, row, col):
    if row < 0 or row >= rows or col < 0 or col >= cols:
        return
    if board[row][col] is already revealed:
        return

    adjacentMines = countAdjacentMines(board, row, col)

    if adjacentMines > 0:
        board[row][col] = str(adjacentMines)
        return

    board[row][col] = "-"  // mark as revealed empty
    for each (newRow, newCol) in 8 neighbors of (row, col):
        reveal(board, newRow, newCol)

function countAdjacentMines(board, row, col):
    count = 0
    for each (r, c) in 8 neighbors of (row, col):
        if inBounds(r, c) and board[r][c] == "M":
            count += 1
    return count

Time & Space Complexity

  • Time: O(m * n) where m and n are the board dimensions. In the worst case (no mines), every cell is visited once.
  • Space: O(m * n) for the recursion stack in the worst case. BFS would use O(m * n) queue space instead.

Key Insights

  • This is a flood-fill algorithm with a stopping condition based on adjacent mine count.
  • Cells with adjacent mine counts > 0 act as natural boundaries that stop the recursive expansion.
  • All 8 directions (including diagonals) must be checked for both neighbor counting and recursive expansion.
  • The board is modified in place, and already-revealed cells prevent infinite recursion.

Edge Cases

  • Clicking on a mine: immediately reveal it, game over.
  • Clicking on a cell adjacent to mines: reveal only that cell with its count, no recursion.
  • Clicking on an already revealed cell: no operation needed.
  • Board with no mines: the entire board is revealed.
  • Board that is entirely mines: clicking any cell ends the game.
  • Single cell board: either a mine or an empty cell with 0 adjacent mines.
  • Corner and edge cells: have fewer than 8 neighbors, requiring bounds checking.

Linked mentions