How to not solve a Sudoku

I found this at Ravi Mohan’s One Man Hacking:

Ron Jeffries attempts to create a sudoku solver – here, here, here, here and here. (You really ought to read these articles. They are ummm…{cough} …err…. enlightening.)

Peter Norvig creates a Sudoku Solver.

Compare. Learn.

To increase the impact, I suggest you read Norvig’s essay first. It’s a great read and the elegance and concision of his solution gave me this tingly warm feeling of sheer developer entrancement. In contrast, Jeffries’ writings on implementing a Sudoku solver by following a test-driven development approach, are just disconcerting. In the end, he abandons his half-finished work after five postings. If he achieves anything, he impressively demonstrates that he’s not exactly an algorithms expert (which Peter Norvig, of course, is).

But, as Ravi says, there’s an important lesson to learn here: agile approaches are about software development, not about algorithm design. To be more precise: they are mainly about achieving software quality, not correctness. It’s the purpose of tests to help the developer maintain functional correctness – not to guide her towards a correct solution of an algorithmically non-trivial problem, such as Sudoku solving.

I think, this is a good example for the old saying “If your only tool is a hammer, every problem looks like a nail.” And it supports my impression that in these days too many people in the development world focus on the methodological aspects of software development and underestimate the importance of fundamentals such as algorithm design.

UPDATE: Vlad Levin goes into more detail on this issue.

Tags: , , ,

30 comments

  1. Brute force sudoku solver in C, works for 9×9, 16×16, but too slow for 25×25.

    The puzzle is pre-loaded into the table.
    When complete, the table holds the solution.
    Method:
    Find an unsolved cell.
    Put 1 into it.
    Does it violate the rules?
    Yes:
    Increment the value. and repeat
    No:
    Last Cell?
    Yes: Done
    no:
    Find the next unsolved cell and repeat.

    int complete = 0;
    int table[81] = {0,0,0,6,0,0,0,3,1,0,0,2,0,0,0,0,0,4,3,0,0,0,0,8,2,0,0,6,0,7,0,8,4,0,0,2,0,0,5,9,0,0,8,0,0,0,0,0,1,0,0,0,0,6,0,0,0,7,0,0,0,0,0,7,0,4,0,0,0,6,0,5,0,0,0,0,5,0,1,0,0};

    void solve(int x);
    void Set(int x, int val)
    {
    table[x]=val;
    }

    int test(int position, int value);
    int FindNew(int start);

    int APIENTRY WinMain(HINSTANCE hInstance,
    HINSTANCE hPrevInstance,
    LPSTR lpCmdLine,
    int nCmdShow)
    {

    solve(-1);

    return 0;
    }

    void solve(int x)
    {
    int newx = FindNew(x+1);
    if (newx == -1)
    {
    complete = 1;
    return;
    }

    for (int i = 1; i

  2. Well said! I tried to say the same thing in my blog, but it came out a lot longer! :)

    Vlad

  3. int complete = 0;
    int table[81] = {0,0,0,6,0,0,0,3,1,0,0,2,0,0,0,0,0,4,3,0,0,0,0,8,2,0,0,6,0,7,0,8,4,0,0,2,0,0,5,9,0,0,8,0,0,0,0,0,1,0,0,0,0,6,0,0,0,7,0,0,0,0,0,7,0,4,0,0,0,6,0,5,0,0,0,0,5,0,1,0,0};
    void solve(int x);
    void Set(int x, int val)
    {table[x]=val;}
    int test(int position, int value);
    int FindNew(int start);
    int main()
    {solve(-1);return 0;
    }
    void solve(int x)
    {int newx = FindNew(x+1);
    if (newx==-1) {complete=1;return;}
    for (int i=1;i

  4. Grrr

  5. Okay, this is basically what you get if you remove the constraint propagation and rely on a depth-first search through problem space only. Easy to grasp & to implement, but – as you say – prone to complexity issues. Nice addition, though.

  6. “And it supports my impression that in these days too many people in the development world focus on the methodological aspects of software development and underestimate the importance of fundamentals such as algorithm design.”

    Thank YOU!!!! At least one person understood what I was trying to convey :-)

    Ravi

  7. I have a question/issue about this algorithm.

    A while ago I wrote myself a sudoku solver in scheme to explore the capabilities of amb (which is quite an elegant closure based implementation of backtracking). But there’s an assumption he (Norvig) makes that I don’t know is trivial.
    Why should substituting only one square guarantee a solution? I refer to:
    “Simple: first make sure we haven’t already found a solution or a contradiction, and if not choose one unfilled square and consider all its possible values. One at a time, try assigning the square each value, and searching from the resulting position.”

    Maybe I’m not understanding what he means but it’s either one of two things:
    a) a sudoku puzzle can be solved with only one guess cell. (if so: why?)
    b) the DFS search algo he is proposing is just a backtracking algorithm since DFS will eventually ‘pop the stack’ which is essentially what backtracking is all about. It’s just an implementation detail.

    Maybe I misread or am completely misunderstanding, anyone care to clarify?

  8. Memet, I’m not sure if I get you right: after eliminating impossible alternatives through constraint propagation, Norvig uses a DFS for searching the remaining problem space. So yes, the second part is “just a backtracking algorithm”.

  9. @Arne: check. I was just puzzled by his claim that it wasn’t…

    “The alternative is to keep track of each change to values and undo the change when we hit a dead end. This is known as backtracking search. It makes sense when each step is a single change, but is usually too complicated to bother with when each change can lead to many other changes via constraint propagation.”

    Which made me question (along with the previous paragraph I quoted about the search algorithm) if he was not having deep branching. i.e. that the choice was a single square being searched on.

    I guess as far as he is concerned, it is only called backtracking in the case that you hold a list of the changes and have a master state, rather than having a list of copy states. I would have still called the DFS search backtracking, but I can live with his terminology so long as I’m clear.

    Anyways, thanks.

  10. @Mernet: I believe the distinction he is making is not so much that it is or isn’t a backtracking algorithm, but rather that rather than having to explicitly deal with backtracking by reverting the data structure, the recursive nature of operation means that any failed path will automatically return up the chain to where the individual data structures are still in previous condition.

  11. [...] Today I stumbled upon another source of developer wisdom, Des Traynor’s Programming Theorems. One of the theorems rings especially true for me after the recent insights into developing a Sudoku solver the TDD way: [...]

  12. [...] Maybe I’m a bit hypersensitive here, but I have some reservations when it gets to using tests to find out how things (could or should) work. I’d think it would it be better to just look it up in a reference and write the test [...]

  13. [...] about five blog posts full of waffle that doesn’t actually DO anything. Read more about that here. 4. The history of Media Molecule: here. 5. Next week, we will get into Gaslamp Games’s [...]

  14. This is great!
    Thank you!

  15. [...] I came across DevGrind’s How not to solve a Sudoku entry – itself linking to Ravi Mohan’s “Leaning from Sodoku Solver” [...]

  16. [...] great tool, it is no excuse for some sort of design process. If you don’t, you’ll most likely end up with a mess. This session was based around this [...]

  17. I think this internet site has some real fantastic info for everyone. “He is able who thinks he is able.” by Buddha.

  18. does whole foods sell saffron extract

    Arnau de Vilanova (or Arnaud de Villeneuve) talked about Ipocras (the medical doctor) and also gave a
    recipe for pimen. There are several straightforward at household workouts to decide on from.

    And generally, point out each individual nutritional supplement you just take
    to your health practitioner.

  19. Woah! I’m really loving the template/theme of this website. It’s simple, yet effective.
    A lot of times it’s hard to get that “perfect balance” between usability and appearance. I must say you’ve done a amazing job with this.

    Also, the blog loads super quick for me on Firefox. Excellent Blog!

    Feel free to visit my webpage magic memory stick

  20. Good day! I know this is somewhat off topic but I was wondering
    if you knew where I could get a captcha plugin for my comment form?

    I’m using the same blog platform as yours and I’m having
    problems finding one? Thanks a lot!

    my web site: Hard disk Repair

  21. Hey there this is kind of of off topic but I was wanting to
    know if blogs use WYSIWYG editors or if you have to manually code with HTML.
    I’m starting a blog soon but have no coding know-how so I wanted to get advice from someone with experience. Any help would be greatly appreciated!

    Here is my site; pc

  22. Blogging software typically comes with WYGIWYGs, but usually let you manually edit the HTML if you want to.

  23. Are fixed to the computer as well. The focus of this article.
    But in a damning report they said the costs of data recovery travel Bailey &
    Cotlar, 1994, p. Thus, in case of empty recycle bin to their astonishment and then there can
    be more than one disk is known as striping. It first executes a thorough
    scan on your system increases greatly. If you have a
    complex thing, with lots of interacting parts. Connecting them can
    be a little less mysterious.

    Also visit my web page data recovery for iphone

  24. are most of the lakes located in the north central region

  25. Excellent beat ! I wish to apprentice while you amend youir site, how could i subscribe for a blog
    site? The account aided me a acceptable deal. I hadd bewen
    a little bit acquainted off thiss your broadccast provided bright
    clear concept

  26. Hi colleagues, how is everything, and what you wish for to say about
    this post, in my view its truly awesome designed for me.

  27. Wow, marvelous blog layout! How long have you been blogging for?
    you make blogging look easy. The overall look of your website
    is excellent, let alone the content!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Better Tag Cloud