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 1, 2  Next
 
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: Sat Jan 30, 2010 10:33 am    Post subject: solving power versus programming effort Reply with quote

Hi

This is my first post in this forum.

I have written a sudoku solver in C (sudoku-navigator = sunavi).
The program is user-unfriendly, meaning no GUI, just plain text input
files and plain text output files. Before extending the set of solving
methods, or extending the application of implemented methods, I would
like to ask you on the ratio between the programming effort and the
solving power of the methods I have in mind. The more complex the methods
are the higher is programming effort. I have all simple methods like subsets,
wings are implemented.


- The code knows basic fish, I could extend it for franken and mutant
fishes, and finned and sashimi.

- Aligned pair exclusion, UR type 3-6 and AR are not supported.

- The code knows POM, single digit, multi-digit (=vulnerable sets)
and same basic equation analysis techniques, I could extend it for full
equation analysis including NOT operator arithmetic.

- The code knows ALS pairs (XZ), also double linked ones, wing (YZ)
and chains with and without overlapping. I think about including death
blossom and closed loop ALS chain (something like a continuous nice loop
consisting of ALS only).

- The code doesn't know anything about Sue de Coq (AALS)

- The code knows nice loops, AIC with group nodes and ALS as nodes. All
three nice loop elimination rules are included. Some types of links are
not recognized, like weak links between two ALS, weak links between a
group node and an ALS.

- The code knows since recently AIC with almost hidden sets (AHS)
as strong links. I could think of supporting more complex strong link
structures like finned fishes and AUR. The idea behind this extension is
find shorter AIC chains with strong-link nodes nodes of higher complexity.

Being impressed by the simplicity and power of AHS in AICs, I tentatively
would continue with finned fishes to include them in AIC, but I'm not
quite sure on their solving power.

surbier
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sat Jan 30, 2010 10:48 am    Post subject: Reply with quote

From a fast first look at your list: Although some of the techniques you mention as "not implemented yet" will be interesting for manual solvers on not too hard sudokus (especially finned basic fish and UR 3, 4, 6), non of them will really expand the solving capabilities of your program.

If you really want to solve harder sudokus you will have to look into Forcing Chains/Nets (aka Kraken Moves).
Back to top
View user's profile Send private message
surbier

Joined: 30 Jan 2010
Posts: 10
:

Items
PostPosted: Sat Jan 30, 2010 5:12 pm    Post subject: Reply with quote

Thanks for the quick answer and suggestions.

I believed that the hidden pair loops / monster loops and
maybe quantums are the key to solve the hardest sudokus by logic.
Kraken is a good idea as well, it certainly easier to code.

I think I will continue with the more complex fishes and the Kraken.

surbier
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sun Jan 31, 2010 9:39 pm    Post subject: Reply with quote

surbier wrote:
I believed that the hidden pair loops / monster loops and
maybe quantums are the key to solve the hardest sudokus by logic.

Yes they are, but between puzzles that can be solved by AICs and ALS-Chains and puzzles like Easter Monster is quite a large gap...

If you go for complex fish I would suggest coding a general fish finder, if your internal data structure supports that. You could find any type of fish by simply using different sets of constraints as input (the logic behind all types of fish is the same). On the other hand you might want to wait till the folks over at the Ultimate FISH Guide in the Player's Forum have finally agreed on something (every time I take a look there, another 5 pages of comments has been added).
Back to top
View user's profile Send private message
surbier

Joined: 30 Jan 2010
Posts: 10
:

Items
PostPosted: Tue Feb 02, 2010 4:19 pm    Post subject: Reply with quote

hobiwan wrote:

If you go for complex fish I would suggest coding a general fish finder, if your internal data structure supports that. You could find any type of fish by simply using different sets of constraints as input (the logic behind all types of fish is the same).

I agree. I'm studying the Obi-Wahn thread in this forum...

hobiwan wrote:

On the other hand you might want to wait till the folks over at the Ultimate FISH Guide in the Player's Forum have finally agreed on something (every time I take a look there, another 5 pages of comments has been added).

Haha! I haven't read all pages, of the UFG as that thread is increasing faster (in particular since page 35) than I ever could write code. Very Happy
For the fishes I have a good understanding of the underlying logic, for the Kraken I will have to study a little bit more...
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Fri Feb 05, 2010 8:36 am    Post subject: re: The Ultimate FISH Guide Reply with quote

hobiwan wrote:

you might want to wait till the folks over at The Ultimate FISH Guide (in the Player's Forum) have finally agreed on something
    every time I take a look there,
    another 5 pages of comments has been added

  • the (un-finned) fish
    are stable

  • for the finned fish,
    they're trying to add the possibility of a fin-cell being indirect ("remote")
    -- i'd just ignore this
Back to top
View user's profile Send private message Visit poster's website
surbier

Joined: 30 Jan 2010
Posts: 10
:

Items
PostPosted: Fri Feb 05, 2010 3:45 pm    Post subject: Reply with quote

[ a post from daj95376 is gone ? ]

I was not aware of that post from Obi_Wahn.
[ I have no permission to post an URL ]
It sounds rather easy and straightforward to code.

Up to now my knowledge about fishes did not exceed what is written on sudopedia.
I will have to study a little bit more the meaning of the different kind of
fins. I have coded already the data management part: loop over digits 1 to 9,
loop over N=3,4,5; combination stuff (e.g. 3 base sectors out of a pool of up to 27;
3 distinct cover sectors out of a pool of up to 24).

It seems to be much easier than I thought.


Thanks
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Fri Feb 05, 2010 9:01 pm    Post subject: Reply with quote

surbier wrote:
It seems to be much easier than I thought.

Yes, coding fish is rather straightforward (finding them manually is another story of course...). The issue in my program was with speed: If you allow mutant fish with endo fins, the number of valid combinations grows very fast.
Back to top
View user's profile Send private message
surbier

Joined: 30 Jan 2010
Posts: 10
:

Items
PostPosted: Fri Feb 12, 2010 11:49 am    Post subject: Reply with quote

Quote:
The issue in my program was with speed


I coded that and it works; also with fins. Although it is a
method with a high ratio of solving power versus programming effort,
it is rather slow. Only my ALS-chain searcher for chain lengths>3 takes
longer on the average. The reason for the speed issue is obvious. All
the methods I have coded so far first follow the candidates, do some
pre-selection and then at a later step check for the constraints for
the particular method. E.g. For xy-wings it is reasonable to consider
only bi-value cells and ignore the remaining cells. This fish algorithm
starts from the other side. Only after the 'cover-minus-base' matrix
has been calculated the comparison with the pm grid is performed.
Selection takes place deeper in the nested programming loops. The only
pre-selection I use at the moment is to exclude sectors with less than
two instances of a considered candidate.

But I'm not disappointed. I will certainly find some ways to speed up
the code a little bit further; maybe some more pre-selections.

'Thank you for the fish' Wink
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Fri Feb 12, 2010 5:12 pm    Post subject: Reply with quote

Hi all,

The discussion on TUFG has gone into armistice (or so I think).

As Pat mentioned, the discussion seem to focus on:

1. Allowing same-single-digit within the pattern remote fin logic to be allowed as fish logic
2. Allowing impossible-fish-body implication logic to be allowed as fish logic.

The 2 points seem to have polarised opinions, however, the deductions remain sound regardless of your opinion.

The terminology section of the TUFG currently allows both points to be incorporated into fish logic.

Regarding Programming ....

I'm sure that everybody mentioned checking templates deletions before embarking on such a task.

Proving within-the-pattern remote fin link to Eliminations is the trick Confused

tarek
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Fri Feb 12, 2010 6:18 pm    Post subject: Reply with quote

tarek wrote:
The discussion on TUFG has gone into armistice (or so I think).

I didnt want to bash your work over at TUFG, the discussion simply got so lively that I wasnt even able to read all posts, not to mention trying something of my own.

tarek wrote:
I'm sure that everybody mentioned checking templates deletions before embarking on such a task.

Not in this thread... Although I find templates only useful for complex fish, for some of the simpler variants the fish search is faster than the template check (at least in my program).

surbier wrote:
But I'm not disappointed. I will certainly find some ways to speed up the code a little bit further; maybe some more pre-selections.

The only preselection that really did something for me was leaving out sectors with no overlap (and that might go out of the window, if impossible fish patterns are allowed). The template check tarek mentioned is great for larger complex fish.

The following three things helped me most:
    Using bitmaps (especially for the "sees all fins" part)
    Doing incremental updates when iterating the possible sector combinations
    Restricting the maximum number of endo fins


If you find something that works I would be really interested in hearing about it Smile
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Sat Feb 13, 2010 2:36 pm    Post subject: Reply with quote

hobiwan wrote:
tarek wrote:
The discussion on TUFG has gone into armistice (or so I think).

I didnt want to bash your work over at TUFG, the discussion simply got so lively that I wasnt even able to read all posts, not to mention trying something of my own.
Would you include in your next update an option to your line solver which shows additional fish related data (Number of Vertices, ExoFins, Endofins, Potential eliminations ... etc) Very Happy

I know this should be simple because you already colour these differently on the GUI Twisted Evil

Thanks

tarek
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sat Feb 13, 2010 9:49 pm    Post subject: Reply with quote

tarek,

I think we are hijacking this thread so I will put my answer in the HoDoKu thread in the players forum.
Back to top
View user's profile Send private message
surbier

Joined: 30 Jan 2010
Posts: 10
:

Items
PostPosted: Sun Feb 14, 2010 3:55 pm    Post subject: Reply with quote

hobiwan wrote:

The only preselection that really did something for me was leaving out sectors with no overlap (and that might go out of the window, if impossible fish patterns are allowed). The template check tarek mentioned is great for larger complex fish.

The following three things helped me most:
    Using bitmaps (especially for the "sees all fins" part)
    Doing incremental updates when iterating the possible sector combinations
    Restricting the maximum number of endo fins


If you find something that works I would be really interested in hearing about it Smile


I'm new in fishing and I haven't gained much experience concerning fishs up to now.

By 'no overlapping' you certainly mean no overlap between the base sector region and the cover set region.
Yes, another exclusion that comes up to my mind are the duplicate base sectors sets:
b1b2b3..\... is a the same as r1r2r3..\.... and are therefore redundant.

I haven't applied yet any of the two pre-selection.

Concerning the maximum number of fins
(I'm not quite sure I understood you right):

In the loop where I calculate the cover-minus-base values,
I also sum up the number of (exo)fins and the number of potential CECs.

I apply then a GetPeersOfCell function to each potential CEC
and sum up the number of (exo)fins in the array containing the peers for reasons of comparison. The CEC must see all (exo)fins.
In my case, the compute time does not scale with the number of exofins.
Endofins appear in the coverminusbase matrix just negative, as any other normal exclusion in a finless fish.
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sun Feb 14, 2010 8:00 pm    Post subject: Reply with quote

I never tried Obiwahn's matrix approach, so I cant say anything relating to that.

I simply try all possible combinations of base sectors with all possible combinations of cover sectors. The optimizations:
    Base sectors, that dont contain the fish candidate, are omited
    Cover sectors, that dont overlap with at least one base sector, are omited (more precise: that dont contain at least one fish candidate from the base set)
    Base sectors, that overlap the current base set, are omitted

When endo fins are allowed, the third restriction goes out the window. That means that the number of possible base set combinations explodes (and the runtime scales with that, at least in my approach). Work around: Every time a new base set is added, I check the number of endo fins (fish candidates contained in more than one base sector). If that number exeeds a configurable maximum, the cover search is skipped entirely for that base set combination.

In your post you mentioned exo fins: Restricting the number of exo fins only disables a few cover set combinations, which has practically no effect. In fact, if you do the "GetPeersOfCell" with bitmaps the check for the number of exo fins is more or less equally slow than the check for eliminations (no performance gain at all).

Bitmaps:

I have a bitmap for all base candidates and one for all cover candidates. In addition I have precomputed bitmaps that contain all buddies for every cell. To check for eliminations I do the following:
    Compute (base & ! cover) -> fins
    Computer (cover & ! base) -> possible eliminations
    For all fins AND the buddies sets -> on set with all cells that see all fins
    AND the set from step 3 with the possible eliminations -> all actual eliminations

Cannibalistic eliminations are tricky: I have to get all candidates, that are in at least two cover sets. I have not yet figured out a quick way to do that with bitmaps.
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 1, 2  Next
Page 1 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