Sudoku Py / C++11 / D?

maarten van damme maartenvd1994 at gmail.com
Tue Aug 21 08:52:58 PDT 2012


2012/8/17, Chris Cain <clcain at uncg.edu>:
>
> Gonna chime in a bit here:
>
> There's a lot of factors at play when deciding to use shorts vs
> bytes vs native-sized ints. The best way to decide is to time all
> of them and see which works best overall.
>
> With caching on a larger problem, I'd guess that the smaller you
> go, the better. The reason is that you run the risk of your data
> getting large enough that it can't all fit in the L2 cache and
> waiting for information to come from memory takes forever
> (comparatively speaking).
>
> Also, I just looked at your solution (not Mr. Gehr's solution),
> but it looks like you could approach this much more efficiently.
>
> It seems like you're storing a lot of information in arrays of
> ints. At least some of that could be stored in a bitmap/bitset
> (http://en.wikipedia.org/wiki/Bit_array) and give you
> significantly better memory efficiency. Array!bool in
> std.container will actually do the correct thing and store things
> like a bitset, so you don't necessarily have to implement your
> own (however, I think that it stores it in an int when you could
> use a short to hold 1-9 ... but it's not enough to really worry
> about).
>

I've been using my phone the last few days to check my emails and
overlooked this message. I've never heard about std.container but this
could indeed be a more efficient solution. I'm now storing a lot in
bytes but that's still 8 times too much :)

> Try this:
> http://dpaste.dzfl.pl/23b1b6e2

Thank you very much, this makes everything more clearer. I'm not very
familiar with binary operators so the comments help out a lot.
Would you mind it if I shamelessly copy your solution of using shorts
to store possibilities in?

I'm also a bit confused. How come the int's you change from a square
passed from squ are stilled referenced to the original array? I
thought it lost that reference as soon as you did any operations (like
concenating) on it?

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

No, that wasn't sarastic. If you look at my last code you see that I
"compose" the squares using something like [....] ~ [.....] ~ [.....]
Using a foreach loop and copying the values was 10 times faster...

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

Yes but when your solver reaches a solution that is wrong, you get a
whole "branch" of numbers falling of, all throwing a "broken sudoku"
exception. It will rarely be called once.

> Not normal but it can be arranged. :p

But I used it in my getRegion code where I do simple calculations on
the contents of that array. It is slower there...


More information about the Digitalmars-d-learn mailing list