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