SudoCue Users Forum Index SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net
 
 FAQFAQ   SearchSearch   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Chains & loops for Killer using AIC

 
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips
View previous topic :: View next topic  
Author Message
Jean-Christophe
Addict
Addict


Joined: 23 Apr 2007
Posts: 92
Location: Belgium

PostPosted: Thu May 17, 2007 8:40 pm    Post subject: Chains & loops for Killer using AIC Reply with quote

I've learn a lot reading posts here & there. I've adapted several existing techniques to killer sudoku. I wrote this post in the hope that it is useful. If you're not familiar with Alternating Inference Chains (AIC), please read this post by Myth Jellies.

X chains & loops
A sum cage in a Killer Sudoku may establish a link for a single candidate X
Strong link: if the cage must include candidate X and there are only two cells with that candidate. eg a cage 9/3 = {125|134} = {1..}, it must include a 1.
Weak link: digits cannot be duplicated in a cage. So it may also establish a weak link. For example two diagonal cells in the same cage but in different nonets.
Strong-only link does not exist in this case. Bilocation strong links are also weak links here.

Grouped X links (like in finned fish, ER...) with same considerations about row/columns intersections as for regular grouped links (eg grouped 2 string kite, ER...)
Grouped Strong-only link: if the cage must include candidate X and all cells with that candidate lie within two "houses" (rows, columns, nonets...)
Grouped Weak link: provided there is no candidate X at the intersection. eg cage with a shape L, T or +, without the candidate at the row/column intersection
Grouped Strong link: both Strong-only & Weak. ie it must include the candidate, but not at the intersection

XY chains & loops
A sum cage can be viewed as a grouped XY node. It may replace a single cell node in an XY chain or loop
XY Strong-only link: not X => Y, not Y => X. In other words the cage must include at least one of X or Y (or both). eg cage 10/3 = {126|135|234} = {(1|2)..}
XY Weak link: X => not Y, Y => not X. In other words it cannot include both X and Y. eg cage 15/3 <> {12..}
XY Strong link: both Strong-only & Weak. eg cage 5/2 = {(1|2)..} & <> {12}

Deductions
A. If continuous AIC loop, then each weak link in the loop must "become" strong and all strong-only link must "become" weak. ie all links forming the loop are then strong and weak.
eg weak X link on 1 through a cage 16/3 => {1(69|78)} (the cage must include a 1, locked within the cells of the link)
eg weak XY link on {12} through a cage 9/2 => {(1|2)..} = {18|27} (the cage must include either 1 or 2, just like a single cell would be restricted to 2 candidates)
eg Strong-only XY link on {12} through cage 10/3 => <> {126) (the cage cannot include both 1 and 2. Similar in logic to X-loop with ER having intersecting cell <> X)
Note: there may exist various ways to establish a weak link between the same two successive nodes in an continuous AIC loop. All of them should then "become" strong.
eg weak X link on 1 through a cage 16/3 in R1C123. There exists also weak links through R1 and N1. If these are not already strong (locked in these), then we may "make them strong" (removing the candidate outside of the links' cells).

B. If not a loop and the two end nodes have the same candidate value, then it's just like finned X wing, grouped turbot fish... We may eliminate the candidate from other buddies/peers of all cells in the end nodes.
If all cells of the two end nodes are within the same cage, then that cage must include the candidate. This indeed forms a continuous AIC loop since a digit cannot be repeated in a cage: there is a closing weak link through the cage.

C. If not a loop and the two end nodes have different candidate values, then it's more complex.
C1. If all cells of the two end nodes are within the same cage, then that cage must include at least one of the candidates, possibly both. Note: if the cage cannot include both candidates, this indeed forms a continuous AIC loop.
C2. If all cells of the two end nodes are buddies/peers of each other (usually they are all within the same "house" but more complex cases exists).
Then if all cells of one end node (X) are in a cage and all cells of the other end node (Y) are not in that cage.
We may then deduce the cage either must include X or cannot include Y. Similarly for the other end.
eg cage 9/2 in r1c12 and AIC (1)r1c12= ... =(2)r1c9. The first node lies in the cage 9/2. The last node lies is same row but outside the cage => either cage 9/2 = {18} or <> {27} => cage 9/2 <> {27}
The corresponding case for a regular XY chain is: two end cells have different candidates and are in the same "house". Which allows to eliminate the other candidate from each of the end cells (it's either X or not Y => <> Y)

More generally for chains, we may eliminate any candidate (or cage combination) for which there exist weak links to both end nodes of the chain. Except for the candidate nodes making the chain, of course. We can eliminate this candidate (or combination) since it would otherwize cancel both ends of the chain.

Examples

Killer X Wing
The two strong links:
Cage 13/4 which must include a 1 in R3C4 or R4C2
1 locked in R34C7 (a regular strong link)
The two weak links: R3 & R4
(1)R3C4=(1)R4C2-(1)R4C7=(1)R3C7... => no 1 elsewhere in R3 & R4


Killer Grouped X Wing
The two grouped strong links:
Cage 13/4 which must include a 1 in R3C34 or R4C34
Cage 8/3 which must include a 1 in R3C7 or R4C67
The two weak links: R3 & R4
(1)R3C34=(1)R4C34-(1)R4C67=(1)R3C7... => no 1 elsewhere in R3 & R4


Killer Turbot Fish (here a two string kite)
The two strong links: 1 locked in R3C47, 1 locked in R47C3 (two regular strong links)
The weak link: Cage 15/3 (cannot have duplicates in a cage)
(1)R3C7=(1)R3C4-(1)R4C3=(1)R7C3 => R7C7<>1


Killer Grouped Turbot Fish (here a grouped two string kite)
The two strong links: 1 locked in R3C247, 1 locked in R247C3 (two grouped strong links)
The weak link: Cage 25/5 (cannot have duplicates in a cage & the cell R3C3<>1)
(1)R3C7=(1)R3C24-(1)R24C3=(1)R7C3 => R7C7<>1
Note: R3C3 cannot have candidate 1 otherwize there is no weak link


Killer Grouped Swordfish
The three strong links:
Cage 18/5 which must include a 1 in R3C234 or R234C3 (possibly in R3C3)
1 locked in R36C7, 1 locked in R7C36 (two regular strong links)
The three weak links: R3, C3 & cage 15/3
(1)R234C3=(1)R3C234-(1)R3C7=(1)R6C7-(1)R7C6=(1)R7C3... => no 1 elsewhere in R3, C3, cage 15/3 & R3C3<>1 & cage 15/3 must include a 1 in R6C7 or R7C6
Note: R3C3<>1 could also be deduced from the two string kite in R7 & C7
cage 15/3 must include a 1 in R6C7 or R7C6 because the AIC forms a loop


Killer XY Wing
The three strong links:
Cage 9/2 in R5C23 <> {18|27} = {36|45} = {(3|5)..} (ie it must include 3 or 5)
R5C7 = {34}
Cage 6/2 in R6C89 = {15|24} = {(4|5)..} (ie it must include 4 or 5)
The two weak links: R5 & N6
(5)R5C23=(3)R5C23-(3)R5C7=(4)R5C7-(4)R6C89=(5)R6C89 => R5C89&R6C123<>5
Note: there is also a killer naked pair on {34} in R5 since Cage 9/2 = {36|45} = {(3|4)..}


Killer Y Wing
This is a simple mix of X links & XY links
The three strong links:
9 of N5 locked in R4C5 or R5C4
Cage 14/2 in R4C23 = {59|68} = {(8|9)..}
Cage 21/3 in R5C789 = {489|579|678} {(8|9)..} (possibly both 8 & 9)
The two weak links: R4 & R5
(8)R4C23=(9)R4C23-(9)R4C5=(9)R5C4-(9)R5C789=(8)R5C789 -> R4C789&R5C123<>8
Note: there is also a killer Y Wing on {69} since both cages must include 6 or 9


Killer XY loop
A mix of various links forming a loop
The three strong links:
1 locked in R25C4 (a regular strong link)
2 locked in R2C457 (a grouped strong link)
R5C7 = {12} (a bivalue cell)
The three weak links:
Cage 9/2 cannot include both 1 & 2
C7 & R5
(1)R2C4=(1)R5C4-(1)R5C7=(2)R5C7-(2)R2C7=(2)R2C45... -> no 1 elsewhere in R5, no 2 elsewhere in C7, Cage 9/2 = {(1|2)..} = {18|27}


Killer XY chain
A mix of various links forming a chain (case C2)
The three strong links:
1 locked in R25C4 (a regular strong link)
2 locked in R3C4567 (a grouped strong link)
R5C7 = {12} (a bivalue cell)
The two weak links: C7 & R5
(1)R2C4=(1)R5C4-(1)R5C7=(2)R5C7-(2)R3C7=(2)R3C456 -> Cage 9/2 = {1..} | <> {2..} => <> {27}
Cage 9/2 either must include a 1 in R2C4 or cannot include a 2 which is locked R3C456


Altough I focused on Killer Sudoku, it's not limited to killer but may also be used for other variants with constraints on combinations: (non)-consecutive, renban...
Back to top
View user's profile Send private message
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Sat May 19, 2007 9:18 am    Post subject: Reply with quote

Excellent post, JC!

Have you coded these techniques into JSudoku already?

Ruud
Back to top
View user's profile Send private message Send e-mail
Jean-Christophe
Addict
Addict


Joined: 23 Apr 2007
Posts: 92
Location: Belgium

PostPosted: Sat May 19, 2007 11:01 am    Post subject: Reply with quote

All the single candidate patterns : X chains & loops were already in JSudoku, from version 0.4 (if I remember well). It's available on my site.

The Killer XY chains & loops will be avail in the next release. I've already implemented them except for the last example (case C2) which is more complex.

All the images are screen shots of JSudoku. I didn't alter them, except for the last example.

I made several test with hard puzzles. This is not as useful as I thought. I will have to investigate further with the harder case C2.

Some other thing which could be "killerized" : Killer ALS for such patterns as ((V)W)XYZ-Wings & the like. Where some ALS cells are replaced by sum cages. I think that a single cage could even replace 2 cells if it must include at least 2 candidates out of those forming the ALS.
But I don't have regular ALS yet, so I'll leave this for the future.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips 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


Powered by phpBB © 2001, 2005 phpBB Group