## Solving Sudoku using Combinatorial Evolution

I wrote an article titled “Solving Sudoku using Combinatorial Evolution” in the November 2016 issue of Microsoft MSDN Magazine. See https://msdn.microsoft.com/magazine/mt788626.

If you’re reading this blog post, you almost certainly know what a Sudoku puzzle is. Most Sudoku puzzles you see in magazines are easy in the sense that they can be solved by using brute force where you repeatedly check each cell in the 9×9 grid looking for cells that can only have one legal value.

But some Sudoku puzzles cannot be solved this way. I tried several standard algorithms to solve difficult Sudoku puzzles but they didn’t work. So I created a custom combinatorial optimization algorithm.

Combinatorial evolution is a name I coined for the algorithm presented in the article. The algorithm borrows mostly from bee colony optimization (a form of swarm optimization) and genetic optimization (loosely modeling genetic mutation and crossover).

Each virtual Organism has a 9×9 grid that represents a possible solution. Here’s kind of what the algorithm looks like (with several important details, such as organism death and mutation, left out):

```initialize n Organism objects
loop maxEpochs times
for-each Organism
if Organism is a worker
examine a neighbor solution
if neighbor is better replace current grid
else if Organism is an explorer
examine a random solution
if better replace current grid
end-if
end-for
end-loop
return best Organism solution found
```

Anyway, the algorithm works in the sense that it was able to solve all the very difficult Sudoku problems I could find on the Internet.

The high level moral of the story is that in most cases standard algorithms work fine, and you should use them, but in some situations you must create custom algorithms.