On Monday, 20 August 2012 at 20:43:54 UTC, maarten van damme
wrote:
Yes, but these techniques have a drawback : they are not
guaranteed to find solutions yet they are guaranteed to
increase the time a run takes.
The extra time it takes via a planned route rather than brute
forcing is well worth the effort. Besides, they mostly make it
more possible for the one-one-possible matches to be found much
faster and safely.
In my tests with the C version (that was written 6 years ago?)
each time I added an extra algorithmn to remove dead
possibilities, it sped the code up by a factor of 3 or more.
I'm still unsure if it would be worth carrying over that
possibilities array. I'm going to implement auto-solving of
single candidates and see how big the performance hit/gain is.
Yes but I only test allowed numbers so if of those 20
combinations we need 5 fours, 3 nines, 4 twos and 8 ones, the
possibilities to test are only 3491888400 which is reasonable
for a pc :)
Indeed. My code only does that too, but it's still alot of
possibilities.
That is indeed a really smart approach, I'll try that.
By optimizing a bit more (who would've thought that a for loop
copying values one by one is way faster then some slice magic?)
I was able to make my program 3 times faster. Now it can solve
an empty sudoku in 0.05 ms and solve the hard sudoku in 0.06s.
My sudoku generator for valid sudoku solution now runs at 13000
sudokus a second.
Was that sarcasm? My own code only uses copying when it's
working in the next section of brute force, otherwise it's all
referenced.
And vera, why are you using exceptions instead of return
values? I think it's slowing your solver down considerably.
I only use exceptions twice and both when it would be unable to
find a solution; I suppose I can try putting nothrow on
everything and return a bool if it had an error for solving, or
when it had to, inside a structure. Mmmm... I'll give it a try.
This is actually one of the first time's I'm actually using
exceptions.
