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

Advanced methods and approaches for solving Sudoku puzzles

Re: bi-directional Y-cycle - "simple" bi-direction

Postby ronk » Mon Apr 23, 2007 12:48 am

claudiarabia wrote:To answer Rons question, an x-cycle is never identical with an y-cycle.

Agreed, I was erroneously referring to a pure cycle of conjugate links as an X-cycle. My post with the illustrations has been corrected.:(
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Mon Apr 23, 2007 1:21 am

claudiarabia wrote:You don't minimize the numbers within the cycle cells

That's not necessarily true when you progress to full nice loops. For example in your example:
Code: Select all
r1c5=8=r1c7=3=r5c7-3-r5c6-9-r6c6-2-r6c1=2=r3c1-2-r3c5=2=r1c5
+-------------------+-------------------+----------------------+
|   5   269   2679  |     4   28*    1  | 38-67*  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-93  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  |
+-------------------+-------------------+----------------------+

Because the loop is continuous, the adjacent colors: r1c5=8=r1c7=3=r5c7 imply that r1c7=38. (You can think of a weak link existing between the 3 and 8 in r1c7 so the other candidates in the cell can be eliminated). Eliminations can also occur in cells adjacent to the discontinuity in a discontinuous nice loop.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby tarek » Mon Apr 23, 2007 4:31 pm

ronk wrote:When is an X-cycle "identical" to a Y-cycle:?:

Ah.... so we have a broad defenition of the word "identical":D

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

Postby daj95376 » Mon Apr 23, 2007 4:42 pm

I don't understand the logic behind continuous nice loops, but they appear to start with the answer and then find a chain that returns to it. Also, by starting with the correct value, you don't have to worry about running into any ole nasty contradictory logic. Amazing!

Here's Mike Barker's loop with the starting premise included.

Code: Select all
2=r1c5=8=r1c7=3=r5c7-3-r5c6-9-r6c6-2-r6c1=2=r3c1-2-r3c5=2=r1c5
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Mon Apr 23, 2007 5:01 pm

daj95376 wrote:Also, by starting with the correct value, you don't have to worry about running into any ole nasty contradictory logic.
[...]
2=r1c5=8=r1c7=3=r5c7-3-r5c6-9-r6c6-2-r6c1=2=r3c1-2-r3c5=2=r1c5

Remember that nice loop expressions are meant to be read both left-to-right and right-to-left. For continous loops, if you start with the incorrect value, you still don't run into a contradiction.

=8=r1c5=2=r3c5-2-r3c1=2=r6c1-2-r6c6-9-r5c6-3-r5c7=3=r1c7=8=r1c5=2=
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Wed Apr 25, 2007 7:02 am

I posted a link to some algebraic insights into sudoku edge coloring 3x in this thread
rep'nA took the bait (thanks)
but nothing else
any kind of comment ( rubbish, been there done that, incomprehensible ) besides pin drop would be nice
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Wed Apr 25, 2007 10:11 am

gsf wrote:any kind of comment ( rubbish, been there done that, incomprehensible ) besides pin drop would be nice

:DSorry, math tends to make my eyes glaze over, but I'll give it a go anyway.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Wed Apr 25, 2007 2:17 pm

ronk wrote:
gsf wrote:any kind of comment ( rubbish, been there done that, incomprehensible ) besides pin drop would be nice

:DSorry, math tends to make my eyes glaze over, but I'll give it a go anyway.

scroll down to the pictures -- probably the best start for any paper
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby claudiarabia » Fri Apr 27, 2007 10:37 pm

Mike Barker wrote:
claudiarabia wrote:You don't minimize the numbers within the cycle cells

That's not necessarily true when you progress to full nice loops. For example in your example:
Code: Select all
r1c5=8=r1c7=3=r5c7-3-r5c6-9-r6c6-2-r6c1=2=r3c1-2-r3c5=2=r1c5
+-------------------+-------------------+----------------------+
|   5   269   2679  |     4   28*    1  | 38-67*  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-93  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  |
+-------------------+-------------------+----------------------+

Because the loop is continuous, the adjacent colors: r1c5=8=r1c7=3=r5c7 imply that r1c7=38. (You can think of a weak link existing between the 3 and 8 in r1c7 so the other candidates in the cell can be eliminated). Eliminations can also occur in cells adjacent to the discontinuity in a discontinuous nice loop.


True. My definition was lacking clarity. In some cells of a bi-directional cycle you can also eliminate numbers but only numbers who don't belong to the cycle itself and only in cells were you have two different numbers who form part of the cycle. In these cells the two cycle-relevant numbers stay while the other candidates in the cell can be removed. This is also the case in r5c6 or r6c6 in the example where you have the candidates 93 and 92 as cycle-relevant. These cells belong to the part of the cycle, which resembles the bi-directional Y-cycle, where you have only cycle-relevant candidates in the cycle cells, i.e. two candidates only.
On the other Hand in some cells of the cycle you have only one candidate, which is cycle-relevant as for instance 2 in r6c1 , r3c1 or the only-cycle-candidate 3 in r5c7. In these cells there is no possibility of such an elimination because these cells have the character of the part of a bi-directional x-cycle.
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby ronk » Sat Apr 28, 2007 12:10 am

claudiarabia wrote:On the other Hand in some cells of the cycle you have only one candidate, which is cycle-relevant as for instance 2 in r6c1 , r3c1 or the only-cycle-candidate 3 in r5c7. In these cells there is no possibility of such an elimination because these cells have the character of the part of a bi-directional x-cycle.

In other puzzles, an elimination can occur in those cells too. In the puzzle below, r9c1 is one cell of a conjugate pair, but r9c1<>8 is a valid elimination because ALS r9c78 is part of the continuous loop ("bi-directional cycle").

Code: Select all
Michael Mepham Unsolvable #13
...2.1.3.3...5...8....4...5.....8.7...4.3.1...9.5...2.9...8....6.......7.3.9.5...

After SSTS and r2c6<>6:

*4578  -45678 56789 | 2    *679   1     |-4679   3    *469
 3      12467 12679 |*67    5     *79   | 24679  1469  8 
 127    1267  12679 | 8     4     3     | 2679   169   5
--------------------+-------------------+-------------------
 125    1256  12356 | 14    29    8     | 4569   7     3469 
 2578   25678 4     |*67    3    *29    | 1      5689 *69 
 178    9     13678 | 5     16-7  467   | 468    2     346
--------------------+-------------------+-------------------
 9      12457 1257  | 134   8     67    | 3456   456   12 
 6      1458  158   | 134   12    24    | 345-89 45-89  7
*1247-8 3     127-8 | 9    *67    5     |*468   *468   12

Ignoring the details of the strong inference between r1c5 and r1c9 that uses an almost remote pair, we have

Continuous loop: r1c1=4=r9c1-4-{ALS:r9c78=4|8|6=r9c78}-6-r9c5-7-{derived ALS:r1c5=7|4=r1c9}-4-r1c1

This continuous loop converts all weak links to strong links for exclusions r1c27<>4 and r6c5<>7. It also locks digit 8 into the r9c78 ALS (in row 9 and box 9) for exclusions r9c13<>8 and r8c78<>8.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Wed May 02, 2007 4:14 am

thanks to claudia and the others for going over cycle/chain details
it exposed a flaw in my Y cycle code that only handled bivalue cells (and not bilocation candidates)
I reformulated the algorithm for degree-2 candidates (bivalue/bilocation) and it sped up 2X as a bonus
many puzzles that I had missed now fall to y-cycles and y-knots (Y contradiction chains)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

first results

Postby claudiarabia » Wed May 02, 2007 8:39 pm

gsf wrote:thanks to claudia and the others for going over cycle/chain details
it exposed a flaw in my Y cycle code that only handled bivalue cells (and not bilocation candidates)
I reformulated the algorithm for degree-2 candidates (bivalue/bilocation) and it sped up 2X as a bonus
many puzzles that I had missed now fall to y-cycles and y-knots (Y contradiction chains)


Whow! I'm honored that this discussion bears so much fruit. For me new horizons have opened too with these cycles. The most easy to discover are the ones with 4 cells only where 2numbers form the simple bi-directional cycle.

Here is another puzzle with the rare ER-rating of 7,0 from my ugly-but-fascinating-betty-collection.

Code: Select all
. 4 9 . . 2 5 . 3
. . 1 . 4 9 . . .
. . 2 3 . . 4 . .
. 9 . . . . . . .
. . 3 . . . 2 7 6
6 . 7 . . 5 . . .
. . 6 . . 1 . . .
. 3 . . . . 7 4 .
. 8 . . . . . 6 .


You can solve it with 3 xy-wings and one bi-directional cycle.
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby ravel » Wed May 02, 2007 9:41 pm

... or one contradiction chain:
Code: Select all
 *--------------------------------------------------------------------*
 | 78     4      9      | 1678   1678   2      | 5      18     3      |
 | 3      57     1      | 578    4      9      | 6      2      78     |
 | 578    6      2      | 3      1578   78     | 4      189    789    |
 |----------------------+----------------------+----------------------|
 | 24     9      8      | 267    267    467    | 13     35     15     |
 | 45     15     3      | 189    189    48     | 2      7      6      |
 | 6      12     7      | 12     3      5      | 89     89     4      |
 |----------------------+----------------------+----------------------|
 | 279    27     6      | 4      25789  1      | 389    35     2589   |
 | 129    3      5      | 2689   2689   68     | 7      4      1289   |
 | 1279   8      4      | 2579   2579   3      | 19     6      1259   |
 *--------------------------------------------------------------------*
r3c1=5 => r5c1=4 => r5c6=8 => r3c6=7 => r2c9=7 => r2c4=8 => r3c5=5
ravel
 
Posts: 998
Joined: 21 February 2006

Postby re'born » Thu May 03, 2007 12:23 am

ravel wrote:... or one contradiction chain:
Code: Select all
 *--------------------------------------------------------------------*
 | 78     4      9      | 1678   1678   2      | 5      18     3      |
 | 3      57     1      | 578    4      9      | 6      2      78     |
 | 578    6      2      | 3      1578   78     | 4      189    789    |
 |----------------------+----------------------+----------------------|
 | 24     9      8      | 267    267    467    | 13     35     15     |
 | 45     15     3      | 189    189    48     | 2      7      6      |
 | 6      12     7      | 12     3      5      | 89     89     4      |
 |----------------------+----------------------+----------------------|
 | 279    27     6      | 4      25789  1      | 389    35     2589   |
 | 129    3      5      | 2689   2689   68     | 7      4      1289   |
 | 1279   8      4      | 2579   2579   3      | 19     6      1259   |
 *--------------------------------------------------------------------*
r3c1=5 => r5c1=4 => r5c6=8 => r3c6=7 => r2c9=7 => r2c4=8 => r3c5=5


A slightly shorter version of this chain would be:

[r3c1]-5-[r5c1]-4-[r5c6]-8-[r3c6]-7-[r3c9]=7=[r2c9]-7-[r2c2]-5-[r3c1]

implying r3c1 <> 5.
re'born
 
Posts: 551
Joined: 31 May 2007

Re: first results

Postby re'born » Thu May 03, 2007 12:40 am

claudiarabia wrote:
Here is another puzzle with the rare ER-rating of 7,0 from my ugly-but-fascinating-betty-collection.

Code: Select all
. 4 9 . . 2 5 . 3
. . 1 . 4 9 . . .
. . 2 3 . . 4 . .
. 9 . . . . . . .
. . 3 . . . 2 7 6
6 . 7 . . 5 . . .
. . 6 . . 1 . . .
. 3 . . . . 7 4 .
. 8 . . . . . 6 .


You can solve it with 3 xy-wings and one bi-directional cycle.


Just to check whether I've figured this bi-directional cycle business out, is this what you had in mind:

Code: Select all
 *--------------------------------------------------------------------*
 | 78     4      9      | 1678-  1678-  2      | 5      18     3      |
 | 3      57     1      | 57(8)  4      9      | 6      2      (78)   |
 | 57-8   6      2      | 3      157-8- (78)   | 4      189    (7)89  |
 |----------------------+----------------------+----------------------|
 | 24     9      8      | 267    267    467    | 13     35     15     |
 | 45     15     3      | 189    189    48     | 2      7      6      |
 | 6      12     7      | 12     3      5      | 89     89     4      |
 |----------------------+----------------------+----------------------|
 | 279    27     6      | 4      25789  1      | 389    35     2589   |
 | 129    3      5      | 2689   2689   68     | 7      4      1289   |
 | 1279   8      4      | 2579   2579   3      | 19     6      1259   |
 *--------------------------------------------------------------------*


Eliminations : r1c45<>8, r3c1<>7, r3c5<>7,8
re'born
 
Posts: 551
Joined: 31 May 2007

PreviousNext

Return to Advanced solving techniques