Nice loops for elementary level players - the x-cycle

Advanced methods and approaches for solving Sudoku puzzles

Postby Pep » Mon Jan 09, 2006 10:54 am

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

Postby Carcul » Mon Jan 09, 2006 11:22 am

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

Postby Jeff » Mon Jan 09, 2006 11:22 am

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.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Mon Jan 09, 2006 12:03 pm

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

Postby Jeff » Mon Jan 09, 2006 6:15 pm

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

Postby Jeff » Sat Jan 14, 2006 6:07 am

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

Conjugate link - replaced by link with strong inference
Unconditional link - replaced by link with weak inference

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

Postby Jeff » Tue Jan 31, 2006 7:38 am

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

Image
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby vidarino » Tue Jan 31, 2006 12:40 pm

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

Postby ronk » Tue Jan 31, 2006 12:56 pm

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

Postby Jeff » Tue Jan 31, 2006 2:23 pm

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

Image

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

Postby Carcul » Wed Feb 01, 2006 6:04 pm

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

Postby Jeff » Wed Feb 01, 2006 6:38 pm

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

Postby Carcul » Wed Feb 01, 2006 6:51 pm

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

Postby ronk » Sat Mar 04, 2006 4:36 pm

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

Postby aeb » Sun Mar 05, 2006 10:13 pm

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

Return to Advanced solving techniques