|
|
|
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.
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 of 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
|
Unique Rectangle Figure 1 |
For all Unique Rectangles we are going to look for potential deadly patterns and take advantage of them. A Type 1 Unique Rectangle is illustrated in Figure 2. The three circles marked in green rings contain 5/7. The fourth corner marked with a red square also contains 5/7 and two other candidates. If the 3/6 were removed from that cell we would have a Deadly Pattern. This cannot be allowed to happen so its safe to remove 5 and 7 from that cell.
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.
|
Unique Rectangle Figure 2: Load Example |
In Figure 3 we have a similar pattern, but this time, R2C4 and R2C6 (green circles at the top), the squares which share the same block have a single extra possibility - in this case, 8.
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.
|
Unique Rectangle Figure 3: Load Example |
I couldn't resist adding this example which I found while looking for Empty Rectangles. It's as clear as day how the 8s in H4 and H6 combine with the {1,6} Deadly Pattern. 8's on brown cells are eliminated. I need say no more.
|
Unique Rectangle Figure 4: Load Example or : From the Start |
Type 2B Unique Rectangles
|
There is a second variant of Type-2 Unique Rectangles as illustrated In Figure 5.
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".
|
Unique Rectangle Figure 5: Load Example |
Type 3 Unique Rectangles
In this variant we have a floor with a pair as before but the roof contains two different candidates (occurring once or twice in each cell of the roof). In the Figure 5 the floor and roof contain 2/4 and the extra candidates in the roof are 1 and 5. Removing both the 1 and 5 from the roof would leave the deadly pattern so either the 1 or 5 in B2 must be a solution or the 5 in B9 is a solution. Knowing this does not get us as far as an elimination, however, but we can say that the 1/5 in B2 and B9 act as a pseudo-cell in their own right. The clever bit is using this pseudo-cell with a bi-value cell containing the same candidates. Such a cell is circled on the board – B8. We effectively have a “locked set” like a Naked Pair. 1 will occur in B8 or B2 or 5 will occur in {B8,B9,B2}, we just don’t know which way round.
|
Unique Rectangle Figure 5: Load Example or : From the Start |
Such reasoning allows us to remove other 1s and 5s on the unit shared by the roof cells (but not the cell we’re using to create a locked set with). There are 1s and 5s in B1 and B4 which can be eliminated.
|
Type 4 Unique Rectangles - Cracking the Rectangle with Conjugate Pairs
An interesting observation is that it is sometimes possible to remove one of the original pair of possibilities from the roof squares. Consider the following puzzle in Figure 6.
|
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).
Type 4B Unique Rectangles
|
Unique Rectangle Figure 6: Load 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.
|
Unique Rectangle Figure 7: Load Example |
Comments...
... by: Harmen Dijkstra
I made this sudoku: . 9 . | 5 . . | 6 4 7 6 . 5 | . . 7 | . 9 3 . 7 . | . . . | 2 5 8 ----------------------- . 5 6 | . 7 . | 9 . . . . 7 |9 . 5| 3 8 6 . . 3 |8 . 2| 4 7 5 ----------------------- . . . | . 5 .| 8 3 9 5 6 . | . . .| 7 2 . . . . | . . 8| 5 6 4 If you filling this sudoku in the sudoku solver, the solution Count will say that there are 17 solutions. But if you try TAKE STEP then you will get only this sudoku (with Unique Rectangles): 2 9 1 | 5 8 3 | 6 4 7 6 8 5 | 2 4 7 | 1 9 3 3 7 4 | 1 9 6 | 2 5 8 ----------------------- 8 5 6 | 3 7 4 | 9 1 2 4 2 7 | 9 1 5 | 3 8 6 9 1 3 | 8 6 2 | 4 7 5 ----------------------- 7 4 2 | 6 5 1 | 8 3 9 5 6 8 | 4 3 9 | 7 2 1 1 3 9 | 7 2 8 | 5 6 4 But there are more solutions, for example: 1 9 2 | 5 8 3 | 6 4 7 6 8 5 | 2 4 7 | 1 9 3 3 7 4 | 6 9 1 | 2 5 8 ----------------------- 8 5 6 | 3 7 4 | 9 1 2 2 4 7 | 9 1 5 | 3 8 6 9 1 3 | 8 6 2 | 4 7 5 ----------------------- 4 2 1 | 7 5 6 | 8 3 9 5 6 8 | 4 3 9 | 7 2 1 7 3 9 | 1 2 8 | 5 6 4 The sudoku solver said that (because of Unique Rectangles) R7C4 has to be a 6, but in this example you see that you get an other solution with a 7. Is this a fault in the sudoku solver?
... by: Lea Hayes
Just to clarify my question: Rectangle Cells: A(1,5,6) B(1,5,6) C(1,5) D(1,5) Why remove 1 from both A and B and not either of the following: A(5,6) B(1,5) C(1,5) D(1,5) or A(1,5) B(5,6) C(1,5) D(1,5)
... by: Lea Hayes
Re: Type 4 Unique Rectangles - Cracking the Rectangle with Conjugate Pairs I do not understand how you came to the conclusion that 1 can be removed? Why not remove 6 instead?
... by: John_Ha
Andi I too was puzzling over that but I think the answer is simple. See Fig 2. (5 and 7) are unsolved in Col 4 otherwise they wouldn't be candidates in R2C4. Similarly (5 and 7) are unsolved in Col 6. Similarly (5 and 7) are unsolved in Row 5. Because the cell at R5C4 is unsolved for 5 and 7, then the centre 3x3 must be unsolved for (5 and 7). There is therefore no way before now that the cell at R5C6 could have had either 5 or 7 eliminated as candidates because there are no solved (5 or 7) that it can see. The 5 and 7 at R5C6 could not have been eliminated by something happening on R5, nor on C6, nor in its 3x3. So, the cell at R5C6 MUST have BOTH 5 and 7 as candidates (as well as possibly others, in this case 3 and 6). Now assume R5C6 is 5 - we get the deadly pattern. So R5C6 cannot be 5. Now assume R5C6 is 7 - we get the deadly pattern. So R5C6 cannot be 7. So R5C6 cannot be 5 or 7 and both can be eliminated.
... by: Andi
I do not understand this strategy. In the first example for Type 1 UR, I understand that if 3 or 6 would be removed from R5C6, you would end up with a deadly pattern. That's fine so far. But I do not see why you can eliminate 5 AND 7 for this reason from R5C6. IMHO, if in R5C6 3,5,6 would be possible, well then this would just imply R5C4 and R2C6 being 7 and R2C4 being 5. An "ordinary" solution. OTOH, if in R5C6 3,6,7 would be possible, R5C4 and R2C6 would be 5 and R2C4 would be 7. Quite straightforward, too. My point is: both possibilities would be valid. But I cannot spot a "deadly pattern" here because to remove the ambiguity in this sitatuation, all you can postulate is that *either* 5 *or* 7 must be removed from the possibilities in R5C6. With either number removed, the ambiguity is removed, thus no deadly pattern anymore. But I just don't see why you eliminate *both* 5 and 7 in R5C6? Am I missing something?
... by: Dennis Daft
Shouldn't your Type 4B example be "solved" using the Type 2A method? Using this method the 6 in R1C3 and R3C5 would be eliminated, forcing one of the "roof" cells to be a 6. I believe the end result is the same. This would be consistant with only using Type 4 when no other solution is possible. Dennis
|
