solving power versus programming effort

surbier

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

hobiwan · Posted: Sat Jan 30, 2010 10:48 am Post subject:

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

surbier · Posted: Sat Jan 30, 2010 5:12 pm Post subject:

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

hobiwan · Posted: Sun Jan 31, 2010 9:39 pm Post subject:

surbier · Posted: Tue Feb 02, 2010 4:19 pm Post subject:

Pat · Posted: Fri Feb 05, 2010 8:36 am Post subject: re: The Ultimate FISH Guide

surbier · Posted: Fri Feb 05, 2010 3:45 pm Post subject:

[ 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

hobiwan · Posted: Fri Feb 05, 2010 9:01 pm Post subject:

surbier · Posted: Fri Feb 12, 2010 11:49 am Post subject:

tarek · Posted: Fri Feb 12, 2010 5:12 pm Post subject:

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

hobiwan · Posted: Fri Feb 12, 2010 6:18 pm Post subject:

tarek · Posted: Sat Feb 13, 2010 2:36 pm Post subject:

hobiwan · Posted: Sat Feb 13, 2010 9:49 pm Post subject:

tarek,

I think we are hijacking this thread so I will put my answer in the HoDoKu thread in the players forum.

surbier · Posted: Sun Feb 14, 2010 3:55 pm Post subject:

hobiwan · Posted: Sun Feb 14, 2010 8:00 pm Post subject:

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:

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:

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.