Rätsel und Puzzles

Sudoku

Meisterhafte Lösungstechniken

Die meisterhaften Strategien sind in der Regel so kompliziert, dass sie von einem menschlichen Löser kaum angewandt werden können. Nichtsdestotrotz sind die hier aufgeführt, um zu zeigen, dass man auch Aufgaben durch reine Logik lösen kann, bei denen man allgemein meint, dass es ohne Raten nicht geht.

Grundlegende Strategien:
Naked Pairs, Naked Triples, Naked Quads, Hidden Pairs, Hidden Triples, Hidden Quads, Intersection Removal, Pointing Pairs/Triples, Box/Line Reduction
Fortgeschrittliche Strategien:
X-Wing, Swordfish, Jellyfish, Squirm Bag, Turbofish, Finned X-Wing, Sashimi Finned X-Wing
Meisterhafte Strategien:
Singles Chains (Simple Coloring), Multi-Coloring, Y-Wing (XY-Wing), Y-Wing Chain, XY-Chains, XYZ-Wing, WXYZ-Wing, Aligned Pair Exclusion, Remote Pairs, Unique Rectangles, Guardians (Broken Wings)

Signgle Chains

(auch: Coloring oder Open Chain of Sudo)

In the example to the right there are only two 5's at A and B IN THAT ROW. Our first pair. B and C link two 5's in their column. And so on to D

We are hoping to make an odd number of links (the green lines in the diagram). If we do then something very useful occurs.

Singles Chain Example 1: Load Example or From the start

 

Chains can be any length. In some cases, ridiculously long as in this example. Here twelve cells (A to L) are joined by eleven links to target the cell at G2.

The minimum number of links is 3. It will be a rare occasion if you need more than 5.

Singles Chain Example 2: Load Example or From the start

 

We'll go back to our first example. You assign the start of a promising chain with an arbitary colour, in this case Green (A at D3). Remember, we are only looking at candidate 5 and units with two 5s in them (called conjugate pairs).

A has two conjugate pairs, B and X - which are painted in an alternative colour, blue. From cell B I can find two more pairs at C and E which I colour in green. Both these point to D which must be coloured blue, as well as F along the bottom row.

Now we have arrived at the contradiction. X and D are both blue and they are in the same unit (the row in this case).

Our first rule is: whenever a candidate outside the chain relates by column, row or box to two alternately coloured cells in a singles chain, that 'non-chain' candidate can be excluded. This applies to X.

Colouring Example 1:

 

Multi-Coloring

(siehe auch: http://www.setbb.com/phpbb/viewtopic.php?p=2575&mforum=sudoku#2575)

Given two chains we can label them A and B. A+ and A- will indicate the alternating states so that EITHER all of A+ are true OR all of A- are true. We don't know which way round yet. Similarly B+ and B- indicate alternating true/false for that chain. C+ and C- continues the theme if there are more chains on the same candidate number. Give A+, A-, B+ and B- we can colour them on the board to see the patterns.

Type 1 Multi-Colouring
The Rule is as follows: If A+ shares a unit with B+ and B- then A+ must be the false candidate since either B+ or B- must be true.

 

In this Sudoku we've looking at number 7 and labelled two chains A and B and settled on the plus and minus symbols. I have labelled them so that they match the rule. (Don't make a category mistake and think the rule applies just because you've assigned the lables!).

Now the yellow cell marked A- does not share a unit with and B. However, all three cells marked A+ can see a B+ or a B- in one or more shared units. Since the solution cannot be both B+ and B- every cell in A+ must be false and number 7 can be removed.

Multi-Colouring Type 1, Example 1: Load Example or From the start

 

Interestingly, although B can be a chain of just two cells A must be a longer chain. Otherwise we'd be in a situation where the sudoku has two solutions or multi-colouring can be reduced to a Unique Rectangle.
 

Multi-Colouring Type 1, Example 2: Load Example or From the start

 

This is a bit of a mouthful. What we're looking at are cells marked A+ which can see B+ cells but A- cells cannot see B- cells. A+ and B+ both can't be true since they share units in two cases. One or perhaps both of the units marked A- and B- must be true. All cells that can see an A- and a B- can't contain the candidate, in this example number 8. In R3C5 an 8 can see R2C4 AND R8C5. Similarly the 8 in R7C4 can see R2C4 and R8C5/R7C9.

This smaller example might be more easy to understand. The labels are the same so that one A+ can see a B+. There is just one place where a 7 is at the overlap of an A- and a B-.

Multi-Colouring with 3+ chains
I don't have an example of a sudoku requiring a multi-colouring solution using three or more chains. I'd be very grateful for an example.

 

Y-Wing

(coined here)

This is an excellent candidate eliminator. The name derives from the fact that it looks like an X-Wing - but with three corners, not four. The forth corner is where the candidate can be removed but it leads us to much more as we'll see in a minute.

Lets look at Figure 1 for the theory.

A is a locked pair and so is B. In two corners an occurrence of A is shared with another number C. B also shares C. The cell marked AB is the key. If the solution to that cell turns out to be A then C will definitely occur in the lower left corner. If AB turns out to be B then C is certain to occur in the top right corner. C is a complementary pair.

So whatever happens, C is certain in one of those two cells marked C. The red C is can be 'seen' by both Cs - the cell is a confluence of both BC and AC. Its impossible for a C to live there and it can be removed.



In Figure 2 I'm demonstrating the sphere of influence two example cells have, marked red and blue. X can 'see' all the red cells, Z can 'see' all the blue ones. In this case there are two cells which overlap and these are 'seen' by both.






If our A, B and C are aligned more closely they can 'see' a great deal more cells than just the corner of the rectangle they make. In Figure 3 B is a locked pair because they share the same box. A is a locked pair because they share the same row. BC and AC can see all the cells marked with a red C where this Y-Wing can eliminate whatever number C is.

 

Figure 1



Figure 2



Figure 3


 

Figure 4



Figure 5


 

Y-Wing Chains

Our pivot chain for a y-Wing must proceed at odd numbered lengths. A Y-Wing is simply a chain with length = 1.

In Figure 1 we have a Y-Wing Chain marked our in green cells. The 5/7 pivot consists of three pairs of 5/7. The first 5/7 (in which ever order) is connected to the last 5/7 by a third 5/7 in the middle, and by definition this is a locked pair. If the first 5/7 is a 5 them the third one must be a 5 as well. Same goes for number 7.

Our pincer is based on the two green cells marked with a red border - the pairs 7/9 and 5/9. The principle of the Y-Wing says that any cells that both those can see we can eliminate the common number - in this case 9. The two cells marked with a red circle can be 'seen' by both and the 9 removed.

 

Figure 1
Load This Example From the start or at the required point

XY Chains

The example here is a very simple XY-Chain of length 4 which removed all 5's in the pink cells. The chain ends are A7 and C2 - so all cells that can see both of these are under fire. It's possible to start at either end but lets follow the example from A7. We can reason as follows
 

Figure 1
Load This Example From the start or at the required point

When you've got a good spread of bi-values this is a useful trick. Remote Pairs, described below are also a special sub-set of XY-Chains - they merely have a double-chain of inference through both values in each chain link because they contain the same values from start to end. Remote Pairs were discovered/described first before this more general approach. 

Figure 1
Load This Example From the start or at the required point

XYZ-Wing

(a.k.a. "Hinge", or "Extended Trio" (John MacLeod))

 

It follows therefore that one or other of the three cells must contain the common number; and hence any extraneous cell (there can only be two of them!) that "sees" all three cells of the Extended Trio cannot have that number as its true value.

It gets its name from the three numbers X, Y and Z that are required in the hinge. The outer cells in the formation will be XZ and YZ, Z being the common number.

In this example the candidate number is 7 and R3C5 is the Hinge. It can see a 1/7 in R2C4 and a 5/7 in R3C8. We can reason this way: If R2C4 contains a 1 then R3C5 and R3C8 become a naked pair of 5/7 - and the naked pair rule applies. Same with R3C8. If that's a 5 then R2C4 and R3C5 become a naked pair of 1/7 each. If any of the three are 7 then 7 is still part of the formation. Any 7 visible to all three cells must be removed, in this case in R3C6.

The second example shows a double XYZ-Wing. R4C6 is common to both XYZ-Wings.

Aligned Pair Exclusion

The logic on an XYZ-Wing is completely different and lot simpler than the Aligned Pair Exclusion described below but the funny thing is that XYZ-Wing is a total sub-set of APE. Every XYZ-Wing can be solved by APE (but not vis versa).

WXYZ-Wing

(a.k.a. "Extended Quad")

 

Its name derives from the four numbers W, X, Y and Z that are required in the hinge. The outer cells in the formation will be Wz, XZ and YZ, Z being the common number.

In this example our four-value hinge is R3C3 marked in green. The three outlier cells, marked in orange each contain a 9 (our Z) plus one other number unique to themselves and the hinge. It's important that these extra numbers really are common only to the hinge and there are no pairs like 5/9 and 5/9 in two of the orange cells.

There is only one cell that all four of the WXYZ can see - R3C1, marked in yellow. It has a 9 which can be removed. No matter what number is the final solution in the hinge, one of the WXYZ must be a 9.

XYZ-Wing, Example 1: Load Example or From the start

 

Aligned Pair Exclusion (APE)

This is an interesting strategy since it overlaps with Y-Wings and XYZ-Wings but uses very different logic. APE logic will solve an XY-Wing (3 bi-values) and an XYZ-Wing (bi-value <-> tri-value <-> bi-value).
There are two types of APE - the normal APE and Extended APE.

Aligned Pair Exclusion - Type 1

 

The Aligned Pair Exclusion can be succinctly stated: Any two cells aligned on a row or column within the same box CANNOT duplicate the contents of any two-candidate cell they both see.

The Y-Wing strategy has some diagrams (see Figure 2) to show how cells can see other cells along the row, column or box and how they intersect or overlap. In Figure 1 X and Y are two cells and the yellow shading shows the common cells they can both 'see'.

Lets consider all the possible pairs of numbers in X and Y. These are:

3 and 2 (in X and Y)
3 and 5
5 and 2
5 and 5
7 and 2
7 and 5


 

Now is obvious that 5 and 5 can't be a solution to X and Y. If any of the other pair solutions were true we'd be able to remove those solutions from the candidates in all the other yellow squares. The strategy asks us to look at all the bi-value cells X and Y can 'see'. Cells marked A, B and C containing 2/7 and 3/5 and 5/7 match some of the options we have for X and Y. Any of these pairs would remove ALL candidates from one of A, B or C which is illogical, captain. This means we can exclude them from possible solutions for X and Y. This leaves us with a shorter list:

3 and 2 (in X and Y)
5 and 2
 

What are we left with? According to our new list Y can only take the value 2 so we can remove 5.
We can also remove the 7 from X. This helps us solve the Sudoku.

Credits - Rod Hagglund first popularised this method. A good thread with a double example and walk-through is here

Aligned Pair Exclusion - Type 2

 

The Extended Aligned Pair Exclusion includes tri-values spread over two cells as part of the attack. APE 2 Says that any two cells with only abc excludes combinations ab, ac and bc from the pair under consideration.

This example is very clear since the two-cell tri-value is convieniently 4/5/6 in both cells. (see next example for alternative tri-value formations).

Lets consider all the possible pairs of numbers in X and Y first. These are:

1 and 4 (in X and Y)
1 and 6
1 and 8
4 and 4 (impossible)
4 and 6
4 and 8
6 and 4
6 and 6 (impossible)
6 and 8


 

Cell R5C6 marked C removes a 1/4 pair.

Now the tri-value: These are 4/5, 4/6 and 5/6.
Removing these from the possibles for X but Y leaves us:

1/4/6 remains in X but Y is reduced to 6/8. Why should this work? Well, 5 is not really part of the tri-value that effects our APE. The key combination is 4/6 and that does the damage. Pretend that X is 4 and Y is 6 (or the other way round). This would leave A and B both equalling 5. Thats illegal which is why 4/6 is a combination we can remove from possible pairs in X and Y.

 

1 and 6 (in X and Y)
1 and 8
4 and 8
6 and 8
 

Figure 3, Load This Example From the start or at the required point

 

In this second example the tri-value contained in A and B is 2/7/8. The only common value is 2. Nevertheless, the abc combinations are 2/7, 2/8 or 7/8.

All the possible pairs of numbers in X and Y are.
7 and 5 (in X and Y)
7 and 9
8 and 5
8 and 7
8 and 9


Our one tri-value which matches these is 7/8. If we remove 7/8 from our list Y is reduced to 5 and 9. We get a naked pair and the rest of the Sudoku solves. 

Credits: Myth Jellies came up with the insight for Type 2 (see bottom of this page)

Remote Pairs

The point of this test/strategy is that we want to eliminate the 9 from square Z and leave the 8. Can we do this logically, or must we guess? What about square X which also looks like a candidate for removing the 6 and 9?

 

Consider Figure 1. We have five squares with the same pairs of numbers. Arranged in a pentagram as a network diagram each square has four links to every other square.
I have drawn in red the links between locked pairs and ignored all other links. Let us say these links have a distance of 1 between the nodes.



Now, in figure 2, we map all the pathways of distance 2. Valid pathways must be along the routes defined in Figure 1. What we are mapping here is all the complementary pairs, and I've drawn the links green. Topologically there cannot be ANY red links matching two locked pairs with distance 2.


In figure 3, we are mapping all the possible pathways of distance 3. These paths represent connections between newly discovered locked pairs. There are only two possible paths in this example, and again they can only be between locked pairs at this distance.

If we had more nodes we could carry on like this and look for distance 4 paths representing new complementary pairs but distance 4 is not possible in this example.

However, we now know that we can show that AE is a locked pair if we can show that its minimum distance is an odd number (or distance mod 2 = 1 in arithmetical terms). They become a special locked pair I call a remote pair. Thus we may safely remove the 9 from Z. Because the distance between BE is an even number (2) we know we have a complementary pair and the information is useless for deciding the fate of X. Its important to remember numbers can be removed from any cell that both ends of the chain can see, so consider boxes as well as rows and columns.

Now the problem has been generalised we may proceed to code the rule into an algorithm. Test 9 on the solver page is the result.

Credits

I'd like to credit the person who posted the board I've worked from but they didn't leave a name. The debate on this problem is on this discussion forum. Philip Frampton summarised the solution for Z most concisely.


 

We would like to remove the 3 and 8 from Z and X. However, it is only safe to remove the numbers from Z. Why? Because AD is an odd number of locked pairs from each other (ACED or ACBFGD) . AG, whether you go via ACBFG or ACEDG are even numbers apart.

A word of warning though. It is essential that the line of attack is supported by a contiguous line of locked pairs. In the example on the right we have four pairs of 3/4 at A,B,C and D. However, while AB is connected and so is CD, there is no connection between the two groups. Therefore the elimination of the 3/4s on Z and X are not legal or logical.

Unique Rectangles

Unique Rectangles takes advantage of the fact that published Sudokus have only one solution. If your Sudoku source does not guarantee this then this strategy will not work. But it is very powerful and there are quite a few interesting variants. Note: Only Type 1 Unique Rectangles are currently included in the solver but for others you can load the Sudoku example which take it up to the point where the example occurs.

Credits first: The ideas for these strategies I have lifted wholesale from MadOverLord's description (11 Jun 05) on the forum at www.sudoku.com. The original Thread is here. To my credit I have provided my own examples. (please email me for other credit requests). I will stick to MadOverLord's nomenclature.


 

Noticing the 'Deadly Pattern'

In Figure 1 we have two example rectangles formed by four cells each. The pattern in red marked A consists of four conjugate pairs of 4/5. They reside on two rows, two columns and two blocks. Such a group of four pairs is impossible in a Sudoku with one solution. The reason? Pick any cell with 4/5. If the cell solution was 4 then we quickly know what the other three cells are. But it would be equally possible to have 5 in that cell and the others would be the reverse. There are two solutions to any Sudoku with this deadly pattern. If you have achieved this state in your solution something has gone wrong.

The pattern ringed in green looks like a deadly pattern but there is a crucial difference. The 7/9 still resides on two rows and two columns, but instead if two boxes it is spread over four boxes. Now, such a situation is fine since you can't guarantee that swapping the 7 and 9 in an alternate manner will produce two valid Sudokus. One of them is the real solution, the other a mess. Why? Swapping the 7 and 9 around places them in different boxes and 1 to 9 must exist in each box only once. In the red example, swapping within the box does not change the content of that box.


Type 1 Unique Rectangles

 

Figure 1


 

The proof is pretty straightforward once you get your head around the basic idea. Assume R5C6 is 5. That forces R5C4 to be 7, R2C6 to be 7, and R2C4 to be 5. That's the deadly pattern; you can swap the 5's and 7's and the puzzle still can be filled in. So if the Sudoku is valid, R5C6 cannot be 5. The exact same logic applies if you assume R5C6 is 7.
So R5C6 can't be a 5, and can't be a 7
- it must be either 3 or 6.


Type 2 Unique Rectangles

 

Figure 2 - Load This Example

To make subsequent discussion easier to follow, we will refer to the two squares that only have two possibilities as the floor squares (because they form the foundation of the Unique Rectangle); the other two squares, with extra possibilities shall be called the roof squares.

 

In this "Type-2 Unique Rectangle", one of the blocks contains the floor squares, and the other contains the roof squares. In order to avoid the deadly pattern, 8 must appear in either R2C4 or R2C6 (the roof squares). Therefore, it can be removed from all other squares in the units (row, column and box) that contain both of the roof squares (in this case, row 2 and block 2).

Now that you've gotten your head around the basic unique rectangle concept, the proof should be pretty obvious:

If neither R2C4 or R2C6 contains an 8, then they both become squares with possibilities 2/9. This results in the deadly pattern - so one of those squares must be the 8, and none of the other squares in the intersecting units can contain the 8. So R2C3, R3C4 and R3C6 can have 8 removed. This cracks the Sudoku.


Type 2B Unique Rectangles

 

Figure 3 - Load This Example

In this puzzle, we have the same pattern of 4 squares in 2 blocks, 2 rows and 2 columns. The floor squares are R1C1 and R1C9, and the roof squares are R2C1 and R2C9. However, in this Unique Rectangle, each of the blocks contains one floor and one roof square. This is perfectly fine, but it means that the only unit (row/column/box) that contains both of the roof squares is row 2, so that is the only unit that you can attempt to reduce; in this case, R2C7 cannot contain a 8. This is called at "Type-2B Unique Rectangle".


 

Figure 4 - Load This Example

Look closely at the roof squares, R3C1 and R3C3, but this time, don't look at their extra possibilities; look at the possibilities they share with the floor squares.

If you look carefully, you'll see that in box 1, the roof squares are the only squares that can contain a 5. This means that, no matter what, one of those squares must be 5 - and from this you can conclude that neither of the squares can contain a 1, since this would create the "deadly pattern"! So you can remove 1 from R3C1 and R3C3.

Nomenclature: When two squares are the only two squares in a unit that can have a particular value, they are referred to as a conjugate pair on that value.

This is an example of a "Type-4 Unique Rectangle". As you have probably realized, since the roof squares are in the same block, you can search for conjugate pairs in both of their common units (the row and the block, in this case).



 

Figure 5 - Load This Example

And, as you might expect, there is a Type-4B Unique Rectangle variant, in which the floor squares are not in the same block, and you can only look for the conjugate pair in their common row or column. For example:

In this case, since 7 can only appear in row 4 in the roof squares, 5 can be removed from both of them.

As Type-4 Unique Rectangle solutions "destroy" the Unique Rectangle, it is usually best to look for them only after you've done any other possible Unique Rectangle reductions.



 

Figure 6 - Load This Example

Guardians

(a.k.a. Broken Wings, Turbot-Fish)

This strategy works with single numbers.
We've already used closed loops of conjugate pairs to find things like X-Wings and Sword-Fish. X-Wings contains 4 cells in a perfect rectangle. Sword-Fish requires 6 or 9 cells in a grid. This strategy works with odd numbers of pairs in a loop starting with 5. There are several varieties depending on how 'perfect' the loop is.

Let us use the words perfect pair instead of conjugate pair to mean any number that exists only twice in one unit (row, column or box). This means we can use imperfect to mean a number that occurs three or more times in a unit. (Obviously if it only occurred once it would solve that cell).

Credits: I want to thank Rod Hagglund for explaining this technique although for Type 1 Single Guardians (this first example) Singles Chain might be simpler logic. Some of the Type 2 and Type 3 Guardians can also be attacked with Multi-Colouring but I've not discovered how with the two examples below.

 

In Figure 1 we have highlighted the number 3. Amongst all the candidate threes is a loop of five 3's. They form four perfect pairs:

R5C7 - R5C5 - along the row
R5C5 - R7C5 - along the column
R7C5 - R7C9 - along the row
R7C9 - R4C9 - along the column

To close the loop we have an imperfect triplet in the sixth box.

The question is: can a closed loop of five candidate cells be constructed with each cell perfectly-paired in two ways with the next linking cells in the loop? The answer is no. Such a formation is impossible in a Sudoku puzzle. In such a loop, if you "placed" a candidate in any one of the cells and followed the consequences around the loop, you'd generate an automatic contradiction - forcing the number to disappear entirely from a row, cell or block, or to appear twice in a single line or block, depending on how you proceed.
 

To repeat, In an actual Sudoku there can never be a closed loop of five perfectly paired cells. And that is exactly where the solving technique lies. Any such structure must have one or more cells that disrupt the perfect pairings. We can refer to the cells which prevent one of the pairings from being perfect as guardians. Here's the trick: logically, one or more of the guardians must contain the candidate number. If none of the guardian cells were real, then the pairings would all be perfect and, as was already noted, that is flat-out impossible in a valid Sudoku. Accordingly, we can make the following assertions:

• If there is only one guardian cell, the candidate number can be installed in that cell.
• If there is more than one guardian, any cell that is seen by all the guardian cells cannot contain the candidate number; hence
• If all the guardian cells are in a single column, row or block of the Broken Wing, the candidate can be erased from both the Broken Wing cells in that column, row or block.

Type 2 - Double Guardians

In Figure 2 we have highlighted the number 7. Amongst all the candidate 7's is a loop of five 7's. There are two imperfect connections in the loop:

R8C3 - R8C9 - along the row
R8C3 - R7C2 - within the box

This gives us two guardian 7's in R7C1 and R8C7 marked in red squares. Whatever cells these two can both 'see' we can eliminate the 7 from them. Since in this example they form the opposite corners of a rectangle we can safely remove the 7 from R7C7 marked in a red circle. The other corner, R8C1, contains a solved square.

Solving R7C7 allows us to complete the puzzle using other strategies.

 

Type 3 - Disruptive Guardians

 

Figure 3
Load This Example From the start or at the required point