Searching is the universal technique of problem-solving in AI. The search algorithms help you search for a particular position in single-player games such as tile games, Sudoku, crossword, etc.
This project by Team VALORANT aims to explore the search algorithms and compare them by implementing them in a single-player game like Sudoku. We learned new search algorithms from theoretical and practical perspectives through the implementation of the project. We also learned the properties, features, and limitations of each algorithm implemented.
We create a Sudoku from scratch and then solve using different algorithms to compare their results and performance. We also developed GUI to show algorithms’ working which helps others understand more clearly. Our final goal is to compare the algorithms on the following metrics: - Space Complexity: The maximum number of nodes that are stored in memory. - Time Complexity: The maximum number of nodes that are created. - Admissibility: A property of an algorithm to always find an optimal solution.
list of algorithms that we have implemented.
- Backtracking Algorithm
- Simulated Annealing Algorithm
- Genetic Algorithm
Import packages:
- To install pygames for GUI:
$ pip install pygame - To install simanneal:
$ pip install simanneal
- NumPy
- matplotlib
- time
- statistics
- maths
- random
To run this project:
$ python3 A_main.py
Code built-in Jupyter Notebook and Spyder, python version - 3.7.4
NOTE: Please be patient with genetic algorithm (It could take sometime as the result depends on the number of generations).
Link to access demo: https://drive.google.com/drive/folders/1QjDqkL9semF5GnBr0A_x8glGtCRmA1vm?usp=sharing