Domino Loops (SK Loops & Beyond)

Advanced methods and approaches for solving Sudoku puzzles

OT

Postby eleven » Tue Nov 17, 2015 4:37 pm

David P Bird wrote:Feedback on this and any bludners or omissions I've made would be welcomed.

here you are :)
Last edited by eleven on Fri Nov 20, 2015 1:19 pm, edited 1 time in total.
eleven
 
Posts: 1447
Joined: 10 February 2008

Re: Domino Loops (SK Loops & Beyond)

Postby ronk » Tue Nov 17, 2015 5:42 pm

ronk wrote:Oops, I lost sight of H1521 being a "1/3 loop" rather than a "2/2 loop." I'll tweak my post tomorrow (and make an email generating post as well.)

David, before making a significant effort to write definitions, edit posts, etc., I'd like you to consider this.

(1) Continuous loops with almost-hidden sets (or aahs) through the "pivot cells" should be considered potential sk-loops. Such sk-loops are usually "2/2 loops" but may be something else.
(2) Continuous loops with almost-locked sets (or aals) in the four boxes containing the pivot cells, and in the same rows and columns as the pivot cells, should be considered potential v-loops. Such v-loops are usually "2/2 loops" but may be something else.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Domino Loops (SK Loops & Beyond)

Postby David P Bird » Wed Nov 18, 2015 9:05 am

Ronk, here are my thoughts having slept on this:

Every few months there has been a resurgence of debate about the ins and outs of SK loops, how to notate them and what to call them, and I found the most recent one very disturbing. I therefore went through this analysis in the hope that it would put a stop to this periodic bickering.

I now consider that domino loops are much better considered as patterns on a par with fish and multi-fish and it's a big mistake to try to use weak and strong links to analyse them which only causes confusion. I therefore think we should avoid any mention of hidden or naked pairs in describing them as these terms have specific meanings in AICs.

Stephen Kurzhals was brilliant at developing solving ideas, but he was the first to admit that he had problems in converting these ideas into words, so we shouldn't feel bound to use his 'hidden pair loop' terminology.

On naming the different loop varieties I'm fairly relaxed - a rose by any other name etc. How the types I've identified are bundled together isn't that important because they are all rare and in the case of Vloops we only have one example. I'd therefore be happy to call loops with the 4 boxes containing diagonals of givens SK loops and anything else a Vloop regardless of whether the linking digits are split 2/2 or 1/3.

The Dloop term can then be relegated to being used as a crutch to help describe the common proof for both SK loops and Vloops.

On notating the loops my preference would be not to use weak and strong link symbols as they are liable to be misinterpreted. I would prefer something like (29/68)r13c2 - (68/15)r79c2 - (15/46)r8c13 - but this isn't a major issue.

Finally the reason I take the spaces out of Vloop and Dloop is to overcome the inadequacies of the forum's search engine.
.
David P Bird
2010 Supporter
 
Posts: 940
Joined: 16 September 2008
Location: Middle England

Re: Domino Loops (SK Loops & Beyond)

Postby ronk » Fri Nov 20, 2015 3:55 am

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. When they occur the grid can be rearranged so that all the cells pairs resemble dominos with pivot cells containing givens.
Code: Select all
 *--------*--------*--------*
 | * H H  | . . .  | G G *  | 
 | A . .  | . . .  | . . F  |  Lettered cell pairs all 
 | A . .  | . . .  | . . F  |  contain four candidates. 
 *--------*--------*--------*
 | . . .  | . . .  | . . .  |  * = Pivot Givens
 | . . .  | . . .  | . . .  |
 | . . .  | . . .  | . . .  |
 *--------*--------*--------*
 | B . .  | . . .  | . . E  |
 | B . .  | . . .  | . . E  |
 | * C C  | . . .  | D D *  |
 *--------*--------*--------*

I recommend that you rearrange the cells shown so that the exemplar is compatible with a minimal symmetric pattern, a pattern to which SKloop, Vloop, & "Dloop" puzzles can be normalized.
Code: Select all
 *--------*--------*--------*
 | . A .  | . . .  | . F .  | 
 | H * H  | . . .  | G * G  |  Lettered cell pairs all
 | . A .  | . . .  | . F .  |  contain four candidates. 
 *--------*--------*--------*
 | . . .  | . . .  | . . .  |  * = Pivot Givens
 | . . .  | . . .  | . . .  |
 | . . .  | . . .  | . . .  |
 *--------*--------*--------*
 | . B .  | . . .  | . E .  |
 | C * C  | . . .  | D * D  |
 | . B .  | . . .  | . E .  |
 *--------*--------*--------*

GP-H1521 has perfect diagonal symmetry (d) and the Easter Monster is one cell short of perfect diagonal symmetry (d-1). See r4c5.
Code: Select all
..1.....2.3...4.5.6.....7.......5.3....47.....8.9.3.....7...1...4.8...9.2.......6  # Easter Monster morph
..1.....2.3...4.5.6.....7......49.3....86.....9.3.1.....8.....1.4.5...9.7.....6..  # GP-H1521 morph


 . . 1 | . . . | . . 2                . . 1 | . . . | . . 2
 . 3 . | . . 4 | . 5 .                . 3 . | . . 4 | . 5 .
 6 . . | . . . | 7 . .                6 . . | . . . | 7 . .
-------+-------+-------              -------+-------+-------
 . . . | . . 5 | . 3 .                . . . | . 4 9 | . 3 .
 . . . | 4 7 . | . . .                . . . | 8 6 . | . . .
 . 8 . | 9 . 3 | . . .                . 9 . | 3 . 1 | . . .
-------+-------+-------              -------+-------+-------
 . . 7 | . . . | 1 . .                . . 8 | . . . | . . 1
 . 4 . | 8 . . | . 9 .                . 4 . | 5 . . | . 9 .
 2 . . | . . . | . . 6                7 . . | . . . | 6 . .
# Easter Monster morph                # GP-H1521 morph
                               
The Truth/Link solutions from Allan Barker's XSUDO:                               
Easter Monster morph
     16 Truths = {28N1379 1379N28}
     16 Links = {89r2 35r8 59c2 48c8 16b37 27b19}
     13 Eliminations --> r45c2<>9, r2c5<>89, r8c5<>35, r1c7<>6, r1c1<>7, r3c9<>1, r3c3<>2, r5c2<>5, r5c8<>8, r6c8<>4

GP-H1521 morph
     16 Truths = {28N1379 1379N28}
     16 Links = {3r8 9r2 4c8 5c2 16b37 2b179 7b19 8b139}
     16 Eliminations --> r1c17<>8, r2c45<>9, r7c17<>2, r8c56<>3, r45c2<>5, r39c3<>2, r56c8<>4, r39c9<>8

Easter Monster has a "2/2 loop" and GP-H1521 has a "1/3 loop."

(Aside: I think I'll wait to post more after I see others chime in.) :-)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Domino Loops (SK Loops & Beyond)

Postby David P Bird » Fri Nov 20, 2015 8:35 pm

ronk wrote: I think I'll give this thread a rest, until after I see others chime in.

So be it, but that's a very unsatisfactory way to end a discussion. As the chance of others chiming in are slim at best, I'll have no clue as to where you accept what I say, where you remain to be convinced, and where we must agree to disagree.
.
David P Bird
2010 Supporter
 
Posts: 940
Joined: 16 September 2008
Location: Middle England

Re: Domino Loops (SK Loops & Beyond)

Postby Leren » Sat Nov 21, 2015 3:57 am

Hi David,

You are sounding a bit neglected, so I thought I'd participate in this thread and say what I think constitutes a full SK loop and what doesn't. I've attached an Excel file containing 3 sheets, the watchamacallit loop moves for three puzzles: Your classic SK Loop puzzle; Blue's puzzle (suitably rearranged so that the pivot boxes are 1, 3, 7 & 9); and Champagne's Virus loop (French) puzzle.

Here is a line version of Blue's rearranged puzzle : 2.......5.67....1...1.4.69......63....5.97......18.....782..1...1....98.3.......4

What distinguishes the SK loop puzzle from the other two is the existence, in addition to the 4 box Naked Pair loop, a Hidden Pair loop in the mini-lines connecting the 4 pivot cells (shown in purple in the first puzzle sheet). This is facilitated by the arrangement of the non-pivot cell givens in the 4 pivot boxes and 4 other givens, one in each of the mini-lines connecting the 4 pivot cells. The 2nd and 3rd puzzles don't have this extra arrangement so there is no Hidden Pair loop, but this does not prevent the identification of a Naked Pair loop in each puzzle.

What use is the Hidden Pair loop ? Well nothing directly, it does not provide for any extra direct eliminations, but when I coded SK loops about 3 years ago I took a careful look at the arrangement of the 4 Hidden Pair loop digits in the 8 Hidden Pair loop cells. Depending on which Hidden Pair loop digits were missing from which cells it is possible to derive some inferences that may be of use later on in the solution. As I said, I coded this up about 3 years ago, so I'd need a good look at my notes to understand them thoroughly if you are interested.

As I said, the identification of the Naked Pair loop and the Hidden Pair loop are independent, so my solver recognizes all three puzzles as having SK Loops.

In more up-to-date terminology I'd say something like Naked Pair loop + Hidden pair loop = SK Loop.

The overwhelming majority of puzzles with Naked pair loops also have a Hidden Pair loop - I gather that puzzles 2 and 3 are the only known exceptions. Why is that ? I have absolutely no idea why !

Leren
Attachments
Domino_Loop_Puzzles.xlsx
(42.02 KiB) Downloaded 55 times
Leren
 
Posts: 2730
Joined: 03 June 2012

Re: Domino Loops (SK Loops & Beyond)

Postby David P Bird » Sat Nov 21, 2015 1:32 pm

Hi Leren, welcome to the thread and thanks for your concern about my welfare and the spread sheets. I had a mental bet that if I said there was slim chance of others chiming in then it might prompt someone to prove me wrong!

If the 'hidden pair loop' has no use then in modern day parlance it's too much information – a distraction that will put off improving players from trying to understand the technique. To change that you would have to show there's an additional inference that's otherwise unavailable. In that case all you have to do is to define the term and give it a better name that doesn't conflict with the usual meaning of a hidden pair. And the same goes for 'naked pair loop'.

That said, it's been a disappointment to me that, without an accompanying Exocet, the derived inferences from the loop generally only come into play once a puzzle is essentially solved.

Regarding the rarity of some varieties; as I mentioned for VLoops, it's probable that most of the puzzles where they occur can be solved quite simply so they won't be picked up, and for Blue's puzzle it needs 4 boxes with 4 givens which won't be popular with puzzle composers.

I had two aims when I went through this exercise
1) To de-mystify SK Loops for manual players
2) To identify the different pattern varieties that have been found.
I then hoped it would prevent further spats on how the pattern works and what names should be used for it.

So please wear your manual solver's hat rather than your program writer's one when considering the approach I've taken.

David
.
David P Bird
2010 Supporter
 
Posts: 940
Joined: 16 September 2008
Location: Middle England

Re: Domino Loops (SK Loops & Beyond)

Postby eleven » Sat Nov 21, 2015 6:40 pm

David,

in my manual solving career i never tried to solve a puzzle with a SK or Domino loop completely.
So my interest in variations was relatively small.

A naked pair loop indeed is easy to spot, if you look for it (easier than JExocets, where there are more possibilities to check). And we know, that it is sufficient to find one, to be able to make all the (direct) eliminations. This only had to be proved once.

From this point of view i see no differences in the classic, close related and virus loop examples. And it seems that i am in line with Leren here.

Concerning the 1&3 loop, which was new for me, i simply see it as a 4 singles loop with (the same kind of) side steps.
Once you see the 3 digits trick, you have
3r56c4->8r7c56->6r89c7->7r4c89->3r56c4 or (if r56c4<>3)
7r4c56->6r56c7->8r7c89->3r89c4->7r4c56
No third possibility (both are false) as for the SK loop.
So i don't see much relation.

Or am i missing something ?
eleven
 
Posts: 1447
Joined: 10 February 2008

Re: Domino Loops (SK Loops & Beyond)

Postby David P Bird » Sat Nov 21, 2015 10:25 pm

Welcome to you too Eleven,

So now with you included, that's three people that are happy with the 'naked pair loop' term compared to my lone voice against it, so I must moderate my objections. (It seems I must just add it to my list of undesirable terms.) So all it wants now is someone to formalise it with a definition.

You wrote:A naked pair loop indeed is easy to spot, if you look for it.

That's right, but you must know what you are looking for which requires an explanation of the components to look for.

You wrote:Or am I missing something?

Frankly yes you are. I think you are oversimplifying the problems I have attempted to address; showing that there are still naming issues, demonstrating that these loops are not AICs, and providing a reference source for improving players. (The reference material available to them is full of unnecessary 0 rank XSudo grids and other complications which is enough to frighten anyone off.) What you dismiss as "seeing the three digit trick" has to be explained somewhere you know! :-)
.
David P Bird
2010 Supporter
 
Posts: 940
Joined: 16 September 2008
Location: Middle England

Re: Domino Loops (SK Loops & Beyond)

Postby eleven » Sun Nov 22, 2015 9:10 pm

So i will try to make these points clearer.

Probably it is best to show with an example, how i look for a naked pairs loop.

Some general properties:
The loop can only be in 4 boxes in a rectangle (in 2 bands and 2 stacks).
In each box there must be 2 pairs of disjunct cells in a minicolumn and a minirow resp., with 4 candidates. The pairs have at least 2 candidates in common.

Now look for one this grid:
Code: Select all
*----------------------*----------------------*----------------------*
| 45     25     <6>    | 1789-4 248    249    | <3>    2457   1789-2 |
| 34     <9>    <7>    | 168-4  2348   <5>    | 248    246    168-2  |
| <1>    <8>    2345   | 679-4  2349   23469  | 2457   24567  679-2  |
*----------------------*----------------------*----------------------*
| 6789-3 167-3  189-3  | <2*>   3489   349    | 478    347    <5*>   |
| 3589   235    23589  | 4589   <6>    <7>    | 24-8   <1>    238    |
| 3578   <4>    2358   | 58     35-8   <1>    | <6>    <9>    2378   |
*----------------------*----------------------*----------------------*
| <2>    356    49     | 49     <7>    <8>    | <1>    35-6   36     |
| 34567  3567   345    | 456    <1>    24-6   | <9>    <8>    2367   |
| 6789-5 167-5  189-5  | <3*>   259    269    | 257    2567   <4*>   |
*----------------------*----------------------*----------------------*

Forget box 1, no minicolumn pair with 4 candidates.
Box 2: Nothing in minicol 1, in minicol 2 try cells 25&79 - no, 28&46 no, 58&13 no, nothing in minicol 3.
So nothing in band 1.
Box 4: Nothing in the minicols.
So nothing in stack 1.
Box 5: minicol 1/cells 47 fit with cells 23 in minirow 1 (common digits 489). This gives a possiple loop start r4c56=48->r56c4=59.
Now continue with the next box - only box 8 left. Indeed in the same column we have a 4 candidates pair containing 59: r56c4=59->r78c4=46.
But now 46 leaves 3 candidates 259 in r9c67.
So try 49 in r4c56, leaving 58r56c4 - and 3 candidates in r78c4.
Last try 89r4c56 -> 45r56c4-> 69r78c4 -> 25r9c56 -> 67r9c78 -> 23r78c9 -> 78r56c9 -> 34r4c67 -> 89r4c56 loop


The "3 digits trick" is just my way to spot this special 5 digits ALS implication:
Code: Select all
  a a a  |  abcd  abcd  .
  . . .  |    .    .   xbcd
  . . .  |    .    .   xbcd


If you have an a in r1c123 only 3 digits are left for r1c45, 2 of them therefore cannot be in r23c6. Then x must be there. (ar1c123 -> xr23c6).
eleven
 
Posts: 1447
Joined: 10 February 2008

Re: Domino Loops (SK Loops & Beyond)

Postby David P Bird » Sun Nov 22, 2015 11:57 pm

Eleven, thank you for patiently giving your search method. It seems I read something into your post that wasn't intended.

As written, your method seems quite a long operation but with practice I'm sure you can do it quickly.

..6...3...97..5...18..........2....5....67.1..4...169.2...781......1.98....3....4 Blue 2011b
Code: Select all
       *-----------------------*-----------------------*-----------------------*
       | 45     25     <6>     | 1789-4 248    249     | <3>    2457   1789-2  | 
       | 34     <9>    <7>     | 168-4  2348   <5>     | 248    246    168-2   |
       | <1>    <8>    2345    | 679-4  2349   23469   | 2457   24567  679-2   |
       *-----------------------*-----------------------*-----------------------*
(34)r4 | 6789-3 167-3  189-3   | <2*>   3489   349     | 478    347    <5*>    |
       | 3589   235    23589   | 4589   <6>    <7>     | 24-8   <1>    238     | (89)b5
       | 3578   <4>    2358    | 58     35-8   <1>     | <6>    <9>    2378    | (78)b6
       *-----------------------*-----------------------*-----------------------*
       | <2>    356    49      | 49     <7>    <8>     | <1>    35-6   36      |
       | 34567  3567   345     | 456    <1>    24-6    | <9>    <8>    2367    | (69)b8
(25)r9 | 6789-5 167-5  189-5   | <3*>   259    269     | 257    2567   <4*>    | (67)b9
       *-----------------------*-----------------------*-----------------------*
                                 (45)c4                               (23)c9

My manual search method starts by looking for 4 potential pivot givens in four boxes that form a rectangle.
This quickly limits them to boxes 5689 where there are three possibilities.
I then gather the digits involved eg (168)r58c58 and check that none of them are givens in any of the other cells in these boxes.
In this case they all are and this also shows r67c67 won't work either, leaving (2345)r49c49 as the only possibility and this passes the test.
Now the linking digits in the boxes can't be members of [2345] and the linking digits in the rows and columns can't be members of [16789] (the other givens in these boxes) allowing me to check if a loop exists.
In this case the two digit sets are complementary but when they aren't and a digit or two is missing, it's fairly easy to see which set it/they should belong to.
.
David P Bird
2010 Supporter
 
Posts: 940
Joined: 16 September 2008
Location: Middle England

Re: Domino Loops (SK Loops & Beyond)

Postby eleven » Mon Nov 23, 2015 9:41 pm

Yes, this way is more elegant, clever and quicker than mine.

But i am not eager to try it out, it seems, that i tire of sudoku.
eleven
 
Posts: 1447
Joined: 10 February 2008

Re: Domino Loops (SK Loops & Beyond)

Postby ronk » Mon Nov 23, 2015 10:33 pm

David P Bird wrote:My manual search method starts by looking for 4 potential pivot givens in four boxes that form a rectangle.
This quickly limits them to boxes 5689 where there are three possibilities.
I then gather the digits involved eg (168)r58c58 and check that none of them are givens in any of the other cells in these boxes.

My search method is much the same. The primary difference is I scan all 32 cells of the rows and columns that include the pivot givens. I don't know if including the mini-lines of the side boxes (of the normalized pattern) is actually necessary.

But the main purpose of this post is to point out that the "blue 2011b" puzzle can be morphed to (p-1) symmetry. This means the morph is within one cell of having perfect (180-degree) pi-rotational symmetry. See r4c4.

Code: Select all
 . . 1 | . . . | 2 . 3
 . 4 . | . . . | . 5 .
 2 . 3 | . . 6 | . . 7
-------+-------+-------
 . . . | . 2 . | . . 4
 . . . | 1 . 3 | . . .
 8 . . | . 7 9 | . . .
-------+-------+-------
 1 . . | 5 . . | 9 . 2
 . 6 . | . . . | . 8 .
 9 . 2 | . . . | 7 . .    # blue 2011b morph

blue 2011b p-1 morph
     16 Truths = {28N1379 1379N28}
     16 Links = {68r2 45r8 58c2 46c8 1b39 3b79 7b17 9b13}
     16 Eliminations --> r2c456<>8, r8c456<>4, r456c2<>5, r456c8<>6, r1c1<>7, r3c7<>1, r7c3<>7, r9c9<>1

Additionally two features are unusual:
1) The mini-lines r2b2, c8b6, r8b8 and c2b4 are clueless.
2) The clues of b5 are exactly the same as the corner cells of the pivot boxes (r1379c1379).

blue, do you have a link to your original posting of this puzzle?
Last edited by ronk on Tue Nov 24, 2015 4:55 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Domino Loops (SK Loops & Beyond)

Postby David P Bird » Tue Nov 24, 2015 11:49 am

eleven wrote:Yes, this way is more elegant, clever and quicker than mine.

Closure! Thank you!

you wrote:But i am not eager to try it out, it seems, that i tire of sudoku.

You can't fool me – you're as addicted as the rest of us - you'll be back!
.
David P Bird
2010 Supporter
 
Posts: 940
Joined: 16 September 2008
Location: Middle England

Re: Domino Loops (SK Loops & Beyond)

Postby blue » Wed Nov 25, 2015 8:24 pm

ronk wrote:blue, do you have a link to your original posting of this puzzle?

I don't. From the date that David has for it, it must have been on the old Programmer's Forum.
blue
 
Posts: 572
Joined: 11 March 2013

PreviousNext

Return to Advanced solving techniques