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.
