Implementation, comparation and testing of CSP solver algorithms based on Backtracking.
Implementation of different inference strategies (csp.py) :
- Pure backtracking
- Backtracking with forward checking (FC)
- Maintaining arc consistency (MAC).
Comparation of the strategies in terms of time complexity and number of backtracks.
Testing on Sudoku game instances.
The code in csp.py was taken from AIMA repository (https://github.com/aimacode/aima-python) with little modifications to simplify the algorithms and remove dependencies from other files (check comments for further info).
All the work and results are explained in the PDF paper included in this repository.
To reproduce the results of the paper you have to modify the parameters in main.py according to the test you want to execute (more detailed information can be found in the comments of the code) and then run it from there.
Python 3.6 or later is required to run the application.