Domino Loops (SK Loops & Beyond)

Advanced methods and approaches for solving Sudoku puzzles

Re: Domino Loops (SK Loops & Beyond)

Postby logel » Thu Dec 15, 2016 7:51 pm

Somehow related to this topic I present an interesting observation about this puzzle containing an sk-loop.
Code: Select all
2.......6.5..8..1...4...9...7.3.1......82.......7.5.3...9...4...8..1..5.6.......2;10;tax;tarek-ultra-0203

The loop eliminates 13r5c2,1r6c2,37r2c6,37r8c6,8r4c8,7r5c8.
My aim was to test a new analysis tool that finds elimination patterns for a specific candidate. It creates sets of bases ( cells, rows, cols, boxes ) that are non-reducible. It works in an unbiased manner as it uses no predefined Sudoku methods. The above puzzle was used as test case with the candidate 1r5c2 and produced surprising results.
David P Bird wrote:.
2. Domino Loop Definition
Domino Loops consist entirely of arguments for the digits that can occupy a loop of cell pairs.
The patterns can also be expressed as XSudo rank 0 structures or as multi-sector locked sets which allows them to be formulated in a large variety of ways
SK Loops, discovered by Stephen Kurzhals, were the first form of domino loop to be identified.

The sk-loop written in domino terminology:
(69=37)R2C13 - (37=42)R2C78 - (42=78)R13C8 - (78=69)R79C8 -
(69=37)R8C79 - (37=42)R8C13 - (42=13)R79C2 - (13=69)R13C2 - loop
We have 8 pairs of cells and consecutive pairs are double linked and ends connected. To explain the patterns I found, the lo0p is re-written in this form:
{R2C13} - 37R2 - {R2C78} - 42B3 - {R13C8} - 78C8 - {R79C8} - 69B9 -
{R8C79} - 37R8 - {R8C13} - 42B7 - R79C2 - 13C2 - R13C2 - 69B1 - loop
Pattern example found:
{R13C2} - 9R1,6B1 - {9B2,6R2} - R2C46 - {24B2} - 4R1,2R3 - {24C8} - R45C8 -
{6C8,9B6} - 6R7,9C9 - {6B7,9R8} - R8C46 - {2B7,4R8} - 2R7,4B7 - {R79C2} - 13C2 - loop
another without any cells:
{69R2} - R2C46 - {24R2} - 24B3 - {24C8} - R45C8 - {6B6,9C8} - 6C7,9R9 -
{6R8,9B8} - R8C46 - {24R8} - 2C3,4B7 - {4C2,2B4} - R56C2 - {9B4,6C2} - 9C1,6B1 - loop
and many more ...
All these loops are on a certain abstraction level of the same structural kind as sk-loops, whatever name you like to assign them. The construction elements are pairs of bases that are double linked to another pair. In place of cells there is any base type possible. The above notation tries to point this out. OK. Why do I think this is interesting?
1) The sheer number. There are >1000 or more. Very surprising.
2) All elimination patterns found have at least 16 bases and those with 16 are all of 16-matrix type (16 links containing 16 non-overlapping bases) (rank-0 size 16 in your terms) and all eliminate the same 9 candidates.
3) The are even more 17-matrix or 18-matrix ... ( > 10000 ) partially with more eliminations.
4) It seems that the sk-loop (domino loop) is a special case of a much larger class of elimination patterns.
5) All this points to a hidden symmetry property, but I have no idea to get nearer to the mystery.
6) There are other 16-matrix patterns (same elimination set) with a more complex structure but all contain some double linked pairs.

Two double linked pairs consist of four bases diminished by two links. So the remaining candidates at both ends contain together two solution candidates. This property is retained when chaining double linked pairs. The two closing links assure a rank-0.
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Domino Loops (SK Loops & Beyond)

Postby David P Bird » Thu Dec 15, 2016 9:28 pm

Hi Logel,
SK Loops are interesting to analyse and I hope you are enjoying them.

I am using a categorising method based on how many sides of the loop contain all four of the base digits as givens in the loop boxes which determines other properties of the pattern.
The options are 0, 2, and 4 with your example being a SK-Loop-4
Notice that in r28c46 the base digits are a locked quad and present a UR threat
Other locked quads are in r56c2,r45c8 and r5c2568
Can you prove that each pair in the loop notation must contain a single truth?
If so, what are the requirements regarding the placement of any givens in these non-pivot boxes for different categories for this to apply in other cases?

It's something that I set out to explore recently but I haven't been able to spend enough time on so far.

DPB
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Domino Loops (SK Loops & Beyond)

Postby logel » Sun Dec 18, 2016 6:31 pm

Hi David
David P Bird wrote:Hi Logel,
SK Loops are interesting to analyse and I hope you are enjoying them.

After a long break I restart Sudoku activities with fresh ideas. I enjoy it.
David P Bird wrote:Notice that in r28c46 the base digits are a locked quad and present a UR threat
Other locked quads are in r56c2,r45c8 and r5c2568

I don't really understand what you mean by "threat".
David P Bird wrote:Can you prove that each pair in the loop notation must contain a single truth?

Ops. I had been not precise enough in the last sentence of the post. Both ends of double linked pairs contain together at least two truth. So with a closed loop its exactly two truth, obvious, nothing to prove. The loop pattern does not force the truth on different sides of the pair. So nothing to write home about.

I the meantime I leaned that v-loops (virus-loops) had been already discussed. These patterns match what I presented in my post. But there is still more. I picked two examples of patterns that do not seem to fit to those pattern definition, but are fairly similar. Two examples: tarek-ultra-0203_21.png and tarek-ultra-0203_23.png in case you or someone else is interested.
BKR
User avatar
logel
 
Posts: 55
Joined: 29 April 2012
Location: Germany

Re: Domino Loops (SK Loops & Beyond)

Postby David P Bird » Mon Dec 19, 2016 11:44 am

Hi Logel,
You and I are looking at these loops from different angles, you as a mathematician to explore all the ways the truth and links sets can be composed, and me as a solver looking to find the simplest sets which can be repeated for the biggest range of puzzles.

Taking the example puzzle you posted
2.......6.5..8..1...4...9...7.3.1......82.......7.5.3...9...4...8..1..5.6.......2 tarek-ultra-0203
Code: Select all
            c2 13                                         c8 78   
      *----------------------*-----------------------*----------------------*
      | <2>    139    1378   | 1459   34579  3479    | 3578   478    <6>    | b1 69
r2 37 | 379    <5>    367    | 2469   <8>    2469-37 | 237    <1>    347    |
      | 1378   136    <4>    | 1256   3567   2367    | <9>    278    3578   | b3 24
      *----------------------*-----------------------*----------------------*
      | 4589   <7>    2568   | <3>    469    <1>     | 2568   2469-8 4589   |
      | 13459  469-13 1356   | <8>    <2>    469     | 1567   469-7  14579  |
      | 1489   2469-1 1268   | <7>    469    <5>     | 1268   <3>    1489   |
      *----------------------*-----------------------*----------------------*
      | 1357   123    <9>    | 256    3567   23678   | <4>    678    1378   | b7 24
r8 37 | 347    <8>    237    | 2469   <1>    2469-37 | 367    <5>    379    |
      | <6>    134    1357   | 459    34579  34789   | 1378   789    <2>    | b9 69
      *----------------------*-----------------------*----------------------*

SK Loop: (69=37)r2c13 - (37=24)r2c79 - (24=78)r13c8 - (78=69)r79c8 -
(69=37)r8c79 - (37=24)r8c13 - (24=13)r79c2 - (13=69)r13c2 - Loop

Using the linking digits in the SK loop in each house this can be expressed as a Multi-Sector Locked Set:

MS-NS: 16 digits, 16 cell covers (37)r2, (37)r8, (13)c2, (78)c8, (69)b1, (24)b3, (24)b7, (69)b9
Eliminations 9 digits in 6 cells 37r2c6, 8r4c8, 13r5c2, 7r5c8, 1r6c2, 37r8c6
(469)NakedTriple:r5c268 => r5c19 <> 49, r5c37 <> 16

Using XSudo setting all 16 cells as truth (strong) sets should work.

This can be extended by adding one more cover set for r5
MS-NS: 19 digits, 19 cell covers (37)r2, (469)r5, (37)r8, (13)c2, (78)c8, (69)b1, (24)b3, (24)b7, (69)b9,
Eliminations 12 digits in 8 cells 37r2c6, 8r4c8, 49r5c1, 6r5c3, 6r5c7, 49r5c9, 1r6c2, 37r8c6,
(469)HiddenTriple:r5c268 => r5c2 <> 13, r5c8 <> 7

In Xsudo add cells r5c268

However for us solvers this does not shorten the solution as there is still a locked set to use in a following step.

So although you have discovered further truth and link sets to make the same eliminations the basic SK loop is still there, and that's the easiest one to look for.

When I talk about the pairs in the loop holding a single truth, in the SK loop (69=37)r2c13 (69) has one true digit and (37) has the other. This can only be proved in some cases. In other cases one of the pairs can have both the true digits, so there are three possibilities.

Regarding what I called the UR (Unique Rectangle) threat; the four cells r28c46 cannot reduce to holding just holding two digits such as (26) or (69) as then there would be two ways these cells could be filled and the puzzle would not be unique.

Only some of these puzzles can be solved without considering the multiple cases that are possible, and that's what I'm trying to improve.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Previous

Return to Advanced solving techniques