Cycles and chains in spades

Advanced methods and approaches for solving Sudoku puzzles

Cycles and chains in spades

Postby Max Beran » Fri Oct 21, 2005 10:37 pm

We all enjoy the challenge of winkling out chains and cycles. Here's one from another forum that's got them in spades.

.6.|143|...
..7|...|..4
...|7..|.9.
---+---+---
9..|.5.|3.1
7..|2.6|..5
6.5|.9.|..8
---+---+---
.7.|..9|...
8..|...|5..
...|432|.8.

Solution next week (if necessary).
Max Beran
 
Posts: 57
Joined: 17 August 2005

Re: Cycles and chains in spades

Postby angusj » Fri Oct 21, 2005 11:39 pm

Max Beran wrote:Here's one from another forum that's got them in spades.

Solved it with 2 forcing chains.
angusj
 
Posts: 306
Joined: 12 June 2005

Postby Max Beran » Sat Oct 22, 2005 4:33 pm

The way I did it used the repetitive cycle rule on a combination bilocation bivalue diagram. This forced a 7 into r1c9 with a cycle:
r1c9 (7) r9c9 (9) r9c2 (5) r9c1 (-5) r1c1 (5) r1c8 (7) r1c9.

I then needed six xy-chains to complete the job:
Eliminate 3 from r7c9
Eliminate 3 from r3c3
Eliminate 5 from r3c2
Eliminate 3 from r3c2
Eliminate 2 from r2c1
Eliminate 1 from r2c1

After posting the puzzle I hit upon a conflicting path that forced a 3 into r5c2. Having sussed out all those xy-chains - up to 8 cells in the chain - it was almost disappointing to find that the 3 and the 7 allowed the puzzle to be solved with no further searches.

Angusj - were these the two cells that your forcing chain identified? I guess not as the classic forcing chain comprises bivalue elements alone.
Max Beran
 
Posts: 57
Joined: 17 August 2005

Postby Sue De Coq » Sat Oct 22, 2005 10:27 pm

My solver clearly isn't as elegant as some because, instead of the two chains found by angusj, I find the promised spadefuls. Here's my solver log for the tricky middle-section of the puzzle:

Code: Select all
20. Consider the chain r7c3~1~r3c3-1-r2c1~1~r2c8-1-r7c8.
When the cell r7c3 contains the value 1, so does the cell r7c8 - a contradiction.
Therefore, the cell r7c3 cannot contain the value 1.
- The move r7c3:=1 has been eliminated.
Consider the chain r7c1-3-r2c1~3~r2c8-3-r3c9~3~r7c9.
When the cell r7c9 contains the value 3, so does the cell r7c1 - a contradiction.
Therefore, the cell r7c9 cannot contain the value 3.
- The move r7c9:=3 has been eliminated.
Consider the chain r3c3-1-r9c3~1~r9c1~5~r1c1~2~r3c3.
When the cell r3c3 contains the value 2, it likewise contains the value 1 - a contradiction.
Therefore, the cell r3c3 cannot contain the value 2.
- The move r3c3:=2 has been eliminated.
Consider the chain r7c8-1-r9c7-7-r6c7-2-r6c8~2~r7c8.
When the cell r7c8 contains the value 2, it likewise contains the value 1 - a contradiction.
Therefore, the cell r7c8 cannot contain the value 2.
- The move r7c8:=2 has been eliminated.
Consider the chain r2c7~2~r1c9-7-r1c8-7-r6c8-2-r6c7.
When the cell r2c7 contains the value 2, so does the cell r6c7 - a contradiction.
Therefore, the cell r2c7 cannot contain the value 2.
- The move r2c7:=2 has been eliminated.
Consider the chain r9c7~6~r7c9~2~r1c9-7-r9c9-7-r9c7.
When the cell r9c7 contains the value 6, it likewise contains the value 7 - a contradiction.
Therefore, the cell r9c7 cannot contain the value 6.
- The move r9c7:=6 has been eliminated.
The value 6 in Box 3 must lie in Column 7.
- The move r3c9:=6 has been eliminated.
Consider the chain r3c3-1-r9c3-6-r7c3-6-r7c9~2~r3c9~3~r3c3.
When the cell r3c3 contains the value 3, it likewise contains the value 1 - a contradiction.
Therefore, the cell r3c3 cannot contain the value 3.
- The move r3c3:=3 has been eliminated.
Consider the chain r6c8-2-r6c7-7-r9c7-1-r7c8~3~r8c8~2~r6c8.
When the cell r6c8 contains the value 2, the chain is self-contradicting.
 Therefore, the cell r6c8 cannot contain the value 2.
- The move r6c8:=2 has been eliminated.
The value 7 is the only candidate for the cell r6c8.
21. The value 2 is the only candidate for the cell r6c7.
22. The cell r1c9 is the only candidate for the value 7 in Row 1.
23. The cell r9c7 is the only candidate for the value 7 in Row 9.
24. The cell r7c8 is the only candidate for the value 1 in Box 9.
25. The value 3 in Box 7 must lie in Row 7.
- The moves r8c2:=3 and r8c3:=3 have been eliminated.
The values 1, 3, 6 and 8 occupy the cells r3c3, r5c3, r7c3 and r9c3 in some order.
- The move r7c3:=2 has been eliminated.
Consider the chain r1c8-2-r1c1~2~r7c1-2-r7c9~2~r3c9.
When the cell r3c9 contains the value 2, so does the cell r1c8 - a contradiction.
Therefore, the cell r3c9 cannot contain the value 2.
- The move r3c9:=2 has been eliminated.
The value 3 is the only candidate for the cell r3c9.
26. The cell r8c8 is the only candidate for the value 3 in Row 8.
27. Consider the chain r2c2-3-r2c1-1-r9c1-5-r9c2~5~r2c2.
When the cell r2c2 contains the value 5, it likewise contains the value 3 - a contradiction.
Therefore, the cell r2c2 cannot contain the value 5.
- The move r2c2:=5 has been eliminated.
Consider the chain r2c1-1-r9c1-1-r9c3-6-r7c3-3-r7c1~2~r2c1.
When the cell r2c1 contains the value 2, it likewise contains the value 1 - a contradiction.
Therefore, the cell r2c1 cannot contain the value 2.
- The move r2c1:=2 has been eliminated.
Consider the chain r2c1-1-r9c1-1-r9c3-6-r7c3-3-r7c1-3-r2c1.
The cell r2c1 must contain the value 3 if it doesn't contain the value 1.
Therefore, these two values are the only candidates for the cell r2c1.
- The move r2c1:=5 has been eliminated.
Consider the chain r9c3-1-r9c1-5-r9c2-5-r3c2-5-r3c6~8~r3c3-1-r9c3.
When the cell r9c3 contains the value 1, the chain is self-contradicting.
 Therefore, the cell r9c3 cannot contain the value 1.
- The move r9c3:=1 has been eliminated.
The value 6 is the only candidate for the cell r9c3.


Things improve if tabling is turned on but that isn't really in the spirit of the thread:

Code: Select all
20. Consider the chain r7c3~1~r3c3-1-r2c1~1~r2c8-1-r7c8.
When the cell r7c3 contains the value 1, so does the cell r7c8 - a contradiction.
Therefore, the cell r7c3 cannot contain the value 1.
- The move r7c3:=1 has been eliminated.
Consider the chain r7c1-3-r2c1~3~r2c8-3-r3c9~3~r7c9.
When the cell r7c9 contains the value 3, so does the cell r7c1 - a contradiction.
Therefore, the cell r7c9 cannot contain the value 3.
- The move r7c9:=3 has been eliminated.
Consider the chains r1c8-7-r1c9~2~r8c9, r1c8-7-r6c8~2~r7c8, r1c8-7-r1c9~2~r7c9 and r1c8-7-r6c8~2~r8c8.
Whichever of the 4 candidates in Box 9 contains the value 2, the cell r1c8 does not contain the value 7.
- The move r1c8:=7 has been eliminated.
The cell r1c9 is the only candidate for the value 7 in Row 1.
21. The cell r9c7 is the only candidate for the value 7 in Row 9.
22. The value 2 is the only candidate for the cell r6c7.
23. The value 7 is the only candidate for the cell r6c8.
24. The cell r7c8 is the only candidate for the value 1 in Box 9.
25. The value 3 in Box 7 must lie in Row 7.
- The moves r8c2:=3 and r8c3:=3 have been eliminated.
The value 6 in Box 3 must lie in Column 7.
- The move r3c9:=6 has been eliminated.
The values 1, 3, 6 and 8 occupy the cells r3c3, r5c3, r7c3 and r9c3 in some order.
- The moves r3c3:=2 and r7c3:=2 have been eliminated.
Consider the chain r1c8-2-r1c1~2~r7c1-2-r7c9~2~r3c9.
When the cell r3c9 contains the value 2, so does the cell r1c8 - a contradiction.
Therefore, the cell r3c9 cannot contain the value 2.
- The move r3c9:=2 has been eliminated.
The value 3 is the only candidate for the cell r3c9.
26. The cell r8c8 is the only candidate for the value 3 in Row 8.
27. Consider the chains r3c2~2~r1c1~5~r9c1-1-r9c3 and r3c2-2-r3c5-6-r3c7-1-r3c3.
Whichever of the 2 candidates in Column 3 contains the value 1, the cell r3c2 does not contain the value 2.
- The move r3c2:=2 has been eliminated.
The cell r3c5 is the only candidate for the value 2 in Row 3.
Sue De Coq
 
Posts: 93
Joined: 01 April 2005

Re: Cycles and chains in spades

Postby angusj » Sat Oct 22, 2005 10:59 pm

angusj wrote:Solved it with 2 forcing chains.


OK. Here's the way I've navigated through the tricky parts, five in total. Sorry for the heavy use of images - I'm personally finding that images are overused here - but for these really tough puzzles I think an image is a lot easier to understand than wading through lots of text.

In the 5 images below, 3 steps show what I call "multi-color" techniques and 2 show "forcing chains". The multi-color steps also happen to be what Nick70 calls Turbot fish (which are a very common subset of simple colors and multicolors).

For those not familiar with multi-colors -
Start by filtering on a specific candidate. If 2 conjugate pairs exist (say A, B & Y, Z) where one cell from each conjugate (say A & Y) shares a group, then any cell sharing a group with the other two conjugates (B & Z) mush be 'false'. Reason: at least one of the two cells sharing the first group (A,Y) must be 'false'. Consequently at least one of the other 2 conjugate cells (B &/or Z) must be 'true'. Therefore any cell that contains the specific candidate and shares a group with B and Z can have that candidate removed. (nb: This "multi-color" rule equally applies to conjugate chains.)

Anyhow here are the 5 tricky steps:

1. Multi-color to remove 1 from r7c3.
(Pink and orange are conjugates as are blue and bright green. One or both of the pink and blue cells must be 'false' since they both share a group and can't both be 'true'. Therefore one or both the orange and bright green cells must be 'true'. Cell r7c3 shares a group with both an orange and a bright green cell so must also be a 'false' cell. Remove candidate 1 from that cell.)
Image

2. Multi-color to remove 3 from r7c9.
Image

3. Forcing chain starting at r1c9 to force 7 into r9c7
Image

4. Multi-color to remove 2 from r3c9.
Image

5. Forcing chain starting at r1c1 to force 1 into r3c3
Image
angusj
 
Posts: 306
Joined: 12 June 2005

Postby Max Beran » Sun Oct 23, 2005 12:49 pm

What comes out of all this for me is that there are several ways to skin this particular cat. Having looked at angusj's images I rather think that using the Eppstein-type diagrams with Jeff's dotted lines for weak links is more in tune with my rather mechanistic approach (though I do reckon I'm quite good at identifying where an xy-chain might fit and then finding it).

What I mean by "mechanistic" is that one follows tightly defined "graphical" rules. There is skill and pleasure in then identifying the repetitive, non-repetitive and conflicting path patterns once the diagram is drawn but it might be thought of as infra-dig by the purists because one is not forever thinking about truth tables - they're all embedded in the diagram.

I say "all", but even that is dubious because I note that sue's solver's first chain:
r7c3~1~r3c3-1-r2c1~1~r2c8-1-r7c8
starts with a link that doesn't even appear on an Eppstein diagram as it is neither bivalue or bilocation. The logic is undeniable but operates in only one direction whereas the links on my diagrams are symmettrical.

It would certainly be useful to llisten in on a discussion about the interrelations between the various techniques. Turbot fishes are identifiable as cycles on bivalue/bilocation diagrams but clearly others do not.

On another topic, I would quite like to share the sort of redrawn grids I use for identifying the patterns but the FAQ is deeply unhelpful about how to post images (possibly deliberately pour discourager les punteurs).
Max Beran
 
Posts: 57
Joined: 17 August 2005


Return to Advanced solving techniques