The 8-puzzle is a classic problem in artificial intelligence and computer science, which involves a 3x3 grid with tiles numbered 1 through 8 and one empty space. The goal is to rearrange the tiles from an initial random configuration to the target configuration using the minimum number of moves. The project focuses on implementing various heuristic search algorithms to solve the puzzle efficiently.
The game is implemented in Python, leveraging the A* search algorithm, which combines the benefits of uniform-cost search and greedy best-first search. The project includes several heuristic functions to guide the search:
Misplaced Tiles Heuristic (h1): Counts the number of tiles not in their goal position. Euclidean Distance Heuristic (h2): Calculates the sum of the Euclidean distances of the tiles from their goal positions. Manhattan Distance Heuristic (h3): Computes the sum of the vertical and horizontal distances of the tiles from their goal positions. Tiles Out of Row and Column Heuristic (h4): Counts the number of tiles out of their goal row and column.
Random Puzzle Generation: The program can generate a random solvable 8-puzzle configuration. Heuristic Choice: Users can select the heuristic function to use for the A* search. Visualization: The solution path is displayed, showing each move from the initial to the goal state. Performance Metrics: The solver provides information on the number of nodes expanded, the depth of the solution, and the runtime for each heuristic.
The performance of each heuristic is evaluated based on several metrics, including the number of nodes expanded, solution depth, and computation time. The Manhattan Distance Heuristic generally provides the best performance, balancing accuracy and computational efficiency. The project also discusses the trade-offs between different heuristics and their impact on the solver's performance.
This project demonstrates the application of heuristic search algorithms in solving the 8-puzzle problem. By comparing different heuristics, it highlights the importance of heuristic selection in optimizing search performance. The solver serves as an educational tool for understanding heuristic search techniques and their practical applications in problem-solving.
Pipeline Step | What I Did | Azure Equivalent |
---|---|---|
Data Ingestion | Loaded initial and goal puzzle states from CSV | Azure Data Factory |
Processing | Applied A* / BFS / DFS search logic in Python | Azure Databricks (PySpark) |
Storage | Saved results and comparison metrics in CSV | Azure SQL Database |
Modeling/Analysis | Compared algorithm performance (time, steps, nodes) | DBT (custom metrics modeling) |
Automation | Used automate.py to run experiments across inputs | Azure Logic Apps |
Versioning & CI/CD | Tracked code and structure in GitHub | Azure DevOps Git |