View previous topic :: View next topic 
Author 
Message 
keith
Joined: 19 Sep 2005 Posts: 3192 Location: near Detroit, Michigan, USA

Posted: Sat May 06, 2006 12:14 pm Post subject: Unique Rectangles: May 2, 2006 


Revision: May 27, 2006
An improved version of this guide is now posted at:
http://www.sudoku.com/forums/viewtopic.php?p=29105#29105
Keith
=========================================
Unique Rectangles: An Introduction
Terminology: In the following,
cell = square
possibility = candidate
Most people consider a Sudoku puzzle to be "valid" only if it has a single solution.
If one is willing to take advantage of this uniqueness, there are solution methods that can be applied.
Consider the following fragment of a puzzle solution:
Code: 
++
    
 6  4 
    
++
 4  6 
    
    
++

This is not a unique solution: You can interchange 4 and 6 in the above diagram to get a second solution. Each row, column and block still has one 4 and one 6.
Now, suppose that the possibilities leading to the solution were:
Code: 
++
    
 46  46 
    
++
 46  46 
    
    
++

This cannot lead to a unique solution: Each diagonal is either 4 or 6, and they can be interchanged.
Either of the above is often called the "deadly pattern".
Note that this pattern obviously occupies only two rows and two columns. It also can occupy only TWO blocks. (If the rectangle occupies four blocks, the corners cannot be interchanged to get another solution. Try it!)
How is this useful? Well, suppose we have the following set of possibilities
Code: 
Case A:
++
    
 46  246 
    
++
 46  46 
    
    
++

The top right cell MUST be 2. (It cannot be 4 or 6, because either would force the deadly pattern.) After reduction, the result is:
Code: 
++
    
 46  2 
    
++
 46  46 
    
    
++

If three of the cells have only two possibilities, it does not matter how many additional possibilities are on the fourth cell. The "deadly" candidates can both be eliminated from the fourth cell.
Suppose instead we have the possibilities:
Code: 
Case B:
++
 x   
 46  246 
 x   
++
 246  46 
   x 
   x 
++

One of the top right or bottom left cells must be 2. Therefore, none of the cells marked "x" can be 2.
There are obvious variations. Above, the extra possibilities are on a diagonal. They can be in the same column:
Code: 
++
   x 
 46  246 
   x 
++
 46  246 
   x 
   x 
++
   x 
   x 
   x 
++

or in the same row, or in the same block:
Code: 
++
    
 46  46 
    
++++
 246 x 246  x x x  x x x 
 x x x         
 x x x         
++++
    
    
    
++

Etcetera. I count five variations: Not in the same block, and in the same row (1), column (2), or on a diagonal (3). In the same block, and in the same row (4) or column (5).
Next, suppose there is more than one additional possibility on two of the corners:
Code: 
Case C:
++
    
 46  246 
    
++
 46  469 
    
    
++
    
    
    
++

The cells on the right have possibilities 2, 4, 6, 9. At least one of them is not 4 or 6. Is there another cell containing some of these possibilities? We might have the following:
Code: 
++
   x 
 46  246 
   x 
++
 46  469 
   x 
   29 
++
   x 
   x 
   x 
++

In this case, we can eliminate 2 and 9 as possibilities in any of the cells marked "x".
What?
Look at it this way. The rectangle has two corners containing four possibilities. Normally, one would need to find a quad (four cells) containing the four numbers to make eliminations in other cells. However, one of the cells does not contain one of the deadly candidates (4 or 6), so we only need to find three cells (a triple) containing the four candidates. Then, we know that one of the cells outside the triple contains one of the deadly candidates; we can make eliminations only of the "extra" possibilities (2 or 9).
There are obvious variations when the extra possibilities are in the same row and / or the same block.
There may be other possible reductions. Suppose, in the above, that the only possibilities for 4 in the right column are the corners of the rectangle. One of them must be 4; neither can be 6, and the result is:
Code: 
++
    
 46  24 
    
++
 46  49 
    
   29 
++
    
    
    
++

As a final example, let's go back to Case B above, and suppose that the corners of the rectangle are also an Xwing on 4. Then, the result must be:
Code: 
++
    
 4  26 
    
++
 26  4 
    
    
++

The bottom right cell cannot be 6, because that would force the deadly pattern. (In fact, you do not need the full Xwing to make this reduction. Think about it!)
How does this apply in practice? Let's take a look at the puzzle that started this all. It is the Daily Sudoku of May 2, 2006:
Code: 
Puzzle: DS050206
++++
  7 8       1  
 5     4      
   6   7 2     
++++
 8 5          
   4  5  7  9   
          6 4 
++++
     1 8   2   
      6     1 
  1       3 5  
++++

After using all the techniques required in every previous Daily Sudoku, we get to here. Now what?
Code: 
++++
 249 7 8  369 5 39  46 1 29 
 5 239 239  68 4 1  68 27 279 
 1 49 6  89 7 2  48 3 5 
++++
 8 5 239  4 239 6  1 27 237 
 23 6 4  5 1 7  9 8 23 
 7 239 1  29 239 8  5 6 4 
++++
 349 349 7  1 8 5  2 49 6 
 249 8 5  239 6 39  7 49 1 
 6 1 29  7 29 4  3 5 8 
++++

There is a unique rectangle on <39> in R18 C46. R1C4 and R8C4 cannot be <9>. In C4, the only possibilities for <3> are the corners of the rectangle. Therefore, neither of these corners can be <9>.
There is a unique rectangle on <49> in R78 C18. R1C1 cannot be <2>. In C1, the four possibilities on the rectangle corners are <2349>. We can form a reduced triple with the <23> in R5C1. Therefore, R1C1 cannot have the possibility <2>.
There is a unique rectangle on <27> in R24 C89. R2C9 and R4C9 cannot be <2>. In C9, the only possibilities for <7> are the corners of the rectangle. Therefore, neither of these corners can be <2>.
Closing
Above is a summary of unique rectangles and solution strategies that are, I believe, most useful to human solvers using pencil and paper. There is much more on this subject. Take a look at
http://www.sudoku.com/forums/viewtopic.php?p=21804#21804
I hope this helps.
Keith
(Last edit 050706 2:30 pm EDT)
Last edited by keith on Sun May 28, 2006 4:06 am; edited 3 times in total 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5275 Location: Rochester, NY, USA

Posted: Sat May 06, 2006 4:08 pm Post subject: 


Hey there, "Mr. Rectangle", very nice primer. 8)
That thread you linked to looks very intimidating at first glance. I wonder about some of these arcane techniques; are they necessary for one to become a pretty good solver or are they of interest mostly to the Sudoku "wonks" ( I'm not using that word in a negative sense)? 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3192 Location: near Detroit, Michigan, USA

Posted: Sat May 06, 2006 9:57 pm Post subject: Thanks! 


Marty,
Thanks for the kind words. I wrote this because of a comment you made!
Shameless selfpromotion: I am pleased that Mike Barker has listed this primer as his first resource on Unique Rectangles. It is in the link I gave in the original post.
You wrote:
Quote: 
I wonder about some of these arcane techniques; are they necessary for one to become a pretty good solver ...

Actually, I think you are already a pretty good solver!
In my opinion, strong links and weak links are the keys to becoming a good (human) solver. If you understand multicoloring, you can forget about many of these arcane techniques.
Havard wrote an excellent introduction to strong links:
http://www.sudoku.com/forums/viewtopic.php?t=3326
Anyway, sudoku.com is a very interesting site. You can, for example, find puzzles that have extreme symmetry, or ones that require particular solution methods.
By the way, today's SudoCue Nightmare was kind of interesting. It has a couple of unique rectangles, and then some strong links (coloring) that allow you to avoid XYZ and XYwings.
I've posted my solution in the SudoCue forum; here is the link:
http://www.sudocue.net/forum/viewtopic.php?p=406#406
Best wishes,
Keith
Last edited by keith on Sun May 07, 2006 3:46 am; edited 1 time in total 

Back to top 


Robert Ferre
Joined: 09 Apr 2006 Posts: 10

Posted: Sun May 07, 2006 3:20 am Post subject: 


I'm missing some point of logic here, Keith. Above you said this:
++++
 249 7 8  369 5 39  46 1 29 
 5 239 239  68 4 1  68 27 279 
 1 49 6  89 7 2  48 3 5 
++++
 8 5 239  4 239 6  1 27 237 
 23 6 4  5 1 7  9 8 23 
 7 239 1  29 239 8  5 6 4 
++++
 349 349 7  1 8 5  2 49 6 
 249 8 5  239 6 39  7 49 1 
 6 1 29  7 29 4  3 5 8 
++++
There is a unique rectangle on <27> in R24 C89. R2C9 and R4C9 cannot be <2>. In C8, the only possibilities for <7> are the corners of the rectangle. Therefore, neither of these corners can be <2>.
***********
Now, if C8 contains the only two possibilities for 7, and they are on the corners of the rectangle, wouldn't only one of them become a 7? Why wouldn't the other corner then become a 2? You are saying that 2 can be eliminated from both corners. I don't get it. Same for R24 C9 which you have also eliminated. So you have eliminated 2 from all four corners. I'm missing something here.
Robert 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3192 Location: near Detroit, Michigan, USA

Posted: Sun May 07, 2006 4:06 am Post subject: 


Robert,
Thank you! You have found a typo. I said:
Quote: 
In C8, the only possibilities for <7> are the corners of the rectangle. Therefore, neither of these corners can be <2>.

This should be:
Quote: 
In C9, the only possibilities for <7> are the corners of the rectangle. Therefore, neither of these corners can be <2>.

I have edited to original to correct this.
If this is still not clear, please let me know.
Best wishes,
Keith 

Back to top 


Guest

Posted: Sun May 07, 2006 10:52 am Post subject: Re: Unique Rectangles: May 2, 2006 


keith wrote:  Code: 
++
   x 
 46  246 
   x 
++
 46  469 
   x 
   269 
++
   x 
   x 
   x 
++

In this case, we can eliminate 2 and 9 as possibilities in any of the cells marked "x". 
I see one error in your otherwise very nice primer. The unique rectangle cells with 246 and 469 behave as a single cell. To then have the eqivalent of a naked pair, your fifth cell must contain 29 ... not 269. 

Back to top 


George Woods
Joined: 28 Mar 2006 Posts: 255 Location: Dorset UK

Posted: Sun May 07, 2006 11:14 am Post subject: Re: Unique Rectangles: May 2, 2006 


I am too slow to understand this part of your argument You say::
++
   x 
 46  246 
   x 
++
 46  469 
   x 
   269 
++
   x 
   x 
   x 
++
[/code]
In this case, we can eliminate 2 and 9 as possibilities in any of the cells marked "x".
If I put a 2 into one of your "forbidden" cells I come up with the solution
0 0 0
6 0 4
0 0 0
4 0 9
0 0 0
0 0 6
0 0 2
0 0 0
0 0 0
and similarly for a 9 a different but apparently valid solution!
So where have I got it wrong?
I now realise the answer lies in the posting above 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3192 Location: near Detroit, Michigan, USA

Posted: Sun May 07, 2006 6:45 pm Post subject: Thanks 


"Guest" and George,
Thank you. I have edited it to make the corrections.
Keith 

Back to top 


George Woods
Joined: 28 Mar 2006 Posts: 255 Location: Dorset UK

Posted: Tue May 09, 2006 3:55 pm Post subject: unique rectangles 


Keith  Don't you find that knowledge of advanced techniques can sometimes be a "nuisance"
Today's puzzle (tuesday) has a unique rectangle that allows the placing of a 2 in box8  so when the puzzle was solved I asked myself Did it rely on spotting the unique rectangle?  answer NO so if someone asks "how" was it done  it must be better to give the solution that uses "simple" logic! 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3192 Location: near Detroit, Michigan, USA

Posted: Tue May 09, 2006 10:24 pm Post subject: Well, no 


George said:
Quote: 
Don't you find that knowledge of advanced techniques can sometimes be a "nuisance"

No, I don't think so, but it's an interesting question. I think each technique is just another tool in the toolbox. As someone said: "If all you have is a hammer, every problem looks like a nail."
I think it is wonderful how SamGJ has everyone flummoxed. Today's puzzle was "very hard", so we all were looking for Xwings and UR's. They were there to be found, but not essential!
If that's the way you found the solution, it must have been the "easiest" for you.
Someone, in another thread, made the observation:
Computers solve by traversing a hierarchy of heuristics, and by analyzing every pattern before considering the next heuristic.
Humans solve by recognizing patterns, and then applying heuristics.
So, if the UR leaps out at you, use it! Who cares if there was also a hidden single you didn't spot?
And, my personal opinion: If you use an online or other solver, lose it! Print out the puzzle, get a pencil, and find an armchair. In two weeks your skills will have improved immensely. (After you have solved a puzzle, by all means go back to the software and step through the solution, to see if you missed something.)
Best wishes,
Keith 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5275 Location: Rochester, NY, USA

Posted: Thu May 18, 2006 8:04 pm Post subject: 


Quote:  Code:  The cells on the right have possibilities 2, 4, 6, 9. At least one of them is not 4 or 6. Is there another cell containing some of these possibilities? We might have the following:
Code:
++
   x 
 46  246 
   x 
++
 46  469 
   x 
   29 
++
   x 
   x 
   x 
++
In this case, we can eliminate 2 and 9 as possibilities in any of the cells marked "x".
What?
Look at it this way. The rectangle has two corners containing four possibilities. Normally, one would need to find a quad (four cells) containing the four numbers to make eliminations in other cells. However, one of the cells does not contain one of the deadly candidates (4 or 6), so we only need to find three cells (a triple) containing the four candidates. Then, we know that one of the cells outside the triple contains one of the deadly candidates; we can make eliminations only of the "extra" possibilities (2 or 9). 

Quote:  Code:  Code:
++++
 249 7 8  369 5 39  46 1 29 
 5 239 239  68 4 1  68 27 279 
 1 49 6  89 7 2  48 3 5 
++++
 8 5 239  4 239 6  1 27 237 
 23 6 4  5 1 7  9 8 23 
 7 239 1  29 239 8  5 6 4 
++++
 349 349 7  1 8 5  2 49 6 
 249 8 5  239 6 39  7 49 1 
 6 1 29  7 29 4  3 5 8 
++++
There is a unique rectangle on <39> in R18 C46. R1C4 and R8C4 cannot be <9>. In C4, the only possibilities for <3> are the corners of the rectangle. Therefore, neither of these corners can be <9>.
There is a unique rectangle on <49> in R78 C18. R1C1 cannot be <2>. In C1, the four possibilities on the rectangle corners are <2349>. We can form a reduced triple with the <23> in R5C1. Therefore, R1C1 cannot have the possibility <2>.
There is a unique rectangle on <27> in R24 C89. R2C9 and R4C9 cannot be <2>. In C9, the only possibilities for <7> are the corners of the rectangle. Therefore, neither of these corners can be <2>. 

Keith,
I've been studying this concept of the "reduced triple." The first definition was "However, one of the cells does not contain one of the deadly candidates (4 or 6), so we only need to find three cells (a triple) containing the four candidates. Then, we know that one of the cells outside the triple contains one of the deadly candidates;"
Now look at the "49" rectangle above in cols. 8 and 9. It would seem that r1c1 would meet the definition of "three cells containing the four candidates." However, it was r5c1 that completed the triple. In both this rectangle and the first "46" rectangle shown in the grid with the other numbers filtered out, the third cell contains both of the "extra possibilities."
So, can we narrow the definition of the reduced triple to say that it must consist of the the two corner cells plus a third cell that must contain both of the extra possibilities?
My next questions also concern the third cell: must that third cell be only a pair, containing the extra possibilities, such as the "29" in the "46" rectangle and the "23" in the "49" rectangle?
If the above answer is "yes", then we're done. If not, the cell could presumably be, using the "49" rectangle and the "23" in r5c1 as an example, "23x", "23xy", or "23xyz." Could "xyz" include either or both of the rectangle numbers, in this case, "4" and/or "9"? 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3192 Location: near Detroit, Michigan, USA

Posted: Thu May 18, 2006 10:31 pm Post subject: Weak explanation 


Marty,
I have always thought this is a very weak explanation. I think I have figured out how to explain it better. I was planning to rewrite and expand this Introduction, and post a revised article this weekend.
Let me try this:
If you write the UR as
then you can make a reduction if there is another cell
Code: 
12  123
12  124 34

You can eliminate <3> and <4> from all cells that are buddies of <123>, <124>, and <34>.
Here is the (new) explanation.
<123>, <124>, and <34> are three cells containing four candidates. However, <1> and <2> are candidates only on the corners of the UR. To avoid the deadly pattern, these two cells cannot be <1> AND <2>. So, the missing (fourth) candidate in the three cells must be <1> or <2>. So, the three cells must contain either <134> or <234>. Either way, all occurrences of <34> are in these three cells.
So, if you can find a cell that contains only the extra possibilities, you can make the eliminations. The folllowing also works:
Code: 
12  123 45
12  124 345

and you can eliminate <3>, <4>, and <5> from the other cells.
So, the principle is to find a reduced subset where the "extra" cells involve only the "extra" candidates.
You are correct, that eliminations can be made if the "extra" cells involve one of the "deadly" candidates. But, the reasoning is different, and the eliminations are on the rectangle, not on cells outside the rectangle.
Stay tuned!
Keith
PS: I realize I have not answered all the specifics of your questions. I will, but later, after I have had a chance to print and study your message. 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5275 Location: Rochester, NY, USA

Posted: Fri May 19, 2006 3:55 pm Post subject: 


As always, thank you Keith. I have been fascinated with rectangles since I first learned about them. I have no quantitative evidence to base this on, but rectangles seem to be one of the most powerful techniques in the "toolbox."
One of the reasons I ask such detailed questions is that the way my brain is wired is such that I am unable to deduce all this stuff. Any success I may have at solving has come from learning "rules" and applying them when I can recognize a situation.
I look forward to the next rectangles primer. 

Back to top 


David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Posted: Fri May 19, 2006 4:52 pm Post subject: "UR"s are easy to see 


Marty R wrote:  ... rectangles seem to be one of the most powerful techniques in the "toolbox." 
I agree with this  and I think it's mostly because the rectangle pattern is fairly easy to spot. I've run into a lot of puzzles where a pair can be seen at three corners of the rectangle, meaning that neither of those values can appear in the fourth corner. That's very useful information. dcb 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3192 Location: near Detroit, Michigan, USA

Posted: Fri May 19, 2006 9:18 pm Post subject: UR's are good clues 


Marty,
As always, it is a pleasure. I think I have answered your question, with more to come in my revised Introduction to UR's.
I think this is very powerful, especially when combined with other techniques. Some people talk about "Almost Unique Rectangles" (AUR's) in which you do not have a cookbook pattern. Rather, you have a strong clue to look for a short elimination chain. (Keith's interpretation!)
Best wishes,
Keith 

Back to top 


guest Guest

Posted: Sat May 20, 2006 4:13 pm Post subject: May 18 daily sudoku 


I'd like to know if anybody had problems with sudoku from May 18. I can not find reasoning for given hints.
sudoku lover 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3192 Location: near Detroit, Michigan, USA

Posted: Sat May 20, 2006 7:23 pm Post subject: May 18 


The last question does not really belong here.
May 18: Look for a triple <356> in column 5, and in block 5, and in block 8.
Keith 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3192 Location: near Detroit, Michigan, USA


Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
