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: , , ,

19 Responses to “How to not solve a Sudoku”

  1. Professor Oak says:

    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. Professor Oak says:

    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. Professor Oak says:

    Grrr

  5. Arne says:

    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. Arne says:

    Thanks, Vlad :)

  7. Ravi Mohan says:

    “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

  8. Memet says:

    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?

  9. Arne says:

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

  10. Memet says:

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

  11. John Reese says:

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

  12. [...] 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: [...]

  13. [...] 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 [...]

  14. [...] 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 [...]

  15. rechuk says:

    This is great!
    Thank you!

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

  17. [...] 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 [...]