| Platform | Execution Time (for several thousand valid solutions) |
| C++ | 250ms |
| C# (.NET 1.1) after NGEN | 390ms |
| Java (JDK 1.4.2) | 680ms |
| C# (.NET 1.1) | 790ms |
I calculated the execution time by feeding the solver with a sparsely populated puzzle that has thousands of valid solutions (Sudoku purists will point out that this is a non-well-formed puzzle). The algorithm uses a slightly optimized brute force approach (my intention was runtime comparison, not building a hyperfast solver algorithm) - so it finds all the solutions.
The algorithm, when implemented in C++, delivers around 60.000 valid solutions per second on my 2.4GHz Athlon for average one-solution 9x9 Sudoku puzzles. The time it takes to solve one of those can hardly be measured, and I didn't want to inject the same puzzle a thousand times for the benchmark.
It depends heavily on the intial puzzle values, though. I digged out a puzzle - one that is considered more or less unbreakable for humans - that took the C++ implementation 15ms to solve. 15ms for one solution, mind you.
I doubt that there is a lot of optimzing potential for Java Hotspot other but compiling the algorithm's main method (which only consists of a few lines of code anyway) to native code as soon as possible. Dynamic memory allocation only happens for storing away solution arrays, and those are not going to be garbage collected until the end, so there is not a lot of optimizing potential on the memory management side. The .NET CLR should JIT all of the code at startup anyway. I did some tests to go sure, and the numbers did not change neither under Java and nor under .NET even after running the same stack of puzzles many times in a row.
Previos Posts:
Follow-Ups: