Hard puzzle in Eppstein's paper

Advanced methods and approaches for solving Sudoku puzzles

Postby Max Beran » Tue Aug 30, 2005 8:41 am

While it's nice to be the Newton to all you Leibnitz's I still retain a smigeon of doubt about the validity which I would like to have formally removed for full satisfaction. The issue that keeps looming in my mind is that in this non-bivalue world the decision to exclude the 7 from cells T and U is not the converse of accepting anything because row 8 has another 7 in it. You can exclude neither or both and still be left with a viable row 8.

Also Eppstein talks about path ends and cell T is not a path end, it is on a cycle. Perhaps this is less of a bother as one can imagine inserting arbitrary new candidates that would destroy the continuation but not influence the logic (if logic it is).
Max Beran
 
Posts: 57
Joined: 17 August 2005

A simple explanation...

Postby Big Blue » Tue Aug 30, 2005 9:45 am

...of the conflicting paths:

start in the "critical cell", r1c4, and assume that the number 7 is NOT placed there

there are three paths emanating from this cell with the label 7 attached

follow first the one that goese straight down into box 8 - the assumption above establishes that 7 must be placed in this box. end of path 1.

following the path that reaches next an 8 (no matter where you go) yields nothing, because either a sequence of 88 or of 66 damps the ripples that the assumption above sends into the bilocation spacetime. end of path 2.

thus, follow finally the third path (no, I am not Tony Blair): because of the assumption above you have to place 7 in box 1; but this implies you have to place 2 in box 3; but this implies you have to place 9 in box 9; but this implies you have to place 7 in box 8 (and also a 7 in box 9, r8, if you prefer this end of the path). end of path 3.

therefore, two of the three paths establish that you have to put a 7 in different cells of box 8 (or in different cells of r8 if you prefer the alternative end of path 3) if you assume that 7 is NOT placed in the critical cell r1c4

clearly, this is a contradiction, and therefore 7 must be placed in r1c4

P.S.: a shorthand notation for the two paths would be 7 for path 1 and 7297 for path 3 - or you may use Scott's notation which is more descriptive, see his post above
Big Blue
 
Posts: 28
Joined: 01 August 2005

Postby Nick B » Tue Aug 30, 2005 6:18 pm

Compared to all of you I guess I'm a novice. I have spent the day on Eppstein's puzzle and have yet to solve it. I have read his paper but need to go through it more thoroughly. Would one of you be kind enough to give me a hint as to where to go next. This is as far as I've got with fairly advanced (so I thought) methods.


56x xx1 xx8
x8x 5xx 6xx
xxx 862 57x

x9x 2x5 18x
xx4 618 3xx
xx8 3x9 x2x

x76 98x xxx
xx5 x2x 8xx
8xx 15x xx3

Not having studied Eppstein's paper thoroughly I don't understand the 'edges' notation. Could you just write the chain out in rxcy notation?

Cheers

Nick
Nick B
 
Posts: 1
Joined: 30 August 2005

Postby Jeff » Wed Aug 31, 2005 4:47 am

Nick B
I suggest that you should check your 'fairly advanced methods'. Your grid is wrong in 4 places, namely r2c2<>8, r3c4<>8, r5c4<>6, r5c6<>8.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Wed Aug 31, 2005 6:04 am

After the placement of 7 from the conflicting chain, I managed to complete the puzzle with nothing more than an x-wing and the unique-solution rule.

Max, can you list the xy-chain. I am interested to know how long it is.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Max Beran » Wed Aug 31, 2005 4:50 pm

Jeff (everyone else close your eyes)

Here it is:

9 - 13725165 - 9
and remember it's curly as well as long.
Max Beran
 
Posts: 57
Joined: 17 August 2005

Postby Max Beran » Wed Aug 31, 2005 5:13 pm

Thanks Big Blue for that explanation and sorry Scott H for needing this additional clarification to your notation. It's so simple if you work forwards - I was getting into a tangle by working backwards from the ends of the path and thinking not all possibilities were exhausted by exclusions.

Thanks also for pointing out that there was an alternative end of path that was in the same box, reminding us of the rule that the path ends have only to be in the same domain - row, path or box.

That just leaves the tiny issue of Eppstein talkng about path ends. Clearly, given the watertightness of the logic, that is an unnecessary restriction. Any point along a path could be considered in the test.
Max Beran
 
Posts: 57
Joined: 17 August 2005

Postby Jeff » Thu Sep 01, 2005 3:35 am

Thank you Max, you may now remove the post so that others need not to close theirs eyes.

Can this long and curly chain be found by pure inspection? Did you construct a bivalue graph first? I couldn't find your chain. But that was just by pure inspection. Instead, I found a non-repetitive cycle (closed xy-chain) 91374742, which is not as long as yours. I wonder what would be the maximum length of an xy-chain that can be reasonably identified by pure inspection within average human ability.
Jeff
 
Posts: 708
Joined: 01 August 2005

End of path

Postby Big Blue » Thu Sep 01, 2005 6:49 am

Ah... Only now I understand your previous concern, Max!

In any graph (bivalue or bilocation) you are free to choose where to start and where to end your path - it is as simple as that.

If you have, for instance, a closed cycle you are of course free to stop before the cycle closes, if this helps (usually it does not).

Similarly, on a long path you are free to say: "STOP! This vertex looks interesting because there is another vertex with an edge with the same label in the same box/row/column, so maybe there are some conflicting paths!"

You are the master and the graph is the slave, not the other way around:)
Big Blue
 
Posts: 28
Joined: 01 August 2005

Postby Max Beran » Thu Sep 01, 2005 9:36 am

Jeff

After placing the "7" in r1c4 there's a bit of tidying and the removal of some 9's using an x wing with a rectangle of 9's in r19 and c37. After some further tidying up 39 cells have been filled.

The exclusion of the 9 takes place in r5c9 and the xy-chain that allows this starts in r3c9 and ends at r5c8.

No I didn't use a bilocation or bivalue path map - it was purely by inspection of the pairs on Angus pair filter plan. There are 28 two-candidate cells so it took some finding. I can't recall how precisely I hit upon it but as a rule my strategy is to look at three-candidate cells and do a quick search in its column and row for pairs that would result in an exclusion, if a path was found. Then I look for a path. Obviously 9 times out of 10 I don't find one but this one struck gold.

As regards your speculation about the maximum length of xy-chain I do have a brain the size of a planet so such trifles hardly concern me:D
Max Beran
 
Posts: 57
Joined: 17 August 2005

Postby Jeff » Thu Sep 01, 2005 10:07 am

Thank you for your thorough description. I am now convinced that an xy-chain is more user friendly; unlike the bilocation chains where a graph must be prepared. It may not be possible to identify all xy-chains, but it usually takes one to solve the puzzle anyway.:)
Jeff
 
Posts: 708
Joined: 01 August 2005

Previous

Return to Advanced solving techniques