Sudoku solver

[Marko Rauhamaa]

BartC <bc at freeuk.com>:

> As Chris mentioned, when I say 'faster than C', I mean X running my
> algorithm was faster then C running Marko's algoritim (on Ian's data).
> This was just an illustration of algorithm being more important than
> language.

Be careful with the benchmark comparisons. Ian's example can be solved
with the identical algorithm in eight different ways (four corners, left
or right). I ran the example with my recent Python solver and got these
times in the eight cases:

    884   s
      2.5 s
     13   s
    499   s
      5.9 s
    128   s
   1360   s
     36   s

(That suggests a slight modification to the original strategy: solve it
in each of the eight ways "in parallel" and the worst case should be
significantly alleviated.)

I'm actually fascinated by the Python modifications that were
conceptually insignificant but dramatically speeded up the execution
(7880 seconds to 884 seconds). That's something I'll have to keep in
mind in the future.


Marko