Sudoku solver

[BartC]

On 29/03/2015 13:01, BartC wrote:
> On 29/03/2015 11:35, Steven D'Aprano wrote:

>> 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...
>
> My solver definitely works, as the solutions produced by the two
> algorithms are identical.
>
> I'm not clever enough to produce a properly analytical solver, but
> perhaps it is not quite as brute force as the Python one.
>
> I've looked at my code and I don't really understand it (it's from a
> long time ago), and it would take quite a while to convert it to Python
> and post it. (Most of it seems to be preoccupied with multiple ways of
> indexing the board or grid.)
>
> (If it's of any interest, this non-Python code is here:
>
> http://pastebin.com/5cXd2Pef )

I've managed to create a Python version of my 'brute force' sudoku solver:

http://pastebin.com/CKmHmBKm

It was hard going as I don't normally write Python. But it worked 
practically first time, after building it bottom-up and then putting the 
solvepuzzle() routine in place.

The data for the 'hard' puzzle is hard-coded into it, so you just run it.

Python 3.1 (normal CPython) took 13 or 14 seconds to solve (previously 
1700 seconds with the OP's code).

PyPy took 1.3 seconds (previously 93 seconds). (Annoyingly, faster than 
the 1.7 seconds of my language...)

(The original code in my language that I posted has been simplified - 
which also made it faster, and the Python code was based on that 
version. The Pastebin code has been updated.)

I won't bother to test a C version of this, as it's a bit more awkward 
to translate (making use of strings and deep copies of arrays).

-- 
Bartc