[olug] Programming Question

[Obi-Wan]

> how long does it take to solve this one?
> It's a near worst case scenario.
> 
> http://upload.wikimedia.org/wikipedia/en/1/17/Sudoku_puzzle_hard_for_brute_force.jpg

Yeah, that's ugly.  It took 3.5 minutes on my shiny new Athlon 5000+.

9 8 7   6 5 4   3 2 1
2 4 6   1 7 3   9 8 5
3 5 1   9 2 8   7 4 6

1 2 8   5 3 7   6 9 4
6 3 4   8 9 2   1 5 7
7 9 5   4 6 1   8 3 2

5 1 9   2 8 6   4 7 3
4 7 2   3 1 9   5 6 8
8 6 3   7 4 5   2 1 9

Having a solution that starts with 9 in the upper left and has 14 empty
cells at the top requires LOTS of useless recursion before it finds the
right answer.  Prefilling that first 9 got the solution in just 30 seconds.

In fairness, any purely recursive algorithm will have special cases
that give it trouble.  Randomly inserting values will make it hard to
find those special cases, because you MIGHT insert something that would
make this particular puzzle easier, but there will still be just as
many of them.

> does you solver use randoms?

No, it's a deterministic, brute force, recursive algorithm.

-- 
Ben "Obi-Wan" Hollingsworth                             obiwan at jedi.com
   The stuff of earth competes for the allegiance I owe only to the
     Giver of all good things, so if I stand, let me stand on the
       promise that You will pull me through.  -- Rich Mullins