## Nice loops for elementary level players - the x-cycle

Advanced methods and approaches for solving Sudoku puzzles
I merely wish to point out that these x-cycles (if I understand them correctly) are the same as X constraints in Glenn Fowler's paper http://www.research.att.com/~gsf/sudoku/.

I found them by a very different route by considering polygons, where the sides are units (r/c/b) and the vertices are the cells that lie at the intersections between adjacent sides. For example, if we have a polygon with an even number of sides, and alternate sides have a particular candidate only at the vertices, then that candidate can occur only at the vertices of the whole polygon. Therefore, in the other alternate sides it can be eliminated elsewhere than the vertices. The other x-cycles can be re-phrased appropriately too.

The result of this analysis is that we can extend the cycles to consider sets of cells shared by adjacent units in the x-cycle, rather than single cells.

Here is an example:
Code: Select all
`.5. .21 79. 27. ... .51 13. .57 .26 .67 1.. 582 5.2 87. 16. .81 265 9.7 ..5 .12 .7. 72. 5.. .19 .1. 796 2.5 with candidate list+----------------+----------------+----------------+ | 468  5    468  | 346  2    1    | 7    9    348  | | 2    7    69   | 69   348  348  | 34   5    1    | | 1    3    489  | 49   5    7    | 48   2    6    | +----------------+----------------+----------------+ | 349  6    7    | 1    34   349  | 5    8    2    | | 5    49   2    | 8    7    349  | 1    6    34   | | 34   8    1    | 2    6    5    | 9    34   7    | +----------------+----------------+----------------+ | 469  49   5    | 34   1    2    | 3468 7    348  | | 7    2    346  | 5    348  348  | 346  1    9    | | 48   1    348  | 7    9    6    | 2    34   5    | +----------------+----------------+----------------+`

Look at candidate 4, and treat {r9c1,r9c3} as the intersection between r9 and b7 see what you can find.

Cycles exist for candidate 3 as well.

Pep.
Pep

Posts: 12
Joined: 29 November 2005

Interestingly, there is an AUR in the grid posted by Pep that, if properly used, immediatly solves the puzzle.

Carcul
Carcul

Posts: 724
Joined: 04 November 2005

Pep wrote:I merely wish to point out that these x-cycles (if I understand them correctly) are the same as X constraints in Glenn Fowler's paper.

Thanks Pep for pointing that out. I just hope that we could restrict our discussions to x-cycles under this thread.
Jeff

Posts: 708
Joined: 01 August 2005

Pep wrote:Look at candidate 4, and treat {r9c1,r9c3} as the intersection between r9 and b7 see what you can find.

I think your example is covered by Jeff's Nice loops for intermediate level players - Grouped x-cycle thread.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Pep wrote:Look at candidate 4, and treat {r9c1,r9c3} as the intersection between r9 and b7 see what you can find.

Hi Pep, thanks again. I have posted this grouped x-cycle on 4s here.
Jeff

Posts: 708
Joined: 01 August 2005

### First post edited

Please be advised that I have edited the description of x-cycle with the following changes:

These changes are made to remove the term 'unconditional' which could have double meanings. I hope this doesn't cause much inconvenience to you.
Jeff

Posts: 708
Joined: 01 August 2005

2 x-cycles of length 7.

x-cycle in red: [r3c4]-5-[r2c5]=5=[r2c7]-5-[r3c9]=5=[r7c9]-5-[r9c7]=5=[r9c4]-5-[r3c4] => r3c4<>5

x-cycle in black: [r8c5]-5-[r2c5]=5=[r2c7]-5-[r3c9]=5=[r7c9]-5-[r9c7]=5=[r9c4]-5-[r8c5] => r8c5<>5

Jeff

Posts: 708
Joined: 01 August 2005

Hmm, I never saw the point in treating these discontinuous cycles / loops as closed.

If you disregard the discontinuity and instead think of the cycle as an open-ended piece of string, you can eliminate all candidates that exist in the intersecting area of the two endpoints (minus the endpoints themselves, of course).

I've had X-cycles that yielded a large number of eliminations, and it would be rather tedious to regard them as a big set of cycles which differ only at one node.

I'm not saying my way is "better", of course, but for some reason I'm finding it easier to use. Perhaps because there's one less node to look for.

The same idea works for Y-cycles (XY-chains) as well, by the way.

Vidar
Last edited by vidarino on Tue Jan 31, 2006 9:00 am, edited 1 time in total.
vidarino

Posts: 295
Joined: 02 January 2006

Jeff wrote:2 x-cycles of length 7.

x-cycle in red: [r3c4]-5-[r2c5]=5=[r2c7]-5-[r3c9]=5=[r7c9]-5-[r9c7]=5=[r9c4]-5-[r3c4] => r3c4<>5

x-cycle in black: [r8c5]-5-[r2c5]=5=[r2c7]-5-[r3c9]=5=[r7c9]-5-[r9c7]=5=[r9c4]-5-[r8c5] => r8c5<>5

I see those as x-cycles of length 5 (turbot fish):

[r3c4]-5-[r2c5]=5=[r2c7]-5-[r9c7]=5=[r9c4]-5-[r3c4] => r3c4<>5

[r8c5]-5-[r2c5]=5=[r2c7]-5-[r9c7]=5=[r9c4]-5-[r8c5] => r8c5<>5

Can you give another example of length 7?
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:Can you give another example of length 7?

Hi Ronk, Here is another example of an x-cycle of length 7:

[r3c3]-5-[r3c6]=5=[r7c6]-5-[r7c9]=5=[r6c9]-5-[r4c8]=5=[r4c3]-5-[r3c3] => r3c3<>5

BTW, this is no ordinary grid. You might like to solve it from the beginning:

Code: Select all
` *-----------* |1.8|4..|5..| |...|..7|..2| |...|...|...| |---+---+---| |.2.|.9.|..7| |.6.|.5.|.89| |9..|.1.|.4.| |---+---+---| |...|...|...| |5..|6..|...| |..4|..3|9.8| *-----------*`
Jeff

Posts: 708
Joined: 01 August 2005

Hi Jeff.

Jeff wrote:BTW, this is no ordinary grid.

This is indeed a very hard puzzle. I have two questions:

1. What is the source of this puzzle?
2. Just by curiosity, how many steps does your solution have?

Regards, Carcul
Carcul

Posts: 724
Joined: 04 November 2005

Carcul wrote:1. What is the source of this puzzle?
2. Just by curiosity, how many steps does your solution have?

Hi Carcul, I knew you'll be interested.

1. Refer here for the source.

2. This is one of the hard puzzles that I haven't started solving. I'll be happy to hear how you go with it.
Jeff

Posts: 708
Joined: 01 August 2005

Hi Jeff.

Jeff wrote:I knew you'll be interested.

Very smart.

Jeff wrote:This is one of the hard puzzles that I haven't started solving. I'll be happy to hear how you go with it.

I have already solved this puzzle, but I don't like my solution because the last three steps of it are very complex. However, using more simple arguments, I have noted that the Turbot Chain above is not necessary, because we can prove that r6c2<>5,7. I will try to spot a simpler solution.

Regards, Carcul
Carcul

Posts: 724
Joined: 04 November 2005

A relatively rare "pure" discontinuous x-cycle of length 9.

Puzzle #41 of the top1465
Code: Select all
` 4.3|5..|.2. ...|.16|... 7..|...|... ---+---+--- ...|.89|5.. ...|3..|8.. 2..|...|... ---+---+--- ...|4..|.7. .9.|...|6.. .1.|...|...`

With basic techniques can be advanced to:
Code: Select all
` 4     68     3     | 5    9     78     | 17    2      1678 589   258    2589  | 278  1     6      | 347   3458   34578 7     2568   1     | 28   34    34     | 9     568    568--------------------+-------------------+-------------------   13    347    6     | 17   8     9      | 5     134    2 159   457    59    | 3    2457  12457  | 8     1469   1467 2     34578  589   | 6    457   1457   | 1347  1349   1347--------------------+-------------------+-------------------   3568  2358   258   | 4    356   1358   | 13    7      9 358   9      47    | 178  2357  123578 | 6     13458  13458 3568  1      47    | 9    3567  3578   | 2     3458   3458`

With 1s color map:
Code: Select all
` . . . | . . . | A . a . . . | . . . | . . . . . . | . . . | . . . - - - + - - - + - - - C . . | D . . | . 1 . c . . | . . 1 | . 1 1 . . . | . . 1 | 1 1 1 - - - + - - - + - - - . . . | . . B | b . . . . . | d . 1 | . 1 1 . . . | . . . | . . .`

For nice loop expression:
[r5c9]-1-[r5c1]=1=[r4c1]-1-[r4c4]=1=[r8c4]-1-[r7c6]=1=[r7c7]-1-[r1c7]=1=[r1c9]-1-[r5c9]
... and elimination r5c9<>1

Ron

P.S "Pure x-cycle of length 9" above means no shorter x-cycle may be found within the one illustrated. Has anyone seen a "pure" x-cycle of greater length?
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Jeff wrote:BTW, this is no ordinary grid. You might like to solve it from the beginning:
Code: Select all
` *-----------* |1.8|4..|5..| |...|..7|..2| |...|...|...| |---+---+---| |.2.|.9.|..7| |.6.|.5.|.89| |9..|.1.|.4.| |---+---+---| |...|...|...| |5..|6..|...| |..4|..3|9.8| *-----------*`

I have not seen a solution posted here or here.
My solution is not terribly complicated. The most interesting step occurs at this point:
Code: Select all
`       .     379       .       .     236      29       .    3679      36      36    3459    3569    1589     368       .   13468    1369       .    2367   34579   23679    1589     368    1589  134678   13679    1346     348       .     135      38       .     468     136    1356       .     347       .     137     237       .      24     123       .       .       .    3578     357    2378       .      26     236       .     356   23678   13789   23679    1259    2478   12589   13467  123567   13456       .   13789    2379       .    2478    1289    1347    1237     134     267      17       .     125      27       .       .   12567       .`

where (1,6)2 is ruled out as follows:
If (1,6)2 then (456,6)468 and (789,5)2478, but four digits cannot be in three cells.
aeb

Posts: 83
Joined: 29 January 2006

PreviousNext