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:
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)
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...
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:
and here is another one:
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:
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:
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.nethappy hunting!
Havard