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.

sudokuusingcombinatorialevolutiondemo

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.

This entry was posted in Machine Learning. Bookmark the permalink.