# Sudoku Solver

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

## 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.

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.