Sudoku Py / C++11 / D?

[Era Scarecrow]

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.