The New Sudoku Players' Forum

[Mike Barker]

One thing that Jeff did, which I've never quite agreed with, was to include the CEC (candidate elimination cell) as part of the cycle or nice loop. From this perspective a discontinuous Y-cycle is a cycle since you can travel around it continuously. Continuous or discontinuous refers to the labels of the edges which connect the vertices and not whether the start and end vertices are the same.

[re'born]

I'm not sure I understand the definition of bi-directional Y-cycle. Would the the following be an example?

[r8c6]-2-[r8c8]-9-[r1c8]-2-[r1c2]-9-[r2c1]-4-[r5c1]=4=[r5c5]=1=[r9c5]-1-[r9c4]-9-[r9c6]-2-[r8c6]

No, for two reasons. Firstly, it is not "bi-directional" -- according to Nicolas Juillerat's apparent usage -- since the loop is discontinuous instead of continuous. Personally, I think "bidirectional" is a poorly chosen term because the inferences of a discontinuous loop are also bi-directional.

Ah hah. Well, I agree with you on the nomenclature question.

Secondly, a y-cycle deduction has strong inferences based on bivalue cells only. The elimination cell need not be bivalued, however. Your loop has two strong inferences of an x-cycle (highlighted above). (see last paragraph)

Okay, so we're only dealing with continuous loops (i.e., I shouldn't be getting chains of the form [rAcB]-X-...-X-[rAcB]). So if I do 3D-coloring, I will get all possible Y-cycles, but not everything I get will be a Y-cycle.

We then are left with a BUG+4 grid (is it +3 or +4 when two of the candidates are in the same cell?) and it is easy to check that this implies r8c5<>5, solving the puzzle.

That confused me for some time too. In the BUG+n notation, the number of candidates in a poly-valued cell is irrelevant. As I was unable to spot that deduction, would you please post the pencilmarks and the BUG+n splitting of candidates TIA

Sorry, I somehow copied but forgot to paste my BUG+3 grid. After the Sue De Coq, we get:

Code: Select all

.---------------.---------------.---------------.
| 3    29   8   | 15   7    15  | 4    29   6   |
| 49   1    45  | 2    6    8   | 59   7    3   |
| 6    25   7   | 3    9    4   | 25   8    1   |
:---------------+---------------+---------------:
| 25   3    1   | 69   25   69  | 7    4    8   |
| 45   7    9   | 8    14+5 15  | 6    3    2   |
| 8    6    24  | 7    24   3   | 1    5    9   |
:---------------+---------------+---------------:
| 29   59  36+25| 56   8    7   | 23   1    4   |
| 1    8    56  | 4    35-  26  | 39+2 29   7   |
| 7    4    23  | 19   13   29  | 8    6    5   |
'---------------'---------------'---------------'


Now, r8c5=5 (=> r5c5<>5) => r8c3=6 => r8c6=2 (=>r8c7<>2) => r9c6=9 => r9c3=2 (=>r7c3<>2) => r7c1=9 => r7c2=5 => r7c3<>5.

[claudiarabia]

Of course here it is:

Code: Select all

 
 *-------------------------------------------------------------------*
 | 5      269    2679    | 4      #28     1    |#3678  3679   679    |
 | 149    8      1679    | 3579   37     *35-9 | 467    2      45679 |
 | #249   *49-2    3     | 579     #28     6   | 478    4579   1     |
 |-----------------------+---------------------+---------------------|
 | 7      126    126     | 138    5      238   | 9      1346   46    |
 | 8      1569   4       |*17-39  *7-3   #39   |#136    *156-3  2    |
 | #129    3     *159-2  | 6      4      #29   | 17     8      57    |
 |-----------------------+---------------------+---------------------|
 | 149    149    8       | 2      6      7     | 5      149    3     |
 | 3      7      259     | 58     1      458   | 246    469    469   |
 | 6      1245   125     | 35     9      345   | 1247   147    8     |
 *-------------------------------------------------------------------*


The cycle cells have the route-sign. The cells in which an elimination occurs, have a star. The eliminated numbers come after the numbers to stay and a minus.
The cycle consists of the numbers:

Code: Select all

.  .  .  .  28 .  38 .  .
.  .  .  .  .  .  .  .  .
2  .  .  .  2  .  .  .  .
.  .  .  .  .  .  .  .  .
.  .  .  .  .  39 3  .  .
2  .  .  .  .  29 .  .  .
.  .  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .  .


And here the description how the cycle works:

1. clockwise: If r1c7=3 -> r5c7= -3 -> r5c6=3/-9 -> r6c6=9/-2 -> r6c1=2 -> r3c1=-2 -> r3c5=2 -> r1c5= -2/8 -> r1c7= -8/3 Cycle is closed.

2. Anticlockwise: If r1c7=8 -> r1c5= -8/2 -> r3c5= -2 -> r3c1=2 ->r6c1=-2 -> r6c6=2/-9 -> r5c6=9/-3 -> r5c7=3 -> r1c7=-3/8 cycle is closed.

The above mentioned eliminations are confirmed in both directions. Sorry I forgot the 8 in r1c5 before in my cycle skizze.

[ronk]

Heres a discontinuous Y-cycle which solves claudiarabia's puzzle:
6-node XY-chain (r5c6-5-r5c1-4-r6c3-2-r9c3-3-r9c5-1-) => r5c5<>1

Nice deduction, which I missed before. Using a graph theory term, I guess that would be a "bivalue path." That would take some getting used to.

[gsf]

Based on that link, it appears Bob Hanson picked up the x-cycle and y-cycle terminology from Glenn S. Fowler -- our very own gsf.

ha, at the time, and still now, I assigned single upper-case letters to the constraint methods in my solver
I happened to pick X for the single valued cycles and when I added bivalue cycles I simply did alpha X+1

but there's always something to learn past the terminology
in this case I had thought (but would have known better had I read just a bit more than coded)
that there's eliminations to be gained from even cycles (not just odd ones as mentioned in
my monoid coloring post on this forum)
I hope to merge that into my X/Y algorithm in the next weeks

[tarek]

A Y-cycle is equivalent to an X-cycle, but in the former case the cells are all bivalues and the later they are strong links.

That's a very broad definition of equivalency.

Yes VERY BROAD but VERY NICE

tarek

[ronk]

When is an X-cycle "identical" to a Y-cycle

[tarek]

I'm not sure if your question is directed towards mike but could the answer be a single digit cycle connecting bivalue cells only (xy chains all linked by the same digit)?

tarek

[ronk]

tarek, the question was to everyone, but I was only expecting a response from you, Mike or gsf.

tarek, you're on the right trail ... but with bivalue cells, the answer can't possibly be limited to one digit.

[tarek]

tarek, you're on the right trail ... but with bivalue cells, the answer can't possibly be limited to one digit.

True...
How about same digit strong links from the "bivalue start node" & to the "bivalue end node" ([rXcY]=W=...(strong links).....=W=[rAcB]) ?????

(I will stop guessing as of NOW )

tarek

[ronk]

Based on gsf's observation that discontinuous cycle is oxymoronic, I was referring to what we've generally been calling continuous loops.

[edit: I had incorrectly referred to a pure cycle of conjugate links as an X-cycle.

If we start with a pure cycle of conjugate links, then after eliminations we have a Y-cycle as well. If we start with a Y-cycle, then afer eliminations we have a pure cycle of conjugate links as well.]

Code: Select all

    a           c
 .  /   .  | .  /   .  | .  .  .
 /  ab* /  | /  bc* /  | /  /  /  b
 .  /   .  | .  /   .  | .  .  .
-----------+-----------+----------
 .  /   .  | .  /   .  | .  .  .
 /  ad* /  | /  cd* /  | /  /  /  d
 .  /   .  | .  /   .  | .  .  .
-----------+-----------+----------
 .  /   .  | .  /   .  | .  .  .
 .  /   .  | .  /   .  | .  .  .
 .  /   .  | .  /   .  | .  .  .

 r2c2=b=r2c5=c=r5c5=d=r5c2=a=r2c2,
 implies r2c2=ab, r2c5=bc, r5c5=cd and r5c2=ad



    a           c
 .  *   .  | .  *   .  | .  .  .
 *  ab  *  | *  bc  *  | *  *  *  b
 .  *   .  | .  *   .  | .  .  .
-----------+-----------+----------
 .  *   .  | .  *   .  | .  .  .
 *  ad  *  | *  cd  *  | *  *  *  d
 .  *   .  | .  *   .  | .  .  .
-----------+-----------+----------
 .  *   .  | .  *   .  | .  .  .
 .  *   .  | .  *   .  | .  .  .
 .  *   .  | .  *   .  | .  .  .

 r2c2-b-r2c5-c-r5c5-d-r5c2-a-r2c2,
 implies r2c1346789<>b, r1346789c5<>c, r5c1346789<>d and r1346789c2<>a

[Mike Barker]

Ron, you are right that the statement is broad, but there are lots of parallels. Both X-cycles and Y-cycles are types of nice loops. X-cycles use strong links which consist of two of the same digit which are the only two occurrances in a row, column or box. Y-cycles use strong links which consist of two different digits which are the only two candidates in a cell (I believe this is Myth's AIC arguement). X-cycles propagate with weak links with the same label as the strong link (Havard's strong link approach). Y-cycles propagate with a weak link with the same label as one of the bivalue candidates. In both cases, if the cycle is continuous (by Jeff's definition) candidates equal to the weak link labels can be eliminated from cells sharing a unit with the weak links. For discontinuous cycles, if the start and end vertices could have links with the same label going into and out of them (this is trivial for X-cycles), then the candidate of the label can be eliminated from cells which see both vertices. So they are not equal, but there is a reasonable equivalence between the two. Thanks for keeping me honest .

[claudiarabia]

Hi, it is nice to have instigated such a nice discussion here. As for me I referred to the continuous bi-directional cycles like the three kinds, Nicolas Juillerat shows in the Sudoku-Explainer.

As Ron said before, a continuous x-cycle is based upon one Number who formes strong links in some regions and the regions are all connected by these strong links (only two digits of one Number in one region). Every simple X-Wing, every minimal Sword- or Jellyfish is also a bi-directional x-cycle. The only difference between the non-fishy and the fishy x-cycles is, that in the fishy x-cycles there are columns and rows only, who shape the cycle, whereas in the other x-cycles boxes play a role too. The trick is that if you go round the cycle only after every second circle digit may follow a potential elimination. Otherwise there are not enough strong links holding the cycle together

Code: Select all

. . . |. . . |. . .
. # x |. . . |. . .
. x . |x . . |. . .
--------------------
. . . |. . . |. . .
. . . |. . . |. . .
. . x |# . . |x . .
--------------------
. . . |x . . |. x .
. . . |. . . |x # .
. . . |. . . |. . .

A non-fishy bi-directional-x-cycle
x= cycle-cells
#= possible eliminations.

Code: Select all

. . . |. . . |. . .
. x . |. . . |. x .
. . . |. . . |. . .
--------------------
. x . |x . . |. . .
. # . |# . . |. . .
. . . |. . x |. x .
--------------------
. . . |x . x |. # .
. . . |. . . |. . .
. . . |. . . |. . .

A minimal Jellyfish with possible eliminations (#). Here too you see that the eliminations occure only after every second cycle-digit. No wonder because the Jellyfish consist of rows, so that the eliminations are surely to find in the crossing regions, i.e. in the columns.

[gsf]

tarek, the question was to everyone, but I was only expecting a response from you, Mike or gsf.

tarek, you're on the right trail ... but with bivalue cells, the answer can't possibly be limited to one digit.

I coded X/Y cycles based on different definitions for strong/weak link/edge
I laid it out in the writeup of up the math behind my X&Y cycle algorithm
but the title was probably too esoteric for anyone to make a connection to cycles (my fault)
in the note there are four edge types { 0 1 2 3 }, 0 carrying no information, but present
to form a closed algebra on edge combinations

in that model pure X cycles are formed from type { 1 3 } edges and pure Y cycles are formed from type { 2 3 } edges
the neat thing is that edges can be combined and that combinations of pure X edges
can form a Y edge, and vice versa

the new insight for me is that along with tri-cycles mentioned in the note, 4-cycles can also
provide coloring information (outlined in claudia's example) -- I've yet to write that up

[claudiarabia]

To answer Rons question, an x-cycle is never identical with an y-cycle. The bi-directional y-cycle consists, as said before of cells with two digits inside only. A difference to the x-cycle is also, that an Y-Cycle may have an odd number of cycle-cells, while an x-cycle must have an even number of cells. An elimination occurs only outside the cycle. You don't minimize the numbers within the cycle cells.

Code: Select all

.  .  . | -3 .  .  |.  .  .
.  .  . | .  .  .  |.  .  .
.  12 . | 13 .  -1 |.  .  .
----------------------------
.  .  . | .  .  .  |.  .  .
.  .  . | .  .  .  |.  .  .
.  .  . | 34 .  .  |.  .  .
----------------------------
.  28 . | .  -8 .  |.  83 .
.  .  . | 14 .  .  |13 -3 .
.  .  . | .  .  .  |.  .  .

Every time, when after the two turns of the cycle two cycle-digits of the same kind share one region, non-cycle digits of the same kind can be eliminated in the respective region.

For example the neighboring cycle cells r3c4 and r6c4 contain the digit 3. The 3 must appear in every turn either in r3c4 or in the turn of the opposite direction in r6c4. For there are only these two possibilities left for the digit three in this cycle-region (column 4) we can eliminate all the other occurances of the digit 3 in column 4 outside the cycle.




Resumee of the bi-directional cycle in the sudoku below:
.

Code: Select all

 *-------------------------------------------------------------------*
 | 5      269    2679    | 4      #28     1    |#3678  3679   679    |
 | 149    8      1679    | 3579   37     *35-9 | 467    2      45679 |
 | #249   *49-2    3     | 579    #28      6   | 478    4579   1     |
 |-----------------------+---------------------+---------------------|
 | 7      126    126     | 138    5      238   | 9      1346   46    |
 | 8      1569   4       |*17-39  *7-3   #39   |#136    *156-3  2    |
 | #129    3     *159-2  | 6      4      #29   | 17     8      57    |
 |-----------------------+---------------------+---------------------|
 | 149    149    8       | 2      6      7     | 5      149    3     |
 | 3      7      259     | 58     1      458   | 246    469    469   |
 | 6      1245   125     | 35     9      345   | 1247   147    8     |
 *-------------------------------------------------------------------*

Code: Select all

.  .  .  .  28 .  38 .  .
.  .  .  .  .  .  .  .  .
2  .  .  .  2  .  .  .  .
.  .  .  .  .  .  .  .  .
.  .  .  .  .  39 3  .  .
2  .  .  .  .  29 .  .  .
.  .  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .  .


When I now come back to the original bi-directional cycle in the Sudoku above, I can resume that it has well elements of an X-cycle (the digit 2 in th left side of the cycle) as well as elements of the y-cycle (pair of 28 in r13c5) as well as cells with more then the digits who form the cycle (r15c7). So we see here a highly complex cycle with a combination of 3 different cycle-styles, with 8 participating cells and four kinds of digits. Thats why Nicolas Juillerat subsumated it under the type cycle with the highest heterogenicity composition, the "simple" bi-directional cycle. To discover such a cycle you really have to spot the sudoku very neatly.