Introduction
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
Solving Sudoku puzzles can be reduced to a graph coloring problem, or more often an exact cover problem that can be solved with Knuth’s elegant Dancing Links algorithm (DLX). There are DLX-based solvers in C, C++, Java, C#, Python, Ruby and Javascript. Google search will give you many more. These solvers are usually fast, but for the few I have tried, they are not the fastest. To the best of my knowledge, the fastest implementations for each programming language are all based on generic backtracking without using DLX. The basic idea behind these fast solvers is simple: we select the cell or the constraint with the minimum choices, fix to one number and move forward; when a cell is left with no choice, we go back to the previous step and select the next allowed number. The key to fast solving is to quickly find cells that can be determined with simple logic, including at least the naked single and hidden single rules. Fast solvers may employ a little more advanced logic (e.g. locked candidates) if that can be computed fast. The rest is data structures and details which vary a lot and also matter a lot. It is the great variability in algorithms and implementations that makes Sudoku fascinating.
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) |
---|---|---|---|---|
JSolve | backtracking | Yes | C | 0.25 |
kudoku | backtracking | Yes | C | 1.1 |
fast_solv_9r2 | DLX | Yes | C | 1.4 |
kudoku | backtracking | Yes | Java | 2.0 |
kudoku | backtracking | Yes | JavaScript | 6.3 |
kudoku | backtracking | Yes | Lua | 7.5 |
sudoku-bb | Backtrack | No | Python | 33.5 |
sudoku-gh | DLX | Yes | JavaScript | 41.2 |
Peter Norvig’s | backtracking | No | Python | 147.4 |
kudoku | backtracking | Yes | Python | 190.5 |
sudoku-pk | backtracking | No | Javascript | 278.4 |
sudoku-aa | DLX | Yes | Python | 514.0 |
sudoku_db | backtracking | No | Python | 1915 |
Sudoku_bc | backtracking | Yes | Java | 2180 |
Sudoku_dl | unknown | No | Java | 2975 |
Sudoku_6l | brute-force | No | Java | 25385 |
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.
Discussions
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.
Peter Norvig has also implemented a nice solver in Python, which has been ported to Ruby and Javascript among a few others. “sudoku-pk.js” is one of the Javascript ports. Note that Peter’s solver stops at the first solution (if I am right), while Kudoku finds all solutions. If I make Kudoku find one solution only, it takes 100 seconds, faster than other Python implementations.
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.
Conclusions
- 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.
- I have added Sudoku solving to my programming language benchmark as a performance measurement for a real-world application (incomplete right now). The Javascript solver is also available online. You may get a sense how fast it is to solve Sudoku puzzles, unless you are using IE 6/7/8 which are known to have crappy Javascript engines.
Hello,
I stumble onto your blog, and I thought it’s an occasion to pass on a pure python 2.5 sudoku solver (pure in the sense that the solver doesn’t import any module), that I wrote back in ’06 is about 35 slocs and is quite fast (it does your 1000 solutions test in less than 21 secs). I couldn’t find an e-mail adress, though, so I include it here in between code tags counting on the blog platform not to mangle the code. At the price of doubling code size, I managed to gain about 10% in speed. As for implementing Knuth’s dlx in python, it only makes sense if you use a code acceleration like psyco and pypy. At the same period I wrote a dlx implementation that ran just slightly faster (than the attached code) but only when accelerated using psyco.
Cheers, Boris Borcic
Attractive Chaos Edit: I have moved Boris’ source code here under his consent.
Chaos mentions that you use a “two-choice maximum” rule to speed up backtracking, but that this means you can’t verify unique solutions.
Does this also mean that if you feed in a puzzle with multiple solutions, your program isn’t guaranteed to find one?
This means that the solver can’t reach a solution that is not attainable by complete propagation of constraints alternating with the non-deterministic choice of one possibility among two from a cell that at the time of choice only admits two possibilities. In particular, the solver can obviously be made to fail by feeding it a sufficiently underdetermined problem easily solvable with brute force (for instance the completely undetermined problem). Otoh, this solver quickly found a solution to any from the thousand problems from public problem lists on the internet.
It is also written not to look for further solutions once it meets one, but it is a minor modification to make it completely explore the search space subject to the restriction to 2-possibilities choice points. I guess the easiest to do, to learn more on the matter, would be to offer a bounty for a problem that has (possibly many solutions but) a -single- solution -not- attainable by such a solver.
To keep to the terms of your question, no, it can’t offer the required guarantee, but further than relatively trivial problems cases for which it will obviously fail, its failure domain is ill understood and seems in practice not to intersect with real sudoku problems.
2-choicepoints are actually many enough in difficult problems that it makes sense for the algorithm to become picky on which to use. I did in fact experiment with tuning a quickly computed decision heuristic on whether to keep some 2-choicepoint as “good enough” or go looking for a better one to use. Even though the slowness of Python doesn’t allow much sophistication on that road, this allowed me to shave a good 10% running time over my testing corpus.
My expectations concerning the use of
tags weren't met, obviously - although they were deleted :( I'll send the code to you by email reply - mine is bborcic [at] gmail
Cheers, Boris Borcic
Hello
I’m author of Fast_Solv_9r2, witch (Sudoku Fast solver version 9 revision2)
Just to point Knuth’s DLX still is a backtracking algorithm. What it makes special is the way its decided when to backtrack.
By the time I make that code it was fast, maybe fastest solving general sudoku problems. Several faster programs appeared and finaly come Brian Turner with his BB_Sudoku and record solving time. Uses Logic first, then backtracks.
Cant say if solving sudoku is the best way to benchmark languages, but for sure you should think to make bigger sudoku problems sets, in the way times are higher and better measured. Current hardware is very fast!
Ignacio.
If I used a large data set, the slowest implementation would take days.
In my understanding, most naive algorithms only use the “naked singles” rule. Better algorithms use the “hidden singles” rule, which is a little bit harder to code. With the exact-cover binary matrix, the two rules are naturally applied. BB_Sudoku uses the “locked candidate” rule in addition to naked/hidden singles rules. It is able to use other rules as well, but not by default, probably because considering complex logic involving multiple cells takes more time than simply backtracking. JSolve optimizes BB_Sudoku a little bit and thus faster. I do not know the algorithm behind fsss.
Similar to suexco, my algorithm takes the exact-cover binary matrix but without dancing. I know DLX is a special way of doing backtracking. Wiki is very clear about this.
I’m sure, you’re aware of DEK’s qnd hack of ‘sudoku.w’ (CWEB, http://www.cs-faculty.stanford.edu/~knuth/programs/sudoku.w). In combination with DEK’s ‘dance.w’ (CWEB, http://www-cs-faculty.stanford.edu/~knuth/programs/dance.w), it can be used in a Unixish pipe to solve sudokus: echo ‘…..5.74 […] 36.5…..’ | sudoku | dance 1. The resulting output is not easy to read at first glance, but by hacking some code in AWK a/o Ruby, it can transformed into human-readable form.
[…] de un tiempo de ejecución de segundos a otro de años. Por ejemplo, aquí podéis encontrar una comparativa entre diferentes programas para resolver Sudokus (con tiempos de 0.25 segundos a 7 […]
I also have a sudoku solver here: http://www.vantasyworld.com/fun/sudoku/sudokusolver.html
How well does it compare to the others?
Can the above detect unsolvable sudokus? Mines should!
[…] real time! The Sudoku solver the authors used was Brian Turner’s open source solver. (Here is a review of solvers.) Very impressive… […]
A easy way to speed the Boris Borcic program is to pass the globals into search so Python spends less time having to look them up, that saves about 2.5% runtime on my PC. The Peter Norvig program can be speeded by removing the duplicated calls to len(values[s]) in the eliminate function by storing the return, that’s about a 5% saving.
I had to program a sudoku solver for a class. I found your entry pretty late–my work is pretty much done, and I’m not starting over, even with the Kudoku approach, which is arguably better than mine.
To test my implementation, I generated about 12,000 puzzles. (It turns out that over these, Kudoku is roughly 1.7 times faster than my program. Close enough.) Much to my surprise, though, the generator came up with that grid:
6….894.9….61…7..4….2..61……….2…89..2…….6…5…….3.8….16..
It takes about 21 ms to solve with Kudoku on my computer, which is by far the hardest grid I could find for it. It’s roughly 3 times longer to solve than the longest puzzle in the ‘hardest puzzles’ list.
So I thought I’d share it. I’m not creative enough to give it a name.
Thanks a lot. Actually my calling those 20 as “hardest” is not quite right. The “hardness” is with respect to the algorithm. A sudoku hard for one solver may be easy for others. Thanks again.
I have written an article about solving and generating Sudoku using backtracking and Human-like aproach. Backtracking is implemented in Java and C++, human-like approach in Java. Also several popular solving strategies are described there.
http://en.algoritmy.net/article/42521/Sudoku
What CPU did you use to run the tests?
[…] of Sudoku’s at the same time for some proper bench-marking, something like what was done here, but for now this screenshot will have to do! This same Sudoku took around 0.433 seconds the last […]
[…] be seen below, I found an interesting difficult set of Sudoku’s on another blog (thanks to attractivechaos) that I’ve been testing with, and modified the input system of the application so that it […]
[…] there have been some very fast Sudoku-solving algorithms produced, a basic backtracking algorithm implemented efficiently will be hard to beat. Even a […]
I just tried out your Java implementation of kudoku, and ran it against 2365 hard puzzles. It solved them all in 1,5 seconds, 0,7 if I didn’t print the solutions. It even took less than a second to print out about 6300 solutions for one of those puzzles from which I removed a couple of cells.
I have to say that I am surprised. I was expecting DLX to be faster than backtracking, since backtracking revolves around trial-and-error, and could possibly go through hundreds of millions of choices before finding the right solution.
But you have obviously done your job very well with this, and I tip my imaginary hat to you, good sir.
[…] I decided to also measure performance, using the same approach as attractivechaos in the blog post An incomplete review of Sudoku Solver Implementations. The author uses 20 really hard Sudokus that are solved repeatedly 50 […]
I wrote a fun sudoku solver, and it is quite fast. Why don’t you try it out against your own solution? http://www.codeotaku.com/journal/2011-05/solving-sudoku-efficiently/index
Please modify your program to read my input file: https://github.com/attractivechaos/plb/blob/master/sudoku/sudoku.txt. This is largely the standard input for sudoku solvers. Usually a solver not accepting batch input is slow.
I recently have written a python Sudoku solver, which I intend to make it run fast. For the 20 hard puzzles, it is still about 1/3 slower than Norvig’s algorithm; but on sets of simpler puzzles (such as those 40000+ 17-clues), it is about 1/3 faster.
Hi, I am the author of fsss. Some of the tricks I used are inspired from Brian’s BB Sudoku. I focused on tasks different than just solving and optimized the solver for multithreading/parallelism, earlier determination of invalid puzzles, etc. For most of the solving modes even the solved cells’ content isn’t recorded. More recent upgrades are available in my more general sudoku tool “gridchecker” – it is free and periodically I am publishing its source code.
To my knowledge the fastest solver for the moment is ZSolve (http://forum.enjoysudoku.com/post225783.html#p225783). It is about 2 times faster than fsss.
Thanks for the update!
[…] Rather than write my own from scratch, for this part of the development, I wanted to use an existing implementation of the machine-like solver. After a little research (more on this some other time), I found one I liked a lot — the Kudoku solver written in Java from attractive chaos. […]
It’s interesting to see how things have progressed since 2011. Below are benchmarks on several datasets including, for reference, two of the fastest solvers listed above and then a bunch of contemporary solvers. (I hope the formatting is readable).
If I have the history correct ZSolve, which Mladen mentions above, became JCZSolve in collaboration with the author of JSolve and others. Its profile was similar JSolve but strictly faster. Around the same time Mladen developed FSSS2, which was faster than JCZSolve for most practical use cases, but a little slower for hard puzzles. Then came SK_BFORCE2, a derivative of and improvement over JCZSolve. Last, and very recently, came my solver, Tdoku, which was optimized with a focus on hard puzzles.
It’s hard to strictly order these solvers without use cases in mind since they each have different strengths and weaknesses.
|puzzles1_17_clue | puzzles/sec| usec/puz| %no_guess| guess/puz|
|----------------------------|-----------:| -------:| --------:| --------:|
|kudoku | 37,547.7 | 26.6 | NA | NA |
|jsolve | 171,679.8 | 5.8 | 50.0% | 3.21 |
|jczsolve | 290,958.0 | 3.4 | 69.6% | 1.86 |
|tdoku | 303,742.6 | 3.3 | 78.7% | 0.63 |
|fsss2 | 305,781.3 | 3.3 | 72.5% | 1.31 |
|skbforce | 379,242.8 | 2.6 | 73.7% | 0.99 |
|puzzles6_serg_benchmark | puzzles/sec| usec/puz| %no_guess| guess/puz|
|----------------------------|-----------:| -------:| --------:| --------:|
|kudoku | 75,409.6 | 13.3 | NA | NA |
|jsolve | 236,083.1 | 4.2 | 0.0% | 8.43 |
|jczsolve | 309,202.9 | 3.2 | 0.0% | 7.09 |
|skbforce | 347,680.1 | 2.9 | 0.0% | 7.08 |
|fsss2 | 381,116.3 | 2.6 | 0.0% | 7.76 |
|tdoku | 391,696.0 | 2.6 | 0.0% | 7.13 |
|puzzles2_magictour_top1465 | puzzles/sec| usec/puz| %no_guess| guess/puz|
|----------------------------|-----------:| -------:| --------:| --------:|
|kudoku | 9,312.3 | 107.4 | NA | NA |
|jsolve | 47,069.9 | 21.2 | 0.1% | 30.56 |
|fsss2 | 70,848.7 | 14.1 | 1.7% | 19.22 |
|jczsolve | 77,886.9 | 12.8 | 2.2% | 20.78 |
|skbforce | 86,714.0 | 11.5 | 3.6% | 15.44 |
|tdoku | 114,934.7 | 8.7 | 7.9% | 9.05 |
|puzzles5_forum_hardest_1106 | puzzles/sec| usec/puz| %no_guess| guess/puz|
|----------------------------|-----------:| -------:| --------:| --------:|
|kudoku | 1,113.4 | 898.2 | NA | NA |
|jsolve | 4,414.8 | 226.5 | 0.0% | 388.77 |
|fsss2 | 6,503.4 | 153.8 | 0.0% | 277.08 |
|jczsolve | 6,606.7 | 151.4 | 0.0% | 366.43 |
|skbforce | 7,263.5 | 137.7 | 0.0% | 271.29 |
|tdoku | 12,966.6 | 77.1 | 0.0% | 113.21 |
Thanks for the update. Very interesting!
Thanks for your write-up and as Tom mentioned it’s interesting how things have changed in the last 8 years. I am currently working on a constraint programming solver so a general solver but using sudoku as an example in my blog. I use graph theory in my latest post to speed things up but specialized solvers are way faster. Mine is quite a bit better than Norvig’s solver but that’s about it.
Maybe some of you are interested in the different approach and maybe the full constraint solver: https://opensourc.es/blog/constraint-solver-alldifferent
I like it. Thank you.
I have developed a number junctions game that’s similar to Sudoku in which a
number can not be used more than once in any column or row. I have called it
Sudoku Octangles:
Android:https://play.google.com/store/apps/details?
id=air.Ganaysa.SudokuOctangles
iOS: https://itunes.apple.com/app/id1480851707
Amazon: https://www.amazon.com/dp/B081VVC1G9/
I hope you like it.
Thanks for this. I am quite impressed with how fast some of these solvers are. Turns out there is quite some room for improvement for my own solver…
I wrote gss (https://github.com/bartp5/gss). It is a bit more generic solver that can do many types of sudokus like jigsaw, X, NRC, etc. You can look at the bottom of https://bartp5.github.io/gss/ to see examples of what it can do. It certainly is not as optimized as these solvers and I suppose it is a bit harder to optimize as my solver does not only deal with one specific sudoku topology. I thought is was interesting to see how my solver compares so I added it to the benchmark tool from t-dillon. My solver implements “levels” of logic it can apply from 1 till the blocksize-1 (i.e. 8 in a standard sudoku). If logic fails it resorts to backtracking. Here are some results:
|puzzles5_forum_hardest_1106 | puzzles/sec| usec/puzzle| %no_guess| guesses/puzzle|
|————————————–|————:|————:|———–:|—————:|
|gss | 35.7 | 28,009.4 | N/A | N/A |
|gss1 | 414.2 | 2,414.3 | N/A | N/A |
|fast_solv_9r2 | 852.5 | 1,173.1 | 0.0% | 372.40 |
|kudoku | 684.8 | 1,460.2 | N/A | N/A |
|jsolve | 2,889.5 | 346.1 | 0.0% | 389.12 |
|tdoku | 8,205.3 | 121.9 | 0.0% | 113.13 |
Here gss is my solver with the maximum level logic and gss1 only applies basic elimination.
Obviously, my higher levels of logic are not so efficient as they slow down the solution of hard puzzels by more than a factor of 10. However, I find (unsurprisingly) that backtracking scales very very poorly so higher levels of logic are required for larger sudokus (gss can do blocks sizes up to 128 when compiled with 128 bit integers, i.e. up to 100×100 sized sudokus with the standard topology).
Cheers,
Bart
Isn’t it strange that less logic performs better in your case if I understood it correctly? My general constraint solver solves about 200 per sec (on the Top95 dataset…) (as much logic as possible without backtracking and the rest with if not solved yet)
Ongoing series about it: http://opensourc.es/blog/constraint-solver-1
on the top95 set I get
|gss | 697.5 | 1,433.7 | N/A | N/A |
|gss1 | 2,395.8 | 417.4 | N/A | N/A |
So less logic is quite a bit faster. When I see the fast solvers here it seems they all do only logic that can be evaluated very fast and do the rest with backtracking. The grid is not so big and if you choose fields with few candidates, this is not all that expensive. Obviously, it also depends on how well the logic is implemented and if you have larger sudoku grids backtracking will quickly limit your performance.
[…] de un tiempo de ejecución de segundos a otro de años. Por ejemplo, aquí podéis encontrar una comparativa entre diferentes programas para resolver Sudokus, con tiempos de ejecución que pasan de 0.25 […]
Coming back to this yet a decade later, I see this UFO piece of code deserves a better shrine. A less confused story. The wasted meantime, unfortunately, had AI evolve a new spot common-sense meaning for “algorithm”, which steals light from expounding the glories of the UFO.
10 years back, I could have made a splash by adjusting Knuth’s and mine to dance in parallel. More exactly, start with pure python implementations of both, instrument them at least enough to verify sync if it happens, and then tweak them towards performing a parallel detailed dance on identical input. The timely reward of success with it: perhaps evolving the intelligence of the name of algorithm — very much vanished.
@attractivechaos on the importance of “knowing native routines, etc”. It’s mostly the solid performance of Python sets of integers (even if the code tracks cardinalities to save on copying sets).