Almost locked sets xy wing rule definition and Example

Advanced methods and approaches for solving Sudoku puzzles

Almost locked sets xy wing rule definition and Example

Postby bennys » Wed Dec 07, 2005 6:15 am

Code: Select all
Almost locked sets xy wing rule definition and Example

For two sets A,B that have common candidate x we will say that x is restricted common if it can't be
in A and B in the same time.(being in A exclude it from B)

Almost locked sets xy wing rule

If A B C almost locked sets
x common to A,B
y restricted common to B,C
z restricted common to A,C

then  a cell that can 'see' all the x candidates of both A and B can't be x.



Example of almost locked sets xy wing

Puzzle: Menneske.no Very Hard #909905
+-------+-------+-------+
| . 1 . | . 3 . | 2 . 6 |
| . . . | . . 4 | . . . |
| 8 3 2 | 5 6 1 | 7 9 4 |
+-------+-------+-------+
| . 7 . | 6 4 5 | 8 . . |
| 6 . . | 9 . 7 | . . 5 |
| . . 5 | . 1 . | . 6 7 |
+-------+-------+-------+
| 7 4 . | . . 6 | 1 . 8 |
| . . . | 4 . . | . 7 . |
| . . 8 | 1 7 . | . 4 . |
+-------+-------+-------+

+-------------------+-------------------+-------------------+
| 459   1    %479   |%78    3    %89    | 2    %58    6     |
| 59    569   679   | 278   289   4     |^35    1358  13    |
| 8     3     2     | 5     6     1     | 7     9     4     |
+-------------------+-------------------+-------------------+
|*139   7    *139   | 6     4     5     | 8     123   1239  |
| 6     28   *134   | 9     28    7     |^34    13    5     |
| 24    289   5     | 238   1     238   |^49    6     7     |
+-------------------+-------------------+-------------------+
| 7     4     39    | 23    259   6     | 1     235   8     |
| 12359 2569  1369  | 4     2589  2389  | 3569  7     239   |
| 2359  2569  8     | 1     7     239   | 3569  4     239   |
+-------------------+-------------------+-------------------+

A={R4C1,R4C3,R5C3}
B={R2C7,R5C7,R6C7}
C={R1C3,R1C4,R1C6,R1C8}
x=9
y=5
z=4

and we get R6C2<>9 which solve the puzzle
bennys
 
Posts: 156
Joined: 28 September 2005

Postby rubylips » Wed Dec 07, 2005 11:58 am

In order forcing chains logic to detect this pattern there would have to be a new link type, perhaps called an extended disjoint subset link that could deduce r6c2=9 => r5c3=4. It might be written r6c2 -><9|4>->r5c3, or something similar in order to suggest the lack of symmetry. The general pattern is that when a cell in a sector that contains an Almost Disjoint Subset / Locked Set takes a value associated with that set, the set is locked, so any value in that set that is a candidate for just one position must take its position.

With this link type, the critical chain would be:
r6c2-><9|4>->r5c3-4-r1c3+<4|5>+r1c8~5~r2c7+<5|9>+r6c7-9-r6c2, which is self-contradictory if r6c2 contains 9.

Without this link type, it's possible to make good progress:

Code: Select all
Consider the chain r2c3+<7|3>+r2c7~3~r5c7-4-r5c3+<4|6>+r8c3.
When the cell r2c3 contains the value 6, so does the cell r8c3 - a contradiction.
Therefore, the cell r2c3 cannot contain the value 6.
- The move r2c3:=6 has been eliminated.
The cell r8c3 is the only candidate for the value 6 in Column 3.

Unfortunately, this chain isn't a killer. After some straightforward progress:

Code: Select all
2. The cell r8c1 is the only candidate for the value 1 in Row 8.
3. The cell r2c2 is the only candidate for the value 6 in Row 2.
4. The cell r9c7 is the only candidate for the value 6 in Row 9.
5. The value 5 in Box 7 must lie in Row 9.
- The move r8c2:=5 has been eliminated.
The cell r9c2 is the only candidate for the value 5 in Column 2.
6. Consider the chain r8c2-9-r6c2~9~r6c7-9-r8c7.
The cell r8c7 must contain the value 9 if the cell r8c2 doesn't.
Therefore, these two cells are the only candidates for the value 9 in Row 8.
- The moves r8c5:=9, r8c6:=9 and r8c9:=9 have been eliminated.
Consider the chain r6c2-9-r8c2-9-r8c7-9-r6c7.
The cell r6c7 must contain the value 9 if the cell r6c2 doesn't.
Therefore, these two cells are the only candidates for the value 9 in Row 6.
- The move r6c1:=9 has been eliminated.

the following candidate grid remains:

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

whereupon the puzzle falls to the following observation:

Code: Select all
Consider the cell r6c1.
When it contains the value 4, the values 5 and 9 in Column 1 must occupy the cells r1c1 and r2c1 in some order.
When it contains the value 2, the values 8 and 9 in Box 4 must occupy the cells r5c2 and r6c2 in some order.
Whichever value it contains, the cells r4c1 and r5c1 cannot contain the value 9.
- The move r4c1:=9 has been eliminated.
The value 3 is the only candidate for the cell r4c1.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby ronk » Wed Dec 07, 2005 5:27 pm

rubylips wrote:In order forcing chains logic to detect this pattern there would have to be a new link type, perhaps called an extended disjoint subset link that could deduce r6c2=9 => r5c3=4.

r5c3-4-r5c7+<4|5>+r2c7~5~r1c8+<5|4>+r1c3 ... which is contradictory since column 3 may not contain two 4s. Therefore r5c3 candidate 4 may be eliminated.

But I don't get 'z' part of an xy-wing yet.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby rubylips » Wed Dec 07, 2005 6:27 pm

You're right in that it's not strictly necessary to introduce a new technique in order to solve this puzzle. I highlighted the chain

r6c2-><9|4>->r5c3-4-r1c3+<4|5>+r1c8~5~r2c7+<5|9>+r6c7-9-r6c2

in order to replicate the logic of bennys and the chain

r2c3+<7|3>+r2c7~3~r5c7-4-r5c3+<4|6>+r8c3

to show how existing techniques could solve the puzzle. Your chain

r5c3-4-r5c7+<4|5>+r2c7~5~r1c8+<5|4>+r1c3

is superior because once 4 has been removed from r5c3 the remainder of the puzzle is trivial.

ronk wrote:But I don't get 'z' part of an xy-wing yet.

I'm not entirely sure what you mean by this comment. bennys refers to the 4 in r1c3 and r5c3 as his 'z', which is the 4 you remove by contradiction. I think you mean that the solution discussed here is overcomplicated because it's not necessary to involve the cells r4c1, r4c3, or r6c7. I agree with you if that's the case but I still think the post raises an interesting discussion point.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby ronk » Wed Dec 07, 2005 7:13 pm

rubylips wrote:Your chain

ronk wrote:r5c3-4-r5c7+<4|5>+r2c7~5~r1c8+<5|4>+r1c3

is superior because once 4 has been removed from r5c3 the remainder of the puzzle is trivial.

I think it's bennys' style to post examples with eliminations that "break" the puzzle.

rubylips wrote:
ronk wrote:But I don't get 'z' part of an xy-wing yet.

I'm not entirely sure what you mean by this comment.

I hadn't yet realized there is an unnamed (and unheralded) 'z' in the traditional xy-wing pattern.
Code: Select all
 .  .  xz | .  .  .  | xy .  .
 .  .  .  | .  .  .  | .  .  .
 .  .  .  | .  .  .  | .  .  .
 ---------+----------+----------
 .  .  .  | .  .  .  | .  .  .
 .  .  *  | .  .  .  | yz .  .
 .  .  .  | .  .  .  | .  .  .
 ---------+----------+----------
 .  .  .  | .  .  .  | .  .  .
 .  .  .  | .  .  .  | .  .  .
 .  .  .  | .  .  .  | .  .  .

rubylips wrote:I still think the post raises an interesting discussion point.

No question. But if the weak link in box 3 was replaced by yet another Almost Locked Set, it would *really* be an interesting example. Heck, bennys is probably trying to find one of those right now.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Thu Dec 08, 2005 12:22 pm

ronk wrote:r5c3-4-r5c7+<4|5>+r2c7~5~r1c8+<5|4>+r1c3 ... which is contradictory since column 3 may not contain two 4s. Therefore r5c3 candidate 4 may be eliminated.


On second thought, I think the equation should be ...

r5c3~4~r5c7+<4|5>+r2c7~5~r1c8+<5|4>+r1c3~4~r5c3

With "r5c3~4~" and "~4~r5c3" at the ends of the loop, ...
1) the contradiction r5c3=4 and r5c3<>4 is easier to see,
2) the equation may be read either left-to-right or right-to-left, and
3) it shows weak links are sufficient even though strong links may exist.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA


Return to Advanced solving techniques