SudokuSolver Forum

A forum for Sudoku enthusiasts to share puzzles, techniques and software
It is currently Thu Mar 28, 2024 9:51 am

All times are UTC




Post new topic Reply to topic  [ 9 posts ] 
Author Message
 Post subject: Locking/Blocking Cages
PostPosted: Sat Feb 06, 2010 10:41 pm 
Offline
Grand Master
Grand Master

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
Please also read the next post to fully understand what this table is about.

Direct-link (->) candidate's table
This table is of combinations in cages (above 2 cells and no single combination cages) where one candidate forces a second candidate in the same cage (I'll use the shorthand "->" to show this forcing). For example, an 11(3) cage = {128/137/146/236/245}. 8, 7 and (surprisingly) 5 only occur in one combination -> each one has a direct-link with the other candidates in that one combination. So, for example, if 5 is in an 11(3) ->it must also have 4 and 2. 4 and 2 are both direct-link (->) candidates. But note that the reverse does not work, 4 does not force a direct-link to 5! Careful!!

This table has very limited use since it gets longer once combinations from any cage are eliminated during solving.

3-cell cage combinations with candidates that force a direct-link (->): note, a direct-link only works one way! The first couple have the links listed for illustration.
.8(3) = {125/134}: 2,3,4,5 ie (2->5),(3->4),(4->3),(5->2)
.9(3) = {126/135/234}: 4,5,6 ie (4->2,3),(5->1,3),(6->1,2)
10(3) = {127/136/145/..}: 4,6,7 (4->1,5),(6->1,3),(7->1,2)
11(3) = {128/137/245/...}: 5,7,8
12(3) = {129/138/...}: 8,9
13(3) = {139/...}: 9
.
.
17(3) = {179/...}: 1
18(3) = {189/279/...}: 1,2
19(3) = {289/379/568/...}: 2,3,5
20(3) = {389/479/569/...}: 3,4,6
21(3) = {489/579/678}: 4,5,6
22(3) = {589/679}: 5,6,7,8

4-cell combinations with candidates that force a direct-link (! = 2 combinations still have a candidate that force a direct-link)
12(4) = {1236/1245}: 3,4,5,6
13(4) = {1237/1246/1345}: 5,6,7
14(4) = {1238/1247/1256/1346/2345}: 5(5->2)!,6(6->1)!,7,8
15(4) = {1239/1248/1257/1347/1356/2346}: 6(6->3)!,7(7->1)!,8,9,
16(4) = {1249/1258/1348/...}: 8(8->1)!,9
17(4) = {1259/1349/...}: 9(9->1)!
.
.
23(4) = {1589/1679/...}: 1(1->9)!
24(4) = {1689/2589/2679/...}: 1,2(2->9)!
25(4) = {1789/2689/3589/3679/4579/4678}: 1,2,3(3->9)!,4(4->7)!
26(4) = {2789/3689/4589/4679/5678}: 2,3,4(4->9)!,5(5->8)!
27(4) = {3789/4689/5679}: 3,4,5
28(4) = {4789/5689}: 4,5,6,7

In digit form summary
1:
17(3) = {179}
18(3) = {189}
23(4) = {1589/1679}: (1->9)!
24(4) = {1689}
25(4) = {1789}

2:
.8(3) = {125}
18(3) = {279}
19(3) = {289}
24(4) = {2589/2679}: (2->9)!
25(4) = {2689}
26(4) = {2789}

3:
.8(3) = {134}
19(3) = {379}
20(3) = {389}
12(4) = {1236}
25(4) = {3589/3679}: (3->9)
26(4) = {3689}
27(4) = {3789}

4:
.8(3) = {134}
.9(3) = {234}
10(3) = {145}
20(3) = {479}
21(3) = {489}
12(4) = {1245}
25(4) = {4579/4678}: (4->7)!
26(4) = {4589/4679}: (4->9)!
27(4) = {4689}
28(4) = {4789}

5:
.8(3) = {125}
.9(3) = {135}
11(3) = {245}
19(3) = {568}
21(3) = {579}
22(3) = {589}
12(4) = {1245}
13(4) = {1345}
14(4) = {1256/2345}: (5->2)!
26(4) = {4589/5678}: (5->8)!
27(4) = {5679}
28(4) = {5689}

6:
.9(3) = {126}
10(3) = {136}
20(3) = {569}
21(3) = {678}
22(3) = {679}
12(4) = {1236}
13(4) = {1246}
14(4) = {1256/1346}: (6->1)!
15(4) = {1356/2346}: (6->3)!
28(4) = {5689}

7:
10(3) = {127}
11(3) = {137}
22(3) = {679}
13(4) = {1237}
14(4) = {1247}
15(4) = {1257/1347}: (7->1)!
28(4) = {4789}

8:
11(3) = {128}
12(3) = {138}
22(3) = {589}
14(4) = {1238}
15(4) = {1248}
16(4) = {1258/1348}: (8->1)!

9:
12(3) = {129}
13(3) = {139}
15(4) = {1239}
16(4) = {1249}
17(4) = {1259/1349}: (9->1)!


Top
 Profile  
Reply with quote  
PostPosted: Sat Feb 06, 2010 11:05 pm 
Offline
Grand Master
Grand Master

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
Locking Cages and it's inverse, Blocking Cages, both use cage combinations to either lock candidates or block permutations/combinations. This technique is called Locked Cages in sudopedia but I feel that Locking Cages is a better name since the inverse Blocking Cages makes more sense than "Blocked Cages". But, take your pick.

Locking Cages is when two cages contain the only candidate for a house which then "locks" a second candidate if that second candidate has a direct link to the first in both cages. It is easiest to see when two cages in the same house have the same cage total.

Two-cell cages

Image

In this example above from A167, 1 in c1 must be in one of the 10(2) cages -> one of those cages must also have 9 -> 9 locked for c1.

For some reason, it is much more common that one of the cages is hidden.

Image

In MessyOne#1 above, r56c3 (in yellow) is a h9(2) cage. Candidate 8 in this nonet must be in this hidden 9(2) or in the 9(2) cage -> 1 locked for the nonet. These become easy to find since the cage totals are the same.

Much more difficult is when the cage totals are different, ie, when at least one of the cages is more than 2 cells.

One two-cell and one three-cell cages

Image.

This pic above is an alternative way to do Andrew's step 18 in A174 here, using Locking Cages. 5 in n8 must be in the 11(2) = {56} or the hidden 19(3) at r7c45+r8c4 = {289/379/469/478/568}. The only combination with 5 is {568}, so, if it has 5 it must also have 6 (and of course 8 but that is not relevent here). In both cages, 5 forces candidate 6 -> 6 locked for n8.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Extension: locking-out combinations/candidates
But another extention of this move is possible, to lock-out combinations and possibly candidates within the locking cages. In the final example above, Other combinations in the h19(3) with the second candidate (6) can be eliminated since they don't also have the forcing candidate (5). So, {469} is not possible since it would leave no 5 available for n8! This second part is essential to Andrew's step 18.

The table in the previous post may make it easier to find Locking Cages when the two cages do NOT have the same total. Andrew notes that his move was available at the beginning of the puzzle. As the table shows, a 19(3) cage is one of those special cages that has this direct-link feature.

Image

This pic above is from Texas Jigsaw Killer 39 and is from manu's walkthrough here.
Quote:
3)a) 1 locked for n6 at r3c9+5(2)={14/23} : r3c9 <> 4 !
This move above involves just one cage (and one cell) but works by the locking-out principle to eliminate 4 from r3c9.

Locking-out also works for two 2-cell cages that have different cage totals. For example, if 6 is only in a 15(2) and 10(2) (in the same house) -> {19} is blocked from the 10(2)

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Now, a look at the inverse, Blocking Cages.

Image

This is from A171 ALT and is an alternative way to do manu's step 5b here. There is a hidden 12(2) at r23c3 which overlaps a 13(2) & a 10(3) -> [84] permutation is blocked from the h12(2) since 5 is also required in both cages ie, 5 is forced into both the 13(2)=[58] and 10(3)={15}[4]. So, the 13(2) and 10(3) work as Blocking Cages to h12(2) permutations. This leaves the h12(2) = {57} and cracks the puzzle.

Further applications of these techniques are available but those can wait for a separate post sometime. For example, almost Locking Cages can form killer subsets with other cages or almost Blocking Cages will eliminate combinations in other cages. The interesting sudopedia article shown in the link above includes an example of innies/outies as another way to use this locking technique.

Many thanks to Andrew and Afmob for encouraging this post onto this technques forum.

Cheers
Ed


Top
 Profile  
Reply with quote  
PostPosted: Fri Mar 19, 2010 4:35 pm 
Offline
Expert
Expert

Joined: Mon Apr 21, 2008 6:23 am
Posts: 113
Location: Germany
Ed wrote:
This technique is called Locked Cages in sudopedia but I feel that Locking Cages is a better name ...

I agree, but when I originally wrote that Sudopedia article, I used the term "locked cages" because it was already being referred to as such by JSudoku in its solver logs, although Jean-Christophe had unfortunately only implemented the technique, and had not documented it. :-(

Thanks to Ed for starting this thread and for providing some great illustrations of this technique :thumbs:. In the meantime, I have found another interesting example of a locking cages move involving three :shock: such cages in the same house. It essentially comes from my walkthrough for Ed's excellent Texas Jigsaw Killer 40, although I originally saw the move as involving a chain. It was only later that I noticed that the chain is unnecessary if one uses the combined cages technique instead. To illustrate, here is the grid state after my step 3:

Image

From this position, we can remove the 9 at R2C5 (an important elimination) as follows:

Quote:
4. 1 in R2 locked in either of 10(2) at R2C1 and R2C8, or combined 24(4) at R12C67
4a. 10(2) at R2C1 and R2C8 = {19/28/37/46} (1->9)
4b. combined 24(4) at R12C67 = {1689/2679/3678} (1->9)
4c. -> all 3 cages also lock 9 if 1 locked (hence nomenclature "1->9" in steps 4a and 4b above)
4d. -> 9 locked in R1C67+R2C1289
4e. -> no 9 in R2C5 (common peer)

Thereafter, the following steps can be used to break into the puzzle:

Quote:
5. 9 in N2 locked in 15(2) = {69}, locked for R1 and N2
5a. cleanup: no 4 in R1C89, no 3 in R2C67

6. 15(2) at R1C6 and 22(3) at R5C6 form grouped X-wing on 9 within C67
6a. -> no 9 elsewhere in C67

7. 9 in N3 locked in 10(2) at R2C8 = {19}, locked for R2 and N3
7a. cleanup: no 8 in R2C67, no 4 in R5C8

8. Law of Leftovers (LoL) R12: R3C126+R4C1 = R12C89 = {1589}
8a. -> R3C6 = 1, R3C12+R4C1 = {589}, locked for N1 and 37(7)
8b. cleanup: no 2 in R2C12

9. R2C4 = 5 (innie, N2)

...

Ed also came up with a couple of very clever moves for this puzzle himself, but that's a different story for another post. :) Look forward to reading more about that, Ed! ;)

_________________
Cheers,
Mike


Top
 Profile  
Reply with quote  
PostPosted: Sun Mar 28, 2010 5:23 am 
Offline
Grand Master
Grand Master

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
Huge move that one Mike. Congratulations on finding it. It effectively cracks the puzzle. and avoids the need for the Nishio move.

This is a nice simple example of Locking-out cages: where candidates within the cages that contain the forcing candidate are eliminated. It's from the same puzzle as Mike's post, TJK40 but is from my walk-through here
Image

At the spot above with the 9's highlighted.
6. 9 in n3 only in 13(2) = {49} or 10(2) = {19} -> {46} blocked from the 10(2) (Locking-out Cages)
6a. 10(2) = {19/28/37}(no 4,6)

I seem to see this technique in nearly every puzzle now!
Cheers
Ed


Top
 Profile  
Reply with quote  
PostPosted: Sat Apr 03, 2010 3:58 am 
Offline
Grand Master
Grand Master

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
This post extends the Locking Cages technique. First, to cages that are not wholly in the same house and second, to cages outside of the same house that only have a partial direct-link candidate but do have a common peer cell.

A bit of background first. I found these in A35v1.5 but only the 2nd and 3rd examples made my walkthrough here. I mistakenly called them Killer pairs. Afmob gave some really good feedback by PM which suggested they were a cross between Locking Cages and Killer pairs. So, this post is now in this thread. Perhaps they are Remote Locking Cages since they don't share a house. Better names welcome! [edit: Killer ALSxz; a new thread on this started here].

Example 1

Image

In the above pic, there is a hidden 17(3) at r7c9 + r89c7 which = [2]{69}/[5]{39} = [5/6..] ie, it must have 5 or 6.

In addition, r7c9 is part of an 11(2): if r7c9 = 5 -> r6c9 = 6 ie, if it has 5 it must have 6. If r7c9 is not 5, r89c7 must be 6. Either way, 6 is locked in r6c9 or r89c7 -> no 6 in the common peers in r45c7 or r89c9

Example 2
Example 1 has a crossover cell between the two cages to force an interaction. However, this next example has no crossover cell, but rather, one cell that is a peer between two remote cages. This forces the interaction.

Image

I'll quote Afmob's PM to explain this one.
Quote:
14. "45" on n9: 3 innies r7c9 + r89c7 = 17 and must have 9 for n9 = [2]{69}/[5]{39} = [5/6..]
14a. 14(2)r7c56 = {59/68} = [5/6..] -> Both cages can't have 5 (at the same time) since cells containing 5 see each other (r7c569) -> At least one cage must have 6 -> CPE: no 6 in r7c8

Note the bold part. This makes the move work. If it were only a Killer pair move then it would be cells containing 5 and 6 see each other, so that one cage must have 5 and the other must have 6. This is not the case here because both cages can have 6 (and indeed, both will have 6!).


Example 3
This example is more complex because it involves one cage and one outies "cage" but again, they have one cell that is a common peer.

Image

12. Outies n9 r9c6 + r6c9 = {46}/[19] = [6/[1]..] ie, they have 6 or 1
12a. 8(2) at r6c6 = [71/62] = [6]/[1] ie, they have 6 or 1
12b. Both cages can't have 6 (at the same time) since one cell containing 6 sees all cells of the other, ie r6c6 sees both r6c9 & r9c6 -> At least one cage must have 1 (and indeed, both will have 1!) -> CPE: no 1 in r89c7

Thanks also to Mike for encouraging this post here.

Cheers
Ed


Last edited by Ed on Tue Apr 13, 2010 9:37 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 07, 2010 8:35 am 
Offline
Expert
Expert

Joined: Mon Apr 21, 2008 6:23 am
Posts: 113
Location: Germany
Great post, Ed, and a smart technique, too! :D

Ed wrote:
Perhaps they are Remote Locking Cages since they don't share a house. Better names welcome!

I would much prefer to use the term Killer ALS-XZ, because it's the Killer equivalent of the established ALS-XZ technique in regular Sudoku. A cage which must have at least one of the digits {XZ} behaves (from a logical point-of-view) like a bivalue cell with the candidates {XZ}. A bivalue cell is also an almost locked set (ALS), since it has one more candidates than it does cells.

I'd also use the term "Killer ALS-XZ" for the possible intermediate situation where one of the groups of cells is a cage and the other an ALS.

Incidentally, the digit X, where all cells containing this candidate in both groups see each other, is typically referred to in the literature as the restricted common.

Edit: Further discussion on the topic of Killer ALS-XZ has been moved to here.

_________________
Cheers,
Mike


Last edited by mhparker on Thu May 06, 2010 1:28 pm, edited 1 time in total.

Top
 Profile  
Reply with quote  
PostPosted: Wed May 05, 2010 8:43 pm 
Offline
Grand Master
Grand Master

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
The end of my 2nd post on this thread refers to Blocking Cages. Time for some simpler examples.

Andrew's Walk-through for HBSSF here shows another use of Blocking Cages. In fact, it's probably the classic case of this technique.

Image
NOTE: all the 1 candidate cells are highlighted in blue and a hidden 19(3) cage in mauve.

Andrew wrote:
6b. 1 in N3 only in R1C78 = {14} or 10(2) cage at R1C9 = [91] -> R2C7 + R3C78 = {289/379/478/568} (cannot be {469}, blocking cages) (no immediate eliminations)]
In this classic example Andrew has used, two cages block a combination for a third cage that sees those two. This is different to the example earlier in this thread where two cages blocked the combinations for an overlapping hidden cage.

The next example is also from HBSSF at the same spot and for the same reason, but this time, does give some eliminations.

Image

From Andrew's step 6b, r1c78 = {14} or r1c9 = 9 -> r1c789 = [4/9..]
Add to step 6
13(2) at r1c2 = {58/67}({49} blocked by r1c789: Blocking Cages 1->4/9), no 4,9

This is a harder step to see because the blocking cages block through permutations, not just combinations. Also, they have an effect in another area of the puzzle.

Cheers
Ed


Top
 Profile  
Reply with quote  
PostPosted: Tue Nov 29, 2011 11:14 pm 
Offline
Grand Master
Grand Master

Joined: Wed Apr 23, 2008 6:04 pm
Posts: 1893
Location: Lethbridge, Alberta, Canada
Here is an example of Locking Cages which I found when I solved A57 V1.5 this year.

Image

22. 9 in N5 only in R4C6 + R5C4 -> R4C67 = [93] or R5C34 = [39] (locking cages) -> no 3 in R4C23+ R5C789, clean-up: no 2 in R4C4 ...
[I originally saw this step as a very short forcing chain but, while checking my walkthrough, I realised that it’s actually locking cages so I’ve re-written it that way.]

This led immediately to
23. R7C4 = 2 (hidden single in C4) ...
and the puzzle was cracked.

Thanks Ed for providing the diagram!


Top
 Profile  
Reply with quote  
PostPosted: Wed Nov 30, 2011 7:49 pm 
Offline
Grand Master
Grand Master

Joined: Wed Apr 23, 2008 6:04 pm
Posts: 1893
Location: Lethbridge, Alberta, Canada
And now for a more unusual example of Locking Cages, or maybe this one is Blocking Cages, which I found when I solved PANIV X this year.

Image

31. 45 rule on N12356 1 innie R3C2 = 1 outie R5C3 + 6 -> R3C2 + R5C3 = [82/93]
31a. 9 in R3 only in R3C29, 3 in R5 only in R5C39, R3C2 + R5C3 contains both or neither of 3,9 -> R35C9 must contain both or neither of 3,9
31b. R3C2 + R5C3 = [93] (R35C9 cannot be [93] because no 6 in R4C9), R4C2 = 2 ...

and the puzzle was cracked.

Thanks Ed for providing the diagram!


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 9 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


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 post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group