top95 X-cycle (simple coloring), Y-cycle, and "3D-Medusa" examples

from the Sudoku Assistant

This document discusses three types of "logical chains" that people employ in 
solving Sudoku Puzzles. These include X-cycles, Y-cycles, and 3D Medusa.

See also top95-methods.htm explain.htm.
See examples.htm for almost 1600 examples categorized by type culled from the top95.



X-Cycles                                                                  X-cycles  Y-cycles  3D Medusa 
--------

X-Cycle analysis (Simple coloring) just involves following "conjugate pairs" 
of a specific number around to see if they force a possibility to be eliminated. 

"Conjugate pair" here refers to exactly two occurances of a specific number
("candidate") in a specific row, column, or block. In the diagrams shown below,
conjugate pairs are shown using "blades"---dashed lines that mean there are NO
other occurances of this number in a row (--), column (|), or block (\ or /). 


While there are certainly many examples of this sort of thing in the
top95 collection, there are just four puzzles in top95 that can be solved using 
only basic methods (cross-hatch scanning, locked candidates, and subset analysis)
plus simple coloring (X-cycle) analysis. These include
#5, #13, #17, #24, #25, #38, #41, #47, #53, #63, #71, and #95. 
Only a few examples are shown below.

The figures below use the notation introduced in the Sudoku Programmer Forum

Click on the puzzle number to load the original configuration. 
Click on the description to load the exact configuration.

Puzzle #13

weak 3-blade fishy cycle eliminates r4c2#5:

 r4c2#5       |
       x......5*
       .      |
       .      |
      -5------+--5*-
              | /
              |/
              5
              |


weak 3-blade pentagon eliminates r5c6#5:

 |          r5c6#5
 5*.......x
 |        .
 |        .
 |        .
 |        5
 |       /
 |      /
-5-----5*-
 |


weak 2-blade pentagon eliminates r4c2#7:

  r4c2#7     |
        x....7*
     | .     |
     |.      |
     7       |
     |       |
     |       |
     |       |
     7*......7
     |       |


weak 2-blade fishy cycle eliminates r5c5#7:

             |
             7*
     |       | .
     |       |  .
     7...........x r5c5#7
     |       |
     |       |
     |       |
     7*......7
     |       |



Puzzle #25

strong 4-blade fishy cycle on 5 eliminates all with *:

       
      -1----------1*-
       |          |
       |          |
       1*...........1*
       |          |/
                  1
                  |


Puzzle #53

strong 6-blade fishy cycle on 7 eliminates all with *:

    |      |
   -7*-----7-
    |      |
    |      |       |
   -7------+-------7*-
    |      |       |
           |       |
           |       |
           |       |
           |       7
           |      /|
           |     /
           7*...7*


strong 4-blade pentagon eliminates all with *:

  |        
 -5--------5*-
  |       /
  |     |/ 
  |     5        (more cycles exist in this example)
  |     |
  |     |
  5*....5*
  |     |

 
Puzzle #71

weak 3-blade pentagon eliminates r4c3#7:

           
       -7*-------7-
        .       /
        .     |/ 
        .     7*
        .     |
        .     |
        x.....7
 r4c3#7       |



Y-Cycles                                                                  X-cycles  Y-cycles  3D Medusa 
--------
I learned this term from Glenn Fowler. The idea is that cells 
with exactly two candidates can be traversed one to the 
next to the next, because in each pair if one value is "FALSE" 
then the other will be "TRUE". We can treat them just like 
conjugate pairs, except we must switch numbers each step. 
It's really very easy to do. In the language of strong chains, 
each of the cells involved in a Y cycle is a short strong chain, 
and each connection to the next cell is a weak link. (It might 
be strong -- a conjugate pair -- but that is not required.) 

What's nice about this is that nothing else on the board matters 
at all for the analysis -- just the cells with exactly two 
possible values. 

The examples from top95 that can be solved using only basic methods plus 
Y-cycle include #4, #5, #17, #41, #74, and #76.

Several examples are shown below.

Click on the puzzle number to load the original configuration. 
Click on the description to load the exact configuration.

Puzzle #4

a three-cell Y cycle allowing for the elimination of r2c3#9:

           r2c3#9
     9...x
    5    .
    .    .
    5    .
     8.  .
       . 9
        8
         


a four-cell Y cycle allowing for the elimination of r4c2#4:

 r4c2#4
       x..4
       .   9
       .   .
       .   .
       4   .
    5...5  .
     8     .   
      .    .
       .   .
        .  .
         . 9
          8
         

a four-cell Y cycle allowing for the elimination of r2c2#5:

           r2c2#5
     5.....x
    9      .
    .      .
    .      .
    .      .
    9      .
     6     .
      .    .
       .   .
        6  .
         4 .
         . .
         . .
         . 5
         ./
         4
          
        

#5
a four-cell Y cycle allowing the elimination of r9c1#9:

     5..............5
      9              9
      .              .
      .              .
      .              .
      .              .
      .              .
      x.........9    .
r9c1#9           5   .
                  .  .
                   . 9
                    5


a four-cell Y cycle allowing the elimination of r9C1#5:


       9............9
      5              5
      .              .
      .              .
      .              .
      .              .
      .              .
      x.........5    .
r9c1#5           9   .
                  .  .
                   . 5
                    9


The above two, though independent, can be seen together 
as a double Y cycle involving only 5 and 9.


Puzzle #17
another double 4-cell Y cycle allowing the elimination of both r1c3#4 and r1c3#6:

r1c3#4,6

       x.......4
      . x.....6.
     . .      ..
    4 .       ..
    .6        ..
    ..        ..
    ..        ..
    .6........6.
    4..........4
       
The position of the deletion is set because that is the only cell 
that has any possibilities other than 4 and 6.

The actual logic, remember, involves BOTH 4 and 6 and goes 

-46...64...46...64- and -64...46...64...46-
 FT-->FT-->FT-->FT       FT-->FT-->FT-->FT     
 TF<--TF<--TF<--TF       TF<--TF<--TF<--TF       

Which can also be read in this case as:

 -6--6--6--6- and -4--4--4--4-
  F->T->F->T       F->T->F->T
  T<-F<-T<-F       T<-F<-T<-F

But really this is just a general case of:

-4X...XY...YZ...Z4- 

for the fours, and 

-6X...XY...YZ...Z6-

for the sixes.

The key is that there must be a "F" and the beginning and a "T" 
at the end of the logical chain going either way.

3D Medusa                                                                 X-cycles  Y-cycles  3D Medusa 
---------
As useful as X-cycles and Y-cycles are, one could imagine an improvement
if they were combined. We could "transfer" the strongness of a two-valued
cell to an associated conjugate pair. This synthesis of X and Y I've chosen
to call "3D Medusa" because looking at the 3D rendition at the Sudoku Assistant
and the way the influence of a cell branches out all over the volume made me
think of Medusa and her killer hair. Here are the facts: Using X-cycles alone
we can solve 12 more than the basic 35 puzzles of the top95 collection. Using 
Y-cycles alone, we can solve only six more than the basic 35, and only two of
those (#74, and #76) are ones that X-cycle analysis can't solve.

But, if we allow chains to combine both X and Y characteristics, then we can
solve an additional 13 puzzles of the collection that neither X-cycle or
Y-cycle analysis together can handle. In fact, there is only one puzzle, #85,
in the top95 collection that is solvable without trial and error and actually
requires something more than 3D Medusa alone. This one has an intractable 
X-wing. (Several puzzles have X-wings or swordfish, but 3D Medusa is able to solve 
these puzzles without need for finding them.) 

OK, so the set of additional puzzles that 3D Medusa cracks but X-cycle and Y-cycle
analysis alone can't handle include the following:

#8, #10, #29, #32, #52, #55, #70, #72, #77, #80, #82, #87, and #94.

Shown here are a few examples. They all come from configurations that have no
avenues of advancement involving pure X-cycles, Y-cycles, X-Wings, or Swordfish. 
(Go ahead and look.... I guarantee you won't find any. It is possible, however,
that some of these solutions might benefit from uniqueness tests. The Sudoku 
Assistant does not use uniqueness tests. I do when I'm hand-solving, though,
because they're so handy.)

As a first example of using the 3D Medusa strategy, consider puzzle #8. 
In that puzzle we find this configuration. 



Shown below is the 3D Medusa "strong chain analysis" for this configuration.
The letters are chain designations. Nineteen strong chains 
are labeled A-S, with alternating parity shown using lowercase.


   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8---|---c9-- 
------------------------------------------------------------------------------ 
r1 |    69 |     5 |     2 ||     4 |     8 |     1 ||    79 |   3679 |   367 
   |    bB |       |       ||       |       |       ||    gG |   d    |   D   
---+-------+-------+-------||-------+-------+-------||-------+--------+------- 
r2 |  4689 |   346 |   348 ||    69 |     7 |   569 ||     1 |  24569 | 24568 
   |       |   e k |   E   ||    iI |       |   j   ||       |  h     | H     
---+-------+-------+-------||-------+-------+-------||-------+--------+------- 
r3 |  4689 |    17 |    17 ||     3 |     2 |   569 ||  4589 |   4569 |  4568 
   |       |    aA |    Aa ||       |       |   J   ||    r  |        |       
===========================||=======================||======================== 
r4 |   456 |  1467 |  1457 ||     8 |  1469 |     2 ||  4579 | 134579 | 13457 
   |    f  |    Ka |       ||       |    nP |       ||       |  D     |  d    
---+-------+-------+-------||-------+-------+-------||-------+--------+------- 
r5 |     3 |   124 |  1458 ||    17 |   149 |    47 ||     6 |  12459 | 12458 
   |       |    C  |     o ||    mM |     p |    Mm ||       |      P |     O 
---+-------+-------+-------||-------+-------+-------||-------+--------+------- 
r6 |  2468 |     9 |  1478 ||     5 |   146 |     3 ||  2478 |   1247 | 12478 
   |  c n  |       |       ||       |     N |       ||     R |        |       
===========================||=======================||======================== 
r7 |     1 |   248 |     6 ||    79 |     3 |  4789 ||  2457 |   2457 |  2457 
   |       |     l |       ||    Ii |       |    LI ||       |        |       
---+-------+-------+-------||-------+-------+-------||-------+--------+------- 
r8 |   245 |   234 |   345 ||   167 |    14 |   467 ||  2347 |      8 |     9 
   |   C F |       |   e f ||   MI  |    mM |    i  ||   q   |        |       
---+-------+-------+-------||-------+-------+-------||-------+--------+------- 
r9 |     7 |   348 |     9 ||     2 |     5 |    48 ||    34 |     16 |    16 
   |       |   q L |       ||       |       |    Ll ||    Qq |     sS |    Ss 
..............................................................................


Now what? The key is in the bottom center block and the 69 in the block two above it. 


If we wanted to look at it in terms of cycles, we could write:

   ||
  -69* r2c4
   || 
   ||        
   ||        
   |9  r7c4
   | 7*
   |   .
   |    7 r8c6
   |     .  
  -6*-----6-
    r8c4   r8c6
 
This cycle consists of three conjugate pairs and two two-value cells.
The 7 at r8c6 can be eliminated because it is interacting weakly with both a 
starred and an unstarred node of the cycle.


For a second example, take a look at Puzzle #72. Without 3D Medusa 
we are stuck at the following configuration:


Shown below is the strong chain analysis. The 18 strong chains 
are labeled A-R, with alternating parity shown using lowercase.

   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9-- 
-----------------------------------------------------------------------------
r1 | 139 | 3459 | 1359 || 6 | 7 | 12 || 249 | 8 | 349
| | BC | H c || | | Aa || A | | I
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 | 13789 | 3479 | 6 || 48 | 89 | 12 || 5 | 279 | 3479
| A D | b | || Ee | Gg | aA || | a | i
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 | 789 | 2 | 79 || 458 | 589 | 3 || 479 | 6 | 1
| d | | Jj || eF | f G | || E | |
===========================||=======================||=======================
r4 | 369 | 1 | 4 || 38 | 368 | 7 || 689 | 5 | 2
| L | | || Kk | M | || l | |
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 | 679 | 679 | 8 || 1 | 2 | 5 || 3 | 4 | 679
| | | || | | || | | L
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 | 2 | 3567 | 357 || 9 | 368 | 4 || 1678 | 17 | 678
| | c | C || | m | || h | Hh |
===========================||=======================||=======================
r7 | 13679 | 3679 | 2 || 357 | 35 | 89 || 468 | 179 | 4568
| H | | || | fF | Nn || O | h | oQ
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 | 5 | 8 | 179 || 27 | 4 | 6 || 1279 | 3 | 79
| | | h || Aa | | || Ha | | Pp
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 | 4 | 3679 | 379 || 2357 | 1 | 89 || 68 | 279 | 568
| | | || a Q | | nN || Rr | A | q
----------------------------------------------------------------------------- Do you see the problem? It's hiding in row 1 and block 9. In row 1 (or block 1) we have 1H and 1A. But in block 9, in cell r8c7, we also have Ha. The first, 1A/1H, says "When chain Hh is H, then chain Aa is not A." But the Ha in cell r8c7 says "when chain Hh is H, then chain Aa is not a." Well, that's impossible. Chain Aa has to be something. Chain Ha must not be the H parity. We can delete all the marks represented by the letter H: r1c3#1, r6c8#1, r7c1#1, and r8c7#1. (One of the neat things about 3D Medusa is that often you get to remove several marks at a time.) In terms of cycles, we could write many things. One would be: r1c3 | r1c6 1.....1 | r1c7 | -2*-----2- | | |Chain Hh |Chain Aa | | r8c3 | | -1*----------1-+- | :| r8c7 2* | It's basically two mismatched X chains, one involving 1 and the other involving 2. Here is another view of the situation: My last example is puzzle #80. This puzzle requires just one application of 3D Medusa to do the job. In step 32 we arrive at the following configuration. Well, do you see anything to do? Here's the strong chain analysis. The 13 strong chains are labeled A-M. |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 | 9 | 6 | 3 || 147 | 14 | 147 || 25 | 58 | 28
| | | || D | Cc | d || Aa | Aa | aA
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 | 1 | 5 | 2 || 3 | 9 | 8 || 6 | 7 | 4
| | | || | | || | |
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 | 8 | 7 | 4 || 2 | 6 | 5 || 13 | 19 | 139
| | | || | | || hH | Ii | hI
===========================||=======================||=======================
r4 | 23 | 4 | 5 || 8 | 7 | 269 || 13 | 169 | 1369
| Bb | | || | | b || Hh | I |
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 | 23 | 1 | 8 || 69 | 5 | 269 || 7 | 4 | 369
| bB | | || jJ | | B || | | b
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 | 6 | 9 | 7 || 14 | 3 | 14 || 8 | 2 | 5
| | | || Kk | | kK || | |
===========================||=======================||=======================
r7 | 7 | 28 | 16 || 14569 | 148 | 1469 || 25 | 3 | 1268
| | Ee | Gg || a j | CL | J || aA | |
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 | 5 | 38 | 9 || 16 | 2 | 136 || 4 | 168 | 7
| | Ff | || Mm | | f || | F |
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 | 4 | 238 | 16 || 1567 | 18 | 1367 || 9 | 1568 | 1268
| | ef | gG || A d | Ll | F D || | a | E
----------------------------------------------------------------------------- Chain Aa is an interesting chain. It starts in the upper right, in block 3, and has "tentacles" down into the lower row. Here's the problem: If "a" is TRUE, then from column 8, where there are both a 8a and a 8F, we know that Chain Ff cannot be "F" -- it must be "f". Similarly, in row 7 we have 2a and 2E. Chain Ee must be "e" (assuming chain Aa is "a"). But looking in r9c2 we see that we can't have both "e" and "f". So, therefor, chain Aa cannot be "a". This eliminates all of the following nodes: r1c9#2, r1c7#5, r1c8#8, r7c4#5, r7c7#2, and r9c8#5. That's gotta help! Notice that we didn't have to think at all in terms of "cycles" for this strategy. But using the sort of X-cycle/Y-cycle circuit business, we could write: r1c7 | -2--------2*- | \ r1c9 | -8*----8- | .r1c8 Chain Aa r7c2 | . r7c7 | . 2.........2* . | . | r8c2 . r8c8 | -8-----------8- Chain Ee | 3 | | | | Chain Ff | 3* |: r9c2 2* There are three strong chains involving three weak links. This analysis shows that if Chain Aa is "a" then we will have to knock out both 2s in column 2. We can delete all the "a" nodes. There are many other equivalent analyses with the same overall outcome. You can probably find a simpler one.

Disclaimer