What is the technique used here?

Post the puzzle or solving technique that's causing you trouble and someone will help

What is the technique used here?

Postby Shazbot » Mon Oct 24, 2005 7:57 am

From rows 1, 2, 3:
Code: Select all
 
 *--------------------------------------------------------------------*
 | 69     38     2      | 5      3689   1      | 7      46     346    |
 | 67     1      5      | 4      36     37     | 9      2      8      |
 | 79     4      38     | 368    2      79     | 136    16     5      |
 |----------------------+----------------------+----------------------|



If r1c2=3, then r3c7 must be 3. If r3c3=3 then r1c9=3. Either case will eliminate 3 as a candidate from r1c5 and r3c4. So even though I don't know the location of 3s in boxes 1 and 3, I can eliminate two candidates from box 2.

I haven't done a detailed study of colouring yet, but I'm guessing this might be an application of it. Is that correct, or is this some weird variation of X wing (I also haven't learned XY wing).
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby emm » Mon Oct 24, 2005 8:24 am

Looks like colouring to me - too many candidate 3s for Xwing.
emm
 
Posts: 987
Joined: 02 July 2005

Postby Nick67 » Mon Oct 24, 2005 8:33 am

One way to look at this would be as a form of locked candidates.
The 3's in box 1 are locked in (confined to) rows 1 and 3,
and same with the 3's in box 3. So, 3 can be safely removed
as a candidate from the same rows in box 2.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby simes » Mon Oct 24, 2005 9:00 am

em wrote:Looks like colouring to me - too many candidate 3s for Xwing.
Looks like an XWing to me - not enough conjugate pairs for colouring!

There's more than one way of looking at this, as Nick has pointed out, but to me, this is an XWing.

It's not the "classic" XWing using conjugate pairs in row and columns, but a skewed XWing using rows and boxes. But still an XWing.

Either r1c2 and r3c7 = 3, OR r3c3 and r1c9 = 3. Either way, candidate 3s in rows 1 and 3 in box 2 can be eliminated.

S
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby emm » Mon Oct 24, 2005 9:38 am

Ok we haven't got the whole grid but isn't this simple colouring?

Code: Select all
*--------------------------------------------------------------------*
 | 69     38T     2      | 5      3689   1      | 7      46     346F    |
 | 67     1      5      | 4      36     37     | 9      2      8      |
 | 79     4      38F     | 368    2      79     | 136T    16     5      |
 |----------------------+----------------------+----------------------|

emm
 
Posts: 987
Joined: 02 July 2005

Postby Sue De Coq » Mon Oct 24, 2005 9:49 am

This is an example of Tabling, a technique that's discussed elsewhere on this forum. The idea is that tables of forced chains are built up in order to allow statements such as 'Whichever of the 2 candidates in Box 1 contains the value 3, ...'. Some people don't like the technique as it relies upon brute force rather than elegance. Here's a simplified version of an example I posted to this forum yesterday:

Code: Select all
 . 6 9 | 1 4 3 | 8 . .
 . . 7 | 9 . . | . . 4
 4 . . | 7 . . | . 9 .
-------+-------+------
 9 . . | 8 5 7 | 3 6 1
 7 . . | 2 1 6 | 9 4 5
 6 1 5 | 3 9 4 | . . 8
-------+-------+------
 . 7 . | 5 8 9 | 4 . .
 8 . . | 6 7 1 | 5 . .
 . . . | 4 3 2 | . 8 .


The solver log begins:

Code: Select all
Consider the chain r7c3~1~r3c3-1-r2c1~1~r2c8-1-r7c8.
When the cell r7c3 contains the value 1, so does the cell r7c8 - a contradiction.
Therefore, the cell r7c3 cannot contain the value 1.
- The move r7c3:=1 has been eliminated.
Consider the chain r7c1-3-r2c1~3~r2c8-3-r3c9~3~r7c9.
When the cell r7c9 contains the value 3, so does the cell r7c1 - a contradiction.
Therefore, the cell r7c9 cannot contain the value 3.
- The move r7c9:=3 has been eliminated.
The values 2, 3, 5 and 8 occupy the cells r2c2, r3c2, r1c1 and r5c2 in some order.
- The moves r2c1:=2, r2c1:=5 and r3c3:=2 have been eliminated.
******** START OF INTERESTING BIT **********
Consider the chains r1c8-7-r1c9~2~r8c9, r1c8-7-r6c8~2~r7c8, r1c8-7-r1c9~2~r7c9 and r1c8-7-r6c8~2~r8c8.
Whichever of the 4 candidates in Box 9 contains the value 2, the cell r1c8 does not contain the value 7.
- The move r1c8:=7 has been eliminated.
******** END OF INTERESTING BIT ************
The cell r1c9 is the only candidate for the value 7 in Row 1.
Sue De Coq
 
Posts: 93
Joined: 01 April 2005

Postby tso » Mon Oct 24, 2005 4:48 pm

AngusJ would call this "multiple coloring". Most others refer to it as simply "coloring" or "advanced coloring" and save the term "multiple coloring" for coloring more than one digit. A standard x-wing just a special case of this type of coloring. The skewed x-wing is another special case.

Code: Select all
Skewed X-wing
  . r3  .  |  .  3  .  |  .  . +3 
  .  .  .  |  .  3  3  |  .  .  . 
  .  . b3  |  3  .  .  | -3  .  .



Code: Select all
Standard X-wing
  . r3  .  |  .  3  .  |  .  . +3 
  .  .  .  |  .  3  3  |  .  .  . 
  .  .  .  |  .  .  .  |  .  .  .
-----------+-----------+-----------
  . b3  .  |  3  .  .  |  .  . -3 


In each case, the cells marked r/b are strongly linked -- exactly one must be "true". Same is true for the cells marked +/-. In each case, the cells marked r/+ and b/- are weakly linked -- at most one may be true. In each case, other candidates in the two rows are eliminated.

This type of coloring will find all X-wings, skewed or not. (Some Swordfish will *not* be found by coloring.)
tso
 
Posts: 798
Joined: 22 June 2005

Postby Lummox JR » Tue Oct 25, 2005 6:04 am

Actually tso, the term "advanced coloring" seems to apply only to multi-digit cases, in general parlance. Nick70 uses this term apparently to mean supercoloring that does not use filler colors.

Anyway in this case no advanced techniques are necessary; a simple box-line intersection shows that for a 3 to go anywhere in row 2, it must be in box 2. Therefore the other candidate 3's in box 2 may be eliminated.

This could, however, be looked at as coloring as well. There's just not a lot of point in doing so.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby dgmp » Tue Oct 25, 2005 7:35 am

Only 3's in row 2 are in the middle block, so eliminate other 3's from this block.
dgmp
 
Posts: 4
Joined: 01 October 2005

Postby Shazbot » Tue Oct 25, 2005 7:38 am

Thanks all for your replies - there are certainly a lot of views. I guess whichever technique gives you the numbers fastest is the one to use. I think when I worked it out I considered colouring, but a form of locked candidates would be just as quick, if not quicker. I'm still trying to master those.

On another note, yesterday I finished my VERY FIRST Pappocom V.Hard Sudoku - with NO need to dub into Simple Sudoku and no need to query anyone on the forum! I felt soooooo proud! Today I tackled a few more - 10 minutes and 18 minutes, though I'm sure many of you do them in a much shorter time. I've learned so much from this forum and the various links explaining techniques. Thanks all so much for your help when I've needed it. I think I'm addicted.....
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby tso » Tue Oct 25, 2005 2:38 pm

Lummox JR wrote:Actually tso, the term "advanced coloring" seems to apply only to multi-digit cases, in general parlance. Nick70 uses this term apparently to mean supercoloring that does not use filler colors.

Anyway in this case no advanced techniques are necessary; a simple box-line intersection shows that for a 3 to go anywhere in row 2, it must be in box 2. Therefore the other candidate 3's in box 2 may be eliminated.

This could, however, be looked at as coloring as well. There's just not a lot of point in doing so.


Oops. My mistake. Explains why we haven't come across 'skewed x-wings' before. It's counting legs and dividing by four to see how big the herd is.

Though he never uses the phrase "advanced coloring", the Simes / SadMan Sudoku description of "simple coloring" has a section called "advanced" where he describes the same thing that AngusJ / Simple Sudoku refers to as "multicoloring" (AngusJ doesn't explain this on his website yet, but the Simple Sudoku hint system uses the term.) In both cases, it refers to coloring only one candidate, but some of the links are not conjugates. SadMan's uses the terms "multicoloring" and "supercoloring" interchangably, referring to coloring all candidates, a mostly non-human implementable method.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Guest » Tue Oct 25, 2005 6:05 pm

Nick67 wrote:One way to look at this would be as a form of locked candidates.
The 3's in box 1 are locked in (confined to) rows 1 and 3,
and same with the 3's in box 3. So, 3 can be safely removed
as a candidate from the same rows in box 2.


nick is the simplest answer to the question
double row elimination
:D
Guest
 
Posts: 312
Joined: 25 November 2005

Postby emm » Tue Oct 25, 2005 7:00 pm

I agree - Nick is the simplest answer.:D It was a good example though, Shazbot, it got me thinking about the relationship between colouring and Xwing.
emm
 
Posts: 987
Joined: 02 July 2005

Postby Nick67 » Tue Oct 25, 2005 8:35 pm

em wrote:It was a good example though, Shazbot, it got me thinking about the relationship between colouring and Xwing.


Yes, very interesting to see a situation that could be
analyzed in so many different ways.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby Pat » Thu Oct 27, 2005 2:48 pm

dgmp wrote:Only 3's in row 2 are in the middle block, so eliminate other 3's from this block.


yes!

we see the r2 3 must be in box 2;
so, no other 3 allowed in this box.

dgmp certainly has the simplest explanation!

- Pat
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005


Return to Help with puzzles and solving techniques