Project #1
N-Puzzle Solver
This project implements a solver for the classic sliding N-Puzzle game using three fundamental search algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), and A* search. The solver can handle puzzles of various sizes and provides detailed performance metrics for each algorithm.
Technical Implementations
-
Object-Oriented Architecture
The program follows clean OOP design principles with clear separation of concerns:
- Solver: Coordinates the search process and manages algorithm execution
- Frontier classes: Handle different data structure behaviors (queue for BFS, stack for DFS, priority queue for A*)
- PuzzleState: Represents puzzle configurations and tracks state transitions
-
Performance Metrics/h3>
The solver tracks comprehensive performance data for analysis and comparison:
- Number of nodes expanded
- Maximum search depth reached
- Execution runtime
- Memory usage
-
Search Algorithms
Implemented three core search algorithms:
- 1. Breadth-First Search (BFS) Explores states by level, guaranteeing shortest solution path but potentially consuming significant memory.
- 2. Depth-First Search (DFS) Explores deep as possible before backtracking. Memory efficient but may find suboptimal solutions.
- 3. A* Search Uses a priority queue to expand most promising states first, guided by a heuristic function. Ensures optimal solutions while maintaining efficiency by pruning search space.
-
Optimizations
Efficient data structures drove performance:
- Heaps for priority queues: O(log n) insertions and deletions in A* search
- Sets for state tracking: O(1) lookups to prevent revisiting explored states
- Stale entry handling: Manages duplicate entries in priority queue efficiently
Project #2
Sudoku Solver with CSP
This project implements an intelligent Sudoku solver using Constraint Satisfaction Problem (CSP) techniques. The solver employs backtracking search enhanced with sophisticated heuristics and constraint propagation to efficiently solve Sudoku puzzles of varying difficulty levels.
Technical Implementations
-
Constraint Satisfaction Framework
Built a complete CSP framework specifically designed for Sudoku:
- Variables: 81 cells representing the 9×9 grid
- Domains: Sets of possible values (1-9) for each cell, dynamically pruned during search
- Constraints: No duplicate values in rows, columns, or 3×3 boxes
- Peer relationships: Pre-computed constraint graph mapping each cell to its 20 peers for efficient validation
-
Intelligent Search Heuristics
Implemented multiple heuristics to guide the search process intelligently:
- Minimum Remaining Values (MRV): Selects variables with fewest legal values first, enabling early failure detection and reducing backtracking
- Least Constraining Value (LCV): Orders domain values to try those that eliminate fewest options for neighboring cells, preserving search flexibility
- Degree Heuristic: Breaks ties by selecting cells involved in the most constraints
-
Constraint Propagation
Forward checking dramatically reduces the search space:
- Domain pruning: When a value is assigned, immediately removes it from all peer domains
- Early failure detection: Identifies unsolvable states before exploring further, triggering immediate backtracking
- Efficient undo mechanism: Maintains a trail of all domain modifications for O(1) backtracking
-
Performance Metrics
Comprehensive testing and analysis across diverse puzzle difficulties:
- Success rate: Achieves 99%+ solve rate across 400 test puzzles
- Runtime analysis: Tracks mean, standard deviation, minimum, and maximum solve times
- Efficiency: Average solve time under 0.05 seconds per puzzle
- Scalability: Handles both easy and extremely difficult puzzles effectively
-
Algorithm Design Decisions
Key architectural choices that optimize performance:
- Domain representation: Python sets enable O(1) membership testing and efficient set operations
- State separation: Board tracks explicit assignments while domains track possibilities, preventing premature commits
- Tuple-based tie-breaking: Lexicographic ordering ensures deterministic behavior in heuristic selection
- Trail mechanism: Stack-based undo system allows efficient backtracking without copying entire state
Performance Results
Project #3
2048 Game AI Agent
This project implements an intelligent agent that plays the 2048 puzzle game using adversarial search techniques. The AI consistently achieves tiles of 2048 and beyond by combining expectiminimax algorithm with alpha-beta pruning and sophisticated heuristic evaluation functions.
Technical Implementations
-
Expectiminimax Algorithm
Implemented expectiminimax search to handle the stochastic nature of 2048's tile placement:
- MAX nodes: Player's turn - select move that maximizes expected utility
- CHANCE nodes: Computer's turn - calculate expected value across all possible tile placements (90% probability for 2, 10% for 4)
- Recursive evaluation: Alternates between maximizing player moves and computing probabilistic expectations for opponent moves
-
Alpha-Beta Pruning
Enhanced search efficiency through intelligent branch elimination:
- Prunes branches that cannot influence final decision
- Move ordering heuristics prioritize promising branches first
- Dramatically reduces nodes explored while maintaining optimal decisions
-
Multi-Faceted Heuristic Evaluation
Developed weighted combination of strategic heuristics:
- Rank-Based Monotonicity: Enforces snake pattern with penalties scaled to tile values - breaking monotonicity with 2048-512-1024 is penalized more heavily than with 4-2-4
- Large Tile Adjacency: Rewards positioning high-value tiles (≥64) near similar-valued tiles to facilitate future merges
- Small Tile Penalty: Penalizes boards cluttered with small tiles when large tiles exist, encouraging aggressive consolidation
- Merge Potential: Identifies and values opportunities for immediate tile combinations
- Corner Gradient: Rewards keeping maximum tile in corner with bonus for second-highest tile adjacent to it
-
Optimizations
Performance enhancements enabled deeper search:
- Iterative Deepening: Progressively searches deeper until time limit, ensuring valid move always available
- Transposition Table: Caches previously evaluated board states to avoid redundant calculations, providing 2-5x speedup
- Adaptive Depth: Dynamically adjusts search depth based on board complexity - fewer empty cells allow deeper search
- Strategic Sampling: Prioritizes corner and edge cells in CHANCE nodes to reduce branching factor
- Time Management: Active monitoring prevents timeout violations with 0.2 second move limit
-
Automated Weight Tuning
Implemented Bayesian optimization to discover optimal heuristic weights:
- Systematically tests different weight combinations across multiple games
- Intelligently explores parameter space using Gaussian process models
- Converges to high-performing configurations significantly faster than grid search
-
Performance Results
The agent demonstrates strong and consistent gameplay:
- Consistently achieves 2048 tile (>95% success rate)
- Regularly reaches 4096 tile in optimized configurations
- Maintains strategic board organization throughout gameplay
- Executes moves within strict 0.2 second time constraint