Continuous (coloring) chains i.e. bi-directional(x)cycles

Advanced methods and approaches for solving Sudoku puzzles

Postby Mike Barker » Sun Apr 22, 2007 1:41 pm

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.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Re: bi-directional cycles

Postby re'born » Sun Apr 22, 2007 1:57 pm

ronk wrote:
rep'nA wrote: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.

ronk wrote: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.

ronk wrote:
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.
re'born
 
Posts: 551
Joined: 31 May 2007

Re: bi-directional cycles

Postby claudiarabia » Sun Apr 22, 2007 2:29 pm

claudiarabia"][
Let me at first give you a very simple example of the bi-directional cycle as Nicolas Juillerat define it. In the puzzle above the cycle involves not only 8 cells but 4 different numbers too. That justifys the rating of 7,3 in ER.

Here the simple example of a bi-directional cycle with the minimum number of 4 cells in which 2 numbers form the cycle in their special constellation. Our cycle numbers, the 1 and the 3 must be without other numbers in the r3c7 and r7c3 so that the cycle can work.


Code: Select all
.  .  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .  .
.  1x . -1  .  . 13  .  .
.  .  .  .  .  .  .  .  .
.  .  .  .  .  . -3  .  .
.  .  .  .  .  .  .  .  .
.  13 .  .  .  . 3x  .  .
.  .  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .  .


You move at first from r3c2 in clockwise direction and secondly from the same position counterclockwise. The numbers 1 and 3 are occuring only as I wrote in the respective columns and rows. In every direction you have only one defined way to go. The two ways in each direction are slung together and they form the cycle with the same cells everytime. It is not important which numbers are in addition in the cells r3c2 or r7c7. These additional numbers are the x. There are only eliminations outside of the cycle-cells, never inside. If you consider the X-Wing a simple bi-directional x-cycle, you know what I mean. There are also bi-directional cycles which involve boxes but here we have only 2 rows and 2 columns where there are strong links of 1 and 3 combined together in this cycle. Our aim is to eliminate the 1 in r3c4 and the 6 in r5c7.
1. If you start in r3c2 placing the Nr 1 inside. If you go clockwise, the 1 in r3c2 deletes the 1 in r3c7 and the 1 in r3c4 too. Because there is left a 3 in r3c7 only, we place the 3 here and this 3 eliminates the 3 in r5c7 and r7c7. Because there are only two 3s in r7, the eliminated 3 in r7c7 confirmes the 3 in r7c2. The 3 here eliminates the 1 and the 1 occures again in our starting cell r3c2. End first round.
2. If you start again in r3c2 assuming there is no 1 there going counterclockwise you see that the 1 has to be placed now in r7c2. The 1 there eliminates the 3 there and by this elimination the 3 in r7c7 is confirmed by this confirmation the 3 in r5c7 is eliminated again. By placement of the 3 in r7c7 the 3 in r3c7 is also eliminated and the 1 appears to be left alone and this 1 in r3c7 confirms our starting position of no 1 in r3c2 and eliminates in the second turn the 1 in r3c4. The cycle is closed in both directions and the eleminations of 1 in r3c4 and 6 in r5c7 are valid and final.

quote="gsf"][quote="claudiarabia wrote:
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.
Last edited by claudiarabia on Sun Apr 22, 2007 11:22 am, edited 5 times in total.
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby ronk » Sun Apr 22, 2007 2:46 pm

Mike Barker wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Sun Apr 22, 2007 5:25 pm

ronk wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Sun Apr 22, 2007 7:01 pm

ronk wrote:
Mike Barker wrote: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:D

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ronk » Sun Apr 22, 2007 7:17 pm

When is an X-cycle "identical" to a Y-cycle:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Sun Apr 22, 2007 7:35 pm

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
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ronk » Sun Apr 22, 2007 7:49 pm

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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Sun Apr 22, 2007 8:28 pm

ronk wrote: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:D )

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ronk » Sun Apr 22, 2007 8:49 pm

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
Last edited by ronk on Sun Apr 22, 2007 8:43 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Sun Apr 22, 2007 9:07 pm

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:) .
Mike Barker
 
Posts: 458
Joined: 22 January 2006

All the possible x-cycles

Postby claudiarabia » Sun Apr 22, 2007 9:46 pm

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.
Last edited by claudiarabia on Sun Apr 22, 2007 5:50 pm, edited 2 times in total.
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby gsf » Sun Apr 22, 2007 9:47 pm

ronk wrote: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
Last edited by gsf on Sun Apr 22, 2007 6:33 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

bi-directional Y-cycle - "simple" bi-directional c

Postby claudiarabia » Sun Apr 22, 2007 10:19 pm

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.
claudiarabia
 
Posts: 288
Joined: 14 May 2006

PreviousNext

Return to Advanced solving techniques