Minesweeper: Algorithmic Engine

A Java Swing–based Minesweeper game featuring a graph-backed algorithmic engine and a greedy CPU opponent that uses sorting to make optimal decisions.

---

Game Features

• Human vs CPU turn-based gameplay
• Greedy AI that evaluates risk and sorts candidates
• Graph-based board representation for neighbor discovery
• Color-coded numbers (1=blue, 2=green, 3=red)
• Flag system to mark suspected mines
• How to Play in-game help dialog

---

Tech Stack

Component	Technology
Language	Java 17+
GUI Framework	Java Swing
Build	javac (command-line)
IDE Compatible	Eclipse, IntelliJ, VS Code

---

DAA Algorithms Used

Algorithm	File Location	Purpose	Complexity
Graph (Adjacency List)	graph/BoardGraph.java	Models the game board as a graph where each cell is a node connected to its 8 neighbors	O(1) neighbor lookup
Graph Traversal	BoardGraph.buildGraph()	Iterates through all directions (-1,-1) to (1,1) to discover neighbors	O(V + E)
Greedy Algorithm	algorithm/CpuGreedyPlayer.java	CPU makes locally optimal choice by selecting the cell with minimum risk score	O(n) evaluation
Merge Sort	CpuGreedyPlayer.mergeSort()	Ranks all candidate cells by risk in ascending order before selection	O(n log n)
Risk Heuristic	CpuGreedyPlayer.estimateRisk()	Computes average of neighbor clue numbers using graph traversal	O(degree) per cell

---

Algorithm Details

1. Graph Representation (Adjacency List)

BoardGraph.java
├── Cell[][] grid          → 2D array of nodes
└── Map<Cell, List<Cell>>  → Adjacency list for O(1) neighbor access

Each cell connects to up to 8 neighbors (orthogonal + diagonal). The graph is built once at initialization and reused for:

• Computing adjacent mine counts
• CPU neighbor analysis

2. Greedy Strategy with Sorting

CpuGreedyPlayer.chooseMove()
│
├── Step 1: Graph Traversal → Collect hidden cells
├── Step 2: Risk Computation → Use neighbors to estimate danger
├── Step 3: Merge Sort       → Rank candidates by risk (ascending)
└── Step 4: Greedy Selection → Pick first (lowest risk) cell

3. Merge Sort Implementation

mergeSort(list)
├── Base case: size ≤ 1 → return
├── Divide: split into left/right halves
├── Conquer: recursively sort both halves
└── Combine: merge sorted halves

Time Complexity: O(n log n)
Space Complexity: O(n)

---

Project Structure

mines-algorithmic-engine-main/
├── src/
│   ├── algorithm/
│   │   └── CpuGreedyPlayer.java    # Greedy AI + Merge Sort
│   ├── game/
│   │   ├── Cell.java               # Cell data model
│   │   ├── MineSweeperGame.java    # Game logic & rules
│   │   ├── Move.java               # Move representation
│   │   ├── Player.java             # Player interface
│   │   ├── HumanPlayer.java        # Human player
│   │   └── GameStateListener.java  # Event callbacks
│   ├── graph/
│   │   └── BoardGraph.java         # Graph data structure
│   └── gui/
│       ├── Main.java               # Entry point
│       ├── MinesweeperGUI.java     # Main window
│       ├── GamePanel.java          # Board grid
│       ├── CellButton.java         # Cell UI component
│       └── ImageUtils.java         # Icon utilities
└── bin/                            # Compiled classes

---

How to Run

Compile

javac -d bin -sourcepath src src/gui/Main.java

Run

java -cp bin gui.Main

---

How to Play

1. Left-click a cell to reveal it
2. Right-click to place/remove a flag
3. Numbers indicate adjacent mines (1-8)
4. Avoid mines — whoever hits one loses!
5. Score points by revealing safe cells
6. Beat the CPU by revealing more safe cells

---

Complexity Analysis

Operation	Time Complexity	Space Complexity
Build graph	O(rows × cols)	O(V + E)
Compute adjacencies	O(V × degree)	O(1)
CPU move selection	O(n log n)	O(n)
Risk estimation	O(degree)	O(1)

Where:

• V = number of cells (rows × cols)
• E = number of edges (≤ 8V)
• n = number of hidden cells
• degree = neighbors per cell (≤ 8)

---

Author

DAA Course Project — Demonstrating Graph, Greedy, and Sorting algorithms in a real-world application.