The New Sudoku Players' Forum

[Allan Barker]

Ron,

I don't understand all the eliminations shown on the xsudo graphics you posted. For example, for "123 r4c1.<49> 4-r4c8 9-r6c1589", I see only four eliminations...

If you squint really really hard, you may be able to see 4 incredibly tiny dots in the corner of those candidates in both xsudo graphics. These dots, and the xsudo positions, are generated by my test engine using the options to generate a *.sud file. I could only locate those same 4 eliminations, which is why I want to learn Allan's set/link-set theory. It can squeeze a lot of extra mileage out of dual-linked ALS sets.

Answer Part II

Paul, here is the rest of the story. When you are loading your logic, the "assume weak cover sets" option is switched off. In this case, all the cover sets whose candidates are fully contained in the logic are treated as strong sets, which they are! This provides enough constraint power to fully solve the logic, which is what you see and what Ronk does not see. When this option is on, you will get the eliminations marked by the 4 incedibly ornate dots.

If you squint really really hard, you may be able to see 4 incredibly tiny dots in the corner

Maybe I need to make them black.
.

[aran]

Aran,

I have to admit that I really don't know what to make of what I've called Type 1 DBs. They look/feel/smell like dual-linked ALSs and certainly perform like them in terms of eliminations. I'm slowly looking at over 1200 of these things just from the royle17 collection and I have thousands more from other collections. I guess these are what you call rank-0 structures?

I haven't even nailed down the elimination rules, although I'm working on the assumption that they are similar to standard dual-linked ALSs, and so far that's working. But, my engine is not finding all the potential eliminations as identified by Allan Barker's Xsudo during analysis of the involved sets/link-sets, so there's lots of room for exploration here.

So, is that what I see or have in mind? I guess the answer is that I'm not exactly sure where this is going, but it's been fun so far...

Cheers,
Paul

And as usual, code/executables have been refreshed with the latest dual-link DB code if anyone wants to play in my sandbox.

Paul
Rank 0 : a term which I first came across in Allan Barker's work. An excellent word.
Rank 0 structure just means any identified sudoku figure that has Rank 0.
All of the most interesting structures would appear to have Rank 0 since every link-set is a potential source of eliminations, so the more (link-sets in a Rank 0 structure), the merrier.
The two most prominent Rank 0 structures being Nice Loops and Dual-linked ALSs (DL- ALS).

I have to admit that I really don't know what to make of what I've called Type 1 DBs. They look/feel/smell like dual-linked ALSs and certainly perform like them in terms of eliminations

They are DL-ALSs !
Because you generate a second RCD through the stem cell or blossom or outside link or whatever it is called.
Just to remind ourselves : x is an RCD when x cannot be true in both ALSs (it may be false in both, but cannot be true in both, in other words they are weakly-linked).
Suppose now that A and B are singly linked ALSs : easily shown that this is a Rank 1 structure.
Then if we can find a candidate p in ALS A and a candidate q in ALS B such that p (all instances thereof) and q (all instances thereof) are weakly linked, then we have a second dual link, and so the structure has suddenly been radically improved into a Rank 0 structure.

In your structure, you find an outside stem (p,q) such that if p is true in ALS A then via the stem q is false in ALS B=>p and q are weakly linked=>second RCD=>dual-link=>Rank 0=>good news.
eg in your second example : p=7 {r4c9}, q=6 {r6c9} stem (p,q)=r3c9.

So the whole idea of searching for a second weak link is of the greatest interest.

[PIsaacson]

Allan,

A million thanks for the explanations and for the new settings for generating *.sud files. I've been switching back and forth between the "Draw Sets as Logic, Auto" on and off. I think I like it to default on as well as the "Assume Weak Cover Sets" on, so I'm using a_options = 0x33409430. I just love seeing those massive amounts of eliminations/assignments from some of the dual-link cases. Now if only the candidate dot mark was black...

The good news: I modified my ALS engine to always check chains > length 2 to see if the start/end ALSs can be dual-linked. I'm using the same elimination rules as in DB, and so far, no problems or incorrect eliminations. ALS loops and whips are not checked since they are special cases. Code/executable has been refreshed to sync with the new ALS engine changes.

The bad news: I'm starting to believe that I need a new approach to dual-linked ALSs. The engine finds all possible ALSs from a given grid state, then attempts to form all the possible left-hand/right-hand pairs for use in a standard tree walk algorithm. This is great for finding ALS chains, but I'm thinking of a different approach for finding dual-linked ALSs.

Since I already have found all possible ALS pairs, I can treat them as the start/end of a chain and use multiple techniques to attempt to link another RCD. I'll expand upon this later -- have to take my tweenager to a vollyball game.

Cheers,
Paul

[PIsaacson]

So the whole idea of searching for a second weak link is of the greatest interest.

Aran,

I think I'm on the same page. It shouldn't be too difficult to find a second weak-link for a Type 2 linkage. Single digit analysis based on X-cycles (or equivalent) should quickly find if there are any even length alternating (AIC?) paths. The shortest is just a bi-local within any sector. DB already covers this nicely, and I'm in the process of extending this today.

The Type 1 linkages are going to be slightly more difficult to find, other than bi-value cells, or with XY/ALS-chains which are already covered with my ALS engine. I'm looking for something else like a NL/AIC that starts/ends with two different values. Not impossible, but not the normal (at least in my solver) way that NL/AIC chains are developed. Denis Berthier's nrc chains may be a better choice, if we drop the zt promotions. His nrc logic is 3d (row/col/value) oriented, so I already use graph algorithms and adjacency matrices to perform directed tree walks from nrc candidate A to nrc candidate B. The hard part was always executing the zt promotion, which also made nrczt chains uni-directional. Dropping the zt code should revert nrc to acting very AIC/NL'ish. But it's a huge chunk of code, so I'm not eager to tear it apart. But then so is nice-loops (a huge chunk of code) with all the group logic. Arghhhh!!!

Anyone have any thoughts/suggestions on multi-value weak-link chaining?

Cheers,
Paul

P.S. Changed my mind. I'm busy ripping nrczt to shreds tonight. I just tested some code that generates all the necessary from/to nrc candidates for any given pair of ALSs. Now I just need to feed these into a stripped-down nrc engine to see if any connect. I'm going to try a fancy schmancy new (for me) graph algorithm that traverses multiple paths in parallel using breadth first instead of my normal depth first. It looks interesting...