Strong Links for Beginners

Advanced methods and approaches for solving Sudoku puzzles

Great Explanations!

Postby jimbodiggy » Thu Jun 08, 2006 3:12 pm

Not sure if this thread is stale by now but wanted to thank you for the great explanations and diagrams. They helped alot.:D
jimbodiggy
 
Posts: 1
Joined: 08 June 2006

Re: Great Explanations!

Postby Havard » Thu Jun 08, 2006 6:26 pm

jimbodiggy wrote:Not sure if this thread is stale by now but wanted to thank you for the great explanations and diagrams. They helped alot.:D


As long as people keep reading it, it will never go stale!:) Thank you!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Viggo » Mon Jun 12, 2006 7:14 pm

Havard, thank you for a great post. It is a well written article for a beginner to get familiar with strong links, Turbot Fish and Skyscrapers

Perhaps a beginner may know about Pointing Pairs and Box Line Reduction, before they read about strong links. The simplest way to use strong links is for these simple reductions, and perhaps it helps the understanding to mention that. Here we use one strong link and two weak links for the elimination of candidates.

Example:

Code: Select all
------+-------+------
. . . | A . . | . A .
. . . | . . A | A . .
A---A | * * * | * * *
------+-------+------


If you have got a strong link between two candidates within a box (only two of this candidate in the box) and at the same time these candidates are in the same row, then the remaining candidates in this row can be eliminated in the other boxes (they are marked by a * above). Obviously, you can do this with a box and a column too. If you have got three candidates within the box and row/column, then you have a grouped strong link between the three candidates. One of the three candidates have to be true. Therefore this strong grouped link do also eliminate the remaining candidates in the row/column. This reduction technique is called "Pointing Pair". You have two weak links from the ends of the strong link to each candidate to be eliminated.

Code: Select all
------+-------+------
* * * | . A . | . A .
* * * | . A . | . . A
A---A | . . . | . . .
------+-------+------


If you have got a strong link between two candidates in a row (only two of this candidate in the row) and at the same time these candidates are in the same box, then the remaining of these candidates in this box can be eliminated (they are marked by a * above). Obviously, you can use this on a column too. If you have got three candidates within the row/column and box, then you have a grouped strong link between the three candidates. One of the three candidates have to be true. Therefore this strong grouped link do also eliminate the remaining candidates in the box. This reduction technique is called "Box Line Reduction". You have got two weak links from the ends of the strong link to each candidate to be eliminated.

The normal way of using Pointing Pairs and Box Line Reduction are available without the strong link, but then you have got a single in a box, row, or column instead, which is a simpler way of reduction with a fixed candidate.

The concept of grouped strong links may be too difficult for a beginner - I don't know. However, I just feel, that the simplest way of using a strong link should be present in this thread.

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Postby jeanboucher » Sun Aug 13, 2006 5:34 pm

Trying to understand the concept!

Did I get it right?

Image
jeanboucher
 
Posts: 24
Joined: 04 August 2006

Yes

Postby keith » Sun Aug 13, 2006 6:02 pm

You got it right.

Now, label each alternate node of your diagram "+" and "-". Either + is true (=2) or - is true. So, any cell that "sees" both a + and a - cannot be <2>.

So, eliminate <2> as a candidate in R4C2 and R5C3. This is called "simple colo(u)ring".

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby jeanboucher » Sun Aug 13, 2006 6:33 pm

Can You illustrate it for me Keith.
I am visual (I am a Magician)

I found this thread by searching for coloring actually...

Thanks
jeanboucher
 
Posts: 24
Joined: 04 August 2006

Try this

Postby keith » Sun Aug 13, 2006 8:37 pm

Get it now?

Image

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby jeanboucher » Mon Aug 14, 2006 6:46 am

Thank you keith.
Now I get it...
jeanboucher
 
Posts: 24
Joined: 04 August 2006

Postby jeanboucher » Sat Aug 19, 2006 2:20 am

Still working on that concept...

Did I get ALL the Strong Links for the 3 candidate?

Image


Can I eliminate the candidate 3 in R3-C3?

Image
jeanboucher
 
Posts: 24
Joined: 04 August 2006

Postby daj95376 » Sat Aug 19, 2006 2:50 am

I know Keith has been helping you ... and I hope no one minds if I join in.

All of your strong links look correct. Cell [r3c3] should be Yellow. All the other colors look correct.

Now, if a cell has a <3> and is in a row/column/box that already has a Pink cell and a Yellow cell, then the <3> can be removed from this cell. In your example, this is not the case.

However, it's also illegal for a row/column/box to have two cells with the same color. If you check [b1], [c2] and [r3], you'll see that this is the case in your example. What this means is that none of the Yellow cells can be <3>. You can now set all of the Pink cells to <3>.

BTW: What you have is an example of a BUG+1 with [r3c2] being the +1 cell. If you read up on BUG+1, you'll learn that [r3c2]=3 is needed. This assignment will jump out at you after you set all of the Pink cells to <3>.
Last edited by daj95376 on Fri Aug 18, 2006 11:49 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby jeanboucher » Sat Aug 19, 2006 3:27 am

daj95376 wrote:However, it's also illegal for a row/column/box to have two cells with the same color.


This why, I didn't Know If I could paint the R3C3 Yellow.

You are saying That I should have painted the r3c3 Cell yellow, & then get rid of ALL the candidate 3 in the yellow cell.
jeanboucher
 
Posts: 24
Joined: 04 August 2006

Postby daj95376 » Sat Aug 19, 2006 3:55 am

jeanboucher wrote:
daj95376 wrote:However, it's also illegal for a row/column/box to have two cells with the same color.


This why, I didn't Know If I could paint the R3C3 Yellow.

You are saying That I should have painted the r3c3 Cell yellow, & then get rid of ALL the candidate 3 in the yellow cell.

Yes!!! My suggestion of setting the Pink cells to <3> performs the eliminations and the assignments in one operation.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby jeanboucher » Sat Aug 19, 2006 4:07 am

Thank you for your help.

I am looking at the 'Bivalue Universal Grave' thread at this moment.
jeanboucher
 
Posts: 24
Joined: 04 August 2006

Re: Strong Links for Beginners

Postby Maria » Tue Mar 29, 2011 8:09 pm

Havard wrote:hi.

I got inspired to try and write up a little something about strong links so everyone can understand!:) For me, they represent the real fun in sudoku; finding patterns and putting them to use!

So before we go on we should establish a vocabulary that everyone can follow. I apologize if this is not in line with the standarised terms, but my point here is not to redefine stuff, it is to explain it!:)

First of all: What is a strong link?
A strong link (or a conjugate pair as it is also called) is when you only have two candidates of one number in any row, column or box!

look at this board:
Image

if you concentrate on all the candidates of the number 3. How many strong links can you find? Search the rows, columns and boxes, and count candidates in each of them. Every time you find just two of them, you have a strong link!

Now let's look at the right answer: (all strong links in blue)
Image

11 strong links! Now with that many strong links you will often be able to do some eliminations, and we will now look at how these eliminations are arrived at!

First of all we should establish the powerful logical properties of a strong link!

Now if we all agree that candidates are showing us where the big numbers could go, we can also agree on them showing us where the big numbers have to go. (if we have marked all candidates correctly for each cell) Now if there are just two places in a row where a number can go, we all agree that one of those two numbers is bound to be penciled out, and the other has to become one more filled in square on our sudoku-board! And this is why the strong link is so powerful, because we know that one of the candidates in the strong link has to be true!

When drawing strong links I use this notation:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. A . | . . . | . . .
--|---+-------+------
. | . | . . . | . . .
. | . | . . . | . . .
. | . | . . . | . . .
--|---+-------+------
. | . | . . . | . . .
. B . | . . . | . . .
. . . | . . . | . . .


So here we have a strong link AB! Now from what we have learned, we can now say:
If A is true then B is false.

This means that we put a big number in A, then we will have to wipe out the candidate for that number in B. But more importantly we can say:
If A is false then B is true.

In other words, if we for some reason can erase the candidate in A, we now know that B has to be a "big" number! This is very important, and can create some very powerful logic later on!

Ok so far? Now we need to establish another term: buddies!
Two cells are buddies if they share a column, row or box!

look at this:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
a . . | b . . | . . .
------+-------+------
. . . | . . . | . . .
e . . | . . d | . . .
. . . | c . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .


Here:
a and b are buddies because they share row 3.
b and c are buddies because they share column 4.
c and d are buddies because they share box 5.
d and e are buddies because they share row 5.
e and a are buddies because they share column 1.

ok? Buddies well understood?

We can then go on to look at strong links that are buddies, or have cells that are buddies! In fact, all the eliminations we will be looking at uses two strong links, where at least one cell in each link are buddies!

When finding eliminations with two strong links, one of the cells in both strong links have to be buddies!


This is the first requirement! If you have two strong links like this:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. A . | . . . | . . .
--|---+-------+------
. | . | . C . | . . .
. | . | . | . | . . .
. | . | . | . | . . .
--|---+---|---+------
. | . | . D . | . . .
. B . | . . . | . . .
. . . | . . . | . . .

there is no point going any further! This is useless! None of these two strong links have any buddies. But here:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. A . | . C . | . . .
--|---+---|---+------
. | . | . | . | . . .
. | . | . | . | . . .
. | . | . | . | . . .
--|---+---|---+------
. | . | . D . | . . .
. B . | . . . | . . .
. . . | . . . | . . .

It is a different story! Here A and C are buddies, and we might be able to do some eliminations.... (more on this later...)

And this is also important when dealing with two strong links:
Code: Select all
Two strong links that are connected, are USELESS!

That's right, when trying to find eliminations using strong links, links that look like this:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. A . | . . . | . . .
--|---+-------+------
. | . | . . . | . . .
. | . | . . . | . . .
. | . | . . . | . . .
--|---+-------+------
. | . | . . . | . . .
. B-------------C . .
. . . | . . . | . . .

Are useless! Not worth anything! Main reason for this is that we don't have 4 cells to deal with, just 3. The "B" is being used twice, and for strong link interactions this is not worth anything! (for us, for now anyway!) We need 4 cells to be able to do what we are going to do!:D

Ok! All well so far! We now know what strong links are, how they contain powerful logic and how to find out if two strong links have buddies or not...

Let's now look at how the logic works if we find two strong links that have buddies:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. A . | . . . | . . .
--|---+-------+------
. | . | . C . | . . .
. | . | . | . | . . .
. | . | . | . | . . .
--|---+---|---+------
. | . | . | . | . . .
. B . | . D . | . . .
. . . | . . . | . . .


In this example, we have the two strong links A-B and C-D. B and D are buddies!
I am now going to blurt out:
If you have two strong links where two cells are buddies, then one of the two other (not buddied) cells has to be true!

Let's look at that statement! What I am saying is that since B and D are buddies in our two strong links, then either A or C HAS TO BE TRUE!
Let's try it! If we make our logic starting-point: "A", we get the following.

Trying to prove that either A or C HAS to be true...
if A is true, that is obviously right!
now if A is false, then we get:
If A is false, B has to be true! (remember this about strong links!)
If B is true, then D is false! (because they are buddies!)
If D is false, then C has to be true! (again because it is a strong link)

And hence we get:
If A is true, then A is true...:)
If A is false, then C is true!
ERGO:
Either A or C HAS to be true!

YAY! Get it! It is quite beautiful if you ask me!:)

So now, what can we use this newly aquired knowledge for? I say we can eliminate candidates!

Let's look at our example again:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. A . | . . . | . . .
--|---+-------+------
. | . | . C . | . . .
. | . | . | . | . . .
. | . | . | . | . . .
--|---+---|---+------
. | . | . | . | . . .
. B . | . D . | . . .
. . . | . . . | . . .

Now if A was true, this would kill of all candidates in these positions:
Code: Select all
* * * | . . . | . . .
* * * | . . . | . . .
* A * | * * * | * * *
------+-------+------
. * . | . . . | . . .
. * . | . . . | . . .
. * . | . . . | . . .
------+-------+------
. * . | . . . | . . .
. * . | . . . | . . .
. * . | . . . | . . .

And if C was true, it would finish of all these ones:
Code: Select all
. . . | . * . | . . .
. . . | . * . | . . .
. . . | . * . | . . .
------+-------+------
* * * | * C * | * * *
. . . | * * * | . . .
. . . | * * * | . . .
------+-------+------
. . . | . * . | . . .
. . . | . * . | . . .
. . . | . * . | . . .


Now for the sharp eye! Are there any common "*" in either of these two? Why would we look for that? Because if we can find any candidates that can be elimintated with both A and C as true, we already know that either A or C HAS to be true, and hence we can eliminate them safely! Yippi! And the answer is: YES, it is! They are here:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. A . | . * . | . . .
------+-------+------
. * . | . C . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .

Unfortunately I have got some bad news for this one! Even if we can eliminate those candidates, it will be of no use to us... Simply becase it is not possible for any candidate to live there... Why? Because if there were any candidates at those two positions, then A-B and C-D would not be strong links... sorry!

However, if we instead look at this scenario:
Code: Select all
. . . | . . . | . . .
. . . | . C . | . . .
. A . | . | . | . . .
--|---+---|---+------
. | . | . | . | . . .
. | . | . | . | . . .
. | . | . | . | . . .
--|---+---|---+------
. | . | . | . | . . .
. B . | . D . | . . .
. . . | . . . | . . .

Now if A was true, this would kill of all candidates in these positions:
Code: Select all
* * * | . . . | . . .
* * * | . . . | . . .
* A * | * * * | * * *
------+-------+------
. * . | . . . | . . .
. * . | . . . | . . .
. * . | . . . | . . .
------+-------+------
. * . | . . . | . . .
. * . | . . . | . . .
. * . | . . . | . . .

and if C was true, it would kill of candidates in these positions:
Code: Select all
. . . | * * * | . . .
* * * | * C * | * * *
. . . | * * * | . . .
------+-------+------
. . . | . * . | . . .
. . . | . * . | . . .
. . . | . * . | . . .
------+-------+------
. . . | . * . | . . .
. . . | . * . | . . .
. . . | . * . | . . .

Now how many common "*" can you find this time?

The right answer is:
Code: Select all
. . . | . . . | . . .
* * * | . C . | . . .
. A . | * * * | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .

and by taking away the "useless" ones that can't be there anyway we are left with:
Code: Select all
. . . | . . . | . . .
* . * | . C . | . . .
. A . | * | * | . . .
--|---+---|---+------
. | . | . | . | . . .
. | . | . | . | . . .
. | . | . | . | . . .
--|---+---|---+------
. | . | . | . | . . .
. B . | . D . | . . .
. . . | . . . | . . .

This pattern is part of the Turbot Fish, and I have named it a "skyscraper" because of the way the two strong links looks a bit like two skyscrapers to me...:D That was not so hard was it?

So now for the big question: How many other two-strong link patterns exist? My answer: not so many! Let's list the different type of buddies you can have...
You can have row-buddies, column-buddies and box-buddies. Now our skyscraper was row-buddies. However, making it two strong links that are column-buddies would just turn it over on it's side: (possible eliminations shown with *)
Code: Select all
. . . | . * . | . . .
. . . | . * . | . . .
. A---------B | . . .
------+-------+------
. . . | . . * | . . .
. . . | . . * | . . .
. C-------D . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .

Now remember our picture of all those strong links! What if I told you that somewhere in there is a skyscraper hiding! See if you can find it. (don't cheat!)

solution:
Image
and here is another one:
Image


But back to how many other two-strong-link combinations are possible...
Let's take the case of if two strong links are box-buddies! Then you would have:

Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . A----------B . .
. . . | . . . | . . .
. C . | . . . | . . .
--|---+-------+------
. | . | . . . | . . .
. D . | . . . | . . .
. . . | . . . | . . .

Now using the same logic as we learned before, we know that either B or D has to be true, and they have one cell that they both target! Can you find it?
answer:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . A----------B . .
. . . | . . . | . . .
. C . | . . . | . . .
--|---+-------+------
. | . | . . . | . . .
. D . | . . . | * . .
. . . | . . . | . . .

And elimination can safely be done in that spot!
great huh?:D

This pattern is also part of the Turbot Fish, and I have named it "2-string kite" because of the way the box where the two strong links are buddies looks like a kite, and the 2 strong links looks like it's strings...:)

Now there is a 2 string kite hiding in the strong-link picture as well... Can you find it?

here it is:
Image

Now we have looked at two straight line-strong links and what happends if they are row, column and box-buddies. What could be left then?

Strong links can also sometimes be diagonal, and then you get another pattern if you can find a row or column buddy for that link.

Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . B | . . . | . . .
. / . | . . . | . . .
A . . | . . C | . . .
------+-----|-+------
. . . | . . | | . . .
. . . | . . D | . . .
. . . | . . . | . . .


As you can see, A and C are buddies (on row 6) and that means that either B or D has to be true... Now the elimination then occurs here:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . B | . . . | . . .
. / . | . . . | . . .
A . . | . . C | . . .
------+-----|-+------
. . . | . . | | . . .
. . * | . . D | . . .
. . . | . . . | . . .


This pattern is ALSO part of the Turbot Fish, and it was actually this pattern that inspired the name "Turbot Fish" given to it by Nick70. The reason is obvious if you draw out all the "lines":
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . B | . . . | . . .
. / | | . . . | . . .
A---+-------C | . . .
----|-+-----|-+------
. . | | . . | | . . .
. . *-------D | . . .
. . . | . . . | . . .

look! it's a little fishy!:D

And of course I have hidden a little Turbot Fish for you to find in the strong link picture as well:

here it swims:
Image


Now there is only really one case of two strong links we have not looked at! And that is the configuration known as the x-wing! Now in general terms, the two strong links not only buddy up once, but twice!
As you might have noticed, we have only looked at strong links that buddy up once! Now for x-wing, the two strong links buddy up twice, and this creates a even more powerful reduction!

look at this example:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. A---------------B .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. C---------------D .
. . . | . . . | . . .
. . . | . . . | . . .

As we can see, A & C are buddies in column 2 and B & D are buddies in column 8.
Now lets use our logic again, and again see what happends if A is True, and if A is false...

If A is true then C and B are both false.
if C is false, then D is true.
ERGO:
If A is true, then D is true!

If A is false, then B is true.
If B is true, then D is false
if D is false then C is true.
ERGO:
If A is false, then B and C is true!


hence we can say:
Either A and D is true, OR B and C is true


Now rest your eyes on column 2 and 8. If A and D are true, or B and C are true, it sure looks like column 2 and 8 has one cell that is true, no matter what! For column 2 either A or C is true, and for column 8 either B or D is true... And this means... ELIMINATION!!!!!!
Code: Select all
. * . | . . . | . * .
. * . | . . . | . * .
. A---------------B .
------+-------+------
. * . | . . . | . * .
. * . | . . . | . * .
. * . | . . . | . * .
------+-------+------
. C---------------D .
. * . | . . . | . * .
. * . | . . . | . * .


Now the x-wing comes in many variations, because both straight and diagonal strong links can buddy up in both rows, columns and boxes. Finding an X-wing is always good because as you can see, it will often allow for more eliminations then the other patterns we have looked at!

And that's it! There are no more possible configurations for two strong links! You have learned everything there is to know about it, and the good news is that:
*There is now no eliminations you can't do that can be done with "Turbot Fish"
*You will be able to do pretty much everything coloring can do as well! (even supercoloring!)

And when you are ready: Throw in another strong link! Use the logic described here, and you will be figuring out and maybe making your own patterns in no time!:)

If you want to, you can play around with strong links in my humble program found atwww.sudoku.frihost.net

happy hunting!

Havard



All extremely clear, thanks a lot
Maria
 
Posts: 30
Joined: 19 March 2011

Re: Strong Links for Beginners

Postby ronk-Moderator » Tue Mar 29, 2011 9:44 pm

Maria, rather than quoting an entire post, please quote selectively and appropriately. Thanks.
ronk-Moderator
Moderator
 
Posts: 24
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques