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.
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]
You asserted and assumed that I needed the other columns; I only said I wasn't sure: i.e. can't recall needing them.