Double subset technique - know or not?

Advanced methods and approaches for solving Sudoku puzzles

Double subset technique - know or not?

Postby Morgoth » Mon Mar 12, 2007 9:54 am

I tried to made a description, but it was not clear enough, so I’m going to explain the technique with examples.

In my technique will be used 3 types of cells

Code: Select all
B B B | . . . | . . .
I I I | L L L | L L L
B B B | . . . | . . .


B is part of the Block, L is part of the Line (row or column) and I is part of the block-line interaction.

Lets get two naked pairs, which have one shared candidate {1,2}, {1,2} and {1,3}{1,3}.
If one of the subsets is in the block and the other is in the line we can bind the subsets (distroing them) in a structure named XYZ-Wing
B{1,2}, I{1,2,3}, L{1,3}. In this case all other I cells can not contain the shared candidate, which in this example is

Code: Select all
   B    {1,2}    B   |   .      .      .
{1,2,3}   I      I   |   L    {1,3}    L


So, this was for two pairs, more complex situation we will have with pair and triplet. {1,2}, {1,2} and {1,3} {1,4} {3,4}

Binding them we have double subset:
B{1,2} I{1,2,3} L{1,4} L{3,4} and again all other I cells can not contain 1

The situation is going more interesting if we have two triplets. There are two possible variants for them
1) having one shared cell {1,2} {2,3} {3,1} and {1,4} {1,4,5} {1,4,5}
2) having two shared cells {1,2} {1,2,3} {2,3} and {1,2,4} {1,2,4} {1,2}

The second case will look like this:
Code: Select all
{1,2}    {2,3} B |    .    .   .
{1,2,3,4}  I   I | {1,2,4} L {1,2}


If we want to make the things really complicated and interesting we should use at least on quad.
If the quad is bind with pair there can be only one shared candidate, if it is bind with triplet the shared candidates can be 1 or 2.In case it is binded with another quad it is possible to have up to 3 shared candidates.
You don't need example to understand that, so I'm goging to give you example for a different configuration possible only with quads:

Code: Select all
{3,4} {1,4} B |   .   .   .
{1,2} {2,3} I | {3,5} L {1,5}


Here we have 3 shared candidates and 2 used I cells. In this case we can remove candidates only from one cell.
* here is not mandatory to have only 2 candidates for a cell - it's just easier to see the formation, that's why I use such example

Another interesting thing, which completely separate this technique from XYZ-Wing is that it is not mandatory all shared candidates to be candidates for the shared cell.
Code: Select all
{3,4} {1,4} {2,3} |   .     .     .
{1,2}   I     I   | {3,5} {2,3} {1,5}

In this case 3 is also shared cell and all I cells can not be 3.

And just one example how complex this can look:
Code: Select all
  .     . .|   B    {1,3,4}   {1,2,3} | .   .      .
{1,3,5} L L|{1,2,5}    I         I    | L {2,3} {1,2,5}
  .     . .|   B    {1,2,3,4}    B    | .   .      .


Looking ahead the next techniques will be Hidden double subset and Chain subsets


So, it this something new ot not?
If it is new, I'll implement it in my solver and will try to find examples for puzzles which require all kind of this technique.
Morgoth
 
Posts: 20
Joined: 06 December 2005

Re: Double subset technique - know or not?

Postby RW » Mon Mar 12, 2007 10:20 am

Your technique seems to have a lot in common with XYZ-wing, ALS and more complex wings (...WXYZ-wing).
Code: Select all
   B    {1,2}    B   |   .      .      .
{1,2,3}   I      I   |   L    {1,3}    L

This is a standard XYZ-wing.
Code: Select all
{1,2}    {2,3} B |    .    .   .
{1,2,3,4}  I   I | {1,2,4} L {1,2}

This looks very much like an ALS xz-rule. (A=[R1C12, r2c1], B=[R2C46], X=4, Z=1,2)

Code: Select all
{3,4} {1,4} B |   .   .   .
{1,2} {2,3} I | {3,5} L {1,5}

---

{3,4} {1,4} {2,3} |   .     .     .
{1,2}   I     I   | {3,5} {2,3} {1,5}

---

  .     . .|   B    {1,3,4}   {1,2,3} | .   .      .
{1,3,5} L L|{1,2,5}    I         I    | L {2,3} {1,2,5}
  .     . .|   B    {1,2,3,4}    B    | .   .      .


In all of the above there's a naked quad in row 2, no need to look at the other cells.

If you find a simple and easily explained logic to combine all of those, it would of course be nice. Keep working on it.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Morgoth » Mon Mar 12, 2007 10:45 am

Hi RW,

Yes, the first one is just XYZ-Wing, but the second is just like the ALS:) , not the same.

Next is matter of bad examples - I was hurring, as I had another work to do. Lets make them different:

Code: Select all
{3,4}   {1,4}   B |   .   .   .
{1,2,4,5} {2,3} I | {3,5} L {1,5}



Code: Select all
{3,4}     {1,4} {2,3} |   .     .     .
{1,2,4,5}   I     I   | {3,5} {2,3} {1,5}


Code: Select all
  .     . .|   B      {1,3,4}   {1,2,3} | .   .      .
{1,3,5} L L|{1,2,4,5}    I         I    | L {2,3} {1,2,5}
  .     . .|   B      {1,2,3,4}    B    | .   .      .


There are no more naked quads.

10x for the review.
Morgoth
 
Posts: 20
Joined: 06 December 2005

Postby RW » Mon Mar 12, 2007 12:04 pm

On second thought, your technique is (almost) exactly the same as ALS xz-rule. All of the examples in your second post can be described as such and the XYZ-wing is actually also a small ALS xz. I'd suggest that you rather implement ALS xz-rule in your solver, as it should be able to find some more eliminations. Your technique is kind of a limited ALS as it only considers the 3 types of cells you described in your first post. I suppose it couldn't find this ALS:
Code: Select all
.   .  .   | .     .     1234 | 134 134 .
456 .  456 | 12456 12456 .    | .   .   .

These techniques often come with many different names, depending on how you view them. Your eliminations could also be explained as more advanced ...-wings. It's up to you how you wish to define them. I'd prefer ALS-xz as it covers a lot of different situations.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Morgoth » Mon Mar 12, 2007 1:19 pm

From the same begging it is extension of the XYZ-Wing.
Sure I'll implement ALS, I just kept is as more advance technique.

I'll read more details about it and will play with it to check whether it covers on 100% the double subset.
Morgoth
 
Posts: 20
Joined: 06 December 2005


Return to Advanced solving techniques