Traveling Pairs Type 2

Advanced methods and approaches for solving Sudoku puzzles

Traveling Pairs Type 2

Postby MrHamilton » Wed Feb 28, 2007 11:56 pm

I used that name (Traveling Pairs) already some time ago for certain properties of the sudoku grid. A technique was based on that known as Braid Analysis, worked out by David Bird.
But this is a bit of a new approach using pairs and loops. (Edit: Nothing new under the sun, these have been described before by RW as "entwined pairs" in his structure of the grid thread!)
Not, I should add, implication loops; but actual numerical loops that you can trace when you examine any solved grid.
The idea is, if you select any two adjacent digits, say 1 and 6, and draw a line from the 1 to the 6, proceed by right angle to the next available 1 and next 6 and so on, you sooner or later arrive back at the starting cell, perhaps right away!
Code: Select all
 *-----------*
 |...|...|...|
 |...|...|...|
 |...|...|...|
 |---+---+---|
 |..1|6..|...|
 |..6|1..|...|
 |...|...|...|
 |---+---+---|
 |...|...|...|
 |...|...|...|
 |...|...|...|
 *-----------*

This is the simplest case, a kind of pseudo-Unique Rectangle.
Note that this situation can occur in a solution, but only when one of the digits is a "given"--otherwise the puzzle would have 2 valid solutions.
Of course a similar-looking situation may occur when more than two units are involved.
Code: Select all
 *-----------*
 |...|...|...|
 |...|...|...|
 |...|...|...|
 |---+---+---|
 |..1|...|6..|
 |...|...|...|
 |...|...|...|
 |---+---+---|
 |..6|...|1..|
 |...|...|...|
 |...|...|...|
 *-----------*

This is quite legal, NOT a UR situation.
Digits needn't be adjacent to form a loop--but every adjacent digit-pair does form one.

In more complex cases, you reach the starting cell after a long journey all or part-way around the grid.
Code: Select all
 *-----------*
 |1.6|...|...|
 |...|.1.|.6.|
 |...|6..|1..|
 |---+---+---|
 |..1|...|6..|
 |...|.6.|..1|
 |6..|..1|...|
 |---+---+---|
 |.6.|...|.1.|
 |.1.|..6|...|
 |...|1..|..6|
 *-----------*

Every 1 and every 6 in a puzzle can be linked up as part of a loop; and loops can vary in length. This can be easily verified.

Now, that may be fun with crayons for you, but what use is that in solving a puzzle?
It depends. Consider Ruud's Daily Nightmare for 2/25/07 Sunday:
Code: Select all
 
  *-----------*
 |..2|3..|...|
 |..6|58.|..9|
 |38.|..2|..4|
 |---+---+---|
 |61.|...|.7.|
 |.2.|..3|...|
 |..4|.7.|.12|
 |---+---+---|
 |...|...|4..|
 |...|6.5|..8|
 |.61|..8|.97|
 *-----------*

after basic eliminations:
Code: Select all
 *-----------*
 |..2|3..|.8.|
 |..6|58.|..9|
 |38.|..2|..4|
 |---+---+---|
 |61.|...|.7.|
 |.2.|..3|.4.|
 |..4|.7.|.12|
 |---+---+---|
 |...|...|4..|
 |...|6.5|..8|
 |.61|..8|.97|
 *-----------*

 
 *--------------------------------------------------------------------*
 | 14579  4579   2      | 3      469    14679  | 567    8      156    |
 | 147    47     6      | 5      8      147    | 23     23     9      |
 | 3      8      579    | 179    169    2      | 1567   56     4      |
 |----------------------+----------------------+----------------------|
 | 6      1      3589   | 2489   2459   49     | 3589   7      35     |
 | 5789   2      5789   | 189    1569   3      | 5689   4      56     |
 | 589    359    4      | 89     7      69     | 35689  1      2      |
 |----------------------+----------------------+----------------------|
 | 2589   59     3589   | 279    239    179    | 4      56     1356   |
 | 2479   3479   379    | 6      12349  5      | 123    23     8      |
 | 245    6      1      | 24     234    8      | 235    9      7      |
 *--------------------------------------------------------------------*


We note that r8c7 must be a 1 due to "type 1" UR. After this, Simple Sudoku gets us to this point:
Code: Select all
 
 *--------------------------------------------------------------------*
 | 4579   457    2      | 3      46     4679   | 567    8      1      |
 | 1      47     6      | 5      8      47     | 23     23     9      |
 | 3      8      579    | 19     16     2      | 67     56     4      |
 |----------------------+----------------------+----------------------|
 | 6      1      3589   | 24     245    49     | 389    7      35     |
 | 789    2      5789   | 189    156    3      | 689    4      56     |
 | 589    35     4      | 89     7      69     | 35689  1      2      |
 |----------------------+----------------------+----------------------|
 | 28     9      358    | 7      23     1      | 4      56     356    |
 | 247    347    37     | 6      9      5      | 1      23     8      |
 | 25     6      1      | 24     234    8      | 235    9      7      |
 *--------------------------------------------------------------------*

Observe the ones and sixes in the left stack, they form a complete loop.
r2c1--r2c3--r9c3--r9c2--r4c2--r4c1--r2c1(home).
Now the question becomes, what sort of one-six loops are in the other two stacks?
It becomes evident that a single racetrack-type path using all the ones and sixes does not exist, so smaller loops are present.
Since r6c8 is a given, perhaps it's part of loop r6c8--r7c8--r7c6--r6c6?
Sure enough, that's the backdoor to this puzzle...
r7c8=6, r6c6=6, and Simple Sudoku can take it from there.
Last edited by MrHamilton on Thu Mar 01, 2007 1:44 pm, edited 1 time in total.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Re: Traveling Pairs Type 2

Postby udosuk » Thu Mar 01, 2007 2:52 am

MrHamilton wrote:It becomes evident that a single racetrack-type path using all the ones and sixes does not exist, so smaller loops are present.

I don't find it evident at all... You can do some trial & error to see that, but other than I don't think anyone can just spot this "fact" out with a few glances...

MrHamilton wrote:Since r6c8 is a given, perhaps it's part of loop r6c8--r7c8--r7c6--r6c6?
Sure enough, that's the backdoor to this puzzle...
r7c8=6, r6c6=6, and Simple Sudoku can take it from there.

Looks like guessing to me... It can also be part of the loop r6c8--r3c8--r3c5--r5c5--r5c4--r8c4--r8c7--r6c7... What made you decide it should be the shorter loop?
Last edited by udosuk on Wed Feb 28, 2007 10:53 pm, edited 1 time in total.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby coloin » Thu Mar 01, 2007 2:52 am

Indeed - what you are describing is the variations of 2 clue unavoidable sets in a grid.

Researched by RW in the structures thread

Every "set" of 18 clues with 2 clue values conforms to a finite number of templates patterns.

As you state it can have 1 set envolving all 18 clues - termed fully entwinned - or your 18 clue racetrack.

At most there can be 4 sets of 2-clue unavoidable sets in a template - three U-4s and one U-6.

There has to be a given clue in each of these sets to ensure a unique soluion to the puzzle.

Your puzzle grid solution has one U-6 and one U-12 envolving the 1/6 clues
Code: Select all
+---+---+---+
|952|3.4|78.|
|.4.|587|239|
|387|9.2|.54|
+---+---+---+
|..8|249|375|
|729|.53|84.|
|534|87.|9.2|
+---+---+---+
|895|72.|4.3|
|473|.95|.28|
|2..|438|597|
+---+---+---+ 4 solutions or perms

Code: Select all
+---+---+---+
|...|.6.|..1|
|1.6|...|...|
|...|.1.|6..|
+---+---+---+
|61.|...|...|
|...|1..|..6|
|...|..6|.1.|
+---+---+---+
|...|..1|.6.|
|...|6..|1..|
|.61|...|...|
+---+---+---+
{21,23,41,42,92,93,} in B1B4B7  [U-6 =A]
{15,19,35,37,54,59,66,68,76,78,84,87,} in B2B3B5B6B8B9 [U-12=B]

ABB
ABB
ABB


I think there is a UR at r3c4,r3c5,r5c4,r5c5 in your scheme [EDIT No -this is incorrect] [as is {66,68,76,78} - this is over 4 boxes - not a u-4 therefor not a UR situation !]

MrHamilton wrote:Now the question becomes, what sort of one-six loops are in the other two stacks?

It would be possible to work out all the possible "ways" to insert the 1/6 clues.......but I counted 12..... with
Code: Select all
A**
A**
A**  pattern


It might be demonstable that it cant be
Code: Select all
ABC
ABC
ADD

ABC
ABC
ACC


C
Last edited by coloin on Tue Mar 06, 2007 8:47 pm, edited 1 time in total.
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby MrHamilton » Thu Mar 01, 2007 3:42 am

Well I did say it "becomes evident," not that it was obvious to any child:D
udosuk wrote:
MrHamilton wrote:It becomes evident that a single racetrack-type path using all the ones and sixes does not exist, so smaller loops are present.

I don't find it evident at all... You can do some trial & error to see that, but other than I don't think anyone can just spot this "fact" out with a few glances...

MrHamilton wrote:Since r6c8 is a given, perhaps it's part of loop r6c8--r7c8--r7c6--r6c6?
Sure enough, that's the backdoor to this puzzle...
r7c8=6, r6c6=6, and Simple Sudoku can take it from there.

Looks like guessing to me... It can also be part of the loop r6c8--r3c8--r3c5--r5c5--r5c4--r8c4--r8c7--r6c7... What made you decide it should be the shorter loop?


1. If any 1-6 loop is complete, as the one in the left stack is, you can rule out other 1-6 loops connected to it. As for easily seeing what works, I admit this takes practice.
2. I "guessed" and found the backdoor. (By backdoor I mean cells that crack the puzzle, from the start and/or when you finally find them.) My guess was not based on airy nothing, but on my recent experiences that these very situations, a short loop with two digits, when one or more is a given, do tend to hide a backdoor. I'm not saying this technique is for easy puzzles; but there is room for some exploration here.
That the UR is a structure, or that a loop is a structure, or that that there are only so many of these structures possible in sudoku, is rather off the point. "There has to be a given clue in each of these sets to ensure a unique soluion to the puzzle. " No, not if they are in 4 units...surely?
In any case, the method gives me a plan, a limited number of hypotheses to test, and has a high success rate at finding backdoors. What more can one ask.
Last edited by MrHamilton on Thu Mar 01, 2007 1:48 pm, edited 1 time in total.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Postby StrmCkr » Thu Mar 01, 2007 8:50 am

Well I did say it "becomes evident," not that it was obvious to any child


myself and many others on here may find that remark as degrading/derogatory and undermining our intergatey. i would choose to reword that to better suit your resolve.

now.
even
when you first start looking at the patterns of 1/6 on the left hands side

the first step you will run into leads to a forked path of closing the loop as short or making it longer around the board, if you choose the longer loop you then hit another fork, then another.

the point here is the "choice" how did u make it? "a guess".

there is no simple "seeing" the path you have to guess which path to take then follow it looking for the contradiction, then chooseing the opposit fork if it hits an error. (thats 12 paths to check!)

after checking all the path's (or simply color the pattern out and looking for overlapping 1/6's then back track to the start of that "fork" and try the other one)

you find out that there is only 1 valid path. (the shortest one)

look up gurth's semtrical placement to see how you can utilize parings to solve positions in this manner. (its more persice, and works on "emerald puzzles" aka semetrical puzzles.


further more
the stack on the left is not complete you have 2 choices to contiune the loop, or a third choice to close the loop

list with the @ postions are open loop spots
# = closes loop.

Code: Select all

 *--------------------------------------------------------------------*
 | 14579@  4579   2      | 3      469    14679  | 567    8      156    |
 | 147#    47     6      | 5      8      147@    | 23     23     9      |
 | 3      8      579    | 179    169    2      | 1567   56     4      |
 |----------------------+----------------------+----------------------|
 | 6      1      3589   | 2489   2459   49     | 3589   7      35     |
 | 5789   2      5789   | 189    1569   3      | 5689   4      56     |
 | 589    359    4      | 89     7      69     | 35689  1      2      |
 |----------------------+----------------------+----------------------|
 | 2589   59     3589   | 279    239    179    | 4      56     1356   |
 | 2479   3479   379    | 6      12349  5      | 123    23     8      |
 | 245    6      1      | 24     234    8      | 235    9      7      |
 *--------------------------------------------------------------------*
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Postby MrHamilton » Thu Mar 01, 2007 5:16 pm

StrmCkr wrote:
Well I did say it "becomes evident," not that it was obvious to any child


myself and many others on here may find that remark as degrading/derogatory and undermining our intergatey. i would choose to reword that to better suit your resolve.


No insult to you was made. No insult to the children of the world intended either. I even put a smiley after to indicate a humorous remark.
Do you prefer another wording?

StrmCkr wrote:now.
even
when you first start looking at the patterns of 1/6 on the left hands side

the first step you will run into leads to a forked path of closing the loop as short or making it longer around the board, if you choose the longer loop you then hit another fork, then another.

the point here is the "choice" how did u make it? "a guess".

there is no simple "seeing" the path you have to guess which path to take then follow it looking for the contradiction, then chooseing the opposit fork if it hits an error. (thats 12 paths to check!)

after checking all the path's (or simply color the pattern out and looking for overlapping 1/6's then back track to the start of that "fork" and try the other one)

you find out that there is only 1 valid path. (the shortest one)

look up gurth's semtrical placement to see how you can utilize parings to solve positions in this manner. (its more persice, and works on "emerald puzzles" aka semetrical puzzles.


further more
the stack on the left is not complete you have 2 choices to contiune the loop, or a third choice to close the loop

list with the @ postions are open loop spots
# = closes loop.

Code: Select all

 *--------------------------------------------------------------------*
 | 14579@  4579   2      | 3      469    14679  | 567    8      156    |
 | 147#    47     6      | 5      8      147@    | 23     23     9      |
 | 3      8      579    | 179    169    2      | 1567   56     4      |
 |----------------------+----------------------+----------------------|
 | 6      1      3589   | 2489   2459   49     | 3589   7      35     |
 | 5789   2      5789   | 189    1569   3      | 5689   4      56     |
 | 589    359    4      | 89     7      69     | 35689  1      2      |
 |----------------------+----------------------+----------------------|
 | 2589   59     3589   | 279    239    179    | 4      56     1356   |
 | 2479   3479   379    | 6      12349  5      | 123    23     8      |
 | 245    6      1      | 24     234    8      | 235    9      7      |
 *--------------------------------------------------------------------*


Well at the start of the puzzle yes, there are these 2 choices. However, I was talking about the diagram where choices had been narrowed by other methods and already have 1 and 6 solved in the left stack.
There are two things I want people to take away from this discussion: The recursive pattern exists, such that any 2 digits race around the grid like Pac-mans at right angles and return to the same spot, sooner or later.
The other point is that this fact has implications for what can go where.
I am not spelling out all the implications. It could for example be used as a classification system for grids, i.e. in one grid the 1/2 pair is in a long loop and 3/4 is in three short ones etc.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Postby StrmCkr » Thu Mar 01, 2007 9:22 pm

didnt seem humorous to me.

i read it as, (simplified wording)

if you cant see it then your a child.


edit {weird } my bad "any one else ever have ss not find a sword fish before? mine missed it 3 times and then i restared it and it found it.."

Code: Select all
 *-----------*
 |..2|3..|.8.|
 |..6|58.|..9|
 |38.|..2|..4|
 |---+---+---|
 |61.|...|.7.|
 |.2.|..3|.4.|
 |..4|.7.|.12|
 |---+---+---|
 |...|...|4..|
 |...|6.5|..8|
 |.61|..8|.97|
 *-----------*


 *-----------*
 |..2|3..|.81|
 |1.6|58.|..9|
 |38.|..2|..4|
 |---+---+---|
 |61.|...|.7.|
 |.2.|..3|.4.|
 |..4|.7.|.12|
 |---+---+---|
 |.9.|7.1|4..|
 |...|695|1.8|
 |.61|..8|.97|
 *-----------*

 
 *--------------------------------------------------------------------*
 | 4579   457    2      | 3      46     4679@   | 567@    8      1      |
 | 1      47     6      | 5      8      47     | 23     23     9      |
 | 3      8      579    | 19     16     2      | 67@     56     4      |
 |----------------------+----------------------+----------------------|
 | 6      1      3589   | 24     245    49     | 389    7      35     |
 | 789    2      5789   | 189    156    3      | 689@    4      56@     |
 | 589    35     4      | 89     7      69@     | 35689@  1      2      |
 |----------------------+----------------------+----------------------|
 | 28     9      358    | 7      23     1      | 4      56@     356@    |
 | 247    347    37     | 6      9      5      | 1      23     8      |
 | 25     6      1      | 24     234    8      | 235    9      7      |
 *--------------------------------------------------------------------*


all the @'s are locations where the 6 could go an still line up and loop with the 1 either open or closed.

as there still can be anothe short track,

so how do u not "guess" where the track ends?
and where it starts?
Last edited by StrmCkr on Thu Mar 01, 2007 5:39 pm, edited 2 times in total.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Postby re'born » Thu Mar 01, 2007 9:32 pm

StrmCkr wrote:didnt seem humorous to me.

i read it as, (simplified wording)

if you cant see it then your a child.


pls explain the ur you find

We note that r8c7 must be a 1 due to "type 1" UR. After this, Simple Sudoku gets us to this point


i do not see any ur type 1 lining up with that cell.

how did u elliminate the 1 and 7 from r2c7? leaving a ur type 1

after basic techniques that puzzle looks like this

using simple sudoku program hitting f11 untill it stops = all basics are covered.

Code: Select all
 *-----------*
 |..2|3..|...|
 |..6|58.|..9|
 |38.|..2|..4|
 |---+---+---|
 |61.|...|.7.|
 |.2.|..3|...|
 |..4|.7.|.12|
 |---+---+---|
 |...|...|4..|
 |...|6.5|..8|
 |.61|..8|.97|
 *-----------*

 
 *--------------------------------------------------------------------*
 | 14579  4579   2      | 3      1469   14679  | 15678  568    156    |
 | 147    47     6      | 5      8      147    | 1237   23     9      |
 | 3      8      579    | 179    169    2      | 1567   56     4      |
 |----------------------+----------------------+----------------------|
 | 6      1      3589   | 2489   2459   49     | 3589   7      35     |
 | 5789   2      5789   | 1489   14569  3      | 5689   4568   56     |
 | 589    359    4      | 89     7      69     | 35689  1      2      |
 |----------------------+----------------------+----------------------|
 | 25789  3579   35789  | 1279   1239   179    | 4      2356   1356   |
 | 2479   3479   379    | 6      12349  5      | 123    23     8      |
 | 245    6      1      | 24     234    8      | 235    9      7      |
 *--------------------------------------------------------------------*


My SS agrees with MrHamilton's grid. SS uses

1)Hidden Single
2)Hidden Single
3)Naked Pair
4)Locked Candidates (1)
5)Naked Triple r2c126[147] eliminates 1 and 7 from r2c7
6)Swordfish
7)Multiple Colors

taking us to,

Code: Select all
 *--------------------------------------------------------------------*
 | 14579  4579   2      | 3      469    14679  | 567    8      156    |
 | 147    47     6      | 5      8      147    | 23     23     9      |
 | 3      8      579    | 179    169    2      | 1567   56     4      |
 |----------------------+----------------------+----------------------|
 | 6      1      3589   | 2489   2459   49     | 3589   7      35     |
 | 5789   2      5789   | 189    1569   3      | 5689   4      56     |
 | 589    359    4      | 89     7      69     | 35689  1      2      |
 |----------------------+----------------------+----------------------|
 | 2589   59     3589   | 279    239    179    | 4      56     1356   |
 | 2479   3479   379    | 6      12349  5      | 123    23     8      |
 | 245    6      1      | 24     234    8      | 235    9      7      |
 *--------------------------------------------------------------------*
re'born
 
Posts: 551
Joined: 31 May 2007

Postby StrmCkr » Thu Mar 01, 2007 9:41 pm

ok thats strange... i ran ss a bunch of times and each time it missed the

swordfish
and
5)Naked Triple r2c126[147] eliminates 1 and 7 from r2c7


then i restrated it and it found it and brought the puzzel down to that same grid....no clue on that one.

alright discard that. (edited post)

still leaves the other question open to an aswer
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Postby coloin » Wed Mar 07, 2007 12:39 am

I also made a few errors [now edited] in my post...but in reply to the original thread I think there may be some milage in answering the question
MrHamilton wrote:what sort of one-six loops are in the other two stack?


The partially solved puzzle can be shown to have a [1-6] U-6 in the first stack.
Code: Select all
*--------------------------------------------------------------------*
 | 4579   457    2      | 3      46     4679   | 567    8      1      |
 | 1      47     6      | 5      8      47     | 23     23     9      |
 | 3      8      579    | 19     16     2      | 67     56     4      |
 |----------------------+----------------------+----------------------|
 | 6      1      3589   | 24     245    49     | 389    7      35     |
 | 789    2      5789   | 189    156    3      | 689    4      56     |
 | 589    35     4      | 89     7      69     | 35689  1      2      |
 |----------------------+----------------------+----------------------|
 | 28     9      358    | 7      23     1      | 4      56     356    |
 | 247    347    37     | 6      9      5      | 1      23     8      |
 | 25     6      1      | 24     234    8      | 235    9      7      |
 *--------------------------------------------------------------------*


Bearing in mind there is a unique solution to this puzzle there will only be one way to fill in the rest of the 1-6 template in the other two stacks.
In this case like this
Code: Select all
ABB
ABB       
ABB

+---+---+---+
|...|.6.|..1|
|1.6|...|...|
|...|.1.|6..|
+---+---+---+
|61.|...|...|
|...|1..|..6|
|...|..6|.1.|
+---+---+---+
|...|..1|.6.|
|...|6..|1..|
|.61|...|...|
+---+---+---+


This could be a useful solving technique if it is possible to show that there cannot be U-4s or U-6s in the 2nd and 3rd stacks. In which case it has to be a U-12.

Is this solving using a "templates" technique ?
C
coloin
 
Posts: 2502
Joined: 05 May 2005
Location: Devon

Postby MrHamilton » Sat Mar 10, 2007 5:12 pm

Templates, or a sort of double nishio?
I think the difference is, that I am attempting to follow the right-angle alternation of the groups of 2 numbers. In the puzzle, there's the group of six on the left, a group of 4 (r6c6, r6c8, r7c6, r7c8) and a group of 8 in the remaining placements.
I found the group of four by knowing that either it, or another small group, was present, and then trying to find a refutation, which in this case doesn't happen.
I think that how the patterns relate to the given numbers is critical; you can't have unique rectangles, but you can form a rectangle using one or more givens.
And when you find one, it's often a backdoor.
MrHamilton
 
Posts: 42
Joined: 14 March 2006


Return to Advanced solving techniques