The New Sudoku Players' Forum

[tso]

How common is the shortest possible "nice loop" aka non-repetitive path in various randomly generated puzzles? Is it worthy of being singled out in the same way the xy-wing is? (The xy-wing is merely the shortest possible xy-type forcing chain.)

(This came up in the solution to a puzzle posted here.)

Examples of 4 cell non-repetitve path (shortest possible in standard Sudoku):

Given this:

Code: Select all

[ab][  ][  ]|[bc]
[  ][  ][  ]|[  ]
[  ][  ][  ]|[  ]
------------+----
[ad][  ][  ]|[cd]


... then

'a' can be eliminated from elsewhere in column 1
'b' can be eliminated from elsewhere in row 1
'c' can be eliminated from elsewhere in column 4
'd' can be eliminated from elsewhere in row 4



Given this:

Code: Select all

[ab][  ][  ]|[bc][  ]
[  ][ad][  ]|[  ][cd]
[  ][  ][  ]|[  ][  ]
------------+--------


... then

'a' can be eliminated from elsewhere in box 1
'b' can be eliminated from elsewhere in row 1
'c' can be eliminated from elsewhere in box 2
'd' can be eliminated from elsewhere in row 2


Three cell non-repetitive path is possible in Sudoku that include main diagonals (aka Sudoku X):

Given this:

Code: Select all

[ab][  ][  ]|[  ]
[  ][  ][  ]|[  ]
[  ][  ][  ]|[  ]
------------+----
[ac][  ][  ]|[bc]


... then

'a' can be eliminated from elsewhere in column 1
'b' can be eliminated from elsewhere in the diagonal slanting down to the right
'c' can be eliminated from elsewhere in row 4

I would assume that this would be much more common since it requires only three cells to line up.

[emm]

Thanks tso - I was looking at Max's xy chains in 'Also Stuck' and this exactly answers the questions I had.

[Myth Jellies]

I would say use all nice loops of any length, and just think of a naked pair as a nice loop of length 2. (Or doesn't that qualify? I am not sure what you mean by non-repetitive path.)

[tso]

I would say use all nice loops of any length, and just think of a naked pair as a nice loop of length 2. (Or doesn't that qualify? I am not sure what you mean by non-repetitive path.)

Yes, a naked pair, triple, quad, etc -- as long as each cell has exactly two candidates -- is a degenerate non-repetitive path. A naked triple of two candidate cells is also a degenerate xy-wing.

The xy-wing may be more common than longer chains (depending on the method of puzzle generation). It is certainly easier to find than longer chains.

The 4-cell non-repetitive path would be the easiest to spot -- especially for those in the camp that considers looking for a forcing chain as distastefull T&E. I'm just wondering how common they are.

By non-repetitive path (and I should have been more specific and said xy-type or 'bi-value' non-repetitive path), I mean a loop of 2-candidate cells in which each pair of consecutive cells shares a candidate. The edge between each pair of cells is labeled with the candidate in common. No two consecutive labels are the same.

For example:

Code: Select all

[12]---------2--------[23]
  |                    |
  1                    |
  |                    |
[16]---6---[56]        3
             |         |
             5         |
             |         |
           [45]---4---[34]


This example would eliminate 3's from the rest of the last column, 4's from the bottom row, etc.


XY-wings and standard xy-type forcing chains are REPETITVE paths that have exactly two consecutive labels the same, for example:

Code: Select all

[12]---------2--------[23]
  |                    |
  2                    |
  |                    |
[26]---6---[56]        3
             |         |
             5         |
             |         |
           [45]---4---[34]


The consecutive 2's eliminate the 2 from the top left cell. [EDIT: The next sentence in this paragraph was false and has been deleted.]



Digressing, I realize that the question is not really definitively answerable without making many other arbitrary assumptions. If one solves even the simplest of puzzles by filling in all the pencil marks to start -- one may find lots of pairs, triples, quads, x-wings, etc -- even though the puzzle might need only singles to complete. In fact, you can squeeze more interest out of a very easy puzzle this way - ignore singles until you cannot make any progress another way.

[Jeff]

xy-wing for a repetitive xy-chain of length 4.

How about xy-ring for an non-repetitive xy-chain of length 4.

[tso]

Sounds good. Let's how common it is. Since I posted, I haven't come across another useful xy-ring -- but I'm only searching by hand.

[Max Beran]

Referring to tso's of 9:30 on Monday, what's the rationale for calling a path that you can keep going round and round ad nauseam "non-repetitive" and the other which blocks you at the start "repetitive"? Seems counterintuitive use of lingo to me.

Max Beran.

[tso]

Referring to tso's of 9:30 on Monday, what's the rationale for calling a path that you can keep going round and round ad nauseam "non-repetitive" and the other which blocks you at the start "repetitive"? Seems counterintuitive use of lingo to me.

Max Beran.

The terms are from from David Eppstein's paper, Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku.


These four bi-value cells by definition form a non-repetitive path because the labeled edges do not repeat as you read them around the loop:

Code: Select all

[12]---2---[23]
 |           |
 1           3
 |           |
[14]---4---[34]

1-2-3-4-1-2-3-4, etc.



These four bi-value cells by definition form a repetitive path because the labeled edges DO repeat exactly ONCE as you read them around the loop:

Code: Select all

[12]---2---[23]
 |           |
 2           3
 |           |
[24]---4---[34]

2,2,3,4,2,2,3,4 etc.




These four bi-value cells do not form a useful path and do not allow a deduction, as the labeled edges repeat more than once as you read them around the loop:

Code: Select all

[12]---2---[23]
 |           |
 2           3
 |           |
[23]---3---[34]

2,2,3,3,2,2,3,3 etc.

[Jeff]

In the description of bilocation/bivalue plot which is an extension to Eppstein's paper, I have changed the terms repetitive and non-repetitive to discontinuous and continuous respectively. The changes were not because of similar concern raised by Max's, but to cover a deduction case for combination chain where the nice loop is non-repetitive but the deduction can only be made at a chain node similar to a repetitive path (refer Theorem 5).