Sudoku solver

[BartC]

On 29/03/2015 22:21, Mark Lawrence wrote:
> On 28/03/2015 23:50, BartC wrote:
>> On 28/03/2015 03:39, Sayth wrote:
>>> Good test for pypy to see where it's speed sits between C and Python.

>> Python 3.1:     1700 seconds     (normal Python interpreter)
>> PyPy:           93 seconds
>> C unoptimised:  17 seconds       (gcc -O0 32-bit)
>> C optimised:    3.3 seconds      (gcc -O3 32-bit)

> https://attractivechaos.wordpress.com/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/

"The fastest Sudoku solver can solve even the hardest Sudoku in about 1 
millisecond and solve most others in 0.1 millisecond."

Blimey, we might as well pack up and go home then!

Actually I didn't realise people took these things so seriously. I came 
into the thread when I thought it was being suggested that brute-force 
approaches to this problem were not viable.

I think to be useful, it needs to work in a reasonable amount of time, 
and a few seconds would be more than reasonable; it doesn't need to be 
100 microseconds. Unless somehow somebody's got millions of the things 
to get through.

But I guess people aren't interested in actually solving the daily 
sudoku in the paper** (that would be very dull); maybe there is more 
sport in finding a faster machine solution than anyone else.

(I'm more interested now in getting my own dynamic language to compete 
with PyPy, and in getting own static language to compete with C/gcc, as 
the timing for this benchmark was pretty bad.)

(** Although I did come across a prize 16x16 sudoku in the paper a few 
years back. I adapted my code to 16x16 in 10 minutes or so, which took a 
further couple of minutes to solve the given puzzle, and sent it in. But 
I didn't win...)

-- 
Bartc