The New Sudoku Players' Forum

[Jeff]

......... while I used the following two:

[r3c4]=9=[r1c5]-9-[r1c7]=9=[r9c7]-9-[r9c1]-4-[r9c3]-5-[r9c5]=5=[r6c5]=3=[r6c4]=9=[r3c4], => r3c4=9.

[r7c4]=5=[r9c5]-5-[r9c3]-4-[r1c3]-5-[r3c1]-4-[r3c6]-3-[r7c6]-4-[r7c4], => r7c4<>4 => r7c4=5 which solve the puzzle.

For the benefit of the readers, here are the corresponding b/b plots for these 2 nice loops (grid has been updated between the 2 loops):

[Jeff]

Here is a very simple ‘simple nice loop’ for a rather difficult grid posted by Flip here and I would like to post the corresponding b/b plot for your easy reference. The elimination of this loop is made in accordance with Theorem 5.

Nice loop notation:
[r6c6]=6=[r4c6]=4=[r4c1]=8=[r6c2]-8-[r6c6] => [r6c6]<>8

[Jeff]

Here is another beauty from Flip; a continuous nice loop with eliminations due to both Theorem 1 and 2.

Nice loop notation:
-[r2c4]-8-[r2c7]=8=[r3c7]=7=[r3c1]=2=[r9c1]-2-[r9c4]-5-[r2c4]-
=> r3c7<>3, r3c7<>4 and r9c8<>2

[Mike Barker]

Jeff, I've moved over here because I wanted to ask more questions about nice loops and didn't want to upset the topic police (who serve an important role in this community). What I'm trying to do is figure out how to program up nice loops. The question is, is how to complete a discontinous nice loop? At least one of my mistakes in the last post, as you pointed out, was counting missing links not missing nodes. In the case of an XY-wing, given three bivalue cells, two links can be constructed (assuming appropriate candidates) based on rules 1-6. Now what? Assuming we are looking for a discontinuous loop, based on what you said I assume we need to find one additional node for which the link drawing rules 1-6 don't apply - that means we need two more links with weak inference based on rule 7(?). What labels do we apply to these links? This gets back to what I discussed in the last post. It seems to me that the labels should be minus the candidate not used getting to the bivalue nodes, eg given {xy}-y-{yz}-z-{zw} coming from {xy} the label would be -x and from {zw} it would be -w. If x<>w nothing can be done, but if x=w then we can eliminate candidates in "node" common to the start and end nodes, {xy} and {zw}.

What happens if we have three strong links (or strong-weak inference-strong) where the end nodes don't share a unit? This would be like a Turbot Fish. How do we construct the nice loop, label the links, and perform eliminations? It seems to me that it is exactly as above. We look for one more node common to the start and end nodes. We label the links to this node as minus the labels for the strong links. If these labels are equal then elimination, if not we keep looking.

The third option would be a strong link and a bivalue at the end of the "loop" which don't share a unit {x...}=x={xy...}=y={yx...}-y-{yw}. Same question, and I think the same answer: if w=x then elimination is possible at nodes which are buddies to the start and end nodes. Interestingly all three configurations operate the same way which indicates a strong relationship between between an XY-wing, 3 "nice" strong links, and a "nice" combination of strong links and bivalue nodes totaling 3.

There is another situation which is where I got stuck on the last post, that is, what if the start and end nodes share a unit, but rules 1-6 don't allow a link between them? The answer, I think, is similar to above. From a strong link draw a link with weak inference to the other end node with label equal to minus the strong link label. From a bivalue node draw a link with weak inference to the other end node with a label equal to minus the candidate not already used to link the node. Elimination occurs at the "other end node" based on the link label, eg if {w...}=w={wx...}=x={xy...}={y...} then the first node doesn't contain "y" and the last doesn't contain "w". This is true whether the node is from a strong link or a bivalue cell, though going to a bivalue cell never results in an elimination, because if it did the loop would be continuous.

Does this make sense or is there a better way to answer the question of how to complete a discontinuous nice loop? Also are there any other types of discontinuous nice loops?

[Jeff]

Hi Mike, Your analysis seems fine.

Does this make sense or is there a better way to answer the question of how to complete a discontinuous nice loop? Also are there any other types of discontinuous nice loops?

For a computer solver, slight adjustment to the procedure may ease its implementation. I suggest you could:

Set up data for all +ve links and -ve links including those additional -ve links as mentioned in rule 7, ie.

Each strong link to be stored as a +ve link and a -ve link.

Each link between "the end of a -ve link on a bivalue node" and "any node with a candidate which is not the label of the -ve link", to be stored as a -ve link.

Each link between "the end of a +ve link" and "any node with a candidate matching the label of the +ve link", to be stored as a -ve link.

where:
+ve link = solid line
-ve link = broken line

Start from each linked node, assigning it as the discontinuity (to avoid repeated loops output), follow the links around and check (a) if a close loop can be formed, (b) if the propagation and deduction rules are observed, ie.

If a close loop is formed and propagation rules are observed in a cyclic manner, then the loop is continuous; Theorem 1 and 2 apply.

If a close loop is formed and propagation rules are observed except for 2 adjacent links with same +ve labels, then the loop is discontinuous and Theorem 3 applies.

If a close loop is formed and propagation rules are observed except for 2 adjacent links with same -ve labels, then the loop is discontinuous and Theorem 4 applies.

If a close loop is formed and propagation rules are observed except for 2 adjacent links with different opposite labels, then the loop is discontinuous and Theorem 5 applies.

[Mike Barker]

Thanks that does simplify things and explains rule 7 which has really been the issue. One question shouldn't

Each link between a bivalue node and any node sharing the same candidate, to be stored as a -ve link.

include a requirement that the candidate not be the one on the label already linking the bivalue node?

[Jeff]

.............include a requirement that the candidate not be the one on the label already linking the bivalue node?

You are right, Mike. My original post edited. Thanks

In other words, the propagation rules have to be observed for all additional links mentioned in construction rule No.7.

[Mike Barker]

Looking at your rule 7 construct, it looks like there are only links with weak interference at a discontinuity. It seems like only Th. 4 is required and that 3 and 5 are unnecessary.

[Jeff]

Looking at your rule 7 construct, it looks like there are only links with weak interference at a discontinuity. It seems like only Th. 4 is required and that 3 and 5 are unnecessary.

Yes, all links in rule 7 are links with weak inference so they cannot be useful as far as Th.3 is concerned, but are useful for both Th.4 and Th.5. Link [r6c2]-8-[r6c6] in the following loop was constructed to rule 7 and deduction was to Th.5.

[r6c6]=6=[r4c6]=4=[r4c1]=8=[r6c2]-8-[r6c6] => [r6c6]<>8

[Mike Barker]

Jeff, I finally got basic nice loops working (many other distractions and I still have to work on grouped nice loops). It was kind of interesting to see what they covered and didn't cover. If I ran nice loops before anything, I saw, as expected, no N*N fish with 2-nodes per row and column (eg a 222 swordfish), X-cycles, bivalued locked sets (eg a naked pair), nor XY-wings, chains or rings. I still had plenty of almost locked sets, poly-implication locked sets, and the usual number of uniqueness eliminations. The first and some of the second will be covered when I implement grouped nice loops. The two remaining techniques, SueDeCoq and Empty Rectangles, occurred a handful of times each. SueDeCoq makes sense since it can link ALS with more than one extra candidate. Empty Rectangles appear to be in a catagory of their own. I wonder if there really aren't any other fish in that sea?

On to grouped nice loops. Have you thought how the theorems might change for grouped nice loops? I'm thinking Theorm 1 will only go as far as stating "the node must be filled with one of the two digits that label the links". You're then left with a quantum cell similar to unique rectangles. Theorems 2, 4 and 5 probably extend directly. I'm wondering if Theorem 3 might not reappear. I haven't gotten much farther.

[Jeff]

I finally got basic nice loops working (many other distractions and I still have to work on grouped nice loops

Congratulations Mike for a task well done. Grouped nice loop can be implemented by simply adding a module for identification of links connected to grouped nodes.

I still had plenty of almost locked sets, poly-implication locked sets, and the usual number of uniqueness eliminations. The first and some of the second will be covered when I implement grouped nice loops.

Basically, all ALS rule patterns are discontinuous grouped xy-chains with strong nodes and pure links of weak inference. ALS patterns are poly-implication chains that won't be picked up by simple nice loop that covers double implication chains only. I am sure all ALS rule patterns will be picked up once grouped nice loop is implemented. In fact, grouped nice loop (of combined strong and weak types) should be much more powerful because it considers grouped nodes and links of strong and weak inferences. With the nice loop technique, almost patterns, uniqueness rectangles and BUG-Lites can be considered as a grouped node in the loop. Sometimes, a uniqueness rectangle can be considered as 2 cells with a link of strong inference in between.

The two remaining techniques, SueDeCoq and Empty Rectangles, occurred a handful of times each. SueDeCoq makes sense since it can link ALS with more than one extra candidate. Empty Rectangles appear to be in a catagory of their own. I wonder if there really aren't any other fish in that sea?

Each SueDeCoq is just 2 continuous grouped xy-chains. Empty Rectangles are just grouped x-cycles. They should be picked up once grouped nice loop is implemented.

On to grouped nice loops. Have you thought how the theorems might change for grouped nice loops? I'm thinking Theorm 1 will only go as far as stating "the node must be filled with one of the two digits that label the links".

So far, the grouped nodes that I have come across involve 2 links of weak inference or 2 opposite links. Good question; what would happen to a grouped node with 2 links of strong inference?

Theorems 2, 4 and 5 probably extend directly. I'm wondering if Theorem 3 might not reappear.

Theorem 2 extends directly with multi-eliminations when the link label is multi-valued. Theorems 3, 4 & 5 extend directly to grouped nice loop as long as the node at the discontinuity only has one cell.

[Mike Barker]

I'm beginning to think that Theorem 5 doesn't apply for grouped nice loops either. Consider the following:

Code: Select all

+----------------+-----------------+--------------+
|   1     5    7 |    2    9     8 |  3    6    4 |
|   6     9    3 |    5    4     1 |  2    7    8 |
|   2     8    4 |   36    7    36 |  5    1    9 |
+----------------+-----------------+--------------+
|   8     4    2 |    7   35     9 |  1   35    6 |
|   9   367   56 |  346    1  2346 |  8  235  257 |
|  35   137  156 |    8  356   236 |  4    9   27 |
+----------------+-----------------+--------------+
|   4 *1236 -*156|  136   36     7 |  9    8  *25 |
|  35    36    8 |    9    2   346 |  7   45    1 |
|   7   *12    9 |   14    8     5 |  6  *24    3 |
+----------------+-----------------+--------------+

with the grouped nice loop:
r7c23=1=r9c2=2=r9c8-2-r7c9-5-r7c2
I believe by Th. 5 this should allow elimination of the 5 in r7c3. If the 1 didn't exist in r7c2, that is the loop is not grouped, this would be true. Because it does the contradiction doesn't hold because both the 5 and 1 can exist in the group.

[Jeff]

I'm beginning to think that Theorem 5 doesn't apply for grouped nice loops either.

Hi Mike. I don't think so because the grouped inference [r7c23]=1=[r9c2] infers the {1} in either r7c3 or r7c2; not sure which one.

Theorems 3, 4 & 5 extend directly to grouped nice loop as long as the node at the discontinuity only has one cell. I did have in some cases expressed multiple exclusions with grouped node at discontinuity. But, that was done so because all such exclusions can be expressed in separate nice loops with common implication streams.

[Carcul]

Hi Mike Barker.

You cannot "begin" a grouped nice loop with a strong link that involves more than one cell, as "[r7c23]=1=[r9c2]", because, as Jeff stated, we would then considering that "1" is not in both r7c2/r7c3, which doesn't make sense. However, we can use such a grouped nice loop if it is a weak one, for example, "[r7c23]-1-[r9c2]...", where we are considering that "1" is in one of the cells r7c2/r7c3.

Regards, Carcul

[Jeff]

However, we can use such a grouped nice loop if it is a weak one, for example, "[r7c23]-1-[r9c2]...", where we are considering that "1" is in one of the cells r7c2/r7c3.

That's true, Carcul. Just speculating, say if an exclusion of {1} is to be made in r7c3 due to Theorem 4, hence:

[r7c23]-1-[r9c2].............]-1-[r7c3] => r7c3<>1,

it would be equally valid that if cell [r7c2] is not considered, hence:

[r7c3]-1-[r9c2].............]-1-[r7c3] => r7c3<>1