Forever Learning

Forever learning and helping machines do the same.

Solving Some Sudoku Puzzles Faster (I Stand Corrected)

with 10 comments

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.

Sudoku algorithm mean execution times and standard deviations

Sudoku algorith execution times

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.

Longest execution times original algorithm

Longest execution times modified algorithm

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!

Advertisements

Written by Lukas Vermeer

February 5, 2011 at 14:12

Posted in Mathematics

10 Responses

Subscribe to comments with RSS.

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

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

    Time to write a genetic algorithm?

    Sjors Provoost

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

      lukasvermeer

      February 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 Provoost

        February 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. πŸ˜‰

          lukasvermeer

          February 7, 2011 at 12:53

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

    February 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

      lukasvermeer

      February 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 Provoost

        February 7, 2011 at 13:33

    • 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. πŸ™‚

      lukasvermeer

      October 21, 2011 at 13:08


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: