Sudoku rEvolution

A couple of years ago, I posted about a pet project of mine - my Sudoku Solver program. Over the years, I have continued to tweak it and I am pleased to say that it is evolving nicely.

In my previous post, I showed the results of solving a "Super Difficult" Sudoku puzzle from Carol Vorderman's "How To Do Sudoku" book using my Sudoku2 program. This puzzle required 496 recursions to solve and was solved in 228 milliseconds on my old Pentium D 3Ghz machine.

Well, computers have evolved. The same "Super Difficult" puzzle, using the same Sudoku2 program, was solved in just 156 milliseconds on a single core Windows 7 virtual machine with 1.5GB RAM, hosted on my Macbook Pro 2.4Ghz i5 machine. Not bad!

 Sudoku2 - SOLVED after 496 recursions in 156 milliseconds

 239 485 167

 751 396 284

 846 721 593

 628 173 945

 913 542 876

 475 869 321

 187 254 639

 364 918 752

 592 637 418

My latest version, Sudoku3, makes use of the same recursive, backtracking algorithm as its predecessor, but I have used Lambda expressions to dramatically simplify the code. I also implemented an optimisation to cache row, group and column assignments for cells and changed the algorithm to reduce the number of recursions. These changes have resulted in simpler code and significant performance improvements. Sudoku3 solves the "Super Difficult" puzzle in just 94 milliseconds on the same virtual machine. I am really stoked with these results!

 Sudoku3 - SOLVED after 248 recursions in 94 milliseconds

 239 485 167

 751 396 284

 846 721 593

 628 173 945

 913 542 876

 475 869 321

 187 254 639

 364 918 752

 592 637 418

I have uploaded the code for Sudoku3 to MediaFire for those who are interested.

In future, I plan to make use of threading to see if I can further improve performance by modifying the code to run parallel solution attempts on different processors. This is more tricky than it sounds. My first attempt showed that the thread management overhead resulted in a performance degradation.

I am going to try the new the new .NET Framework 4 parallel programming features and Reactive Extensions to see whether I can harness the power of parallel processing and make it faster. Watch this space...