Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Double subset technique - know or not?

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Morgoth

Joined: 12 Mar 2007
Posts: 3
:
Location: Sofia / Bulgaria

Items
PostPosted: Mon Mar 12, 2007 9:37 am    Post subject: Double subset technique - know or not? Reply with quote
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:
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:
   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:
{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:
{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:
{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:
  .     . .|   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 Smile


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.
Back to top
View user's profile Send private message
Morgoth

Joined: 12 Mar 2007
Posts: 3
:
Location: Sofia / Bulgaria

Items
PostPosted: Mon Mar 12, 2007 10:47 am    Post subject: Reply with quote
Some of the examples were not very good and possible to be solved with naked quads only - here is the update.

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


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


  .     . .|   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    | .   .      .
Back to top
View user's profile Send private message
Steve

Joined: 12 Apr 2006
Posts: 12
:

Items
PostPosted: Mon Mar 12, 2007 3:38 pm    Post subject: Reply with quote
That’s a nice find, Morgoth. Welcome to the forum!

Sadly the examples look to be special cases of bennys’ ALSs, specifically the xz-rule.
Code:

34   14 . | .  . .
1245 23 . | 35 . 15

In bennys’ notation:

A = {r1c1, r2c2, r2c1, r2c2), with candidates 1, 2, 3, 4 and 5
B = {r2c4, r2c6}, with candidates 1, 3 and 5
Restricted common candidate: 5
Consequence: eliminate 1 and 3 from r2c3.

The good news is that ALSs (and sets with higher degrees of freedom) are easy to program.

Steve
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron