Traveling Pairs and Triples

Advanced methods and approaches for solving Sudoku puzzles

Re: Traveling Pairs and Triples

Postby MrHamilton » Wed Mar 15, 2006 4:50 pm

Jeff wrote:
MrHamilton wrote:To be blue, 6 would have to travel with either 2 or 9, but it doesn't: therefore 6 is green and 5 is blue.

Hi Mr Hamilton, The above statement advised that 6 cannot travel with 2. But, I found that 6 can travel with 2 in the following cases. Could you explain what I have done wrong?
Code: Select all
*-------*         *-------*
| . 6 . |         | . 6 . |
| . 2 . |         | . 2 . |
| . . . |         | . . . |
|-------|         |-------|
| . . . |         | 6 . . |
| 2 . . |         | 2 . . |
| 6 . . |         | . . . |
|-------|         |-------|
| . . 6 |         | . . 6 |
| . . . |         | . . . |
| . . 2 |         | . . 2 |
*-------*         *-------*


Yes, thank you Jeff, you would have blue 2, 5, and 6 in C3R7-8-9 and one of them has to be green by the rule. Which one?
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Re: Traveling Pairs and Triples

Postby Jeff » Wed Mar 15, 2006 5:03 pm

MrHamilton wrote:
MrHamilton wrote:To be blue, 6 would have to travel with either 2 or 9, but it doesn't: therefore 6 is green and 5 is blue.

Yes, thank you Jeff, you would have blue 2, 5, and 6 in C3R7-8-9 and one of them has to be green by the rule. Which one?

Mr Hamilton, If you ask me, here is my answer:

Case 1
6 can travel with 2, therefore 5 is green, or

Case 2
5 can travel with 2, therefore 6 is green, or

Case 3
5 can travel with 9, therefore 6 is green.

Therefore 5 can be green too.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Traveling Pairs and Triples

Postby MrHamilton » Wed Mar 15, 2006 9:08 pm

Jeff wrote:
MrHamilton wrote:To be blue, 6 would have to travel with either 2 or 9, but it doesn't: therefore 6 is green and 5 is blue.

Hi Mr Hamilton, The above statement advised that 6 cannot travel with 2. But, I found that 6 can travel with 2 in the following cases. Could you explain what I have done wrong?
Code: Select all
*-------*         *-------*
| . 6 . |         | . 6 . |
| . 2 . |         | . 2 . |
| . . . |         | . . . |
|-------|         |-------|
| . . . |         | 6 . . |
| 2 . . |         | 2 . . |
| 6 . . |         | . . . |
|-------|         |-------|
| . . 6 |         | . . 6 |
| . . . |         | . . . |
| . . 2 |         | . . 2 |
*-------*         *-------*


Okay.
Let me take your second case first. If C1R4 =6 and C1R5 = 2 then C1R6 =1.
But this is impossible since it removes both 1 and 2 candidates from C2 middle box, forcing C2R5 and C2R6 both to be 5.:D
Your first case scenario is more difficult to disprove but involves there being triples in Rows 4-6. I will prepare an answer to this later when I get home.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Re: Traveling Pairs and Triples

Postby aeb » Thu Mar 16, 2006 2:10 am

MrHamilton wrote:Postulate: Each of the six sets of three vertically or horizontally adjacent boxes has a hidden pattern consisting of 3 sets of corresponding ("traveling") pairs or triples.

Yes. A 3x3 grid has 6 transversals:
Code: Select all
*..  .*.  ..*  *..  .*.  ..*
.*.  ..*  *..  ..*  *..  .*.
..*  *..  .*.  .*.  ..*  *..

Each digit must follow one of these patterns. These six patterns fall into two classes: "down right" (the first three) and "down left" (the last three), and patterns from the same class are disjoint, from different classes intersect. You need 9 patterns that together cover each position three times, and the three members of a class occur equally often. Thus, either 9 digits go right, or 6 go right and 3 left, or 3 right and 6 left, or 9 left. The cases of 9 are your traveling triples. The cases of 6 are your traveling pairs. So, yes, they are forced to occur.

Now this is true, and amusing, but is it useful? The information obtained from considering the above is precisely what usually is called "line-box intersection", not a very deep technique. So, I do not think you are going to solve any difficult puzzles using only this. (But in my experience, recognizing 'traveling triples' speeds up the solving process a little.)
aeb
 
Posts: 83
Joined: 29 January 2006

Re: Traveling Pairs and Triples

Postby MrHamilton » Thu Mar 16, 2006 2:26 pm

aeb wrote:
MrHamilton wrote:Postulate: Each of the six sets of three vertically or horizontally adjacent boxes has a hidden pattern consisting of 3 sets of corresponding ("traveling") pairs or triples.

Yes. A 3x3 grid has 6 transversals:
Code: Select all
*..  .*.  ..*  *..  .*.  ..*
.*.  ..*  *..  ..*  *..  .*.
..*  *..  .*.  .*.  ..*  *..

Each digit must follow one of these patterns. These six patterns fall into two classes: "down right" (the first three) and "down left" (the last three), and patterns from the same class are disjoint, from different classes intersect. You need 9 patterns that together cover each position three times, and the three members of a class occur equally often. Thus, either 9 digits go right, or 6 go right and 3 left, or 3 right and 6 left, or 9 left. The cases of 9 are your traveling triples. The cases of 6 are your traveling pairs. So, yes, they are forced to occur.

Now this is true, and amusing, but is it useful? The information obtained from considering the above is precisely what usually is called "line-box intersection", not a very deep technique. So, I do not think you are going to solve any difficult puzzles using only this. (But in my experience, recognizing 'traveling triples' speeds up the solving process a little.)


Yes, recognizing the triples is great. Similarly, ruling them out can help you rule out other possibilities.
For example in the Eppstein puzzle, the presence or absence of triples in rows 4-6 is key to the puzzle's correct solution. If I had ruled it out (edit: established it I mean) at the start, I could perhaps have avoided some confrontations...:)
Last edited by MrHamilton on Fri Mar 17, 2006 2:27 am, edited 1 time in total.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Re: Traveling Pairs and Triples

Postby ronk » Thu Mar 16, 2006 3:15 pm

MrHamilton wrote:
aeb wrote:Now this is true, and amusing, but is it useful? The information obtained from considering [edit: traveling pairs and triples] is precisely what usually is called "line-box intersection", not a very deep technique. ...

Yes, recognizing the triples is great. Similarly, ruling them out can help you rule out other possibilities.
For example in the Eppstein puzzle, the presence or absence of triples in rows 4-6 is key to the puzzle's correct solution. If I had ruled it out at the start, I could perhaps have avoided some confrontations...:)

There's a disconnect here. If aeb's conclusion above is true (and I believe it is), and if all exclusions using line-box interactions have already been made in your example (and I believe they have) ... how can you possibly make additional headway using "traveling pairs?"

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Traveling Pairs and Triples

Postby ravel » Thu Mar 16, 2006 3:33 pm

MrHamilton wrote:For example in the Eppstein puzzle, the presence or absence of triples in rows 4-6 is key to the puzzle's correct solution. If I had ruled it out at the start, I could perhaps have avoided some confrontations...:)

Hm, did you notice that there are 4 ways to solve rows 4-6 alone, that have no wandering triples (like the solution) and the same left box than the middle box in my first sample above ?
Code: Select all
-----------------------------
| 6  9  3 | 2  7 5  | 1 8  4 |
| 7  2  4 | 68 1 68 | 3 59 59|
| 1  5  8 | 3  4 9  | 7 2  6 |
-----------------------------
That means, r5c1=7 cannot be eliminated by any method, that only considers cols 1-3 and rows 4-6.

aeb, i assume, you are right, that this method is equivalent to box/line interaction, but i cannot yet clearly see why.
ravel
 
Posts: 998
Joined: 21 February 2006

Re: Traveling Pairs and Triples

Postby MrHamilton » Thu Mar 16, 2006 3:56 pm

ravel wrote:
MrHamilton wrote:For example in the Eppstein puzzle, the presence or absence of triples in rows 4-6 is key to the puzzle's correct solution. If I had ruled it out at the start, I could perhaps have avoided some confrontations...:)

Hm, did you notice that there are 4 ways to solve rows 4-6 alone, that have no wandering triples (like the solution) and the same left box than the middle box in my first sample above ?
Code: Select all
-----------------------------
| 6  9  3 | 2  7 5  | 1 8  4 |
| 7  2  4 | 68 1 68 | 3 59 59|
| 1  5  8 | 3  4 9  | 7 2  6 |
-----------------------------
That means, the puzzle cannot be solved with any method, that only considers cols 1-3 and rows 4-6.


aeb, i assume, you are right, that this method is equivalent to box/line interaction, but i cannot yet clearly see why.


Nor can I; but I'd be glad to learn.
Ravel, isn't it true that traveling triples in the above rows 4-6 are impossible for some reason? Not in themselves, but in the whole puzzle context. (Edit: Actually they are not only possible but forced)
Code: Select all

 *-----------*
 |562|731|948|
 |741|598|632|
 |983|462|571|
 |---+---+---|
 |397|245|186|
 |254|816|397|
 |618|379|425|
 |---+---+---|
 |176|983|254|
 |435|627|819|
 |829|154|763|
 *-----------*

Did I just make a lucky guess and solve the puzzle with it....?
I claimed about column 3 (correctly enough I think) that
To be blue, 6 would have to travel with either 2 or 9, but it doesn't

I somehow need to back up this sweeping statement or else recall how I reached that conclusion 2 days ago (after midnight).
Apparently it wasn't by checking the rows 4-6 alone, as you show.
Last edited by MrHamilton on Thu Mar 16, 2006 7:07 pm, edited 4 times in total.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Postby MrHamilton » Thu Mar 16, 2006 4:03 pm

I would think though, that by cross-checking what a traveling pair in one chute does to the possible pairs in another, that some headway might be made?
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Postby ronk » Thu Mar 16, 2006 5:15 pm

OK, this is going to seem like an idiotic question, I'm sure. However, in the completed (and trivial) USA Today puzzle for Tues. -- is the 389 in tower 2 a "traveling triple" traveling "down right?" And is the 13 in tower 1 a "traveling pair" also traveling "down right?"
Code: Select all
2 4 8 3 6 7 1 9 5
7 1 6 9 2 5 4 8 3
5 3 9 8 4 1 6 7 2
6 5 1 7 9 2 3 4 8
9 2 3 1 8 4 5 6 7
4 8 7 5 3 6 2 1 9
3 7 4 6 5 9 8 2 1
1 6 5 2 7 8 9 3 4
8 9 2 4 1 3 7 5 6


..8..71....6..5..3..98.1..2.5..9..48.2..8..6.48..3..1.3..6.98..1..2..9....24..7..

And if one identifies such pairs and triples during the solution process ... and properly deduces their interaction with other pairs and triples traveling in other towers and floors ... one is supposed to be able to advance the puzzle?

Is that it?

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby MrHamilton » Thu Mar 16, 2006 5:18 pm

ronk wrote:OK, this is going to seem like an idiotic question, I'm sure. However, in the completed (and trivial) USA Today puzzle for Tues. -- is the 389 in tower 2 a "traveling triple" traveling "down right?" And is the 13 in tower 1 a "traveling pair" also traveling "down right?"
Code: Select all
2 4 8 3 6 7 1 9 5
7 1 6 9 2 5 4 8 3
5 3 9 8 4 1 6 7 2
6 5 1 7 9 2 3 4 8
9 2 3 1 8 4 5 6 7
4 8 7 5 3 6 2 1 9
3 7 4 6 5 9 8 2 1
1 6 5 2 7 8 9 3 4
8 9 2 4 1 3 7 5 6


..8..71....6..5..3..98.1..2.5..9..48.2..8..6.48..3..1.3..6.98..1..2..9....24..7..

And if one identifies such pairs and triples during the solution process ... and properly deduces their interaction with other pairs and triples traveling in other towers and floors ... one is supposed to be able to advance the puzzle?

Is that it?

Ron


Yes. That's the "big if."
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Postby ravel » Thu Mar 16, 2006 6:11 pm

In Eppsteins puzzle neither stack 1 (columns 1-3) nor band 1 (rows 4-6) alone allow the elimination of any candidate (i.e. for each candidate there is a local solution).
Has someone a candidate grid (after basic methods), where an elimination can be made from the candidates in a band or stack alone ?
It would be a better candidate to verify, if the traveling pairs/triples method can be applied for it.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby tarek » Thu Mar 16, 2006 6:39 pm

I'm not sure if this helps but here is puzzle 476 of the top1465, it can be solved only using Box-line interaction (11 of them):
Code: Select all
 . . . | . . . | . 7 1 
 . 2 . | 8 . . | . . . 
 . . . | 4 . 3 | . . . 
-------+-------+------
 7 . . | . 6 . | . 5 . 
 . . . | 2 . . | 3 . . 
 9 . . | . . . | . . . 
-------+-------+------
 6 . . | . 7 . | . . . 
 . 8 . | . . . | 4 . . 
 . . . | . 5 . | . . . 

000000071020800000000403000700060050000200300900000000600070000080000400000050000

Tarek
User avatar
tarek
 
Posts: 2685
Joined: 05 January 2006

Postby ravel » Thu Mar 16, 2006 7:16 pm

Thanks, Tarek, so we can see, if travelers can solve box/line interaction.
This is another one, an xy-wing puzzle of nick70. It can be solved with eliminations in band 2 alone.
Code: Select all
------------
..9|.4.|8.1
.37|6..|...
6..|...|...
------------
...|..5|...
..8|.1.|7..
...|4..|...
------------
...|...|..7
...|..7|32.
5.4|.2.|9..
------------

*---------------------------------------------------*
| 2     5      9    | 7    4   3    | 8   6     1   |       
| 4     3      7    | 6    8   1    | 2   59    59  |       
| 6     8      1    | 259  59  29   | 4   7     3   |       
|-------------------+---------------+---------------|
| 1379  12469  23   | 8    37  5    | 16  349   29  |       
| 39    2469   8    | 29   1   269  | 7   3459  259 |       
| 1379  1269   5    | 4    37  269  | 16  39    8   |       
|-------------------+---------------+---------------|
| 139   129    23   | 19   6   4    | 5   8     7   |       
| 8     19     6    | 159  59  7    | 3   2     4   |       
| 5     7      4    | 3    2   8    | 9   1     6   |       
*---------------------------------------------------*

Can you make some eliminations, MrHamilton ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby MrHamilton » Fri Mar 17, 2006 6:08 am

:(
tough one.
xy-wing seems quicker than anything else here.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

PreviousNext

Return to Advanced solving techniques