| View previous topic :: View next topic |
| Author |
Message |
samgj
Site Admin
Joined: 17 Jul 2005
Posts: 106
Location: Cambridge
|
 Posted: Mon Jul 18, 2005 9:29 pm Post subject: The logic argument |
 |
|
What's all the argument about solving Sudokus using logic alone?
This question has caused much discussion in forums and web pages. In particular, long distance arguments between the creators of the Times and Daily Telegraph Sudoku puzzles have become unfortunately heated. Read some of these discussions in the following places:
The choice then is whether a puzzle can be completed in its entirety without resorting to "trial and error". The confusion stems partly from the use of this term -- perhaps a better term would be that used by Mike Mepham of the DT puzzles: bifurcation. Whatever the terminology, I take the need for "trial and error" to mean that at some point in the solving of thepuzzle it is not possible to say with absolute certainty that a particular number must go in a particular cell without testing one of several options, following a path until the puzzle either completes or fails, and backing up to try another option. This approach could just as validly be considered a chess-like look-ahead, and as such is clearly "logical". The Times puzzles never require bifurcation, DT puzzles often do.
Personally, I'm with Wayne Gould of the Times. Daily Sudoku puzzles can always be solved in a forward direction, with no bifurcation or trial and error. However, it is important to note that this is simply a choice on my part and it is unreasonable to claim that this is better than any other way. My reason for this choice though is fairly easily explained: While completing a puzzle, I like to know that there is always a logic step to find. When I get stuck, I know that if I hunt enough (and if I am clever enough) I can always move forward. If I can't guarantee this, then when I get stuck, it is too tempting to resort to the "trial and error" approach, which to me is time-consuming, but not especially intellectually challenging.
But choice is a good thing. If you like the bifurcation approach, take a look at Mike Mepham's puzzles (http://www.sudoku.org.uk/). If you don't then the Daily Sudoku is for you. Please don't claim however that one way is right and the other is wrong.
Sam |
|
| Back to top |
|
 |
Guest
|
| Posted: Thu Jul 21, 2005 9:38 am Post subject: Sun 29 May 2005 |
|
|
Hi,
Unless I'm mistake (which could be entirely possible), the Daily Sudoku puzzle from 29 May 2005 can't be solved without trial and error. If I'm right, then your statement that the Daily Sudoku puzzles are never "trial and error" is wrong. 
Tom. |
|
| Back to top |
|
|
Bampah
Joined: 21 Jul 2005
Posts: 1
Location: Poole, England
|
| Posted: Thu Jul 21, 2005 3:39 pm Post subject: Re: Sun 29 May 2005 |
|
|
| Anonymous wrote: | Hi,
Unless I'm mistake (which could be entirely possible), the Daily Sudoku puzzle from 29 May 2005 can't be solved without trial and error. If I'm right, then your statement that the Daily Sudoku puzzles are never "trial and error" is wrong.
Tom. |
Sorry Tom
You are mistaken. May 29th is solveable by logic alone. Nothing more sinister than 'hidden pairs' to contend with.
 |
|
| Back to top |
|
|
Seedr
Guest
|
| Posted: Fri Jul 22, 2005 6:24 pm Post subject: They're wkd! |
|
|
Hey love sudoku's they're great, I don't have a single problem with them, and they've given me something decent to by my dad at christmas and birthday's!!
Keep up the work!!  |
|
| Back to top |
|
|
Guest
|
| Posted: Sat Jul 23, 2005 11:23 pm Post subject: Re: The logic argument |
|
|
| samgj wrote: | What's all the argument about solving Sudokus using logic alone?
This question has caused much discussion in forums and web pages. In particular, long distance arguments between the creators of the Times and Daily Telegraph Sudoku puzzles have become unfortunately heated. Read some of these discussions in the following places:
The choice then is whether a puzzle can be completed in its entirety without resorting to "trial and error". The confusion stems partly from the use of this term -- perhaps a better term would be that used by Mike Mepham of the DT puzzles: bifurcation. Whatever the terminology, I take the need for "trial and error" to mean that at some point in the solving of thepuzzle it is not possible to say with absolute certainty that a particular number must go in a particular cell without testing one of several options, following a path until the puzzle either completes or fails, and backing up to try another option. This approach could just as validly be considered a chess-like look-ahead, and as such is clearly "logical". The Times puzzles never require bifurcation, DT puzzles often do.
Personally, I'm with Wayne Gould of the Times. Daily Sudoku puzzles can always be solved in a forward direction, with no bifurcation or trial and error. However, it is important to note that this is simply a choice on my part and it is unreasonable to claim that this is better than any other way. My reason for this choice though is fairly easily explained: While completing a puzzle, I like to know that there is always a logic step to find. When I get stuck, I know that if I hunt enough (and if I am clever enough) I can always move forward. If I can't guarantee this, then when I get stuck, it is too tempting to resort to the "trial and error" approach, which to me is time-consuming, but not especially intellectually challenging.
But choice is a good thing. If you like the bifurcation approach, take a look at Mike Mepham's puzzles (http://www.sudoku.org.uk/). If you don't then the Daily Sudoku is for you. Please don't claim however that one way is right and the other is wrong.
Sam |
You contradict your own site AND you conflate different tactics, thus putting a stink on many solving techniques.
1) I put several puzzles, all of which were difficult but that I had solved by hand, none of which required me to use "trial and error", "bifurcation" or "proof by contradiction" by did require logical tactics beyond what your hardest puzzles require into your solver and got this message:
"This puzzle is not solvable using logic alone. It may require trial and error, have more than one solution, or have no legal solution."
So many things wrong here. You say we should have choice, but this statement claims that the puzzles are invalid, not distinguishing them from a blank grid or one filled with 9s. That statement does NOT say "to each his own" -- it says, we're wrong, our puzzles are not puzzles, we don't use logic, we're guessing, etc. It should say: "This puzzle is more difficult than our software can handle." or "Tactics such as conditional if-then statements may need to be considered by some solvers in this puzzle." or something more truthfull.
Those of us arguing for higher logic methods have been confounded by the other side -- your side -- seemingly unable to distinquish from a simple "if this, then this" conditional statement and "I'll just take a random guess, fill it in, and see if it fits." I don't think you understand that we take it as an insult, that what we are doing isn't logic, it's cheating. Wayne claims in various places that "bifurcation" is wrong both because it's too easy and because it's too hard, depending on who he's talking to.
Simple constructions like:
| Code: |
12 . . | 13 . . | . .
23 . . | 34 . . | . .
. . . | . . . | . . .
r1c1=1 => r1c4=3 => r2c4=4
r1c1=2 => r2c1=3 => r2c4=4
Therefore, r2c4=4
|
... are basic, simple logic. They are not allowed in Pappocom puzzles because "humans cannot solve them and it isn't fun".
Well, I CAN solve them and the ARE fun. Your side seem to think that if we can identify the patteren and give it a name, then it's OK to use, then it's "logic". You go to the ??, you look through your recipe book. If you can't find one for roast chicken, you'll have to order in. Me -- I just go to the ?? and cook. I have no collection of recipes, only a collection of skills. I'll make it up as I go along, depending on what's in the fridge and what I'm in the mood for. But I'm a cook. Anyone can follow a recipe -- but would the disparage cooks, claiming that if you don't follow a recipe, you're not really cooking?
Compare and contrast the above tactic with this:
In both situations, the only way we can deduce that the cell with candidates 34 is a 4 is by considering ALL THREE OTHER CELLS AT ONCE. There is no reasonable logical argument for accepting one and not the other. Expanding, compare these two:
| Code: |
12 . 23|34 .56 |16 .67
. . . | . . . | . . .
. . . | . . . | . . .
|
| Code: |
12 . . | . . . | . . .
. .13 | . .46 |34 . .
46 . . |67 . . | . . .
-------+-------+------
34 . . | . . . | . . .
. . . | . . . | . . .
23 . . | . . . | . . .
|
In each case, the information from ALL marked cells is required to prove the contents of the cell with the candidates "67". There is no logical reason to accept on chain of reasoning and deny the other. One cannot say -- well, it's just too hard for me, so it's trial and error, it's guessing, it's cheating, it's look ahead.
Every move over your eyes across a partially solved grid is a guess! The only person for whom this is NOT the case is someone who follows a rigid sequence of algorthms -- check the 1s, 2s, 3s... check the rows, columns, ... check for hidden pairs, triples ... etc. And for her, other tactics including, but not limited to, forcing chains, proof by contradiction CAN BE BUILT IN AS WELL.
The destinction is absolutely arbitrary and it is NEVER made by anyone who has the least training in logic.
This thinking would relegate the Raymond Smullyan's entire career of logic puzzle creation as failure, since the vast majority of his puzzles must be solved by conditional deductions -- "If she were a Knave, she would lie about what her sister said and say "east" ... etc."
I've been solving puzzles since I was a child. I have a small library of books of logic puzzles -- Martin Garnder, Dudney, Smullyan, many more. I have stacks of Japanese, Dutch and English puzzle magazines and books. I have all of the World Puzzle Competition material. I've never read anywhere, anyone making the rediculous comment "This puzzle cannot be solved by logic." -- until Wayne Gould, a person with no expertise or even much experience in the field, proclaimed it. And because he imported the puzzle, the press looks to him as an authority, and the dumbing down begins. No wonder they advertise -- "no math required" -- which is of course, not true, as logic IS a branch of mathematics. What they mean is no "arithmetic" required -- because everyone is so eager to brag how they're no good at math.
Look, feel free to aviod harder puzzles. (They're not really always harder, just different. Often, the last step, the combining of conditional statements that tips over all the dominos, is by far, the most satisfying moment of the puzzle.) Those on our side do NOT begruge you this. But Wayne and his ilk -- you included -- DO begruge us the same. Even if you DON'T declare our puzzles "invalid" as Wayne does, the actions you and others take have effectively formed created a status-quo that the majority of publishers and software writers feel presured to follow.
If Wayne had brought the Rubik's cube to England, it would probably be only 2x2x2, because we all know, the 3x3x3 is "invalid, too difficult and no fun." |
|
| Back to top |
|
|
samgj
Site Admin
Joined: 17 Jul 2005
Posts: 106
Location: Cambridge
|
| Posted: Mon Jul 25, 2005 6:13 pm Post subject: Re: The logic argument |
|
|
| Anonymous wrote: |
Those of us arguing for higher logic methods have been confounded by the other side -- your side -- seemingly unable to distinquish from a simple "if this, then this" conditional statement and "I'll just take a random guess, fill it in, and see if it fits." I don't think you understand that we take it as an insult, that what we are doing isn't logic, it's cheating. Wayne claims in various places that "bifurcation" is wrong both because it's too easy and because it's too hard, depending on who he's talking to.
|
Well I agree with most of your points, but your slightly aggressive talking about "your side" forces me to be more defensive than I'd like. Your complaints seem to be mostly against Wayne Gould. I don't mean to suggest that I believe in everything he does -- I don't! (I find his assertion that his puzzles are better than everyone else's a little unpleasant.) In the first post in this topic, I was talking specifically about the need to try one of two or more options, and only finding out if it is right or not when the puzzle completes or is found to be unsolvable. This is what I understand and mean by "trial and error" or "bifurcation" -- but I may be misusing both terms. I don't find that this is a fun way to complete puzzles, and therefore don't intend to require this approach in solving my puzzles. But of course the sudoku-er is free to use any tactics they like to get a solution. Indeed, anyone past absolute beginner uses logical approaches far in advance of the difficulty of thought actually required to take the easiest path through.
The examples you present are clearly not trial and error, and not using these types of approaches is an oversight, not a policy decision. When days contain 30 hours, I'll get to dealing with such things. The misleading message on my "draw" thing is an annoying consequence of the slightly dumb way this is implemented, meaning that it currently can't tell the difference between cases it clearly should be able to.
| Anonymous wrote: |
Even if you DON'T declare our puzzles "invalid" as Wayne does, the actions you and others take have effectively formed created a status-quo that the majority of publishers and software writers feel presured to follow.
If Wayne had brought the Rubik's cube to England, it would probably be only 2x2x2, because we all know, the 3x3x3 is "invalid, too difficult and no fun." |
I don't find this argument reasonable. As far as I'm concerned, he is able to do whatever he likes with the puzzles he creates, and I should be free to create puzzles with any characteristics I wish. You of course are entitled to invest time in making puzzles with your favourite characteristics. I agree calling other people's puzzles "invalid" is objectionable -- for my offence in this regard I apologise and will re-word until I get a chance to fix properly.
Sam |
|
| Back to top |
|
|
Anonymous/Chuck
Guest
|
| Posted: Tue Jul 26, 2005 1:25 am Post subject: |
|
|
samgj,
Thanks for your response. We're in agreement for the most part, including that my tone should have been less strident. I appreciate the changes you made to the "draw" page.
Good luck. |
|
| Back to top |
|
|
Guest
|
| Posted: Thu Jul 28, 2005 10:16 pm Post subject: |
|
|
| Code: |
...74...5
...26971.
...53.9..
3..4126..
.1.975.3.
..73861.2
.35.97...
.89154...
4...235..
|
|
|
| Back to top |
|
|
Guest
|
| Posted: Thu Jul 28, 2005 10:23 pm Post subject: |
|
|
| Code: |
...74...5
...26971.
...53.9..
3..4126..
.1.975.3.
..73861.2
.35.97...
.89154...
4...235..
|
sorry, clicked on 'submit' too soon!
I wrote a program to solve sudoku puzzles, and the today's puzzle gets solved up to the situation above, and then the program gets stuck - there is no obvious place to put a new digit.
Then, when I enter this set into the 'sudoku drawer' table on your site, and ask for a hint, the site suggest putting an 8 in the fourth row, third column, resulting in the following set:
| Code: |
...74...5
...26971.
...53.9..
3.84126..
.1.975.3.
..73861.2
.35.97...
.89154...
4...235..
|
why is this hint suggested - this location is not the only possible location for an 8 in this row, column or square?
Does this mean that this pussle needs to be solved by trial and error approach?
TIA! |
|
| Back to top |
|
|
Ian
Guest
|
| Posted: Fri Jul 29, 2005 5:39 pm Post subject: |
|
|
Row four already contains 1, 2, 3, 4 and 6.
Column three already contains 5, 7 and 9.
Therefore the only number that can go where they intersect is 8.
Not too difficult! |
|
| Back to top |
|
|
Guest
|
| Posted: Fri Jul 29, 2005 6:19 pm Post subject: |
|
|
| Ian wrote: | Row four already contains 1, 2, 3, 4 and 6.
Column three already contains 5, 7 and 9.
Therefore the only number that can go where they intersect is 8.
Not too difficult! |
Ah, I never thought of this aspect of it - makes perfect sense of course.
Thanks a lot! |
|
| Back to top |
|
|
diane
Guest
|
| Posted: Wed Aug 03, 2005 6:55 am Post subject: sudoku logic |
|
|
I always use what I consider to be logic to solve all of your puzzles and they all solve quite nicely. I find that if I am having a problem it is because I have overlooked something. I never have to resort to guessing and like you, Samgi, I don't want to do a puzzle where i would have to guess. Thank so much for your daily Sudoku. And yes I like the very hard ones the best
Diane |
|
| Back to top |
|
|
Guest
|
| Posted: Tue Aug 30, 2005 7:55 pm Post subject: |
|
|
| I agree with Diane. I have been doing these puzzles for quite a while now, and have NEVER had to resort to "guessing" to solve them. I am by no means a mathemetician, but the hardest puzzles make me resort to finding logical decisions to finding a solution. If I have to "guess", I put the puzzle down for a while then come back and as I have realized something I have overlooked or new methods to solve. Thanks for a great site. |
|
| Back to top |
|
|
grgr
Guest
|
| Posted: Tue Sep 13, 2005 1:50 pm Post subject: Isn't swordfish/open chains a bifurcation? |
|
|
| You use green/blue to mark two different outcomes and exclude the squares which do not follow either of the scenarios... |
|
| Back to top |
|
|
Guest
Guest
|
| Posted: Tue Oct 25, 2005 7:53 pm Post subject: |
|
|
 I am fairly new to Sudoku, but I have been solving "fiendish" and "diabolical" etc. puzzles (including many that the draw function here labels unsolvable -- which is explained in this string) using what I consider to be only logic, and I find this string fascinating. Here is my observation, and I would like someone to explain how I am wrong (as I know I probably am).
I have never come across a puzzle where I could not solve a cell without having to go to all the way to the end of the puzzle by trial and error. I have had to (and I am now using my own lexicon ) "go out 14 cells," for example, which to me means looking at all the candidates and "exclusives" in 14 cells to ultimately solve for one. In many ways this resembles what some seem to be referring to as trial and error, but it's not. The whole argument seems to come down to how far "out" (if a is x then b is yz then c is yz, etc) one has to go to solve a particular puzzle. This seems arbitrary.
I would also note that I have found numerous puzzles that purport to be examples "advanced" solving techniques, when they really are not. There is often an opportunity to use the technique, but it wasn't critical to solving the puzzle. Many times a purported "hidden quadruple" is really just a hidden pair=naked single in an otherwise barely solved set. And I haven't found any purported "forcing chains" that didn't have a simpler, alternative solve (albeit I am only talking about 4-5 examples here).
Have I just run a streak of coincidence? Or am I actually using those techniques (perhaps in multiple ways) that I am not recognizing?
Or am I an amateur nutcase? |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Tue Oct 25, 2005 11:34 pm Post subject: Look-ahead logic |
|
|
| guest wrote: | Have I just run a streak of coincidence? Or am I actually using those techniques (perhaps in multiple ways) that I am not recognizing?
Or am I an amateur nutcase? |
All of the above?
I agree with you that the people who criticize "trial and arror" are being imprecise in their thinking. Every move in a Sudoku puzzle involves some degree of looking ahead, and the question is how much.
I'm curious what you'll have to say about this puzzle:
400 000 001
080 400 000
000 000 000
000 700 850
001 900 000
200 000 000
030 006 080
600 010 400
000 020 000
Have a great day! dcb |
|
| Back to top |
|
|
Guest again
Guest
|
| Posted: Thu Oct 27, 2005 9:12 pm Post subject: Thanks David |
|
|
 I thought I was right, or at least I now agree with you, and that excellent puzzle proves it; it is "all of the above." By my method, I consider that a logical solve, and it goes out 15 logically related cells (you can see that if you solve for one, you solve for all) containing 7 matched pairs and 2 two-number exclusive cells (two matched pairs share a cell), all by seeing how two cells must interact to solve for the rest. It's cake after that. Beautiful...
I also now see that it can be solved by seeing the xy-wing eliminating the 3 in... I won't spoil it for others. Damn, I was kind of hoping there wasn't a traditional "advanced technique" that solved the puzzle.
In any event, I like the way I solved it a lot better. You can solve the whole puzzle all at once. And I insist it is logical -- though I'd entertain the notion that there is a little art to it.
Thanks again. (Got any more?) |
|
| Back to top |
|
|
Guest again PS
Guest
|
| Posted: Thu Oct 27, 2005 9:27 pm Post subject: |
|
|
| PS: I see someone posted as "Guest" earlier in this string. It is not me. I should have used a different username. |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Thu Oct 27, 2005 9:47 pm Post subject: Don't thank me -- thank someone_somewhere |
|
|
| Guest again wrote: | | Thanks again. (Got any more?) |
You're welcome. But I'm not the one who brought that puzzle to this forum -- thanks are due to someone_somewhere, a prolific poster on this site. Oh -- I have to admit, I used the "XY-Wing" to get through to the end of that one. I can't see as far ahead as you can, apparently.
You can find quite a few excellent puzzles in the "Other puzzles" section of this forum. And if you send a private message to someone_somewhere (just hit the PM button that appears on one of his posts) he'll probably be glad to send you a few real tough ones.
Here's one I particularly liked:
| Code: | 050400000
000030800
000000001
300080700
060000050
000200000
000506040
108000300
000000000 |
Have a great day! dcb |
|
| Back to top |
|
|
Guest Again (Matt)
Guest
|
| Posted: Thu Oct 27, 2005 11:54 pm Post subject: |
|
|
I was hoping you posted it because of the 15 cell solve. Never mind. It is just an x-y wing, but it does solve 15 cells (see below, * means it doesn't matter what's in that cell).
To get to this information is fairly easy:
r2 = *****{35}***
r3 = {35}****{35}***
r5 = {38}{57}**{58}****
r6 = *{57}{38}*{58}***{37}
r8 = **{58}{38}*****{35}
r9 = {58}**{38}*****
So you know from looking at this that if you solve one, you solve all. And there is an imbalance -- there is a non-repeating pair and two "unlinked" cells (naked pairs). If there wasn't, there would be no reason to look at the puzzle this way because you would know that you can't solve anything. So the key to the solve is in the 37 and 35 in column 9, and you can see that if you had a seven in r6c9, you'd have to have two 5s in r8.
Again, as I see now this is just a back door x-y wing -- you can rule out the 3 in r6c9 that way using just the information in rows 6 and 8. But it felt good. And this approach worked for me with a puzzle that had multiple naked and hidden triplets involving linked numbers, and I think, but can't say for sure, that there was no x-y wing in that puzzle. To bad I threw it away -- I din't know it was potentially unique. If I find one like it, I'll pass it along... |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
