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.