Sudoku Py / C++11 / D?

[Timon Gehr]

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.