C++ QT Sudoku Solver
My first big personal project was to create a sudoku solver which shows the process that a computer takes when solving a sudoku board. The method used was a recursive backtracking algorithm. I chose this because it is likely the fastest to reach a solution especially with a simple board. This would also allow me to use threading with a GUI. I used C++ and QT to complete this project.
This project was split into multiple sections to help complete the project
Creating the GUI with instant solving.
Within QT I started with a button and a single Table Item to act as the Sudoku board. When the board is partially filled and the button is hit the solution needs to show up immediately. This will help me make sure that I am solving correctly and writing the QT item to an array to then solve. For the solving algorithm I found a set of functions online that could solve a 2D array that was declared as a global variable.
Creating a Thread to handle solving
Once I got this working I could use QT Concurrent to handle multithreading. The reason that this needs to be multithreaded is because the main thread needs to be free to update the GUI and cannot be stuck in a function trying to solve the solution. Using QT Concurrent and an additional class with all the same solving functions I could print to the output from the other thread while still having the main thread active. Then using slots and signals I could connect a signal and slot from the worker thread and main thread notifying that there has been an update to the sudoku board. When the main thread received this signal I could update the GUI and the main thread would go back to waiting for another update. This worked like a charm and showed the output as the solving happened.
Beautifying the program
The next step was to make the GUI prettier as well as adding exception handling for bad inputs. All of them are as follows.
Clear the board button - Clears the board of the current solution and clears the board.
Undo Solution button - Added a variable that keeps the pre-solution array which can then be restored at any point.
Speed Slider - Added an input to the thread which takes a speed value from the GUI which will tell the thread how long to sleep between iterations.
Stop solution button - Button to kill the thread in it's tracks. This emits a stop variable to the thread which gets picked up and returns out of everything.
Pre-solve Checks - Check before solving to make sure it is a valid solution as well as all the numbers are between 1 and 9.
Grey out filled in cells - Before a solve I gray out the cells that have numbers in it which can help when visualizing the solve.
Lines in board - Added thick lines to help show the 3x3 cells in the board so it not just a big array.
Future Ideas
I have a few ideas on how to make this program a little more fun and to add complexity.
Add an output to show how many valid solutions are possible with the current board. This would require a bulk solve and counting how many can occur which can be very time intensive.
The color of a cell could show if that value is the cell's final number to show how close it is to the final solution.
A few buttons to create an easy, medium, or hard problem automatically generated. This would probably require more beautification to help make the GUI more attractive to look at and work with.
The project is cataloged in the following YouTube Video as well as on GitHub.
Within the GitHub link you should be able to download the zip and run the exe file directly.
