Comparative Analysis of Search Algorithms on 8-Puzzle and 8-Queens Problems

Objective:

Generate numerous instances of 8-puzzle and 8-queens problems and solve them using hill climbing (steepest-ascent and first-choice variants), hill climbing with random restart, and simulated annealing. Assess the search cost and percentage of solved problems and graph these against the optimal solution cost.

Methodology:

1. Problem Generation:

   • Generate a large number of instances for both the 8-puzzle and 8-queens problems.

2. Algorithm Implementation:

   • Implement hill climbing (steepest-ascent and first-choice variants), hill climbing with random restart, and simulated annealing algorithms.

3. Problem Solving:

   • Apply the algorithms to solve the generated instances.

4. Performance Evaluation:

   • Measure the search cost and percentage of solved problems for each algorithm.

5. Graphical Analysis:

   • Graph the search cost and percentage of solved problems against the optimal solution cost for insights.

Results:

• Analyze the performance of each algorithm in terms of search cost and success rates.
• Comment on the effectiveness of hill climbing variants, hill climbing with random restart, and simulated annealing in solving the 8-puzzle and 8-queens problems.
• Provide insights into the strengths and limitations of each algorithm in combinatorial optimization.

Conclusion:

This project aims to evaluate the efficacy of different search algorithms in solving the 8-puzzle and 8-queens problems. By assessing search cost and success rates and graphically analyzing results against optimal solutions, we aim to gain valuable insights into algorithmic performance in combinatorial optimization scenarios.

Video link (with extras)

https://drive.google.com/drive/folders/1HBnr4pd2tAzRFSR4vz2YLfLYWbzl9dGl?usp=sharing