## Solving *Some* Sudoku Puzzles Faster (I Stand Corrected)

Okay. So maybe I was jumping to conclusions a little early in the game.

After I posted my own modified version of Peter Norvig‘s Sudoku Solver, Peter and I had some brief discussion about my results and conclusions. I had only compared the performance of the two algorithms based on the ninety-five difficult puzzles provided by Peter, but he was not convinced. So I set out to make a more rigorous analysis of the relative strengths of our approaches using the method for generating random puzzles included in the original code. The results were a little unexpected, but not very surprising.

**Fair game.**

To make this a fair competition, I made some slight modifications.

Firstly, I had to ensure that both algorithms were solving the exact same random puzzles. Otherwise one algorithm might, simply by virtue of some serious bad luck, end up with more difficult puzzles. This is especially important since Peter’s experiments showed that long execution times (difficult puzzles) are rare but have an extreme impact; a few puzzles taking more than a minute to solve.

Secondly, I modified the code so that it uses the timeit module for measuring execution times. This allowed me to measure execution times more precisely.

**More pudding.**

Overnight, one million random puzzles were attempted by the two competing algorithms (999.925 were actually solved). Peter’s original algorithm required an average of 0.007 seconds per puzzle (142 puzzles per second) with a maximum execution time of 91.06 seconds. For the same puzzles, my modified version required an average of 0.008 seconds per puzzle (124 puzzles per second) with a maximum execution time of merely 5.75 seconds.

Both these averages are far lower than those for the ninety-five difficult puzzles attempted earlier, but the maxima are orders of magnitude higher. This seems to indicate that most of these random puzzles are easier to solve; save for a few extreme puzzles. This is in line with Peter’s earlier findings.

The original algorithm solves these random puzzles about fourteen percent quicker on average, but the distribution of execution times is more spread out; as is evident from the much larger standard deviation and higher maximum.

**Mea culpa. But not for maxima.**

Based on these findings I have to admit I was wrong. My modified algorithm does not solve *every* Sudoku puzzle faster, as the title of my previous post implied. When solving many, randomly generated puzzles the original is slightly faster on average.

But when the task at hand involves more difficult Sudoku puzzles, or when you are operating under strict time constraints (i.e. you want more certainty about the maximum time required to solve a single puzzle), my money is still on the modified version. The exact puzzle that required the original algorithm 91.06 seconds to solve took the modified version a mere 0.0079870224 seconds. I’d say that is an improvement.

**There’s a tool for every job.**

When we were discussing how Peter had generated the graphs he used in his article, I remarked (tongue-in-cheek) that copying and pasting execution times into a spreadsheet sounded a lot like brute-force manual labour to me. I think his response summarizes this whole exercise for me quite well.

Yes, but sometimes a little brute force is easier than figuring out how to do an elegant solution.

It seems to me now that sometimes a little brute force is not only easier, but that it can be faster than a more elegant solution as well. Many thanks to Peter for posing questions and pushing me to dig a little deeper.

**Sir, I stand corrected!**

[…] Update (februari 5th): Okay. So maybe I was jumping to conclusions a little early in the game. Mea culpa. […]

Solving Every Sudoku Puzzle Faster « Corporate NinjaFebruary 5, 2011 at 14:36

So is there no way to make your modified version faster for the easy puzzles?

Time to write a genetic algorithm?

Sjors ProvoostFebruary 5, 2011 at 15:56

There might be some performance to gain still, but my Python skills are pretty weak. Might have a look later. Stay tuned. π

Not sure how you would apply a genetic algorithm to this problem exactly. Why not give it a go yourself? Curious to see what you come up with.

lukasvermeerFebruary 5, 2011 at 17:57

Genetic algorithm might be overkill, but you mention several heuristics in your posts and Peter also suggests that timing can be important. So could run the code through all combinations and see which one performs best. E.g. run original algorithm for 0.01 … 0.5 seconds.

I am already satisfied with your observation that all Sudoku puzzles can be solved faster by a computer than by a human; that’s one more argument I can use to convince people to use their cognitive surplus for something more interesting than manually solving Sudoku puzzles π

Sjors ProvoostFebruary 6, 2011 at 04:37

Like I said to Peter, I might tweak a hybrid later; just to see if I can rev this baby up some more. Sure beats solving them manually, indeed. π

lukasvermeerFebruary 7, 2011 at 12:53

Lukas, you shouldn’t surrender so easily! While the original algorithm might have a slightly better mean time, I would say that the performance characteristics of your algorithm is better overall — for me (and I think for most people) and in most use cases, it would be worth it to give up .001 seconds in the average case to get such a dramatic reduction in the bad cases. And if you want to get the best of both, you could just run the original algorithm for maybe .2 seconds, and then switch to yours — that should improve both average time and variance.

Peter NorvigFebruary 5, 2011 at 23:54

Peter,

Good to hear you consider the reduction in standard deviation worth the (slight) performance impact. I fully agree that the modified version would be better for most use cases.

That being said, the title of my previous post was “solving EVERY sudoku puzzle FASTER”, and that is one of those use cases where I think mean execution time is more important than anything else. Assuming the million random puzzles I tested on accurately represent all sudoku puzzles in existence, your algorithm is simply better suited for that particular use case than my modified version. Thereβs a tool for every job.

I like the idea of a hybrid approach. I can see some potential pitfalls, but it should be possible to switch to more complex rules only when needed.

The main problem with that approach would be that both algorithms check constraints only as options are eliminated. Switching to more complex rules would mean you either start from the beginning of the puzzle (and lose everything you’ve done so far) or re-evaluate previously eliminated numbers (to see if the more complex rule might have been applied there). Both probably result in quite some additional computational work.

I would propose an alternative approach to limiting the execution time of the original algorithm by switching after 0.2 seconds. I reckon that the original algorithm is fast, because it can solve many puzzles without ‘searching’. Long execution times probably occur when ‘searching’ leads to many incorrect assumptions being made and being tested.

Based on that insight, I would want to keep the original algorithm intact as much as possible. The algorithm should only switch to testing more complex rules when it gets stuck, before it attempts to ‘search’. The complex rule thus serves as a ‘last resort’ before the searching strategy is applied. I’m hoping this would give us the best of both worlds.

What do you think of this approach? I might implement this later (I might have to brush up on my Python skills).

Regards,

Lukas

lukasvermeerFebruary 7, 2011 at 12:51

> Assuming the million random puzzles I tested on accurately represent

> all sudoku puzzles in existence

That’s not necessarily the case. There are 5,472,730,538 essentially different sudoku solutions [0], let alone puzzles, and you only sampled a million puzzles. If you are lucky, there exists one puzzle out there that takes more than 0.01 * number_of_puzzles seconds.

That just leaves these questions:

1 – how many essentially different (solvable) Soduko puzzles are there?

2 – can you prove that there is an upper bound to the time the a) original and b) modified algorithm need?

3 – if 2a and 2b don’t resolve the issue: can you reduce the question to a subset that can be simulated on Google’s infrastructure within your lifetime? π

[0] http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_essentially_different_Sudoku_solutions

Sjors ProvoostFebruary 7, 2011 at 13:33

This guy is solving Sudoku puzzles in <10 ms: http://www.basic4ppc.com/forum/basic4android-getting-started-tutorials/12099-how-write-sudoku-solver.html

Nils BreuneseOctober 21, 2011 at 12:39

Impressive result, lousy explanation! Based on his sources I’d say he is using rules similar to mine (I use a generalized form of naked pairs) with some additions, but his post is so convoluted I cannot be sure. I’d have to look at the actual Java source.

The ‘official’ contest results post from the contest organizer lists the best performance as 14ms, so not less than 10ms per puzzle. It is unclear to me what device they used to get that performance figure, but I ran the puzzles from the competition through my solver on a 1.6 Ghz MacBook Air and got the following result.

“Solved 50 of 50 puzzles (avg 0.01 secs (91 Hz), max 0.02 secs).”

There are probably many ways to improve performance by optimizing the code, but my interest was more in the algorithm (the rules) than the implementation.

Thanks for pointing this out. Let me know if you find anything else. π

lukasvermeerOctober 21, 2011 at 13:08