Sudoku Py / C++11 / D?

maarten van damme maartenvd1994 at gmail.com
Mon Aug 20 13:43:36 PDT 2012


>  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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d-learn/attachments/20120820/a58fe1b0/attachment.html>


More information about the Digitalmars-d-learn mailing list