## Nice loops for advanced level players - b/b plot

Advanced methods and approaches for solving Sudoku puzzles
Carcul wrote:......... 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

Posts: 708
Joined: 01 August 2005

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

Posts: 708
Joined: 01 August 2005

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

Jeff

Posts: 708
Joined: 01 August 2005

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?
Mike Barker

Posts: 458
Joined: 22 January 2006

Hi Mike, Your analysis seems fine.

Mike Barker wrote: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:

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:

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.
Last edited by Jeff on Mon Mar 13, 2006 6:16 pm, edited 1 time in total.
Jeff

Posts: 708
Joined: 01 August 2005

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?
Mike Barker

Posts: 458
Joined: 22 January 2006

Mike Barker wrote:.............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.
Jeff

Posts: 708
Joined: 01 August 2005

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.
Mike Barker

Posts: 458
Joined: 22 January 2006

Mike Barker wrote: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
Jeff

Posts: 708
Joined: 01 August 2005

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.
Mike Barker

Posts: 458
Joined: 22 January 2006

Mike Barker wrote: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.

Mike Barker wrote: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.

Mike Barker wrote: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.

Mike Barker wrote: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?

Mike Barker wrote: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.
Jeff

Posts: 708
Joined: 01 August 2005

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.
Mike Barker

Posts: 458
Joined: 22 January 2006

Mike Barker wrote: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.
Last edited by Jeff on Thu Mar 23, 2006 6:36 am, edited 1 time in total.
Jeff

Posts: 708
Joined: 01 August 2005

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
Carcul

Posts: 724
Joined: 04 November 2005

Carcul wrote: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
Jeff

Posts: 708
Joined: 01 August 2005

PreviousNext