Sudoku solver

[BartC]

On 29/03/2015 19:03, Marko Rauhamaa wrote:
> 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.)

Well, in this case all the benchmarks ran the same algorithm on the same 
data, which makes them a better test of the implementations than of the 
algorithm.

I've mentioned a (possibly) significantly faster algorithm which I 
believe to be still brute-force (now in Python here: 
http://pastebin.com/CKmHmBKm).

But I realise it could just be luck in approaching the solution from a 
literally different angle and encountering the answer sooner. (I think 
both stop as soon as they find any valid solution.)

What I've done is try it on 3 rotations as well as the original (+90, 
+180, +270 degrees, but haven't bothered with flips and reflections).

While the original took 13 seconds (using my algorithm in Python), the 
rotations took 18, 49 and 87 seconds respectively.

Since the original time in PyPy took 90-odd seconds, I was about to 
acknowledge that mine might not be that much faster after all. Then I 
realised I was using Python 3.1 not PyPy! Python 3.1 took 28 minutes on 
original hard puzzle using your code, and 13-87 seconds with mine.

So I think this other algorithm is still much faster. I've no idea why, 
especially since it messes about concatenating strings and converting 
them to and from integers.

-- 
Bartc