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

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


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 


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

Posted: Mon Jun 19, 2006 10:42 pm Post subject: Not enough information 


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 "doubleimplication chain." dcb 

Back to top 


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

Posted: Tue Jun 20, 2006 6:02 pm Post subject: Thanks David! 


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 


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

Posted: Sat Jun 24, 2006 1:00 pm Post subject: 


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 'nonbelievers' 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 predefined pattern, which most/many of the other solving techniques do, so there is no predefined 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 xywing, 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 


Marty R.
Joined: 12 Feb 2006 Posts: 5766 Location: Rochester, NY, USA

Posted: Sat Jun 24, 2006 4:47 pm Post subject: 


I've been at this for about six months now and have relied heavily on forcing chains; they've been my "goto" method. I've participated in the trialanderror 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 trialanderror have some valid points. I now am not quite as quick to use the chains. I'll look first for strong links, XWings, 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 xywing, 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 


Chuck B
Joined: 24 Jun 2006 Posts: 24

Posted: Mon Jun 26, 2006 1:33 pm Post subject: 


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! )
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 rightbrain activity in me. Finding one might not be as much 'fun' (to some) as an XYwing, 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!
Cheers!
Chuck 

Back to top 


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

Posted: Thu Jul 06, 2006 11:29 pm Post subject: 


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 


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

Posted: Fri Jul 07, 2006 1:01 am Post subject: 


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 


George Woods
Joined: 28 Mar 2006 Posts: 300 Location: Dorset UK

Posted: Thu Jun 07, 2007 3:29 pm Post subject: xy chains 


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 14466881. 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 144881 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 


ukodus
Joined: 02 Aug 2008 Posts: 2 Location: London

Posted: Sat Aug 02, 2008 9:42 pm Post subject: General Discussion 


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 sudokuists 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 


Marty R.
Joined: 12 Feb 2006 Posts: 5766 Location: Rochester, NY, USA


Back to top 


ukodus
Joined: 02 Aug 2008 Posts: 2 Location: London

Posted: Sun Aug 03, 2008 9:10 pm Post subject: Lingo & Terminology 


Thanks for the sudopedia link, Marty. At first glance I think it'll keep me busy! 

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
