General
Sudoku Solver
A JavaScript Sudoku solver comparing Backtracking, Genetic Algorithms, and Dancing Links through puzzle generation and solution strategies.
Open projectAbstract
This project examines three approaches to solving Sudoku puzzles in JavaScript: Backtracking, Genetic Algorithms, and Dancing Links. The purpose was to compare how different algorithmic paradigms approach the same constraint satisfaction problem, from brute-force recursive search to evolutionary optimization and exact-cover modeling.
Problem
Sudoku requires filling a 9x9 grid so each row, column, and 3x3 section contains the digits 1 through 9 without repetition. Although the rules are simple, the search space can become large, making the puzzle useful for studying algorithmic efficiency and constraint representation.
Method
- 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 attempts to fill each grid cell. Whenever a rule is broken, such as 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.
This approach is useful for experimentation, although it is not naturally the best fit for Sudoku because the puzzle has strict constraints rather than a smooth optimization landscape.
Dancing Links
To solve exact cover problems, Donald Knuth invented Algorithm X, a recursive algorithm that 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.
To solve a Sudoku puzzle using Algorithm X, the grid must be converted to a binary matrix where each constraint, including cell, row, column, and section constraints, is represented explicitly.
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.
Outcome
The project shows how the same puzzle can be represented and solved through multiple algorithmic lenses. Backtracking provides an intuitive recursive baseline, Genetic Algorithms demonstrate an experimental optimization approach, and Dancing Links gives a more formal exact-cover solution for efficient constraint solving.