The New Sudoku Players' Forum

[Big Blue]

Since now more and more people seem to have solved Eppstein's puzzle I am curious whether or not our approaches agree, and to what extent they do.

Therefore, hopefully without spoiling the fun too much for those who still would like to try, I will post the last chain in the bilocal graph that I had used and the penultimate one:

[STILL, I RECOMMEND TO SKIP READING FURTHER IF YOU ARE INTERESTED TO SOLVE EPPSTEIN'S PUZZLE FROM SCRATCH!]

The last chain started in box number 9 and established the number which finally "collapsed the Sudoku". It was a closed cycle with labels 521736152795 (pretty lengthy, eh?).

The penultimate chain started in box number 3 and established a key number in that box (which allowed the chain above). It led to an application of the "conflicting path rule" and the paths were 349 and 393429. The two paths overlap on one edge, but you may check easily that the method still works.

Another reason why I restrict myself to the last two chains is that, embarrassingly, I could not reconstruct how I set up the first chain (it is a bit difficult by looking at the bilocation graph, because of course it was growing during the solution, and I just have the "final" graph on a sheet of paper). I saw in a margin scribbled 776(47)8, where the notation (47) means that the edge carries the labels 4 and 7, but such a closed path does not seem to exist. I then noted that instead the closed path 776(68)8 exists, which at first glance allows to apply the closed cycle rule: after all, the only label that repeats itself is 7, while the other labels, 6, 8 and (68), are all different - but it is not true. The label (68) for all practical purposes should be considered as two edges, one with label 6 and one with label 8. But in the sequence 6(68)8 you will necessarily have a repetition, no matter which of the two ways you choose.

Thus, either there is another path at this stage which yields the crucial 7 in box 2, or my "first application of the bilocation graph technique" was actually a lucky guess.

Therefore my question to those who have solved the puzzle: which chains in the bilocation graph did you employ?

[Max Beran]

My turn to eat humble pie Jeff!

I can't manage such a handsome retraction and apology as Jacko's but on writing out my route in response to your request I now see that I have two nodes with the same labels on exit and entrance. My problem was a careless mind map (I redrew the diagram with all the nodes around a circle and linked them appropriately). My problem was that two links crossed at such an acute angle that it fooled my eye into connecting the wrong nodes together.

From what I now see none of the three 7's that depart from r1c4 go anywhere in the sense that sooner or later they each lead inevitably to another node of the same type. Perhaps, Jeff, you found the same and that's why you asked me for mine.

I''ll remove my triumphalist post after a day of shame and hubris.

[Scott H]

Solution discussion and partial spoiler follows. I RECOMMEND TO SKIP READING FURTHER IF YOU ARE INTERESTED TO SOLVE EPPSTEIN'S PUZZLE FROM SCRATCH!

Blue, The first chain I found had labels 7297687. Your first clue was instrumental in helping me find it, because I had left out some edge markings in my first transcription and had an incomplete search space.

I didn't actually find your penultimate conflicting chain:

The penultimate chain ... led to an application of the "conflicting path rule" and the paths were 349 and 393429. The two paths overlap on one edge, but you may check easily that the method still works.

but I found the 4 edge closed loop after the overlapping part of your conflicting chain (9 from 349, 29 from 393429, and the edge between the two end 9s).

This is a actually a type of nonrepetitive cycle, but more general than Eppstein considers. In my notation described here, the cycle has labels 2, 9, -9, 9, or in more detail:

Code: Select all

[13:29] <2> [17:2*9] <9> [97:9*] <-9*> [93:9*] <9> [13:]

With this cycle you can exclude extra candidates (a 4) from r1c7 and extra 9s from row 9 (so r9c8<>9).

The 4 nodes in this cycle are also the nodes of a X-wing in 9s. We get the X-wing by using label -9 instead of 2 between 13 and 17:

Code: Select all

[13:9*] <-9*> [17:9*] <9> [97:9*] <-9*> [93:9*] <9> [13:]

and we can exclude any extra 9's from the weak edges (rows 1 and 9) in the X-wing (so r1c58<>9 and r9c8<>9).

In a general nonrepetive cycle, successive edge labels must change either sign or absolute value, but not both. Eppstein's nonrepetitive cycles, in my notation, either have all positive labels (bilocation cycles) or all negative labels (bivalue cycles).

After using the 4 edge cycle I found (or the X-wing) and some standard reductions, I used two 7-edge bivalue (xy) repetitive cycles, each starting in column 9, to crack the end of the puzzle.

[Jeff]

Scott

You bilocation graph must be different to mine. I am posting my spaghetti of connections so that you can point out what I have done wrong. I don't get your chain with labels 7297687. Please take me out of misery.


Thanks Big Blue, edge 4 in row 1 removed.

[Big Blue]

...look similar to mine, Jeff.

But naturally, I have more connections in my "final Spaghetti graph".

BTW, your Spaghetti at least resolves the "(47)-mystery" above: it is easy to mistake the label (47) in the centre for the label of the edge with (68)...

@Scott: Thanks for your paths. Your concise notation needs some practice, but it is ok

A shame that you could avoid the conflicting paths by something as mundane as an x-wing ;-)

Regarding your first chain 7297687: I have also difficulties to identify it in Jeff's Spaghetti. I suppose the two sevens just meet in r1, c4, right? But if I go back from 7 to 8 and then to 6 I seem to land at a node which has only edges with 6 and 8 but no 7 - so unfortunately I also fails to see your chain.

[Max Beran]

Scott H; I’m with Jeff on this one as my bilocation diagram is exactly his.

Assuming you are starting at r1c4 then the only viable routes starting 7297 take you to r6c7, a tight little clutch of links whose only exit is through r4c9 involving a 4.

Working back, the only route ending at r1c4 with links 87 must begin at r2c2, r3c4 or r5c6. None of these three cells has a link to r6c7, le alone a link labelled 6.

On my diagram both of the other 7 exits from r1c4 (via r8c4 and r2c6 enter a tight clutch of links whose only exit is through r8c2 but even that is not possible without a duplicated 8.

There is another 7297 route from r1c4 and that ends at r8c9. This is on the same row as the edge leading from r1c4 to r8c4. It would be nice to be able to apply the conflicting path rule. Eppstein’s paper does refer to path ends which I have taken literally to mean situations such as r8c9, but is it essential? If it isn’t then the job’s done.

[Max Beran]

I reckon I was unto something with that conflicting path suggestion.

Name r1c4 "A", r8c4 "T" and r8c9 "U" (which were what they were called on my mind map that led me astray). Then we can explore the consequences of excluding the 7's from T and U. Excluding 7 from T leaves it with 4 or 6 both of which lead to A=7. If we exclude 7 from U then it too leads by simple logical steps back to A=7 (r9c7=7 => r6c7=4 => r7c7=2 => r1c7=9 => r1c5=3 => r1c7=4 => r1c4=7).

But was this kosher? Excluding the 7's in turn from T and U does not exhaust all the possibilities in our normal bivalue world. In tracing back from U to A and one of the routes from T to A cells are used that are not part of the forward chain (though they are cells in the same column and row as the original chain). I look to others to sort this out.

If it is true that path ends don't actually have to be the ends of paths then this if anything adds to the comlication of the search as every point along every chain has to be inspected. It was just pure luck that Scott H's cycle led me this way.

[Scott H]

It's my turn for egg on the face. In manual transcription I missed the 6 in r8c6, so I wrongly marked r5c6-r9c6 with <6> (strong 6) when it is really weak. So my 7297<-6>87 path is wrong and doesn't force anything. Looks like I got lucky(?) and accidentally excluded a correct candidate anyway.

Now I'm really intrigued. My first path was bogus, and Blue can't reconstruct his first path. Looks like more investigation before this mystery is solved.

[Scott H]

There is another 7297 route from r1c4 and that ends at r8c9. This is on the same row as the edge leading from r1c4 to r8c4. It would be nice to be able to apply the conflicting path rule. Eppstein’s paper does refer to path ends which I have taken literally to mean situations such as r8c9, but is it essential? If it isn’t then the job’s done.

Max, your conflicting path [14:] <7> [84:] <-7> [89:] <7927> [14:] does the trick, congratulations! I hadn't absorbed this before my previous post.

[fkereki]

I started noting, for each empty cell, which numbers could go in it.

In the center 3x3 square, "4" can go only down the center column, and this helps eliminating some possible "4"s from the top center square.

At the same square, the top center and bottom center can only be "4" or "7", so no other cell can have those numbers, so the center row cannot have a "7".

The center row in that square has "6" and "8", which allows forbidding these numbers along the row.

Now, to the bottom center square. All "3" must go in the right column, so we can eliminate another "3" possibility in the top center square.

Now, at the top center square, we have this configuration: the top left cell can be "4" or "7"; the right center cell, "4", "7", or "8"; and the bottom left cell, "4" or "8". There is NO other possibility but that these three cells are occupied by "4", "7", and "8" -- work it out! This allows eliminating "7" as a possibility in the top center square.

I don't know if the patterns and rules I'm using are original or well known (though I suspect the latter is more probable) but I wanted to show that you COULD go on with this puzzle.

[Jeff]

Max and Scott

Congratulations, I think you have hit the jackpot. Having captured this configuration, correct me if I am wrong, I couldn't find another similar chain elsewhere. Well done!

[fkereki]

Now I had to resort to some trial and error to finish this! A good problem!

[Jeff]

Fkereki

Just to inform that we have done all these 'local rules' as described in Eppstein's paper. This puzzle needs more than local rules to solve. We are working on the bilocation cycles and paths.

[Max Beran]

Fkereki

As previously posted there is a long xy-chain that'll finish the job for you once you've accepted the "7" in r1c4 (plus the elimination of 6 more cells with nothing more complicated than an x-wing).

Hint follows so shut your eyes when you read the next paragraph if you don't want one.








As a little hint the chain allows a "9" to be eliminated.

[Big Blue]

...Max has found the path and Scott has explained it.

Very nice!

I recall now that it was this kind of path that I had used (although with a different final cell for the longer path - there are two options, both of which lead to a contradiction), but in my final bilocation Spaghetti there is a simpler (closed) path that establishes the same result, namely 76847 - but the 4 in this closed cycle is only present after you have eliminated it from the starting cell! So I am sorry for the confusion that my remark about a "closed cycle" may have caused - but at least you had the appropriate starting cell from my hint ;-)

I think there is an important practical lessons for future use of bilocation graphs: if you have a cell where 3 or more labels with the same number emerge then this cell is a good candidate for a starting point of either conflicting paths or some cycle with one repetition.

The reason is simple: in a pattern like this

|
x
|
o--x--
|
x
|

where x is some digit and o the vertex where the "critical cell" is located, there are two options:

1.) x is located at the ciritical vertex o
2.) x is pushed on three (!) different paths away from the critical vertex

the latter option might easily lead to contradiction

In the example above in one of the paths (78 etc.) the shock of "pushing" of the 7 is absorbed by either a sequence of 88 or of 66

But the other two paths yield just what you want: a contradiction.

@Max, Scott and Jeff: I have learned that you don't need these additional paths if you use the x-wing technique, but just for fun/practice: you may now insert additional edges (e.g. a crucial 4 edge in the first row) in the bilocation graph to obtain the next conflicting paths I posted above and the final, somewhat lengthy, path.