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?

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

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...

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.

>   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 ...

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.

>  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.

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

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.

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.