Strong Links for Beginners

Advanced methods and approaches for solving Sudoku puzzles

Strong Links for Beginners

Postby Havard » Mon Feb 27, 2006 11:56 am

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 at www.sudoku.frihost.net

happy hunting!

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby blairallen » Wed Mar 01, 2006 12:07 am

This is by far the best explanation I've seen of this technique, which I believe is also used in 'colouring'. Thank you for the detailed explanation!

Blair
blairallen
 
Posts: 4
Joined: 27 February 2006

Postby emm » Wed Mar 01, 2006 10:43 am

Nice one Havard! I enjoyed reading this. I'm sure your clear presentation, your lack of mathematical jargon and your friendly style will appeal to a lot of people.
emm
 
Posts: 987
Joined: 02 July 2005

Postby Havard » Wed Mar 01, 2006 10:51 am

thanks!:D
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Kent » Sat Mar 18, 2006 9:21 pm

Best explaination ever!!!!Good job Havard!! I hope u can write more on other techniques!!!
Kent
 
Posts: 98
Joined: 28 February 2006

strong links

Postby cabbie8 » Sat Mar 18, 2006 9:47 pm

hmm...will try this technique
am very new to sudoku - 1 weekend ago i actually picked up a sudoku book and started solving easy/mild
very addictive!!!
cabbie8
 
Posts: 1
Joined: 18 March 2006

Harvard's Simple Solution

Postby billo » Sun Mar 19, 2006 8:36 pm

Great description. One of the best I've seen. I'm new to the game and this is a big help. Hopefully it will get me past [quote]challenging[/quote] and on to tougher puzzles.:D
billo
 
Posts: 1
Joined: 19 March 2006

Thanks!

Postby mona187 » Mon Mar 20, 2006 8:03 pm

Thank you, thank you, thank you. I have taught myself most of the Sudoku basics through just working the puzzles and have been looking for some more advanced techniques to try. However, all the references to filets and turbot fish left me floundering! (sorry about that - I couldn't resist!) not to mention grids with secret codes using anonymous symbols.

Your explantion and examples using real numbers were great! It makes perfect sense now. and I will be trying out some of the techniques the next time I find myself stuck. I also look forward to reading any more msgs you may have posted, but have run out of time for right now!

Keep it up.
mona187
 
Posts: 4
Joined: 20 March 2006

Postby Kent » Tue Mar 21, 2006 2:47 am

Havard should post more techniques in here especially with some real examples.
Kent
 
Posts: 98
Joined: 28 February 2006

Postby SHuisman » Thu Apr 27, 2006 2:42 pm

If you have 2 strong links, both horizontal, and there a column-buddy. ( a skyscraper on it's side), is this also called a skyscraper ?
SHuisman
 
Posts: 17
Joined: 23 March 2006

Postby Havard » Thu Apr 27, 2006 9:29 pm

SHuisman wrote:If you have 2 strong links, both horizontal, and there a column-buddy. ( a skyscraper on it's side), is this also called a skyscraper ?


Well I do...:) You could always just turn the newspaper 90 degrees if you wanted it the "right" way!:D

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

exlusion

Postby 2peter » Sat May 06, 2006 6:53 am

Can anybody explain why the 3's in A7 and A9 are excluded from forming a 'strong link' ?

"Two cells are buddies if they share a column, row or box!" ? ?
I say, any column, row or box exist out of sharing cells.
so what is special about some cells that they are elevated to 'buddy' status?

Thanks, Peter
2peter
 
Posts: 2
Joined: 05 May 2006

Re: exlusion

Postby Havard » Sat May 06, 2006 11:03 am

2peter wrote:Can anybody explain why the 3's in A7 and A9 are excluded from forming a 'strong link' ?

"Two cells are buddies if they share a column, row or box!" ? ?
I say, any column, row or box exist out of sharing cells.
so what is special about some cells that they are elevated to 'buddy' status?

Thanks, Peter


Hi Peter. I have a quiz for you... Can you tell me which ones of the following candidates are buddies, and which ones are not?

Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. a . | . . . | . g .
------+-------+------
. . e | . . . | . f .
. . . | . . . | . . .
. b . | . . . | . . .
------+-------+------
c . . | . . . | . . .
. . . | . . . | d . .
. . . | . . . | . . .


Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby 2peter » Sat May 06, 2006 12:27 pm

Hello Havard,

Thanks for your reply and quiz.
Limiting myself to 'a' and 'd':
(Given: "Two cells are buddies if they share a column, row or box!")

any cell in row '3' shares the fact of being on this row, so also the cell containing 'g' is a buddycell of 'a',

any cell in column '2' shares the fact of being on this column, so also the cell containing 'b' is a buddycell of 'a',

the cell of poor candidate 'd' has the usual number of 24 buddycells, non of these contain a candidate so he (or she) is all-alone.

I am sure it is a blind-spot on my side (just starting with this sport), but what is the unique property of a given cell, to be elevated to 'buddy' status as described by you on Feb 27?

Thanks, Peter
2peter
 
Posts: 2
Joined: 05 May 2006

Postby Havard » Sat May 06, 2006 12:38 pm

2peter wrote:Hello Havard,

Thanks for your reply and quiz.
Limiting myself to 'a' and 'd':
(Given: "Two cells are buddies if they share a column, row or box!")

any cell in row '3' shares the fact of being on this row, so also the cell containing 'g' is a buddycell of 'a',

any cell in column '2' shares the fact of being on this column, so also the cell containing 'b' is a buddycell of 'a',

the cell of poor candidate 'd' has the usual number of 24 buddycells, non of these contain a candidate so he (or she) is all-alone.

I am sure it is a blind-spot on my side (just starting with this sport), but what is the unique property of a given cell, to be elevated to 'buddy' status as described by you on Feb 27?

Thanks, Peter


Two cells are buddies if they share a row, column or box. It is as simple as that. One single cell can not be a "buddy". It needs another cell to buddy up with. Your observations about "a" being a buddy with "b" and "g", and d having no buddies was correct. So when you have two strong links, they need to have at least one cell (each) that are buddies for you to be able to use the links for eliminations.

Another useful word is what cells one single cell can "see". As you pointed out, any one cell can "see" 20 (not 24) other cells on the board. Buddies happend when two cells can "see" eachother.:)

All clear?:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Next

Return to Advanced solving techniques