Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

solving power versus programming effort
Goto page Previous  1, 2
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
surbier

Joined: 30 Jan 2010
Posts: 10
:

Items
PostPosted: Thu Feb 18, 2010 3:43 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Thu Feb 18, 2010 4:28 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Thu Feb 18, 2010 6:23 pm    Post subject: Reply with quote

surbier wrote:
I could try alternatively nested loops...

You could try recursion, which has the advantage, that arbitrary fish sizes can be handled with one code.

surbier wrote:
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.

Since that matrix can be calculated incementally it really could help. I will try that when the new release is finally out.
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Fri Feb 19, 2010 8:44 am    Post subject: Reply with quote

surbier wrote:
---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.

    re Franken,
    do you also check for rb\cb types?
    e.g.
      ccb\rrb
Back to top
View user's profile Send private message Visit poster's website
surbier

Joined: 30 Jan 2010
Posts: 10
:

Items
PostPosted: Sat Feb 20, 2010 9:00 am    Post subject: Reply with quote

JasonLion wrote:
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.


Thanks for pointing to that. I know there are bitmap operators for int.
But is it possible to generate an array out of int, where each int has only 3 bit,
(since the range does not exceed 8 distinct values) ?

hobiwan wrote:
You could try recursion, which has the advantage, that arbitrary fish sizes can be handled with one code.

I agree. A lot of hints to be tested Wink

Pat wrote:

re Franken,
do you also check for rb\cb types?
e.g.
ccb\rrb

Not under the term Franken, only later under the term 'all' or 'mutant'. I thought that for Franken either the base set or the cover set must be 'basic'. Some superficial reading of the UFG from my side. So I will include the
rb\cb and cb\rb combinations (e.g. cbbb\rrrb ) under the term Franken.
Thanks fore spotting.
Back to top
View user's profile Send private message
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Sat Feb 20, 2010 12:43 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Sun Feb 21, 2010 8:48 am    Post subject: Reply with quote

surbier wrote:
JasonLion wrote:
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.

Thanks for pointing to that. I know there are bitmap operators for int.

But is it possible to generate an array out of int, where each int has only 3 bit,
(since the range does not exceed 8 distinct values) ?
    where you have e.g. 8 distinct values,
    a bitmap would use 8 bits ( not 3 )

      where you have e.g. 9 distinct values,
      a bitmap would use 9 bits
      ( thus needing more than 1 byte )
Back to top
View user's profile Send private message Visit poster's website
surbier

Joined: 30 Jan 2010
Posts: 10
:

Items
PostPosted: Sun Feb 21, 2010 5:57 pm    Post subject: Reply with quote

Hi Jason, Hi Pat

Ah, I got it ! I was not familiar with bitmap data types.
Thanks for your patience
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Feb 23, 2010 8:57 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
surbier

Joined: 30 Jan 2010
Posts: 10
:

Items
PostPosted: Sat Mar 06, 2010 5:20 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Mar 09, 2010 3:21 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page Previous  1, 2
Page 2 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron