Colouring with three conjugate chains, I mean four now

Advanced methods and approaches for solving Sudoku puzzles

Colouring with three conjugate chains, I mean four now

Postby TKiel » Mon Feb 13, 2006 3:18 pm

I can't seem to be able to wrap my little brain around colouring with three conjugate chains and am looking for some help. This grid is from Vidarino's Monster #2 with only candidate 8's shown. There are three conjugate chains, marked A-a, B-b, C-c.
Code: Select all
 
 *--------------------------------------------------------------*
 |                |                      |                      |
 |                |                  8   |   8             8b   |
 |                |          8       8   |   8                  |
 |----------------+----------------------+----------------------|
 |     8     8a   |          8       8   |                      |
 |                |                      |                      |
 |     8c         |          8C          |                      |
 |----------------+----------------------+----------------------|
 |                |                      |                      |
 |           8A   |                      |   8              8B  |
 |     8a         |                      |   8A                 |
 *--------------------------------------------------------------*

A & B share a group, therefore either a or b is true. a & c share a group, therefore either A or C is true. What I can't make sense of is if/how B-b relates to C-c. If A, B & C all shared the same group it would seem that any cell that 'sees' any two of a, b or c could be excluded. Since that is not the case here, does an exclusion only take place in a cell that 'sees' the 'one of these must be true' mark for all three of the chains or it is possible to make it for one that 'sees' any two of those marks or only a certain two? I'm not really asking if the chains marked above do make an exclusion (though that would be nice) I just want an understanding of if/how the chains relate to each other.

Tracy
Last edited by TKiel on Wed Feb 15, 2006 12:42 am, edited 3 times in total.
TKiel
 
Posts: 209
Joined: 05 January 2006

Re: Colouring with three conjugate chains

Postby ronk » Mon Feb 13, 2006 5:39 pm

TKiel wrote:A & B share a group, therefore either a or b is true. a & c share a group, therefore either A or C is true. What I can't make sense of is if/how B-b relates to C-c.
.....................
I just want an understanding of if/how the chains relate to each other.


Since B!A (B true excludes A true) and a!c, then B!c and any candidate that sees both b and C may be eliminated... but r1c5 has no candidate.

You get the same result by starting with the a!c, i.e, since c!a and A!B, then c!B.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby TKiel » Mon Feb 13, 2006 8:53 pm

Ron,

Thanks for the reply. I think I understand the relationship but let me try to explain it to make sure.

B and c can't both be true, since then neither A nor a could be true (which would be a contradiction), therefore either/both b or C have to be true and any cell that 'sees' both b and C can be excluded.

So in general when dealing with three conjugate chains, one way to make them relate is to identify which marker in each of two different chains negates both markers in the third chain and the intersection of the opposite markers in the first two chains is where to make the exclusion.

Tracy

(edited to incorporate Ronk's suggestion below)
Last edited by TKiel on Wed Feb 15, 2006 11:58 pm, edited 1 time in total.
TKiel
 
Posts: 209
Joined: 05 January 2006

Postby ronk » Mon Feb 13, 2006 11:05 pm

TKiel wrote:I think I understand the relationship but let me try to explain it to make sure.

B and c can't both be true, since then neither A nor a could be true (which would be a contradiction), therefore either b or C have to be true and any cell that 'sees' both b and C can be excluded.

That's correct. I would just change "either b or C have to be true" to "either b, or C, or both b and C have to be true". The procedure of your 2nd paragraph is correct as well, but it's not (easily) extendible to four conjugate chains.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby TKiel » Tue Feb 14, 2006 1:19 am

Ron,

Good point about either or both and thanks for the help. Now I just hope to be able to use it sometime.

Tracy
TKiel
 
Posts: 209
Joined: 05 January 2006

Postby TKiel » Wed Feb 15, 2006 5:18 am

The following puzzle is a Simple Sudoku extreme. Filtering on 8's shows the following four conjugate chains:
Code: Select all
 *--------------------------------------------------------------------*
 |                      |                      |                      |
 |                      |                      |                      |
 |                      | 389C    13789c       |                      |
 |----------------------+----------------------+----------------------|
 | 358A                 |                      |                689a  |
 | 4578          478B   |                      |                1678A |
 |                      |                      |                      |
 |----------------------+----------------------+----------------------|
 | 2468          4689b  | 25689   589C         |                      |
 |                      |                      |                      |
 | 28d                  | 2389D                |                      |
 *--------------------------------------------------------------------*

I can see that A!B & C!b, so either/both of a & c must be true, but that doesn't lead to an exclusion. I also see that D shares a group with C and d shares a group with both A & b, but can't see how to put any of that info to practical use. Help is needed and appreciated.

Tracy
TKiel
 
Posts: 209
Joined: 05 January 2006

Postby Carcul » Wed Feb 15, 2006 10:01 am

Hi Tracy.

Its not great help, but the only thing that I can say is that I cannot see any possible elimination of "8" in this grid.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby emm » Wed Feb 15, 2006 11:04 am

Hi Tracy, my understanding of your puzzle is this

A excludes B, and C excludes b => A excludes C
=> one if not both of a and c must be true
=> you can eliminate any cells that intersect a and c ... but none do

C excludes D and b excludes d => C excludes b
=> one if not both of c and B must be true
=> you can eliminate any cells that intersect with c and B ... but none do

I don’t see that the 4 chains in this example cross over in a way that you can make eliminations... did you expect them to?
emm
 
Posts: 987
Joined: 02 July 2005

Postby ronk » Wed Feb 15, 2006 12:10 pm

Tracy, when an x-wing, swordfish, jellyfish, or squirmbag "covers" ALL the candidates ... there is no point in attempting coloring. These patterns are irreducible with any pure x-cycle technique.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby TKiel » Wed Feb 15, 2006 2:35 pm

em -- I wasn't really expecting anything. Merely hoping, I guess. Ronk explained, in the first part of this thread, how three chains could relate to each other and which marks could be used to make exclusions, but he said that relationship is not easily extendable to four chains. So I was trying to figure out the relationship with four chains and when I noticed the four chains in this puzzle that interacted in as many ways as they did, I was hoping that it could be used as an example to show at least one such relationship, even if it didn't actually lead to an exclusion.

Ronk -- I didn't notice that it was a squirmbag (too busy looking at the trees to see the forest), but it certainly makes sense that no exclusions are possible using x-cycle in such a situation.

In general, would it be safe to say, that no matter how many different conjugate chains exist, only three at a time, but not necessarily the same three, can be linked in such a manner that would possibly lead to an exclusion? And the only real advantage to more chains is more different three chain connections?

Thanks to all for the replies.

Tracy
TKiel
 
Posts: 209
Joined: 05 January 2006

Postby ronk » Wed Feb 15, 2006 4:24 pm

TKiel wrote:In general, would it be safe to say, that no matter how many different conjugate chains exist, only three at a time, but not necessarily the same three, can be linked in such a manner that would possibly lead to an exclusion?

Yes, and often only two of them at a time.

And the only real advantage to more chains is more different three chain connections?

Once in a while you actually need all four. Here is puzzle #6789 from Gordon Royle's 32930 ...
Code: Select all
 ...|28.|.3.
 1.5|...|6..
 ...|9..|...
 ---+---+---
 .8.|...|32.
 7..|.1.|...
 ...|...|...
 ---+---+---
 4..|...|1.5
 .2.|8..|...
 ...|...|...

... which with basic techniques can be advanced to ...
Code: Select all
 6      47     47     | 2      8      1      | 5      3      9
 1      9      5      | 347    347    347    | 6      8      2
 8      3      2      | 9      56     56     | 47     1      47
----------------------+----------------------+-------------------
 59     8      469    | 4567   4679   4679   | 3      2      1
 7      456    3469   | 3456   1      2      | 8      459    46
 2      1      346    | 3456   3469   8      | 479    4579   467
----------------------+----------------------+-------------------
 4      67     8      | 367    2      3679   | 1      679    5
 59     2      1      | 8      45679  45679  | 479    467    3
 3      567    679    | 1      45679  45679  | 2      4679   8

... for a 9s coloring map of ...
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
 - - - + - - - + - - -
 C . 9 | . 9 9 | . . .
 . . A | . . . | . a .
 . . 9 | . 9 . | D 9 .
 - - - + - - - + - - -
 . . . | . . B | . b .
 c . . | . 9 9 | d 9 .
 . . C | . 9 9 | . 9 .

I'll leave identification of the chaining and the elimination as an exercise.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Wed Feb 15, 2006 6:08 pm

four chains?! I can do it with one strong link and my new pet, the Empty Rectangle!:)

First of all, I assume you ment the candidate grid to look like this:
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
 - - - + - - - + - - -
 9 . 9 | . 9 9 | . . .
 . . 9 | . . . | . 9 .
 . . . | . 9 . | 9 9 .
 - - - + - - - + - - -
 . . . | . . 9 | . 9 .
 9 . . | . 9 9 | 9 . .
 . . 9 | . 9 9 | . 9 .


then you have:
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
 - - - + - - - + - - -
 9 . 9 | .#9 9 | . . .
 | . 9 | X . X | . 9 .
 | . . | X 9 X | 9 9 .
 | - - + - - - + - - -
 | . . | . . 9 | . 9 .
 9 . . | .-9 9 | 9 . .
 . . 9 | . 9 9 | . 9 .

| = shows strong link
X = shows the Empty Rectangle (ER)
# = shows the Empty Rectangle Intersection (ERI)
- = shows the candidate that can be eliminated


I know this is not coloring, but 4 chains seems excessive. Carcul can translate my example into an x-cycle as well!:D

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby Carcul » Wed Feb 15, 2006 7:04 pm

Hi Havard.

Havard wrote:Carcul can translate my example into an x-cycle as well!


And here it is:

[r8c5]-9-[r8c1]=9=[r4c1]-9-[r4c5|r4c6]=9=[r6c5]-9-[r8c5], => r8c5<>9.

However, a more clever deduction would be the following:

[r4c1]=9=[r8c1]-9-[r8c7]=9=[r6c7]-9-[r6c5]=9=[r4c5|r4c6]-9-[r4c1], => r8c5,r8c6,r6c8,r4c3<>9.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Wed Feb 15, 2006 8:07 pm

Havard wrote:I know this is not coloring, but 4 chains seems excessive.

Excessive? You've never heard of x-cycles of length 7? The nice loop guys "break" the strong links of longer chains to create weak inferences for their expressions. Why not use weak links as weak inferences when that's what the puzzle presents?

Havard wrote:I can do it with one strong link and my new pet, the Empty Rectangle!

Very nice, but I was posting in the context of the thread. You do realize the Empty Rectangle ... when properly used ... IS a strong link, don't you?

BTW your Empty Rectangle didn't pick up the same elimination.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Wed Feb 15, 2006 8:42 pm

Hei ronk!:)

ronk wrote:Excessive? You've never heard of x-cycles of length 7? The nice loop guys "break" the strong links of longer chains to create weak inferences for their expressions. Why not use weak links as weak inferences when that's what the puzzle presents?

heh! My whole "misson" is to find easier ways to explain very complicated stuff, only available to the sudoku-geniuses on this forum!:) I respect the x-cycle as a fantastic thing, but I think it's hard for most people to relate to. I feel a bit the same with coloring.

ronk wrote:Very nice, but I was posting in the context of the thread. You do realize the Empty Rectangle ... when properly used ... IS a strong link, don't you?

Yup, grouped strong link!:) The ER is just there to make it easier to spot and relate to. (I am seeing that stuff much easier with them anyway...):)

ronk wrote:BTW your Empty Rectangle didn't pick up the same elimination.

no, I know. However, If I am assuming right, your coloring kills of the same 4 possible ones carcul showed (beautiful x-cycle by the way, Carcul!)
carcul wrote: [r4c1]=9=[r8c1]-9-[r8c7]=9=[r6c7]-9-[r6c5]=9=[r4c5|r4c6]-9-[r4c1], => r8c5,r8c6,r6c8,r4c3<>9


Now all of these can be eliminated much simpler with just three strong links:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
- - - + - - - + - - -
9 .-9 | . 9 9 | . . .
| . 9-------------9 .
| . . | . 9 . | 9-9 .
| - - + - - - + | - -
| . . | . . 9 | | 9 .
9 . . | .-9-9 | 9 . .
. . 9 | . 9 9 | . 9 .

or as Carcul would say:
[r4c1]=9=[r8c1]-9-[r8c7]=9=[r6c7]-9-[r5c8]=9=[r5c3]-9-[r4c1], => r8c5,r8c6,r6c8,r4c3<>9
(oh my god, now I am making those too...):)

So my point was that using 4 strong links seemed at least one too many! I have actually yet too see a puzzle that needs 4 strong links to solve. Even the classic "needs jellyfish" puzzle from ages ago can be solved with just three strong links... So in my opinion, Tracy is right in saying that:
TKiel wrote:In general, would it be safe to say, that no matter how many different conjugate chains exist, only three at a time, but not necessarily the same three, can be linked in such a manner that would possibly lead to an exclusion? And the only real advantage to more chains is more different three chain connections?

At least your example did not disprove this.

ah well, I am sure someone will prove me wrong...

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Next

Return to Advanced solving techniques