Sudoku Py / C++11 / D?

[Timon Gehr]

On 08/16/2012 11:51 PM, maarten van damme wrote:
>
>  > This is because your specific solution is slow.
>  >
>  > Mine takes <20ms on the 'hard' puzzle and ~13s on the impossible one.
>  > (~2.4 GHZ intel x86_64 machine, with gdmd -O -release -inline
> -noboundscheck.)
>  > There is a constant factor between those two solutions.
>
> I've compiled it using dmd on my latitude e5500 which is not that fast
> so I don't think it's that slow...
>

Compiled and run in the same environment, your solution takes 0.26s on
the 'hard' one, whereas mine takes 0.0013s. Your solution takes ~1600s
on the impossible one whereas mine takes ~13s.

> Besides, lets say mine is five times slower,

Hard facts say that it is at around 100x-200x slower.

> 3000 seconds is still waaay  to much.

Sounds reasonable to me.

> When I'm back able to get my laptop to use my crapy data
> connection I'll compare.
>
> Do you have some optimization ideas by the way?
>

First of all, getting rid of the dynamic allocations is low hanging fruit.

Then you'll have to reduce the number of times you recompute the same
information. Update/restore the possibilities array as you
update/restore the solution attempts. Do this for the whole board at
once and use a compact representation of possibilities.