dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Help with the lingo...

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion
View previous topic :: View next topic  
Author Message
AZ Matt



Joined: 03 Nov 2005
Posts: 63
Location: Hiding under my desk in Phoenix AZ USA

PostPosted: Mon Jun 19, 2006 8:31 pm    Post subject: Help with the lingo... Reply with quote

Code:
0 0 14 18   0 0  0 0 0
0 0 14 1678 0 68 0 0 46

Assume 1 must be in r1 or 2, c4. I can tell from this that r2c4 cannot be 1 because r2c3 would also be 1. Hence r1c4=1, and the puzzle crumbled from there.

Please tell me what this solving technique is called?
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Mon Jun 19, 2006 10:42 pm    Post subject: Not enough information Reply with quote

Hi, Matt!
Code:
0 0 14 18   0 0  0 0 0
0 0 14 1678 0 68 0 0 46


From the fragment you posted, I can see that placing a "1" at r4c2 forces a contradiction, although I tend to look at it this way.

A. r2c4 = 1 ==> r2c3 = 4 ==> r1c3 = 1 ==> r1c4 = 8
B. r2c3 = 4 ==> r2c9 = 6 ==> r2c6 = 8

Since we can't have two "8"s in one 3x3 box, we can be sure that r2c4 <> 1.

In general, a chain of inference that forces a contradiction is called a "forcing chain." If we split it into two pieces as I did above, we might also call it a "double-implication chain." dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
AZ Matt



Joined: 03 Nov 2005
Posts: 63
Location: Hiding under my desk in Phoenix AZ USA

PostPosted: Tue Jun 20, 2006 6:02 pm    Post subject: Thanks David! Reply with quote

Thanks David. I hope you are feeling better!


I wanted to make sure this technique is what is referred to as "forcing chains." I use this technique to solve all the time (this solved last Wednesday's Ruud's Daily Nightmare, though don't quote me on the exact numbers as I did the post here from a vague memory of the pattern).

I can't possibly understand why it is not considered a valid technique for solving. You have a finite set of cells from which you can deduce information with a certainty. Sometimes you only eliminate one candidate in one cell, and sometimes you solve for large groups of cells (I think 21 is my record, though only a few were critical to the solve), but it is always an outcome that is certainly correct before you commit to it.

I suppose one could argue that if you could see the whole puzzle this way, you could solve every puzzle from any point with a complicated variation of this technique. Is that the gist of the objection? If so, I don't think it is valid. I know when I pull the cells out to study them that I am going to find something -- if you can do that in your head for a whole puzzle, then God bless you.

I have been "out of the loop" for quite a while, so forgive me if I am beating a dead horse. In response to Samgj's response to my post on the "Very Hard Ugrade???", I am curious if I am in with the "masses" or the "hardcore" on this.
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Sat Jun 24, 2006 1:00 pm    Post subject: Reply with quote

AZ Matt,

Quote:
I can't possibly understand why it is not considered a valid technique for solving.


There are a variety of grounds on which people object to forcing chains. The first thing that 'non-believers' ask is "What logic made you start the chain in 'that' particular cell as if to imply that if there is no logical reason to start in that cell, then the whole sequence is invalid.

Another is that forcing chains don't fit a pre-defined pattern, which most/many of the other solving techniques do, so there is no pre-defined proof behind the logic of any particular chain. Each chain must be proven as it occurs: that proof often starts out like "Assume that 1 must be in..." To a lot of people that sounds like a guess.

Another is that the logic behind longer forcing chains is not easily followed in the mind. It's pretty easy to spot and follow the logic of an xy-wing, which is just a short (3 cell) forcing chain, but much harder to do for a chain that is 8 cells long.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

PostPosted: Sat Jun 24, 2006 4:47 pm    Post subject: Reply with quote

I've been at this for about six months now and have relied heavily on forcing chains; they've been my "go-to" method. I've participated in the trial-and-error discussions and argued that forcing chains are logic as well as other techniques.

But after thinking about it over the last couple of months, I've come to understand that the people who think they're trial-and-error have some valid points. I now am not quite as quick to use the chains. I'll look first for strong links, X-Wings, coloring, etc. But if there's nothing there, I have no qualms about using the chains.

I love doing these puzzles, but let's face it: Sudoku is not up there with world peace, poverty, crime, health care, etc. It's only a game and for me, if I can find a way to solve a difficult puzzle, with or without chains, I'm happy.

Quote:
Another is that the logic behind longer forcing chains is not easily followed in the mind. It's pretty easy to spot and follow the logic of an xy-wing, which is just a short (3 cell) forcing chain, but much harder to do for a chain that is 8 cells long.


Tracy, it's not very difficult when one uses blank grids to write down the chain's effects. I use the blanks supplied on this site, the one that's six to a page, for this purpose.
Back to top
View user's profile Send private message
Chuck B



Joined: 24 Jun 2006
Posts: 24

PostPosted: Mon Jun 26, 2006 1:33 pm    Post subject: Reply with quote

Interesting discussion!

Like Marty, I've been doing this for a little while and also go to forcing chains when necessary. (in my case, when the hints run out! Wink )

This technique is akin to 'proof by contradiction' in mathematics, and its validity derives from the 'law of the excluded middle' , i.e., the proposition that an assertion must be bivalent - true or false, with no other possibility. Some mathematicians object to that 'law' and eschew proofs by contradiction (check out N. Bourbaki), but it does make some theorem proofs easier! Anyway, in a finite 'universe of discourse such as a Sudoku puzzle, every assertion about a cell must be bivalent, so proving one of those assertions by contradiction - i.e., forcing chains - is logically sound.

I think that Nishio goes hand in glove with this technique to eliminate dead ends... it's basically a tree search, which can be as messy or as orderly as the solver wishes to be.

IMHO, arguments against either technique are based on aesthetics more than logic, and grounded in the natural 'feel' of a sighted species for visual cues. We usually associate beauty with pleasing geometric structure but, as in math, there is also a kind of abstract beauty in logical structures that cannot be pictured literally. Implication chains fall into that category for me, and their attractiveness lies in structure that transcends geometry, even though it triggers the same kind of right-brain activity in me. Finding one might not be as much 'fun' (to some) as an XY-wing, but there can be just as much sense of accomplishment in solving the puzzle through these techniques.

Anyway, that's my take on it. YMMV, naturally! Smile

Cheers!
Chuck
Back to top
View user's profile Send private message
AZ Matt



Joined: 03 Nov 2005
Posts: 63
Location: Hiding under my desk in Phoenix AZ USA

PostPosted: Thu Jul 06, 2006 11:29 pm    Post subject: Reply with quote

Just to be clear to TKiel; by saying "Assume that 1 must be in...", I didn't mean to imply I was guessing. It was just a way to shorten the code -- i.e., it was true, I just wanted you to trust me for the sake of simplicity.

And as Chuck B suggested, I use those grids a lot. And no matter how much some one tries to convince me it is trial and error, it isn't. Like I said, I know when I start a grid I am going to find something. I have to work on a way to describe it -- an imbalance? an anomaly?
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Fri Jul 07, 2006 1:01 am    Post subject: Reply with quote

AZ Matt,

I'm a believer in the logic of forcing chains, even though I'm not too much of a user, so no need to explain your wording. I was trying to point out some of the objections I've heard others make about whether or not forcing chains should be considered T&E and that's why I used your quote as an example. A monkey can be trained to recognize patterns and pick them out of a puzzle but to take something that is merely a concept and apply it to a particular puzzle in such a way that makes a proof seems to me to be the essence of logic.

Well, I'm off the pick fleas off my mate, climb trees and eat bananas.
Back to top
View user's profile Send private message
George Woods



Joined: 28 Mar 2006
Posts: 304
Location: Dorset UK

PostPosted: Thu Jun 07, 2007 3:29 pm    Post subject: xy chains Reply with quote

In the example that started this discussion, the elimination of the 1 was described as a forcing chain.

Many forcing chains can be turned into what I think is an XY chain. specifically for the example 14-46-68-81. I consider this as a "pure" chain since it consists of strongly linked doublets (XY). a pure XY wing is an XY chain with only 3 elements e.g. if the 68 had been 48 we would have the shorter chain 14-48-81 which is a pure xy wing.

The difficulty for me arises either if the chain is very long or when the chain is kept going via some of the other forms of strong linking e.g. an 8 in col8 of box3 means the 8 in box 9 must lie in such and such a cell and so on!

Doing it by trial and error seems to be the most unloved method. It can be fun though, searching for the failed case and trying to find the shortest forcing chain - I suppose ultimately trial and error allows any soluble sudoku to be solved given enough time - and an effective eraser!

For me the test of "trial and error"or " clever logic" is whether I can see it without using a pencil!
Back to top
View user's profile Send private message
ukodus



Joined: 02 Aug 2008
Posts: 2
Location: London

PostPosted: Sat Aug 02, 2008 9:42 pm    Post subject: General Discussion Reply with quote

Commenting on the factors that do not appeal in the apparent trial and error nature of forcing chains, or in looking for the shortest chain, I am reminded of those quadratic equations in algebra in which you tried various [from a limited set of] combinations before getting to the right factors for the particular expression, e.g. to establish that 2x+4y and -6x+10y are the factors of -12x² - 4xy - 40y², you will probably try a few combinations before you get there. I have never worked much with forcing chains in sudoku, but am about to give it more of a try.
This is my first posting here, and I wonder whether any more experienced sudoku-ists have posted some sort of handbook here not only on the language & terminology used, but also on how you move into solving the more fiendish levels of puzzles, out of what might be called the more 'amateur' levels, that I feel I'm sticking my head up out of (!) at last.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

PostPosted: Sun Aug 03, 2008 12:08 am    Post subject: Reply with quote

Welcome to the forum.

Maybe this terminology list will be helpful.

http://www.sudopedia.org/wiki/Terminology
Back to top
View user's profile Send private message
ukodus



Joined: 02 Aug 2008
Posts: 2
Location: London

PostPosted: Sun Aug 03, 2008 9:10 pm    Post subject: Lingo & Terminology Reply with quote

Thanks for the sudopedia link, Marty. At first glance I think it'll keep me busy!
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion All times are GMT
Page 1 of 1

 
Jump to:  
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