Minesweeper in Bash: Complete Solution & Deep Dive Guide
The Complete Guide to Solving Minesweeper with Bash Scripting
Learn to solve the classic Minesweeper puzzle using pure Bash scripting. This comprehensive guide explains how to parse a 2D board, iterate through cells, count adjacent mines, and generate the final annotated board, leveraging associative arrays and shell arithmetic for a powerful, text-based solution.
Have you ever looked at a complex problem, like parsing a game board, and thought, "Bash can't do that"? It's a common misconception. We often relegate Bash to simple file operations or one-liner commands, assuming that anything involving multi-dimensional data structures requires a "real" programming language like Python or Java. This belief holds many developers back from unlocking the true potential of the shell that's already at their fingertips on virtually every Linux and macOS system.
This article shatters that illusion. We will take on the classic Minesweeper annotation challenge—a task that inherently involves 2D grids, boundary checks, and neighbor analysis—and solve it elegantly using nothing but Bash. You will discover how a seemingly simple tool can handle complex logic, and you'll walk away with a deeper appreciation for shell scripting and a powerful new technique for your text-processing toolkit. Prepare to see Bash in a whole new light.
What Is the Minesweeper Annotation Problem?
At its core, the Minesweeper annotation problem is a grid transformation task. You are given a two-dimensional grid representing a Minesweeper board. This grid contains two types of cells: empty squares, typically represented by a space character (' '), and mines, represented by an asterisk ('*').
The objective is to process this input grid and produce an output grid of the same dimensions. In the output, the mines ('*') remain unchanged. However, every empty square must be updated to show a count of how many mines are adjacent to it—horizontally, vertically, and diagonally. If an empty square has zero adjacent mines, it should remain an empty space in the output.
Consider this simple 4x4 input board:
+---+
| * |
|* |
| |
| *|
+---+
To solve this, we must examine each empty cell. For the cell at row 0, column 2, we check its 8 neighbors and find two mines. For the cell at row 1, column 2, we find three adjacent mines. After performing this calculation for every empty cell, the resulting annotated board would be:
+---+
|2*2|
|*32|
|12*|
| 11|
+---+
This task tests your ability to handle 2D data, perform careful iteration with boundary checks, and implement a counting algorithm. In Bash, this presents a unique challenge that we can solve effectively using associative arrays to simulate a 2D grid.
The Core Logic: The 8-Directional Neighbor Scan
The heart of the solution is the algorithm for checking the neighbors of any given cell. For any cell at coordinates (row, col), we need to inspect the eight surrounding cells. This can be visualized as a systematic scan around a central point.
The key is to use relative offsets from the current cell's coordinates. We can define a set of "delta" values for rows (dr) and columns (dc) that range from -1 to 1. By adding these deltas to the current cell's coordinates, we can systematically access each neighbor.
Here is a diagram illustrating the neighbor-checking logic for a central cell (r, c):
● Cell (r, c)
│
▼
┌───────────────────┐
│ Loop dr from -1 to 1│
└─────────┬─────────┘
│
▼
┌───────────────────┐
│ Loop dc from -1 to 1│
└─────────┬─────────┘
│
▼
◆ dr=0 AND dc=0 ? (Is it the cell itself?)
╱ ╲
Yes (Skip) No (Process Neighbor)
│ │
└───────────────────┐ ▼
│ ┌──────────────────────────┐
│ │ Calculate neighbor_r = r + dr │
│ │ Calculate neighbor_c = c + dc │
│ └──────────────────────────┘
│
▼
◆ Is (neighbor_r, neighbor_c) within board boundaries?
╱ ╲
Yes No (Ignore)
│ │
▼ └───────────┐
┌──────────────────────────┐ │
│ Check if neighbor is a mine ('*') │ │
└──────────────────────────┘ │
│ │
▼ │
◆ Is it a mine? │
╱ ╲ │
Yes No │
│ │ │
▼ ▼ │
┌───────────────┐ ┌───────────────────┐ │
│ Increment Count │ │ Do Nothing │ │
└───────────────┘ └───────────────────┘ │
│ │ │
└─────────┬─────────┘ │
│ │
└───────────────────────────────────────────────────┘
Why Use Bash for This Challenge?
Choosing Bash for a task traditionally suited for general-purpose programming languages might seem unconventional, but it offers several distinct advantages, especially in certain contexts. It's also important to be aware of its limitations to know when a different tool would be more appropriate.
Bash is the default command-line interpreter on most Unix-like operating systems, including Linux and macOS. This ubiquity means a Bash script is incredibly portable and can run almost anywhere without requiring additional dependencies or runtime installations. For system administrators and DevOps engineers, being able to solve complex text-processing problems with the native shell is a powerful skill.
Furthermore, this challenge forces you to engage with some of Bash's more advanced features, such as associative arrays, arithmetic expansion, and robust loop control. Mastering these concepts through a practical problem like Minesweeper deepens your understanding of shell scripting far beyond simple command execution.
Pros and Cons of a Bash-Based Solution
Like any technical decision, using Bash involves trade-offs. Understanding these helps in making an informed choice for future projects.
| Pros (Advantages) | Cons (Disadvantages) |
|---|---|
| Ubiquity & Portability | Performance Overhead |
| Runs on virtually any Linux, macOS, or WSL environment without installing a new runtime. | As an interpreted language, Bash is significantly slower than compiled languages (Go, Rust) or even JIT-compiled languages (Python, Java) for CPU-intensive tasks. |
| Excellent for Text Processing | Limited Data Structures |
| Bash was designed for manipulating text streams and files, making it a natural fit for a problem with text-based grid input. | While associative arrays can simulate 2D arrays, Bash lacks native support for complex structures like trees, graphs, or objects, making solutions more verbose. |
| No Dependencies | Verbose Syntax for Math |
| The solution is self-contained. You don't need to manage packages or virtual environments. | Arithmetic operations require specific syntax (e.g., $((...)) or let), which can be less intuitive than in other languages. |
| Deepens Shell Scripting Skills | Error Handling Can Be Clumsy |
| Tackling this problem exposes you to advanced features like associative arrays and complex loop control. | Robust error handling often requires explicit checks and can make the script less readable compared to languages with try-catch blocks. |
How to Structure the Bash Solution: A Detailed Code Walkthrough
The provided solution from the kodikra.com learning path is a well-structured script that breaks the problem down into logical functions. We'll dissect this solution piece by piece to understand its inner workings, from parsing the input to generating the final annotated board.
Overall Program Flow
Before diving into the code, let's visualize the high-level flow of the script. It follows a clear, three-stage process: Initialization, Processing, and Output Generation.
● Start Script Execution
│
▼
┌───────────────────────────┐
│ 1. Initialization │
│ - Get board dimensions │
│ - Declare associative array `board` │
└────────────┬──────────────┘
│
▼
┌───────────────────────────┐
│ 2. Parse Input (`parse_input` fn) │
│ - Loop through each input row string │
│ - Loop through each character in the row │
│ - Store char in `board["row,col"]` │
└────────────┬──────────────┘
│
▼
┌───────────────────────────┐
│ 3. Process & Annotate │
│ - Loop through every row `r` │
│ - Loop through every column `c` │
└────────────┬──────────────┘
│
▼
◆ Is `board["r,c"]` a mine ('*')?
╱ ╲
Yes (Keep Mine) No (Calculate Count)
│ │
▼ ▼
┌─────────────┐ ┌────────────────────────────────┐
│ Append '*' to │ │ Call `count(r, c)` function │
│ output row │ │ - It checks 8 neighbors │
└─────────────┘ │ - Returns number of mines │
│ └────────────────┬───────────────┘
│ │
│ ▼
│ ◆ Is count > 0?
│ ╱ ╲
│ Yes No
│ │ │
│ ▼ ▼
│ ┌──────────────────┐ ┌──────────────────┐
│ │ Append count to │ │ Append ' ' to │
│ │ output row │ │ output row │
│ └──────────────────┘ └──────────────────┘
│ │ │
└────────────┬───────┴───────────┬───────┘
│ │
▼ ▼
┌──────────────────────────────────────────┐
│ 4. Output Generation │
│ - After each row is processed, print it │
└──────────────────┬───────────────────────┘
│
▼
● End Script
The Complete Bash Script
Here is the full solution code that we will be analyzing. This script is designed to be executed with the board rows passed as command-line arguments.
#!/usr/bin/env bash
# Exit immediately if a command exits with a non-zero status.
set -e
# Declare 'board' as an associative array to store the grid.
# Keys will be "row,col" strings, values will be the character at that position.
declare -A board
main() {
# Check for empty input.
if [[ $# -eq 0 ]]; then
return
fi
# Store board dimensions globally.
# height is the number of arguments ($#).
# width is the length of the first argument (${#1}).
height=$#
width=${#1}
# Populate the 'board' associative array from input arguments.
parse_input "$@"
# Iterate through each cell of the board to generate the output.
local r c
for ((r = 0; r < height; r++)); do
local output_row=""
for ((c = 0; c < width; c++)); do
local index="${r},${c}"
# If the current cell is a mine, append it directly.
if [[ ${board[$index]} == "*" ]]; then
output_row+="*"
else
# Otherwise, count adjacent mines.
local mine_count
mine_count=$(count "$r" "$c")
if [[ $mine_count -eq 0 ]]; then
output_row+=" "
else
output_row+="$mine_count"
fi
fi
done
echo "$output_row"
done
}
# Function to parse command-line arguments into the 'board' array.
parse_input() {
local rownum=0
local row col index char
for row in "$@"; do
for ((col = 0; col < "${#row}"; col++)); do
index="${rownum},${col}"
char=${row:col:1}
board[$index]=$char
done
((rownum++))
done
}
# Function to count mines adjacent to a given cell (r, c).
count() {
local r=$1
local c=$2
local current_count=0
# Iterate through the 3x3 grid centered on (r, c).
local dr dc
for dr in -1 0 1; do
# Calculate the neighbor's row.
local nr=$((r + dr))
# Boundary check: skip if the neighbor row is out of bounds.
if (( nr < 0 || nr >= height )); then
continue
fi
for dc in -1 0 1; do
# Calculate the neighbor's column.
local nc=$((c + dc))
# Boundary check: skip if the neighbor col is out of bounds.
if (( nc < 0 || nc >= width )); then
continue
fi
# Skip the cell itself.
if (( dr == 0 && dc == 0 )); then
continue
fi
# Check if the neighbor is a mine and increment the count.
local neighbor_index="${nr},${nc}"
if [[ ${board[$neighbor_index]} == "*" ]]; then
((current_count++))
fi
done
done
echo "$current_count"
}
# Pass all command-line arguments to the main function.
main "$@"
Step-by-Step Code Analysis
1. Initialization and Global Variables
set -e
declare -A board
set -e: This is a crucial command for writing safe shell scripts. It ensures that the script will exit immediately if any command fails (returns a non-zero exit code). This prevents unexpected behavior from cascading.declare -A board: This is the cornerstone of our solution. It declaresboardas an associative array. Unlike regular indexed arrays that use integers as keys, associative arrays use strings. We will use keys like"0,1"to represent the cell at row 0, column 1, effectively simulating a 2D grid.
height=$#
width=${#1}
- Inside the
mainfunction, we determine the board's dimensions from the script's arguments. $#is a special Bash variable that holds the total number of positional parameters (arguments) passed to the script. This gives us theheight.$1refers to the first argument.${#1}is a parameter expansion that gives the length of the string in$1. Assuming a rectangular board, this gives us thewidth.
2. The parse_input Function
This function's job is to take the string arguments and populate our board associative array.
parse_input() {
local rownum=0
local row col index char
for row in "$@"; do
for ((col = 0; col < "${#row}"; col++)); do
index="${rownum},${col}"
char=${row:col:1}
board[$index]=$char
done
((rownum++))
done
}
for row in "$@": This loop iterates through each command-line argument. Each argument is a string representing one row of the board.for ((col = 0; col < "${#row}"; col++)): This is a C-style inner loop that iterates through each character of the currentrowstring.index="${rownum},${col}": Here, we construct the unique key for our associative array. For the first character of the first row, this will be"0,0".char=${row:col:1}: This is Bash's substring expansion syntax. It extracts 1 character from therowstring starting at positioncol.board[$index]=$char: We assign the extracted character (e.g.,' 'or'*') as the value for the key we created. For example,board["0,0"]='*'.((rownum++)): After processing all columns in a row, we increment the row number for the next iteration.
3. The count Function: Core Logic
This is where the main algorithm resides. It takes a row and column as input and returns the number of adjacent mines.
count() {
local r=$1
local c=$2
local current_count=0
for dr in -1 0 1; do
local nr=$((r + dr))
if (( nr < 0 || nr >= height )); then
continue
fi
for dc in -1 0 1; do
local nc=$((c + dc))
if (( nc < 0 || nc >= width )); then
continue
fi
if (( dr == 0 && dc == 0 )); then
continue
fi
local neighbor_index="${nr},${nc}"
if [[ ${board[$neighbor_index]} == "*" ]]; then
((current_count++))
fi
done
done
echo "$current_count"
}
for dr in -1 0 1andfor dc in -1 0 1: These nested loops generate the relative offsets (-1, 0, 1) to scan all 8 neighbors plus the center cell.local nr=$((r + dr))andlocal nc=$((c + dc)): We calculate the absolute coordinates of the potential neighbor cell.- Boundary Checks: The lines
if (( nr < 0 || nr >= height ))andif (( nc < 0 || nc >= width ))are critical. They prevent us from checking for cells that are outside the board's dimensions (e.g., row -1). If a neighbor is out of bounds,continueskips to the next iteration. if (( dr == 0 && dc == 0 )): This check is essential to skip the cell itself. When both deltas are 0, we are looking at the original cell(r, c), not a neighbor.if [[ ${board[$neighbor_index]} == "*" ]]: We construct the neighbor's index string, retrieve its value from theboardarray, and check if it's a mine.((current_count++)): If the neighbor is a mine, we increment our counter.echo "$current_count": A function in Bash "returns" a value by printing it to standard output. The calling code will capture this output.
4. The main Function: Tying It All Together
The main loop orchestrates the entire process, iterating through the board and building the final output.
local r c
for ((r = 0; r < height; r++)); do
local output_row=""
for ((c = 0; c < width; c++)); do
local index="${r},${c}"
if [[ ${board[$index]} == "*" ]]; then
output_row+="*"
else
mine_count=$(count "$r" "$c")
if [[ $mine_count -eq 0 ]]; then
output_row+=" "
else
output_row+="$mine_count"
fi
fi
done
echo "$output_row"
done
- The outer loops iterate through every coordinate
(r, c)on the board. local output_row="": For each row, we initialize an empty string to build the result.- If the cell
${board[$index]}is a mine, we simply append*to ouroutput_row. - If it's not a mine, we call the
countfunction. The linemine_count=$(count "$r" "$c")is an example of command substitution. The shell executes thecountfunction and captures its standard output (the number we `echo`ed) into themine_countvariable. - Based on the returned
mine_count, we append either a space (for 0) or the number itself to theoutput_row. echo "$output_row": After the inner loop finishes processing all columns for a given row, this command prints the completed annotated row to the screen, followed by a newline.
How to Run the Script
To execute this script, you would save it as a file (e.g., minesweeper.sh), make it executable, and then run it with the board rows as arguments. Each row should be enclosed in quotes to be treated as a single argument.
# Make the script executable
chmod +x minesweeper.sh
# Run with a sample 3x3 board
# Board:
# *
# * *
#
./minesweeper.sh " * " "* *" " "
# Expected Output:
# 2*2
# * *
# 111
Where This Technique Applies in the Real World
While solving Minesweeper is a fun academic exercise, the underlying techniques are highly applicable to real-world system administration and data processing tasks. The ability to parse and manipulate grid-like textual data in Bash is a surprisingly useful skill.
- Log File Analysis: Many application and system logs are formatted in columns or fixed-width fields. You could adapt this script's logic to parse such logs, treating each line as a row and each field as a column, to extract statistics or identify patterns.
- Configuration Management: Some configuration files use a grid-like structure. A Bash script could parse, validate, or transform these files without needing external tools like Python or Perl. For example, analyzing firewall rules or host access files.
- Simple Image Processing: For text-based image formats like ASCII art or PBM (Portable BitMap), you could use these techniques to perform simple transformations, like detecting edges, inverting colors, or calculating densities in certain regions.
-
Data Transformation for CSV/TSV: While tools like
awkare often superior, a pure Bash approach using associative arrays can be used for quick and dirty transformations of simple CSV or tab-separated files, especially when you need to reference adjacent rows or columns.
The key takeaway is that by simulating a 2D array with an associative array, you unlock a new dimension of problem-solving capabilities directly within the shell, making you a more versatile and effective scripter.
Frequently Asked Questions (FAQ)
Why use a Bash associative array instead of a regular indexed array?
A standard indexed array in Bash is one-dimensional and uses integers for keys (0, 1, 2, ...). While you could simulate a 2D array by calculating a single index (e.g., index = row * width + col), this is cumbersome. An associative array allows us to use a more intuitive string key like "row,col" (e.g., "3,5"), making the code for accessing cells (board["3,5"]) much cleaner and more readable.
What does declare -A board actually do?
The declare command is a Bash builtin used to set attributes for shell variables. The -A flag specifically tells Bash to create an associative array. Without this declaration, Bash would treat board as a standard string variable, and assignments like board["0,0"]="*" would not work as intended.
Is this Bash solution efficient for very large boards?
No, not particularly. For each empty cell, the script iterates through its 8 neighbors. For a board of size HxW, the complexity is roughly O(H*W). While the algorithm itself is efficient, Bash is an interpreted language with significant overhead for loops and command substitution. For very large boards (e.g., 1000x1000), a solution in a compiled language like Go or Rust, or even a faster scripting language like Python, would be orders of magnitude faster.
How can I modify the script to handle invalid input, like a non-rectangular board?
You could add validation at the beginning of the main function. After getting the width from the first argument (width=${#1}), you could loop through all subsequent arguments and check if their length matches. If any row has a different length, you can print an error message to stderr and exit with a non-zero status code.
# Add this inside main() after getting width
for row in "$@"; do
if [[ ${#row} -ne $width ]]; then
echo "Error: Input board is not rectangular." >&2
exit 1
fi
done
What are the key Bash features demonstrated in this solution?
This script is a great showcase of several powerful Bash features:
- Associative Arrays:
declare -Afor simulating 2D data structures. - Parameter Expansion:
$#(argument count),$@(all arguments), and${#var}(string length). - Substring Expansion:
${string:offset:length}for character access. - Command Substitution:
variable=$(command)to capture function output. - Arithmetic Expansion:
$((...))for performing calculations. - C-style For Loops:
for ((i=0; i<N; i++))for controlled iteration.
Could this script be extended to create a playable Minesweeper game?
Yes, but it would be very complex. You would need to manage game state (e.g., which cells are revealed, flagged, or hidden), handle user input (e.g., reading coordinates to click), implement a "flood fill" algorithm for revealing empty areas, and create a game loop. While technically possible in Bash, it would be a significant undertaking and is a task far better suited for a language with better support for user interaction and complex state management.
Conclusion: The Surprising Power of Shell Scripting
We have successfully navigated the Minesweeper annotation challenge using nothing but the tools provided by the Bash shell. This journey has demonstrated that with the right approach—specifically by leveraging associative arrays to simulate a 2D grid—Bash can transcend its reputation as a simple command-runner and become a capable tool for solving algorithmic problems.
The key lessons are clear: understand your tool's advanced features, break down complex problems into manageable functions, and never underestimate the power of creative problem-solving. While Bash may not be the optimal choice for every performance-critical or data-intensive task, its universal availability and powerful text-processing capabilities make it an invaluable asset in any developer's or system administrator's arsenal.
Disclaimer: The code and explanations in this article are based on modern versions of Bash (v4.0+), which include support for associative arrays. The script should be compatible with most default Bash installations on current Linux distributions and macOS.
Ready to tackle more challenges and deepen your command-line expertise? Explore our complete Bash Learning Path or continue your journey on the Kodikra learning roadmap to unlock new skills.
Published by Kodikra — Your trusted Bash learning resource.
Post a Comment