Hard puzzle in Eppstein's paper
56 posts
• Page 2 of 4 • 1, 2, 3, 4
Hard puzzle in Eppstiens paper
by LimeyCliff » Sat Aug 27, 2005 5:30 am
I have worked on this puzzle for too long. I place it in the guessing puzzle catergory. Logic does not do it.
- LimeyCliff
- Posts: 6
- Joined: 25 August 2005
by Scott H » Sat Aug 27, 2005 8:14 am
Max, a slight elaboration on BigBlue's first hit (thanks Blue!): one of Eppstein's chains uses r1c4 and 7 edges. Message me if you want even more detail. I hadn't found it earlier because of a transcription error (I neglected to tick-mark a couple of strong edges seen by software filter).
Jeff, I'd prefer you not post an outright spoiler. And you didn't -- you misidentified edge 41-43 on 7's as strong, when it's actually weak. I think your notation is discarding too much information. The priorities should be understanding, clear communication, and accurate chain finding, not typing a few less characters. Your (non-forcing) path is clear with the nice picture, but a good notation should not need a picture to work.
Jeff, I'd prefer you not post an outright spoiler. And you didn't -- you misidentified edge 41-43 on 7's as strong, when it's actually weak. I think your notation is discarding too much information. The priorities should be understanding, clear communication, and accurate chain finding, not typing a few less characters. Your (non-forcing) path is clear with the nice picture, but a good notation should not need a picture to work.
- Scott H
- Posts: 73
- Joined: 28 July 2005
by Max Beran » Sat Aug 27, 2005 9:49 am
I'm now totally confused.
I thought we were looking for chains or cycles made up of bilocation elements. The edge between r4c1 and r4c3 is not a "7" on that reckoning and even as a "3" doesn't go anywhere as the edge from r4c3 to r3c3 terminates there.
What's the mssing factor in my understanding of non-repetitive cycles?
I thought we were looking for chains or cycles made up of bilocation elements. The edge between r4c1 and r4c3 is not a "7" on that reckoning and even as a "3" doesn't go anywhere as the edge from r4c3 to r3c3 terminates there.
What's the mssing factor in my understanding of non-repetitive cycles?
- Max Beran
- Posts: 57
- Joined: 17 August 2005
by jacko » Sat Aug 27, 2005 2:26 pm
I've never studied any of these techniques and I have no idea what you guys mean by swordfish, chains, xyz, etc.
But I did solve the puzzle from as put forth by Max Beran. Is it terribly unethical on this forum to give hints that would solve the puzzle? It only takes one tiny little hint, and the whole thing solves itself.
I was almost disappointed finishing the puzzle - this was the most challenging one I've ever solved (in my one month experience).
But I did solve the puzzle from as put forth by Max Beran. Is it terribly unethical on this forum to give hints that would solve the puzzle? It only takes one tiny little hint, and the whole thing solves itself.
I was almost disappointed finishing the puzzle - this was the most challenging one I've ever solved (in my one month experience).
- jacko
- Posts: 4
- Joined: 27 August 2005
by Max Beran » Sat Aug 27, 2005 5:07 pm
Actually Jacko, this particular forum is about techniques and as Eppstein's paper and his concepts were novel to some of us I see this as more of an educational process than one where a challenge is set.
So, I'm rather hoping that in a day or two's time we will have an expose from one of the site wunderkinds on how Eppstein's methods translate into practical tools. Personally I wouldn't find this at all an offence against the spirit of the thread.
Anyway many congratulations on completing this puzzle which still has me foxed despite the various small hints that have been dropped.
PS This is a handy site for learning about some of the techniques you mention (or at least I think so, but clearly you may not need).
http://www.simes.clara.co.uk/programs/sudokutechnique6.htm
So, I'm rather hoping that in a day or two's time we will have an expose from one of the site wunderkinds on how Eppstein's methods translate into practical tools. Personally I wouldn't find this at all an offence against the spirit of the thread.
Anyway many congratulations on completing this puzzle which still has me foxed despite the various small hints that have been dropped.
PS This is a handy site for learning about some of the techniques you mention (or at least I think so, but clearly you may not need).
http://www.simes.clara.co.uk/programs/sudokutechnique6.htm
- Max Beran
- Posts: 57
- Joined: 17 August 2005
Re: Hard puzzle in Eppstein's paper
by jacko » Sun Aug 28, 2005 1:43 am
Not to rub this in, but I completed this puzzle with pen and paper - it's possible! But I'll admit that the pen actually was a pencil with an eraser, and I did need to print out several grids.
This is a puzzle (I'm sure you found out) that has no singles. Which means that a whole grid with all candidates ought to be laid out (or at least I did). At this point you can see a few double pairs (called subsets? anyway, a bunch of 47's) which enable you to rule out a few more candidates.
Max, in your first post, you say that "the cell with the highest number of candidates is r2c1 with 1, 2, 4, 7 and 9" - but I can't see how you could have eliminated the 3 from there. Mabye that's where you got stuck, or if there's a good reason the 3 shouldn't be there, I'd love to hear it.
Then it's like Big Blue said - you have to find the right place to start a string or whatever that's called. Use a "either or" technique which is like trying one of two numbers in a 2 candidate cell until you meet error. Error is good, because that means it's the other candidate. Merely meeting an impass, however doesn't prove it's right.
I'll warn you that some of the doors will allow you to go as far as leaving 3-4 squares before reaching an error/impass. Once you find the right 'door', however, the string will take you to the end (didn't have to erase anything).
Hope this still leaves you with a bit of a challenge.
I'm getting curious about this Eppstein chap - can you give me a link to this paper of his?
This is a puzzle (I'm sure you found out) that has no singles. Which means that a whole grid with all candidates ought to be laid out (or at least I did). At this point you can see a few double pairs (called subsets? anyway, a bunch of 47's) which enable you to rule out a few more candidates.
Max, in your first post, you say that "the cell with the highest number of candidates is r2c1 with 1, 2, 4, 7 and 9" - but I can't see how you could have eliminated the 3 from there. Mabye that's where you got stuck, or if there's a good reason the 3 shouldn't be there, I'd love to hear it.
Then it's like Big Blue said - you have to find the right place to start a string or whatever that's called. Use a "either or" technique which is like trying one of two numbers in a 2 candidate cell until you meet error. Error is good, because that means it's the other candidate. Merely meeting an impass, however doesn't prove it's right.
I'll warn you that some of the doors will allow you to go as far as leaving 3-4 squares before reaching an error/impass. Once you find the right 'door', however, the string will take you to the end (didn't have to erase anything).
Hope this still leaves you with a bit of a challenge.
I'm getting curious about this Eppstein chap - can you give me a link to this paper of his?
- jacko
- Posts: 4
- Joined: 27 August 2005
Re: Hard puzzle in Eppstein's paper
by Scott H » Sun Aug 28, 2005 2:24 am
- Scott H
- Posts: 73
- Joined: 28 July 2005
by Max Beran » Sun Aug 28, 2005 2:27 am
Yipee, cripes and other Bunteresque expletives. I’ve done it. If only I’d read Big Blue’s hint more closely and not spent hours searching for a non-repetitive cycle! The elimination that it allows fills a further 6 cells using nothing more complicated than an x-wing. Then it hangs again but is released with an xy-chain of unusual length and curliness (but I’ve checked and re-checked so am 110% confident). Thereafter it rattles through with simple logic so doesn’t require the other Eppstein bilocation techniques at all.
As for the 3 in r2c1, Jacko, it disappears with all the other 3’s in box 1 except the ones in r3 because of the absence of space for a 3 in r3c4-9, ie locked row). So if you didn’t notice that then I wonder at your solution. Perhaps we should share the final solution offline though you can reach it quite easily using Angus programme and forcing a 9 into r9c3 from the layout at the head of this thread (another reason why I know I did it right). Also your comment about the information contained in an error makes me nervous. I’m sure Tso can explain it nicely but what information you can extract from a non-closing chain must depend on whether it’s a blue line or a red line link.
Here’s the URL for Eppstein
http://arxiv.org/PS_cache/cs/pdf/0507/0507053.pdf
posted by Scott H on the Exercise on xyz-wing thread.
As for the 3 in r2c1, Jacko, it disappears with all the other 3’s in box 1 except the ones in r3 because of the absence of space for a 3 in r3c4-9, ie locked row). So if you didn’t notice that then I wonder at your solution. Perhaps we should share the final solution offline though you can reach it quite easily using Angus programme and forcing a 9 into r9c3 from the layout at the head of this thread (another reason why I know I did it right). Also your comment about the information contained in an error makes me nervous. I’m sure Tso can explain it nicely but what information you can extract from a non-closing chain must depend on whether it’s a blue line or a red line link.
Here’s the URL for Eppstein
http://arxiv.org/PS_cache/cs/pdf/0507/0507053.pdf
posted by Scott H on the Exercise on xyz-wing thread.
- Max Beran
- Posts: 57
- Joined: 17 August 2005
by jacko » Sun Aug 28, 2005 9:43 am
Congratulations, Max!
And appologies for the sweats caused by my allusions to an error. I'll bow deeply and accept my failure to see the possibility to eliminate the 3's in r2, box 1&3, I see the light now. The puzzle worked out despite of that oversight, though, but it might have gone a bit faster with less candidates.
I'll send you my solution off-line.
And appologies for the sweats caused by my allusions to an error. I'll bow deeply and accept my failure to see the possibility to eliminate the 3's in r2, box 1&3, I see the light now. The puzzle worked out despite of that oversight, though, but it might have gone a bit faster with less candidates.
I'll send you my solution off-line.
- jacko
- Posts: 4
- Joined: 27 August 2005
by jacko » Sun Aug 28, 2005 2:45 pm
I've been open about the technique I used to solve this puzzle (quoting myself: "trying one of two numbers in a 2 candidate cell until you meet error [meaning getting to a point where two instances of a number in a r, c or box is the outcome]. Error is good, because that means it's the other candidate. Merely meeting an impass [can't get any further], however doesn't prove it's right).
Max now informs me that this method is, by some, called trial and error, and therefore not includable within the spirit of this thread, which is to find logical reasoning that would enable us to deduct why one candidate should be chosen over the other (did I get it right, Max?).
I'll digress, however, and I've since found the method described in Wikipedia's sudoku entry in the paragraph on analylsing: http://en.wikipedia.org/wiki/Sudoku#Construction
Here's their way of saying this: "In the [if-then] approach, a [number in a] cell with only two candidate numbers is selected[. ... The other methods] above are repeated unless a duplication is found, in which case the alternative candidate is the solution. In logical terms, this is known as reductio ad absurdum".
Still in Wikipedia, reductio ad absurdum is defined as a "reduction to the impossible", often used by Aristotle, is a type of logical argument where we assume a claim for the sake of argument, arrive at an absurd result, and then conclude the original assumption must have been wrong, since it gave us this absurd result. This is also known as proof by contradiction. "
This type of logical argument is also used in mathematical logic, where there are some fancy if-then equations: http://en.wikipedia.org/wiki/Reductio_ad_absurdum (then scroll down). I doubt you can use these to solve Sudoku's, though.
In my mind (and you don't have to agree), reduction to the impossible or proof by impossibility are perfectly all right logical alternatives. I'd even add that this is the principle at the base of all logical deductions, including all the basic scanning techniques. It's fine by me if someone wants to call this trial and error, I'll call it an if-then in mathematical terms, or if you prefer a new term, 'deduction in the second degree'.
I've just realized that, especially with this lenghty post, I've just proved Max's point that I'm no help in solving the puzzle with logic-ex-reductio-ad-absurdum. (Anyone wishing to discuss which criteria to include in a logical purist approach should start a new thread).
I'll therefore sign off from this thread now. I'll thank everyone for putting up with an beginner/amateur like me stomping around in a glass house and appologize if anyone was sent off on a wild goose-chase on account of my lack of sudoku-vocabulary and ignorance of protocole pertaining to this thread.
Cheers, Jac
Max now informs me that this method is, by some, called trial and error, and therefore not includable within the spirit of this thread, which is to find logical reasoning that would enable us to deduct why one candidate should be chosen over the other (did I get it right, Max?).
I'll digress, however, and I've since found the method described in Wikipedia's sudoku entry in the paragraph on analylsing: http://en.wikipedia.org/wiki/Sudoku#Construction
Here's their way of saying this: "In the [if-then] approach, a [number in a] cell with only two candidate numbers is selected[. ... The other methods] above are repeated unless a duplication is found, in which case the alternative candidate is the solution. In logical terms, this is known as reductio ad absurdum".
Still in Wikipedia, reductio ad absurdum is defined as a "reduction to the impossible", often used by Aristotle, is a type of logical argument where we assume a claim for the sake of argument, arrive at an absurd result, and then conclude the original assumption must have been wrong, since it gave us this absurd result. This is also known as proof by contradiction. "
This type of logical argument is also used in mathematical logic, where there are some fancy if-then equations: http://en.wikipedia.org/wiki/Reductio_ad_absurdum (then scroll down). I doubt you can use these to solve Sudoku's, though.
In my mind (and you don't have to agree), reduction to the impossible or proof by impossibility are perfectly all right logical alternatives. I'd even add that this is the principle at the base of all logical deductions, including all the basic scanning techniques. It's fine by me if someone wants to call this trial and error, I'll call it an if-then in mathematical terms, or if you prefer a new term, 'deduction in the second degree'.
I've just realized that, especially with this lenghty post, I've just proved Max's point that I'm no help in solving the puzzle with logic-ex-reductio-ad-absurdum. (Anyone wishing to discuss which criteria to include in a logical purist approach should start a new thread).
I'll therefore sign off from this thread now. I'll thank everyone for putting up with an beginner/amateur like me stomping around in a glass house and appologize if anyone was sent off on a wild goose-chase on account of my lack of sudoku-vocabulary and ignorance of protocole pertaining to this thread.
Cheers, Jac
- jacko
- Posts: 4
- Joined: 27 August 2005
56 posts
• Page 2 of 4 • 1, 2, 3, 4
