On 08/16/2012 09:52 PM, maarten van damme wrote:
I've now ran in something odd. Using a slight variant from my program on
dpaste (can't upload modified version atm but changes are minimal) it
takes 0.6 seconds to solve the hard puzzle the python version took 180
seconds for.
This is because the python version happened to choose an unlucky search
order. Sudoku is NP-complete after all, so it is not surprising that
programs have a bad worst case run time.
Yet on the last puzzle, the impossible one, python takes
1800 seconds to figure out it's impossible yet mine takes over 3885
seconds. Where is this slowdown coming from?
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.
