Sudoku-Backtracking algorithm and visualization
Isn’t it cool to visualize the backtracking algorithm while solving Sudoku? Yeh, I am going to discuss the algorithm and also share how I developed a simple program to visualize the algorithm. About the program:
- Algorithm is in
Python - GUI is in
HTML, CSS, JavaScript/JQueryusingeellibrary of python. Read more about eel. - Check the full code on GitHub
Backtracking Algorithm
One of the classic algorithm which approaches a problem recursively to solve it. Trying to build the solution one by one and eliminating those which fail to solve. One of the famous problems is N-Quene Problem, you may have heard about it. Where N Queens need to be placed on the NxN board so that none of the queens are in attacking positions. Check out here to read more about the N-Queen problem here. Sudoku is also one of the famous problem/puzzles which can be solved using the backtracking algorithm.
In the backtracking algorithm, we build a solution tree for the problem and eliminate the solutions which do not satisfy the required conditions.
Sudoku
Sudoku is a number puzzle game in which numbers from 1–9 are to be placed in a 9x9 grid such that no numbers are repeated in each row, column, and 3x3 sub-grid/blocks.
How to solve using backtracking: We start with the first empty cell and iterate over 1–9 one by one, and if a number satisfies all 3 conditions i.e., that particular number is not present in the row, column, and block, we fill with that number. Then we move forward to the next empty cell and we do the same iteration of numbers but with the updated sudoku board. As we move forward with the new empty cell, we may reach a cell where we can’t place a number between 1–9. So, this solution is rejected and now we move backward and try new possible values in those previous cells. As we know that a sudoku board has only one solution, we will keep rejecting the solution until we find the one which satisfies all conditions for each cell that was empty initially.
The above code is validating the particular cell for the different values between 0–9. If the value satisfies all 3 conditions it returns true otherwise false.
The above function is called recursively to build the solution tree and reject all the solutions which do not satisfy the conditions. The value of the variable visualize is by default False which means it will not update the GUI and solve the puzzle quickly. If the value is true then GUI will be updated at each step while solving. So, to visualize the backtracking algorithm in action this variable needs to be True .
Generating the Sudoku
Moving a little forward, and let’s discuss how we can generate sudoku before we go to the visualization part.
How to approach?
- First thing is to generate a solved sudoku board.
- Second thing is to delete a few cells from the solved sudoku board such that it is solvable and the solution must is unique.
- Generating the solved sudoku board: The approach is very similar to that of solving the sudoku board. The only thing that changed here is that we have an empty board. So we can start from the first cell i.e., the upper-left cell, and fill the value randomly. Move to the next empty cell, now we have one value on the board so we have to check the sudoku conditions before filling with the value in the new cell. Again generate a random value between 1–9 and check for the sudoku conditions. If it satisfies all the conditions place the value in the cell and move to the next cell. At a point, it may happen that no values between 1–9 are possible for that cell then move back to the previous cells and try different combinations until the solved sudoku board is ready.
- Deleting cells to generate the puzzle: Randomly pick a cell that is not empty, remove the value then try to solve using our solving algorithm, and count the number of solutions. If the number solution is not one put the value back to the cell and try a different cell. Do this repeatedly until you get the required difficulty for the puzzle. 2 things to keep in mind
- The more cells you remove, the more difficult the puzzle will be.
- The more cells you remove, it will take more time to generate the puzzle.
Removing 30–55 cells will give easy to the very hardpuzzles. But removing cells beyond 55 cells will take much more time to generate the puzzle. This has been suggested that the minimum number of cells required as a clue for the sudoku puzzle is 17. That means you can remove up to 64 cells. But to find such a puzzle may be very time-consuming. I have not tested my algorithm to find such a puzzle and it may fail.
Visualize the algorithm in Realtime
GUI is developed using HTML, CSS, and JavaScript/JQuery. For connecting, frontend and backend eel library is used.
Eel is a little Python library for making simple Electron-like offline HTML/JS GUI apps, with full access to Python capabilities and libraries.
Check about eel on GitHub
eel allows you to call Python functions from JavaScript and vice-versa.
JavaScript Functions exposed to Python.
The function draw_sudoku displays the sudoku to GUI, here data is a parameter that has a 9x9 array, passed through python to JavaScript. Whereas update_sudoku taking parameters val and i from Python to update the GUI while solving the sudoku. Where val is the value for the cell i . Cell i means ith cell out of 81 cells.
Python Functions exposed to JavaScript
These functions can be called from JavaScript. For example, if you need a new puzzle, then click on the new puzzle button on GUI then JavaScript will call the generate_new_sudoku the function of python and pass the level as the parameter.
Visualizing Example:
Full Code
Find full code on my GitHub: https://github.com/tarunk04/sudoku-backtracking-visualizer
Feedback
That’s all for Today’s Post, if you have any questions please let me know in the comments. Also, if you found any error in the post please write to me at tarun12.tarunkr@gmail.com.
If you want me to cover some specific topics in the upcoming posts please let me know in the comments.
Follow:
Thank You for your the time to read this article. Please share it if you like.
I am looking for people with different skill sets to build a closed community so that we can build together awesome products. If you are interested reach me out on Linkedin or mail me tarun12.tarunkr@gmail.com
