solving power versus programming effort

surbier · Posted: Thu Feb 18, 2010 3:43 pm Post subject:

I see.

Concerning the base and cover sector combinations there are not many more
possibilitites on pre-selecting sectors without excluding a certain class
of fishes. I use at the moment a combination algorithm I found on the
web, which returns after each call the next combination (e.g. a sample
size of 3 out of a population of 20). This tool is fine for finding
all possible locked sets (almost/naked/hidden), since the population is
always small=9. But I'm no longer convinced it is appropriate for the
current situation of 3,4 out of 27. Running the sector selection part
without executing anything after the last cover set is determined shows
that this is rather slow. I could try alternatively nested loops, where
I have a better control on each base set individually as you describe.

I separated the problem slightly, as I call the fish function several times,
first for basic fish with restricted set combinations r\c, c\r, then for franken fish with
rb\c, r\cb, c\rb, cb\r and finally for mutant fish without restrictions in
the hope that a simpler fish is found before looking for mutant jellyfish.

Concerning bitmaps, there is not much one can do in C. In C, bitmaps
are structs, and it is not allowed to build arrays out of bitmap structs.
Anyway I applied your hint and generated an unsigned short int array of
81 cells times 20 peers for the peers of each cell.

Concerning the cannibalistic elimimations (candidates in intersecting
cover sets): Obi_Wahn's, daj95376's coverminusbase matrix returns them
for free. They appear just as cells >0 any other regular elimination,
but this matrix maybe does not fit as a java bitmap into your elimination.

JasonLion · Posted: Thu Feb 18, 2010 4:28 pm Post subject:

Any integer type can be treated as a "bitmap". You don't need to be using the C bit field construct to have a bitmap.

hobiwan · Posted: Thu Feb 18, 2010 6:23 pm Post subject:

Pat · Posted: Fri Feb 19, 2010 8:44 am Post subject:

surbier · Posted: Sat Feb 20, 2010 9:00 am Post subject:

JasonLion · Posted: Sat Feb 20, 2010 12:43 pm Post subject:

You can't make an array of bitmaps which only use 3 bits of storage each. You can make an array of bytes and only use 3 bits in each byte. Using bytes will be easier to write and run more quickly than trying to pack each item into only 3 bits.

Pat · Posted: Sun Feb 21, 2010 8:48 am Post subject:

surbier · Posted: Sun Feb 21, 2010 5:57 pm Post subject:

Hi Jason, Hi Pat

Ah, I got it ! I was not familiar with bitmap data types.
Thanks for your patience

PIsaacson · Posted: Tue Feb 23, 2010 8:57 pm Post subject:

Surbier,

If you are coding in C++, investigate the STL bitset templates and functions. The Standard Template Library contains many useful objects/containers/templates for coding sudoku solver techniques. If you want even more powerful STL like containers, review the Boost Library.

Cheers,
Paul

surbier · Posted: Sat Mar 06, 2010 5:20 pm Post subject:

Hi Paul

Thanks for the hint.
I don't use C++, just simple (ANSI) C and gcc compiler.

Instead of linking a graphical library, I use a gnuplot script
which converts the candidate presentation of a grid into a
printer-ready graphical format.

PIsaacson · Posted: Tue Mar 09, 2010 3:21 am Post subject:

Surbier,

Try to compile your code using g++ instead of gcc since ANSI standard C code usually compiles error free either way. Sometimes there are conflicts with C++ reserved words such as "class", but these types of errors are easily corrected. If your code compiles clean, then you will have no difficulties using C++ extentions such as the STL bitset templates in your C code. Just think of it as C+ instead of C++. Nothing says you have to use object oriented design/code in C++, it just becomes possible...

Cheers,
Paul

[edit] I wanted to add that after using templating to determine whether or not to go fishing, it is somewhat simple to use a form of DLX to locate cover sets for any given base set.

I use an optimized version of libexact from http://www.cs.helsinki.fi/u/pkaski/libexact along with a combination method that helps to find base sets from the complete row/col/box coverage for any single digit. I made this code available online somewhere, but I'm uncertain where right now. I'll try looking at what I have uploaded to see if it is still available.