Sudoku solver

[Steven D'Aprano]

On Sun, 29 Mar 2015 03:10 pm, Chris Angelico wrote:

> On Sun, Mar 29, 2015 at 2:06 PM, Steven D'Aprano
> <steve+comp.lang.python at pearwood.info> wrote:
>> On Sun, 29 Mar 2015 10:50 am, BartC wrote:
>>
>>> (X is my own interpreted language, which is where my interest in this
>>> is. This had been generally faster than Python until PyPy came along. It
>>> does however use a pure byte-code interpreter, so the result is not too
>>> bad.
>>>
>>> But using X *and* my own brute-force algorithm, the same puzzle took 2
>>> seconds to solve - faster than C!
>>
>> But, when you tell me that your very own personal interpreted language,
>> which I assume nobody else has worked on, is 40% faster than optimized C,
>> my first reaction is to expect that you've probably made a mistake
>> somewhere. I would have the same reaction if somebody casually dropped
>> into a conversation that they happened to beat Usain Bolt's 100m personal
>> best of 9.58 seconds by almost four seconds. While carrying a 20kg
>> backpack.
> 
> I think you're misreading the stats. The first table compares
> languages, all using the same algorithm, and in that, C beat X ten to
> one, unoptimized. The second figure, when X took only 2 seconds, was
> demonstrating the massive improvement that the algorithmic change
> (from "the OP's algorithm" to "[BartC's] own brute-force algorithm")
> achieved. For comparison, that's like casually dropping into
> conversation that you happened to drive a car faster than Usain Bolt's
> personal best. :)

Swapping from a clever algorithm to a brute force algorithm is not what I
would describe as swapping from running to driving a car. I would describe
it as swapping from running down the street to running through quicksand
while carrying a grand piano. I don't what sort of algorithm you think is
going to be *slower* than brute force.

Wait, I have one... randomly generate a grid of numbers. Is it a valid
sudoko that matches the clues given? If so, we're done, if not, generate
another random grid. Brute force will beat that.

That's why I can't help but feel that, *given the description we've seen*,
perhaps Bart's brute force code doesn't actually solve the problem, and
that's why it is so fast. I'm reminded of the recent thread where somebody
claimed to have a significant speed-up over Timsort by using a binary
search instead of linear search. Tim Peters investigated, and noticed that
the code wasn't actually sorting. It's easy to beat the performance of any
sort algorithm if you don't actually sort...

Anyway, we don't really know where the confusion lies. Perhaps the
description is misleading, or I'm just confused, or Bart's idea of brute
force is not the same as my idea of brute force, or perhaps he really is a
super-genius who has casually relegated C to the dust bin of historic
languages...


-- 
Steven