I conducted a programming language benchmark a couple of months ago. One of the major concerns is that it is a microbenchmark that rarely measures the real-world performance. When I saw Google’s recent publication (PDF) on the real-world comparison of C++, Java, Scala and Go, I was wondering if I could consider to adopt these problems in my benchmark. Nonetheless, I quickly gave up because of its complexity and because I am not quite interested in the problem itself. Is there an interesting problem that is easy to implement and informative for measuring the performance programming languages? Sudoku.
Sudoku is probably the most popular puzzle nowadays. Lots of attempts have been made to solve Sudoku using programs. However, solving Sudoku is known to be an NP-complete problem, which means no efficient algorithm exists so far. Finding the solution largely relies on black magic. On the other hand, lacking a definite answer makes Sudoku more interesting. A variety of methods arise to solve Sudoku. Wiki gives a good brief view of the existing algorithms. I will focus more on the practical implementations.
A brief overview of Sudoku solving algorithms
Benchmarking several Sudoku solvers
To demonstrate how fast a Sudoku can be solved and how the solving speed may be affected by implementations, I briefly evaluated the performance of a few solvers using 20 very hard Sudoku puzzles repeated 50 times (1000=20×50 Sudokus in total). Some of these solvers are casual implementations and not to be perform well. I just choose a few to show the impact of algorithms and implementations. The following table shows the result of solving these 1000 very hard Sudokus.
|Solver||Algorithm||Test Unique?||Language||Time (sec)|
The third column indicates whether the solver finds the first solution only or confirms the input Sudoku having a unique solution. Finding all solutions is typically 50-100% slower than stopping at the first solution.
So far as I know, JSolve and fsss are the fastest Sudoku solvers to date.
JSolve based on BB_sudoku, Brian’s famous Bit Based Sudoku Solver. These three solvers are all based on generic backtracking instead of DLX and all introduce advanced tactics in addition to the basic naked/hidden single rules.
Kudoku is my solver. The basic idea comes from Guenter Stertenbrink’s suexk with some improvements. Kudoku is first implemented in C and then ported to a few other programming languages. It is not the fastest solver, but much simpler than JSolve and fsss.
The speed difference between the four Java implementations is striking. My solver is 1000-10000 times faster than the other three solvers. This proves how important the algorithm is to solving Sudoku puzzles. Choosing the right algorithm can make a huge difference.
EDIT: After I published this post, Boris Borcic has kindly sent me his Python solver (sudoku-bb in the table above), which is easily the fastest among the Python solvers I know. This solver is extremely interesting for two reasons. Firstly, by algorithm, Boris’ solver is not much different from my solver, both based on the exact-cover matrix without dancing. The major difference is sudoku-bb uses Python native functions more while my version, which is literally translated from C, heavily relies on deep nested loops (because I do not know python well). Although my version has smaller time complexity (I believe) and is ~50% faster with Pypy, sudoku-bb is 3X as fast with CPython. This example shows how important it is to make the best use of native routines.
Secondly and more importantly, Boris’ solver relies on a very interesting property of Sudoku: if the Sudoku has a unique solution, using “naked singles” and “hidden singles” rules guarantees that at each step, there are at most two choices. Neither he nor I cannot prove this, but it is true for ~100,000 hard Sudoku puzzles. I do not know if this is a known conclusion (we should ask mathematicians). Using this property can simplify coding, but disables unique solution checking.
- The fastest Sudoku solver can solve even the hardest Sudoku in about 1 millisecond and solve most others in 0.1 millisecond.
- An inefficient algorithm can be 3 to 4 order of magnitude slower than an efficient one, so choose the algorithm carefully.