Sudoku Solver

Solving sudoku as a constraint satisfaction problem (CSP).

Description

This repository is an exploration of various algorithms and heuristics which can be used for solving the classic Sudoku puzzle in python. The sudoku_solvers.py has several classes each employing a different strategy for solving the sudkou problem. You can also enjoy the visualization by running the MAINMENU.py file. The GUI has been built using python's inbuilt tkinter library. You can enter your own Sudoku puzzle or load a random puzzle for solving.

Visualization Demo

1. Run the MAINMENU.py file.
2. Choose your algorithm. Default is Backtracking.
3. Enter your puzzle or load a random one from the dataset.
4. Click on Instant Solve/ Visualize.

WARNING: The Backtracking algorithm might take some time for certain problems since it is very naive. The Contraint Propagation algorithm is a lot faster.

Using the solvers

Use the classes in sudoku_solvers.py file to solve sudoku puzzles in the form of 2D lists in python. Currently, the CP_with_MRV is the most efficient solver of all the classes I have implemented.

1. Create a Sudoku puzzle with blanks marked by 0's:

>>> puzzle = [
...             [5,3,0,0,7,0,0,0,0],
...             [6,0,0,1,9,5,0,0,0],
...             [0,9,8,0,0,0,0,6,0],
...             [8,0,0,0,6,0,0,0,3],
...             [4,0,0,8,0,3,0,0,1],
...             [7,0,0,0,2,0,0,0,6],
...             [0,6,0,0,0,0,2,8,0],
...             [0,0,0,4,1,9,0,0,5],
...             [0,0,0,0,8,0,0,7,9]
... ]

2. Import one of the sudoku-solver class and create its object. Call the solve_sudoku() method to solve the puzzle. The solution is stored in the object's sudoku_soln attribute. (Note that the pprint has only been used for formatting the list.)

>>> from sudoku_solvers import CP_with_MRV 
>>> from pprint import pprint
>>> obj = CP_with_MRV()
>>> obj.solve_sudoku(puzzle)
>>> pprint(obj.sudoku_soln)
[[5, 3, 4, 6, 7, 8, 9, 1, 2],
 [6, 7, 2, 1, 9, 5, 3, 4, 8],
 [1, 9, 8, 3, 4, 2, 5, 6, 7],
 [8, 5, 9, 7, 6, 1, 4, 2, 3],
 [4, 2, 6, 8, 5, 3, 7, 9, 1],
 [7, 1, 3, 9, 2, 4, 8, 5, 6],
 [9, 6, 1, 5, 3, 7, 2, 8, 4],
 [2, 8, 7, 4, 1, 9, 6, 3, 5],
 [3, 4, 5, 2, 8, 6, 1, 7, 9]]

Credits

• The primary motivation for building this project came from the video Python Sudoku Solver - Computerphile.
• For improving the performance of the algorithms, I have been extemsively referring to this awesome book Artificial Intelligence: A Modern Approach.
• The Data folder contains a subset of the original dataset: 3 million Sudoku puzzles with ratings. The puzzles are used in the GUI if you wish to visualize the solving of a random puzzle. They are also been used for measuring the performance of the algorithms in the puzzle_extractor.py file.
• Credits to iotarepeat for suggesting and implementing bitarrays for saving domain information for the puzzle during constraint propagation which resulted in a significant performance improvement. His contributions to the report generation in puzzle_extractor.py are also noteworthy.

Future Work

Will be experimenting with some other heuristics as I learn more and I'll keep committing the code to the repository.

License

The repository is licensed under MIT License.

Contributing

1. Fork it (https://github.com/fork52/Sudoku-Solver/fork)
2. Create your feature branch (git checkout -b feature/fooBar)
3. Commit your changes (git commit -am 'Add some fooBar')
4. Push to the branch (git push origin feature/fooBar)
5. Create a new Pull Request