You might have heard of Sudoku, a popular puzzle where you fill a grid with numbers from 1 to 9. The catch is that each row, column, and small 3x3 grid can't have repeated numbers.
One day, I was reading about Sudoku solving algorithms. After a while of research, I decided to put my newfound knowledge into practice through a project.
The result is a simple JavaScript program ready to solve Sudoku puzzles with three different algorithms:
- Backtracking
- Genetic Algorithms
- Dancing Links
Backtracking
Backtracking is a general algorithmic technique that solves problems recursively. It searches every possible combination and eliminates every incompatible solution.
In other words, it tries different paths to solve a problem, going back when things don't fit.
This technique will attempt to fill each grid cell. However, whenever a rule is broken (like having the same number in a row, column, or section) it retraces its steps.
When we tackle harder puzzles with fewer guesses, the complexity of the algorithm increases and becomes slower in execution, and it fails sometimes.
Genetic Algorithms
Genetic algorithms belong to the class of evolutionary algorithms (EA) inspired by the process of natural selection to find the best solution to an optimization problem.
To solve a Sudoku puzzle with this approach, we will create a population of wrong solutions. Then we will crossover every two solutions to create the next generation at each iteration of the population's evolution.
To select the optimal solutions, our fitness function will calculate the frequency of wrong grid cells. This function is important to guide the randomness of the evolution towards some meaningful solution. This helps us move towards better answers instead of random ones.
I know, this kind of algorithms are not made to solve Sudoku puzzles. So I do more research and I found the golden algorithm to solve Sudoku puzzles efficiently.
Dancing Links
To solve exact cover problems, Donald Knuth invented the Algorithm X, it is a recursive algorithm which can be implemented with the dancing links technique.
According to Wikipedia: The exact cover problem is represented in Algorithm X by a matrix consisting of 0s and 1s. The goal is to select a subset of the rows such that the digit 1 appears in each column exactly once.
So to solve a Sudoku puzzle using Algorithm X, we need to convert the grid to a binary matrix in a such way every constraint (cell, row, column, section) should appear properly to choose one solution for every cell.
This is a portion of the generated matrix where green cells are 1s and empty cells are 0.
After puzzle encoding, we will apply Algorithm X on the generated binary matrix. Once a solution is found, we will decode it back to a sudoku grid solution.
For more information about that, here are some useful resources:
- Sudoku solving algorithms
- Solving Sudoku efficiently with Dancing Links
- Solving Sudoku with Dancing Links
- Exact cover problem - GeeksForGeeks
Finally
Thank you for reaching the end of this description. If you have any questions, or suggestions, or need help feel free to contact me.
Have a nice day ^_^