Sudoku Players' Forum (clone)

Well, that one way to make a point, post twice, sorry. rab

RedEd:

"The approach" = "Allan Barker's approach" ?

Yes, I have been avoiding a name, so "Local Area Sets" or "Bounded Local Area Sets" in full.
RedEd:

"These are not included in any comparison ..." = "These 'other means' are outside of the scope of the present discussion" ?

Yes. One more term would be helpful. Maybe there is already a term for this that I don't know:

Dual cover set methods, a basic method that uses two mutually exclusive exact cover sets S and L to cover two groups of candidates pS and pL where pS ⊂ pL. If S and L have the same number of sets, then all candidates in pL - pS can be eliminated. This idea is not new and is most easily seen as an X-Wing(N=2) and similar fish. The first generalization that I know of was Subset Constraint Theory, which I believe was done here.

Dual cover sets is the starting point for my work, and I believe it is the basis behind Milko's approach (Milko, correct me if I am wrong). The scope of my work is the use of [sets + simple logical rules] to find and represent all possible eliminations in logical ways. The scope doesn't include backtracking, T&E, and enumeration.

My belief is that that dual cover set method methods are powerful but cannot account for all eliminations unless combined with the principles of regions and triplets(boundaries). I say this after testing a large number of methods and because its hard to find thongs that don't fit. The nrct chain above fit easily but I need to study their definition more closely.

I would also like to know what might be a good test. I have also looked at proving loops, which make good examples about regions and boundaries. I have seen some mention of GEM as an interesting test?

Denis, just a quick reply first.

Denis:

I don't know what your pattern is, but it is not an nrct-chain if it relies on such links to previous left-linking candidates.

I don't know what it is either. I too, was a little suspicious but I'm confident of the elimination, there are six permutations and none allow the candidate. I will study more.

Allan, can you code in 'C'? If so, writing a solution technique module to glue into gsf's solver might be a good way to enable large-scale testing of your ideas.

Red Ed wrote:Allan, can you code in 'C'? If so, writing a solution technique module to glue into gsf's solver might be a good way to enable large-scale testing of your ideas.

if you write it with a top level function that takes a puzzle and maybe 1 or two optional numeric parameters
then I can do the impedance matching to my code
with the help of Red Ed my solver has Qb (Red Ed's br nets)
and I also added Qt (Michael McWilliams' red/green transport) from eureka
[ edit ] and Z (Ronk's general fish finder)

its one thing to see the description of an algorithm but often something entirely different to see it in action

RedEd, gsf,

if you write it with a top level function that takes a puzzle and maybe 1 or two optional numeric parameters
then I can do the impedance matching to my code

I like the idea and like the idea of working together. I already have the software, too much, it's all part of a big multipurpose solver/simulator and everything is sets and 3d all the way. But it can definitely be modularized with effort, but I would need to give you more control. It finds everything, and then you control it to limit to what you want. I use is an n-dimension graph search where the sets are the nodes. Let me think on this a bit. It would be a bit longer term project but definitely interesting.

with the help of Red Ed my solver has Qb (Red Ed's br nets)
and I also added Qt (Michael McWilliams' red/green transport) from eureka

Great, more learning to do.

[/quote]

Denis.

I have figured out why the Alex's nrct chain eliminates a candidate after I made a link to an even node, when it should not. The answer is the nrct chain does not cause the elimination, rather it is caused by a smaller chain (l=4) embedded in the nrct chain. This is a not uncommon.

I also figured out a reason for the even and odd elimination pattern in the nrct chains that can be expressed in terms of sets. The reason is shown below. When you add another (uncovered) candidate to the set, the chain goes from rank 1 (good) to rank 2 (bad) and seeing two ends can no longer eliminate a candidate.

If you connect the new candidate as an nrct chain, it forms a triple point. The triple point rule says the rank is lower on the set (vs. linkset) side. So which ever way the set is pointing becomes rank 1, if it points to the end away from the connection (odd connection) that branch is rank 1 and the elimination occurs. In the other direction, the branch merges back to rank 2 before the end of the chain. The two cases are shown below.

The first image is the nrct chain with a correct connection. The elimination zones due to the nrct chain are in the lower right with a slight green highlight. Note that the side of the triple point is pointing to the right. The structure is rank 2. Sets A and B are rank 1 A overlap F for the elimination.



The next image is the nrct chain with a wrong connection. The elimination zones in the lower right are empty. Note that the side of the triple point is pointing to the left. The structure is rank 2. Sets C and D are rank 1 and the rest are rank 2.



I will later post a study on my website.

Denis.

I just noticed something interesting about the above two nrct chains. If you look carefully, there are a few extra yellow elimination zones in addition those due to the ends of the nrct chain. These are from sub-chains. The interesting point is that these have changed position because the location of the rank 1 sets has changed with the connection point, thus all the eliminztion zones are predicted correctly by the one triple point.

Allan, thanks for your detailed answers. I haven't yet had time to study all of your approach in detail but I still want to do it.

Allan Barker wrote:I have figured out why the Alex's nrct chain eliminates a candidate after I made a link to an even node, when it should not. The answer is the nrct chain does not cause the elimination, rather it is caused by a smaller chain (l=4) embedded in the nrct chain. This is a not uncommon.

Such embeddings can never appear in my approach, because short chains are always assigned higher priorities than longer ones; this is a major element for controlling complexity.
This leads me to another question: do you assign different priorities to different cover patterns and on which basis?

Allan, does the "3D" refer to some of your graphics for the single-digit constraint sets you've posted to date ... or are you planning to post examples of multi-digit constraint sets?

Denis:

Such embeddings can never appear in my approach, because short chains are always assigned higher priorities than longer ones; this is a major element for controlling complexity.

OK, but, in the two nrct chains just above (one good and one bad) there is a subchain from set F to set D that has an (empty) elimination zone. This is part of the nrct chain that can't be avoided, thus I mention its presence and the empty e-zone. So, I think you are saying that you will use the subchain first before the nrct chain, but if you need the nrct chain it will still contain the (now used) sub-chain??

.......o you assign different priorities to different cover patterns and on which basis?

Yes, I must, and I think that 1st and 2nd order logic eventually meet the same compexity problems but my guess is that 1st order is easier and more flexible. I currently focus on studing the logic so my priorities will be differnet. However, I control length, no. of candidates/set/linkset, no. of links from one set to then next, kind of links, and of course rank ie (ALS= rank 1, AALS = rank 2, etc). Evntually, I must address some of the things you have already done.

Now I need to go and think how to answer Ronk's superb question "Why does your 3D Sudoku thread have only 2D drawings of 1 digit chains??" The quick answer is oops.....

How does 3D relate to Local Area Set Theory?

The goal is to have one simple logic that can explain all eliminations produced by any solving method. It should produce logical explanations that are easy to reason with e.g., predicting the outcome of changing logic. So far, Local Area Sets seem to achieve this simplicity and scope.

The simplicity and scope are achieved through a mixture of things, notably the use of sets and their properties in regions and along boundaries. However, much of the simplicity is from the symmetrical definition of sets as well as the extension of the dual set cover process into three dimensions. Thus, 3D is as much a part of the LAS approach as the logic of sets. Thus the name of the thread.

Static logic.

LAS produces static logic meaning there are no sequential steps or starting points, even for chains. In this sense, the logic is pattern like or pictographic. Different kinds of logic become easy to recognize with practice however, this pattern and feature recognition really works best in 3D. Working with implications is a serial process where 3D is not very important and perhaps 2D is even better.

What is the impact of three dimensions on logic?

To give the answer in advance, none, at least from a set perspective. LAS provides a few natural and somewhat unique distinctions between kinds of logic thus it seems that LAS might provide valuable input to the classification of logic and solving methods. But, like everything else about Sudoku, not so simple! In this light I would like to show a few of these distinctions in hope of stirring up some thoughts on the subject.

The biggest distinction is between logic with uniform rank and logic that has regions of mixed rank. Rank is basically related to the number of missing constraints. Expanding on this a little gives the following kinds of logic.

1. Rank 0. Fish like logic, from X-wing to Steve's EM solution.
2. Rank 1. Chain like, Kraken fish, ALS wings and chains.
3. Rank 2, Kraken Blossoms? AALS units.
4. Mixed rank, overlap linksets (weak sets), nrct chains, finned fish.
5. Mixed rank, overlap sets (strong sets), broken wings, proving loops.

Then there are categories that seem to make less difference to the set logic:

1. No. of dimensions, 0D, 1D, 2D, 3D.
2. No. of candidates per set.
3. Branching. (related to no. of candidates per set)

From this, the following hierarchy of distinguishing features explains the logic seen in LAS.

I. Uniform versus mixed rank.
II. Rank, 0, 1, 2 ...
III. No. of candidates per set.
IV. Branching, i.e., where to multiple links to a set go.
V. Physical dimensions, 0D, 1D, 2D, 3D.

I welcome any comments or thoughts on how all this might relate to more traditional type of logic and clasification.

Examples.

I include a few visual examples to show these distinctions. In the 3D images, RC placements can be judged from the shadows on the floor (grid). Up and down is roughly aligned with digits where 9 is close to the floor and 1 is high up. Strong vs. weak sets are determined by other unseen candidates.

This nice loop is as simple as they get, rank 0, bi-value, no overlap sets and no branching.



This not so nice loop has 5 segments and must have a set/set overlap. This leads to eliminations and assignments (red and green respectively) in the loop itself. Although it has set overlap, it does not branch.



This multi digit Kraken fish has a loop and a branch, but no overlap sets. It is rank 1 everywhere and the eliminated candidate (orange cube) sees the end of the chain and the bottom green linkset.



This Kraken fish has two kinds of branches, one from a 3-candidate set, and the other from a linking set. It has no overlap sets.



This Kraken Blossom is from one of Mile Barker's solutions. It has multiple branches and is a nice example of rank 2 logic where three intersecting linksets are required for the elimination. The triple point in the box is not generally required for this kind of logic.



This simple finned X-wing has both overlapping linksets and a short branch.



This mixed rank proving loop has a set/set overlap and represents a dual loop where one of the three sides of the loop is rank 0 and the other two are rank 1. Any candidates along the rank 0 path can be removed from linksets. The rank 0 path starts at the triple point in the rear and travels to the front most candiaate in the box set. The two candidates in the vertical cell set marked with the thin black line are eliminated.

The drawings are excellent - and they are a very good way to demonstrate the complexity of the problem.

I am not clever enough to easily see a specific puzzle to which they refer.

For completeness please could you provide this - I must not be alone.

C

Coloin, thanks for the feedback, below are the sources for the examples in order of image:

1. anon.
2. anon.
3. Multi-Digit Kraken Fish: Eureka/Proving Loops/ first example.
4. Kraken fish: example from Sudopedia under Kraken-fish.
5. Kraken Blossom - from /Puzzle 2/ main puzzle , compared to Mike Barker's Kraken Blossum post.
6. anon.
7. Proving Loop from Eureka/Proving Loops/ first example.

Allan, I've now read a large part of your website and I have got a more precise idea of your approach. I would not insist on the words "set cover" about it, because this is not the central aspect.
The approach is not about transforming the whole Sudoku probleminto an exact cover problem.
It is about how to combine several set constraints and how to deal with the different "ranks" of these constraints.
Most of the currently used rules are rank 0 or 1, for the mere reason that the higher the rank the more complex it becomes to find the patterns.

Allan Barker wrote:LAS produces static logic meaning there are no sequential steps or starting points, even for chains.

This is not specific to your approach. It seems that some people don't understand that a chain is a static pattern - they want to prove the chain rule every time they use it. They consider a chain as a chain of inferences instead of a static pattern. I've often written about this conceptual error.
Conversely, being static doesn't mean that a chain has to be an unstructured pattern. A chain can be both static and sequentially ordered. It doesn't seem you have a means of expressing and using sequentiality of patterns.

Allan Barker wrote:In this sense, the logic is pattern like or pictographic.

Now, the word "pictographic" seems very inappropariate - because of all the permutations that can be applied to a pattern, thus changing drastically its visual appearance without changing its fundamental logical nature. That's a point about your graphics. They are fabulous, but at some point they may hide the underlying logical structure. There's no difference between links along a row, a column or a number: that's what 3D symmetry really means. That's why I write an nrc-link simply as "-", whichever type it is (and others use other notations to the same effect).

Allan Barker wrote:The biggest distinction is between logic with uniform rank and logic that has regions of mixed rank. Rank is basically related to the number of missing constraints. Expanding on this a little gives the following kinds of logic.
1. Rank 0. Fish like logic, from X-wing to Steve's EM solution.
2. Rank 1. Chain like, Kraken fish, ALS wings and chains.
3. Rank 2, Kraken Blossoms? AALS units.
4. Mixed rank, overlap linksets (weak sets), nrct chains, finned fish.
5. Mixed rank, overlap sets (strong sets), broken wings, proving loops.

I agree that ranks 0, 1, 2 have a profound meaning - in part because they are tightly related to complexity.
But "mixed rank" doens't seem to have a very precise meaning. When an nrc(z)(t) chain is built from left to right, it is not mixed rank, it is rank 1. This may be the indication that the notion of sequentiality of a pattern is missing in your approach.

Allan Barker wrote:Then there are categories that seem to make less difference to the set logic:
1. No. of dimensions, 0D, 1D, 2D, 3D.
2. No. of candidates per set.
3. Branching. (related to no. of candidates per set)

But they make a great difference in terms of complexity of finding the patterns.

What would be interesting now is an example of how you solve a puzzle using these rules. It is not yet very clear.