This is my latest project, It is a sudoku solver by the use of backtracking. The objective is to be able to take a picture of a sudoku board and then be able to play on a GUI with the sudoku board you just photographed. For the purpose of this project, I divided it into two parts: Sudoku Solver and Sudoku Extractor.
Sudoku Solver
I have completed the Sudoku Solver part of the project, right now it is fully functional.
The sudoku solver uses backtracking to solve the sudoku board.
Backtracking
To understand what backtracking is as a concept lets think of everyday life and forget about the code side of things. When you make a mistake or a wrong decision and you realize that you have done so, you try to “backtrack” to when you made the decision and you had different “paths” or options you did not choose. We can see this logic in the diagram above, where a basic backtracking decision tree graph is displayed.
The coding implementation is more complicated than this also because usually backtracking is applied to recursive solutions which makes it hard to identify and therefore things are getting a bit to complex for this project review.
If you are interested you can find a detailed explanation of the algorithm and problem examples here : https://www.geeksforgeeks.org/backtracking-introduction/
If instead, you are curious about what the recursive backtracking is, you can find some answer here: https://www.cs.utexas.edu/~scottm/cs307/handouts/recursiveBacktrackingExplanation.htm
Sudoku Extractor
This is the part of the project I am currently working on. Grabbing the sudoku image from a .png or .jpg file is harder than I thought it was going to be. I have read numerous tutorials and most state the same steps so I have a good I idea of what the structure of my program will be like:
- Grid detection
- Extract the grid
- Extract the digits
- Recognize the digits
- Create an array with digits
I intend to use OpenCV to help me handle the image part of this project.
During research, I found this library “sudokuextract” which does literally what I want my software to do. I wanted to get it up and running so that I could see how it worked and draw up some ideas for my project but it seems to be filled with errors and problems trying to import features from other libraries it is based off. Now I am trying over and over to get this library to work but it seems pretty stubborn. (at least for now)
Code
If you have any suggestions or tips for my project please let me know, you can find the work in progress code here: https://github.com/NeriCarcasci/SudoluSolver