Traveling Pairs and Triples

Advanced methods and approaches for solving Sudoku puzzles

Traveling Pairs and Triples

Postby MrHamilton » Wed Mar 15, 2006 6:51 am

Here's another (possibly original) technique I like to use involving groups.
I had a deleted post about groups of six that some may recall from a few weeks ago. That technique was insufficient to solve the harder puzzles; i.e. the ones where angusj's Simple Sudoku program says "No Hint Available".
Here I will describe my other method and use it on one of Eppstein's puzzles.
The method can be understood and used with or without a computer, and with or without pencilmarks and colors. (Easiest WITH, of course.) As in my other method, you only need to concentrate on a third of the grid at any given time.
First, some theory:
Any valid grid must have certain properties. When we consider a section of any solved grid (say this one):
Code: Select all
 *-----------*
 |132|958|764|
 |475|623|198|
 |986|741|523|
 *-----------*

We see that certain numbers must "travel together" in pairs (or alternatively in groups of three; more on that later). Here, within this particular chunk of 27 numbers, 8 is always paired with 9, 2 with 3, and 4 with 7. The 1, 5, and 6 in each box are the "old maids" or "odd men out" if you will. (They dine with the Smiths one night, the Joneses the next, and the Robinsons the night after.) The pairs in these rows are shown in this example:

Code: Select all
 *-----------*
 |.32|9.8|7.4|
 |47.|.23|.98|
 |98.|74.|.23|
 *-----------*

When using Simple Sudoku I would color the cells correspondng to these "pairs" blue, and other numbers not part of any pair green. The numbers will be different in a different region; but the pattern is universal.
Triples would look like this:

Code: Select all
 *-----------*
 |132|968|754|
 |475|123|698|
 |986|745|123|
 *-----------*


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.

If this is not intuitively obvious, suppose we attempt to construct a grid, or section of it, where there are NO adjacent traveling pairs, let's see how far we can get.

Code: Select all
 *-----------*
 |123|...|...|
 |456|1..|...|
 |789|2..|...|
 *-----------*


So far so good. In my second box, I couldn't put the 1 on the top row (that's illegal), and had to put the 2 neither on the top row (again illegal) nor the second row since that would pair with the 1. But--there is already no place to put the number 3 in the second box, so that effort is obviously doomed from the start.

Now for the more practical bit.

Eppstein published this very hard puzzle:

Code: Select all
 *-----------*
 |5..|..1|..8|
 |...|...|6..|
 |...|.62|57.|
 |---+---+---|
 |.9.|2.5|1..|
 |..4|.1.|3..|
 |..8|3.9|.2.|
 |---+---+---|
 |.76|98.|...|
 |..5|...|...|
 |8..|1..|..3|
 *-----------*


After a few hints from the solver, we have

Code: Select all
 *-----------*
 |56.|..1|..8|
 |...|5..|6..|
 |...|.62|57.|
 |---+---+---|
 |.9.|2.5|18.|
 |..4|.1.|3..|
 |..8|3.9|.2.|
 |---+---+---|
 |.76|98.|...|
 |..5|.2.|8..|
 |8..|15.|..3|
 *-----------*

 
 *-----------------------------------------------------------*
 | 5     6     279   | 47    39    1     | 249   349   8     |
 | 2479  248   1279  | 5     39    478   | 6     1349  1249  |
 | 349   348   139   | 48    6     2     | 5     7     149   |
 |-------------------+-------------------+-------------------|
 | 367   9     37    | 2     47    5     | 1     8     467   |
 | 27    25    4     | 68    1     68    | 3     59    579   |
 | 16    15    8     | 3     47    9     | 47    2     56    |
 |-------------------+-------------------+-------------------|
 | 1234  7     6     | 9     8     34    | 24    145   1245  |
 | 1349  134   5     | 467   2     3467  | 8     1469  1479  |
 | 8     24    29    | 1     5     467   | 2479  469   3     |
 *-----------------------------------------------------------*


...and the dreaded "No Hint Available" appears.:D

I first try to rule out triples where possible.

Rows 1-3 -- no triples (5 and 6 don't always travel together)
Rows 4-6 -- triples can't be ruled out at first glance.
Rows 7-9 -- no triples (no possible companion for 6 and 7 )
Columns 1-3 -- no triples (5 and 6 don't always travel together)
Columns 4-6 -- no triples (1 and 2 don't always travel together)
Columns 7-9 -- triples can't be immediately ruled out.

[Incidently, in my experience it is quite unusual for there to be more than one set of traveling triples. More often a puzzle will have no groups of traveling triples. I have a theory that it is impossible for the whole puzzle to consist of traveling triples; but I leave it to others to demonstrate this.]

Let us first consider columns 1-3, and look elsewhere only if we need to. (If that happens be sure to distinguish your colors in columns from those in rows, as they will not correlate in any way we need discuss now! If you are using Simple Sudoku, you could open it twice, load the puzzle twice, and do columns on one instance and rows in the other. Or you could, if using pens and paper, use vertical colored lines in the columns and horizontals in the rows; or use a separate sheet. Just keep in mind, a cell may need to be green in a row and blue in a column!)
Okay. Evidently pairs, and not triples, are involved here. That issue settled, we now attempt to assign blue and green colors to numbers/cells as appropriate. Where a cell has more than one candidate, we only assign it a color if we know its color for certain. Obviously if triples were involved we wouldn't need to use contrasting colors at all.

As stated above, 5 and 6 don't travel together. Therefore square C3R9 is not green; it's blue. And 5 and 6 must be blue and green in some order.
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.
(Edit: oops, while this is true, I'm not exactly sure anymore how I figured that out. Eppstein's losing no sleep I imagine!)
We may now safely infer the following:
C1R1 = blue (5)
C2R1 = green (6)
C2R2, C2R3 = blue (they are a traveling pair by default)
C1R5 = blue (since green 6 is in C1R4 or C1R6)
As the 8 in the top box must be in either C2R2 or C2R3 along with the green 6, 8 is definitely blue. It cannot travel with 2 (from info in C3), therefore we may exclude 2 from square C2R2!


It may be helpful at some point to list the numbers, their possible colors, and their possible traveling companions. No number can travel with itself, or with 6. 8 travels only with 3 or 4. The 4 is either green, or travels with 8. It can't travel with 7 or 3 in C3 since that would make three consecutive blue cells (in C3R3-4-5). 3 cannot travel with 5, and vice versa. From the bottom three rows, 9 can only travel with 5 or 8. We now have

[1][BG][2345789]
[2][BG][1345789]
[3][BG][124789]
[4][BG][8]
[5][B][124789]
[6][G][none]
[7][BG][123459]
[8][B][34]
[9][BG][58]

This can be further simplified by a kind of commutative property of traveling. (If you won't go with me, then...guess what?) Thus for example, only 2, 3, 5 and 7 list the 1 as a possible companion, so these four (and no others) must appear in the list for 1:

[1][BG][2357]
[2][BG][1357]
[3][BG][1278]
[4][BG][8]
[5][B][1279]
[6][G][none]
[7][BG][1235]
[8][B][34]
[9][BG][58]

We may rule out 9 traveling with 8 (top box).
3 cannot travel with 1 (middle box).
7 cannot travel with 5. 5 travels only with 2 or 9.
1 cannot travel with 2: since in the bottom box this could only happen in the middle column, but this is refuted by C2R5-6.

[1][BG][7]
[2][BG][357]
[3][BG][278]
[4][BG][8]
[5][B][29]
[6][G][none]
[7][BG][1]
[8][B][34]
[9][BG][5]

As 1 and 7 can only travel with each other (if they do travel), neither travels with 2 or 3. 7 can't travel with 2 or 4, so C2R8 is blue. 7 cannot now travel with 1, so 7 is green and therefore may be excluded from C1R5 and after this the puzzle is basically easy.

Comments welcome.[img][/img]
Last edited by MrHamilton on Fri Mar 17, 2006 4:57 am, edited 2 times in total.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Re: Traveling Pairs and Triples

Postby Jeff » Wed Mar 15, 2006 9:59 am

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 MrHamilton, Thanks for sharing the great idea.:D It appears to be a very promising technique and I am half way going through it.

I can see 6 can't travel with 9. But, I can't see how 6 cannot travel with 2. Could you explain?

Thanks in anticipation
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ravel » Wed Mar 15, 2006 10:04 am

Hi MrHamilton,

sorry, i dont have the time now to read your long post carefully (and it has some mystical part that is hard to understand). But when i got you right, you eliminated the 7 in R5C1 by only using the first 3 columns ? When i look at the candidate list, e.g. this pattern is possible:
Code: Select all
*--------------
| 5   6   7   |
| 2   8   9   |
| 4   3   1   |
|-------------+
| 6   9   3   |
| 7   2   4   |
| 1   5   8   |
|-------------+
| 3   7   6   |
| 9   1   5   |
| 8   4   2   |
*--------------


So i cannot see, how you can exclude it without looking at the other columns.
ravel
 
Posts: 998
Joined: 21 February 2006

Re: Traveling Pairs and Triples

Postby Jeff » Wed Mar 15, 2006 11:06 am

MrHamilton wrote:Thus for example, only 2, 3, 5 and 7 list the 1 as a possible companion,

Hi MrHamilton, Another stupid question. Why can't 9 be a possible companion? Please explain.

Thanks in anticipation
Last edited by Jeff on Wed Mar 15, 2006 7:22 am, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Traveling Pairs and Triples

Postby Jeff » Wed Mar 15, 2006 11:20 am

MrHamilton wrote:..........3 cannot travel with 1 (middle box).......

Hi MrHamilton, Another stupid question. Why can't 3 travel with 1 (middle box). Please explain.

Thanks in anticipation
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Traveling Pairs and Triples

Postby Jeff » Wed Mar 15, 2006 11:29 am

MrHamilton wrote:1 cannot travel with 2: since in the bottom box this could only happen in the middle column, but this is refuted by C2R5-6.

Hi MrHamilton, Another stupid question. Why can't 1 travel with 2 in the first column of the bottom box. Please explain.

Thanks in anticipation
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby MCC » Wed Mar 15, 2006 1:06 pm

A similar idea was started in this thread but no conclusion was reached.

MCC
MCC
 
Posts: 1275
Joined: 08 June 2005

Postby MrHamilton » Wed Mar 15, 2006 2:22 pm

ravel wrote:Hi MrHamilton,

sorry, i dont have the time now to read your long post carefully (and it has some mystical part that is hard to understand). But when i got you right, you eliminated the 7 in R5C1 by only using the first 3 columns ? When i look at the candidate list, e.g. this pattern is possible:
Code: Select all
*--------------
| 5   6   7   |
| 2   8   9   |
| 4   3   1   |
|-------------+
| 6   9   3   |
| 7   2   4   |
| 1   5   8   |
|-------------+
| 3   7   6   |
| 9   1   5   |
| 8   4   2   |
*--------------


So i cannot see, how you can exclude it without looking at the other columns.


Yes but that was the last thing I did, not the first:D
I excluded it only after lots of head-scratching.
And, one may of course glance over at the other columns.
I don't recall exactly but I think this way would mess up Row 4 or create a difficulty elsewhere. Since this possibility turns out wrong and was not reached by using my method I will refrain from a detailed reply to this one.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Postby ravel » Wed Mar 15, 2006 2:34 pm

IMHO either your method or your deductions must be wrong. You conclude (looking at the left 3 boxes only) that "7 cannot now travel with 1", but in my sample it does without any contradiction to the candidates in these boxes. If you need other cells, you should mention it, or no one can follow you.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby MrHamilton » Wed Mar 15, 2006 2:51 pm

ravel wrote:IMHO either your method or your deductions must be wrong. You conclude (looking at the left 3 boxes only) that "7 cannot now travel with 1", but in my sample it does without any contradiction to the candidates in these boxes. If you need other cells, you should mention it, or no one can follow you.


I'm not sure I needed them in that case; but this is a hard topic on a hard puzzle and I don't expect everyone to follow me straight off even if I made no mistakes!
The bottom line is I solved the puzzle logically using local methods, which Eppstein is claiming can't be done without BiValues and BiLocations and the rest of it.
My method seems easier in theory. You have to keep track of two colors and everything else is simple elimination.
If I made a mistake or essential omission in my argument, where exactly did that happen?
I don't think my postulate is wrong, or the general idea that the traveling pairs must exist.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Re: Traveling Pairs and Triples

Postby MrHamilton » Wed Mar 15, 2006 2:55 pm

Jeff wrote:
MrHamilton wrote:Thus for example, only 2, 3, 5 and 7 list the 1 as a possible companion,

Hi MrHamilton, Another stupid question. Why can't 9 be a possible companion? Please explain.

Thanks in anticipation


"9 can only travel with 5 or 8" [Bottom box]
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Postby ravel » Wed Mar 15, 2006 3:02 pm

MrHamilton wrote:I'm not sure I needed them in that case;

Sorry for getting a bit harsh now, but when you explain a new technique you should know, what you have done and needed.
If I made a mistake or essential omission in my argument, where exactly did that happen?

As i said, i cannot understand, why "7 cannot now travel with 1".

MrHamilton wrote:"9 can only travel with 5 or 8" [Bottom box]

Whats wrong with this?
Code: Select all
*-------*
| . . 9 |
| . . 1 |
| . . . |
|--------
| . 9 . |
| . . . |
| . 1 . |
|--------
| 1 . . |
| 9 . . |
| . . . |
*--------
ravel
 
Posts: 998
Joined: 21 February 2006

Postby MrHamilton » Wed Mar 15, 2006 3:20 pm

ravel wrote:
MrHamilton wrote:I'm not sure I needed them in that case;

Sorry for getting a bit harsh now, but when you explain a new technique you should know, what you have done and needed.
If I made a mistake or essential omission in my argument, where exactly did that happen?

As i said, i cannot understand, why "7 cannot now travel with 1".


The short answer is: 7 and 1 wind up being green by elimination and only blue pairs are said to be "travelers." Greens are the "odd men out."
I might reasonably add that when you criticize a new technique, after by your own admission not reading the long post carefully, you might have made a mistake too.:!: You asserted and assumed that I needed the other columns; I only said I wasn't sure: i.e. can't recall needing them.
If my method fails or my deductions were wrong it has not yet been demonstrated in these replies.
MrHamilton
 
Posts: 42
Joined: 14 March 2006

Postby ravel » Wed Mar 15, 2006 3:33 pm

MrHamilton wrote:The short answer is: 7 and 1 wind up being green by elimination and only blue pairs are said to be "travelers."

As my first sample shows, 7 can travel with 1, as my second sample shows, nothing in the bottom box prevents 9 to travel with 1. As long as you cannot explain this, why should i spend much time in trying to understand that all (and you admitted that some things might be missing in this long post) ?
ravel
 
Posts: 998
Joined: 21 February 2006

Re: Traveling Pairs and Triples

Postby Jeff » Wed Mar 15, 2006 4:38 pm

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 |
*-------*         *-------*
Jeff
 
Posts: 708
Joined: 01 August 2005

Next

Return to Advanced solving techniques

cron