View mode: basic / threaded / horizontal-split · Log in · Help
August 19, 2012
Re: Sudoku Py / C++11 / D?
The infinite loop was my mistake. I was looking at your outer while loop
but because you use exceptions instead of return values it indeed throws an
exception, my bad :)

By replacing ref by const ref my program slowed down (looked over a period
of 10_000 runs). Not considerably but noticeable. Compiled with -release
-noboundscheck -O -inline. Anyone else experiencing the same?

Is copying a static arrays cheaper then recalculating the lovation of
collumns and squares btw?
August 19, 2012
Re: Sudoku Py / C++11 / D?
On Sunday, 19 August 2012 at 21:24:26 UTC, maarten van damme 
wrote:
> The infinite loop was my mistake. I was looking at your outer 
> while loop but because you use exceptions instead of return 
> values it indeed throws an exception, my bad :)

 I have a revised version that only does 2 calls for the main 
solve now, but that's not that important.

> By replacing ref by const ref my program slowed down (looked 
> over a period of 10_000 runs). Not considerably but noticeable. 
> Compiled with -release -noboundscheck -O -inline. Anyone else 
> experiencing the same?

> Is copying a static arrays cheaper then recalculating the 
> lovation of collumns and squares btw?

 Are you using ref with it like int[9][9]? Or int[][]? It may be 
making extra calculations but i couldn't be entirely sure.

 Something to try, perhaps wrap the array into a struct and ref 
the struct. I did that in my revision (which also keeps track of 
possible choices within the struct).
August 20, 2012
Re: Sudoku Py / C++11 / D?
I'm using a static array.

I'm hesitating though if I should store possibilities in a precalculated
array or calculate them in-place. If i precalculate the possibilities i'd
have to copy them over and over so i don't know if it's smart.

Going even further I could even store a filled-in value as an array with
one possibilities...
August 20, 2012
Re: Sudoku Py / C++11 / D?
On Monday, 20 August 2012 at 00:13:41 UTC, maarten van damme 
wrote:
> I'm using a static array.

 Good good..

> I'm hesitating though if I should store possibilities in a 
> precalculated array or calculate them in-place. If I 
> precalculate the possibilities I'd have to copy them over and 
> over so I don't know if it's smart.

 Depends. Do you plan on doing more than brute force? Having it 
bulk copy them may not be that bad if it's all in one place, and 
if you do it like that you have all the combinations that carry 
forward to the next level and if you back out it undoes them all 
automatically.

 In my updated code it gets it done in about 5 seconds compared 
to 12. To get it even faster I would have to implement a third 
algorithm to help reduce possibilities, the stored results then 
become a must compared to on-the-fly.

> Going even further I could even store a filled-in value as an 
> array with one possibilities...

 As long as you can tell it apart for it to work, that's up to 
you.
August 20, 2012
Re: Sudoku Py / C++11 / D?
>   Depends. Do you plan on doing more than brute force? Having it
> bulk copy them may not be that bad if it's all in one place, and
> if you do it like that you have all the combinations that carry
> forward to the next level and if you back out it undoes them all
> automatically.
>

No, I think doing something else then brute-force would simply be a
waste of time (except for finding singles in which case you don't need
to use a brute force solver right?)
These are of course speculations, I'm not sure.

>> Going even further I could even store a filled-in value as an
>> array with one possibilities...
>
>   As long as you can tell it apart for it to work, that's up to
> you.
>
yes, that is indeed going to be the problem ...
August 20, 2012
Re: Sudoku Py / C++11 / D?
On Monday, 20 August 2012 at 01:29:06 UTC, maarten van damme 
wrote:
>> Depends. Do you plan on doing more than brute force? Having it 
>> bulk copy them may not be that bad if it's all in one place, 
>> and if you do it like that you have all the combinations that 
>> carry forward to the next level and if you back out it undoes 
>> them all automatically.
>>
> No, I think doing something else then brute-force would simply 
> be a waste of time (except for finding singles in which case 
> you don't need to use a brute force solver right?) These are of 
> course speculations, I'm not sure.

 Not true. Brute force will get the job done, but it's slow and 
bulky. By using other techniques can eliminate thousands, 
millions, or billions of cycles through simply by removing a few 
possible numbers.

 I've seen on the hard level that the brute force recursive code 
went some 20 levels deep (at one point). If it did all 
combinations of 9^20 than you'd get potentially 
12,157,665,459,056,928,801 combinations it may have to brute 
force. That can take a very very very long time. With that in 
mind, brute force should likely be a last resort if you are doing 
other algorithms.

 I've mentioned before I have an old C version of a sudoku 
solver; It can solve any solvable puzzle very quickly, the hard 
one on the best run is 1/5th of a second.

 Here's a compiled binary of the C version.

 http://rtcvb32.herobo.com/SudokuSolver.zip


>>> Going even further I could even store a filled-in value as an 
>>> array with one possibilities...
>>
>> As long as you can tell it apart for it to work, that's up to 
>> you.
>>
> yes, that is indeed going to be the problem ...

Here's what I've done recently. I've made a grid something like 
ubyte[10][9][9]. This represents the grid and all combinations 
needed for it. This way if [0] is non-zero you know it has an 
answer, otherwise the rest are which are potentially possible.
August 20, 2012
Re: Sudoku Py / C++11 / D?
>  Not true. Brute force will get the job done, but it's slow and bulky. By
using other techniques can eliminate thousands, millions, or billions of
cycles through simply by removing a few possible numbers.
>

Yes, but these techniques have a drawback : they are not garantueed to find
solutions yet they are garantueed to increase the time a run takes.

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.

>  I've seen on the hard level that the brute force recursive code went
some 20 levels deep (at one point). If it did all combinations of 9^20 than
you'd get potentially 12,157,665,459,056,928,801 combinations it may have
to brute force. That can take a very very very long time. With that in
mind, brute force should likely be a last resort if you are doing other
algorithms.
>

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 :)

> Here's what I've done recently. I've made a grid something like
ubyte[10][9][9]. This represents the grid and all combinations needed for
it. This way if [0] is non-zero you know it has an answer, otherwise the
rest are which are potentially possible.

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.

Still it comes nowhere near beating timons solution. Is the logic of that
documented somewhere because I don't understand it.

And vera, why are you using exceptions instead of return values? I think
it's slowing your solver down considerably.
August 20, 2012
Re: Sudoku Py / C++11 / D?
On 08/20/2012 10:43 PM, maarten van damme wrote:
>
> Still it comes nowhere near beating timons solution. Is the logic of
> that documented somewhere because I don't understand it.
>

Try this:
http://dpaste.dzfl.pl/23b1b6e2
August 20, 2012
Re: Sudoku Py / C++11 / D?
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.
August 20, 2012
Re: Sudoku Py / C++11 / D?
On Monday, 20 August 2012 at 20:43:54 UTC, maarten van damme 
wrote:

> And Vera, why are you using exceptions instead of return 
> values? I think it's slowing your solver down considerably.

 Wow... Just Wow...

 Optimized I had the code at 5 seconds in my recently updated 
format, however now it increased to 31 seconds.  That makes it 
6-7 times slower by not using the two potential exceptions.
1 2 3 4 5 6 7 8
Top | Discussion index | About this forum | D home