To be honest I have never quite understood why many of the regulars here consider Forcing Chains as an inferior technique compared with X-Wing, Fishes or ALS. In my opinion every technique you use for solving Sudokus is based on contradiction and the question “is it possible that cell A contains candidate x?”. Even a naked single is the only logical solution as any other candidate would lead to a contradiction. As RW pointed out “Forcing Chains is the mother of all techniques”, and I think he is right. According to my experience there is not one elimination you can find by other techniques which you could not find by a forcing chain. I admit that by other techniques you often an easier solution/elimination, but the result is (obviously) not any better.
In my opinion any (solvable) Sudoku can be solved by the following formula, and I am sure there is no technique which is superior to this simple approach.
"If a cell A contains two candidates a and b and if the assumption that a in A is right leads to the elimination of b in a cell B that can be seen by A, then B does not contain b."
For Sudokus without any bivalue-cell (which is rarely the case) the formula has to be extended
"If a cell A contains three candidates abc and if the assumption that a or b in A are right leads to the elimination of c in a cell B that can be seen by A, then B does not contain c."
Kind regards
9x9
Forcing Chains
Forcing Chains
by Neunmalneun » Sat Mar 17, 2007 1:35 pm
- Neunmalneun
- Posts: 52
- Joined: 22 December 2005
by sirdave » Sun Mar 18, 2007 1:33 am
But, think for a moment what the difference is between eliminating a candidate with an X-Wing vs. a double-implication forcing chain. In the case of the former, the X-Wing is a pattern that is sitting there to be seen and the candidate-removal is a done-deal. On the other hand, in the case of the latter (forcing chain), you will have to do a little bit of guess-work to find starting and destination cells that will work. This subject has been discussed ad-nauseum already and I think that the consensus is that any of the higher-level pattern-solving methods are not directly (and most of them not even indirectly) looking for contradictions.
Also, in the end, it's all about solving elegance. One of the things that has made Sudoku so much fun is the development of all these higher-level, pattern-based solving methods that can break the most difficult puzzles. Of course, one can decide that they will use nothing but nice loops and forcing chains and they will probably be able to solve most puzzles that way, but what a bore that would be, not to mention tedious.
Perhaps an analogy (albeit a poor one) can be found in computer programming. One can decide to program in C++ or even Basic which will result in far more efficient and portable programming. Or one can decide to program only in machine language which will result in tedium, boredom and a very lonely life ('cause noone wants to talk about machine language these days).
But, just so there is no misunderstanding, forcing chains (and, Heaven-knows, nice loops) have their place. It just that they involve getting down and a little dirty in the solving process- something that continues to be absolutely necessary in puzzles that are diabolical and beyond!
Also, in the end, it's all about solving elegance. One of the things that has made Sudoku so much fun is the development of all these higher-level, pattern-based solving methods that can break the most difficult puzzles. Of course, one can decide that they will use nothing but nice loops and forcing chains and they will probably be able to solve most puzzles that way, but what a bore that would be, not to mention tedious.
Perhaps an analogy (albeit a poor one) can be found in computer programming. One can decide to program in C++ or even Basic which will result in far more efficient and portable programming. Or one can decide to program only in machine language which will result in tedium, boredom and a very lonely life ('cause noone wants to talk about machine language these days).
But, just so there is no misunderstanding, forcing chains (and, Heaven-knows, nice loops) have their place. It just that they involve getting down and a little dirty in the solving process- something that continues to be absolutely necessary in puzzles that are diabolical and beyond!
- sirdave
- 2010 Supporter
- Posts: 36
- Joined: 04 January 2006
Re: Forcing Chains
by ravel » Sun Mar 18, 2007 6:21 pm
Not the hardest (see e.g. here).Neunmalneun wrote:In my opinion any (solvable) Sudoku can be solved by the following formula, and I am sure there is no technique which is superior to this simple approach.
- ravel
- Posts: 998
- Joined: 21 February 2006
by _m_k » Mon Mar 19, 2007 12:43 pm
Some comments on contradiction chains.
1. It is absolutely necessary because not all puzzles can be solved using widely known "pure" solving techniques.
2. Along the same line, it is not possible to prove that any given puzzle can be solved by such techniques. On the other hand it is easy to prove that all puzzles can be solved by contradiction chains if recursion is allowed. However, I know that recursion is not so desirable.
3. Depth of recursion will be reduced if some solving techniques are employed in addition to the basic elimination. Typically, I prefer to include only hidden singles, because with this I can solve most puzzles without any recursion or with at most two level recursion.
4. Contradiction chains (without recursion) are always the simplest way to explain why certain candidates can be eliminated from particular cells. The simpler, the best. Unfortunately, there are many situations where some complicated "pure" techniques will be able to eliminate some candidates from some cells, while contradiction chains cannot do the same without recursion.
5. There is a reason why contradiction chains are powerful tools for solving the puzzles. In mathematics, all advanced theorems can be proven only by the contradiction method.
Theorem: If P, then Q.
Direct proof: Assume P, and get Q.
Indirect proof: Assume not Q, and get not P.
Contradiction: Assume not (if P, then Q) [i.e. assume P and not Q], and get a contradiction (such as 1 = 2).
The reason is obvious. If you can assume two things at the beginning (P and not Q as opposed to P alone or not Q alone), it is 100 times easier to start proving anything. Of course, getting a contradiction is not an easy matter.
Note: If you remember "not (if P, then Q) = P and not Q", some day you may look smarter than all others because they think that "not (if P, then Q) = if not P, then not Q".
6. I have some problem with Neunmalneun's statement: "If a cell A contains two candidates a and b and if the assumption that a in A is right leads to the elimination of b in a cell B that can be seen by A, then B does not contain b." From my own experience, when I start a chain, often I end up with some empty cell (no possible candidates), which is a contradiction. So I prefer to modify his statement as follows: "If a cell A contains two candidates a and b and if the assumption that a in A is right leads to a contradiction, then A does not contain a." This covers all cases.
M.K.
1. It is absolutely necessary because not all puzzles can be solved using widely known "pure" solving techniques.
2. Along the same line, it is not possible to prove that any given puzzle can be solved by such techniques. On the other hand it is easy to prove that all puzzles can be solved by contradiction chains if recursion is allowed. However, I know that recursion is not so desirable.
3. Depth of recursion will be reduced if some solving techniques are employed in addition to the basic elimination. Typically, I prefer to include only hidden singles, because with this I can solve most puzzles without any recursion or with at most two level recursion.
4. Contradiction chains (without recursion) are always the simplest way to explain why certain candidates can be eliminated from particular cells. The simpler, the best. Unfortunately, there are many situations where some complicated "pure" techniques will be able to eliminate some candidates from some cells, while contradiction chains cannot do the same without recursion.
5. There is a reason why contradiction chains are powerful tools for solving the puzzles. In mathematics, all advanced theorems can be proven only by the contradiction method.
Theorem: If P, then Q.
Direct proof: Assume P, and get Q.
Indirect proof: Assume not Q, and get not P.
Contradiction: Assume not (if P, then Q) [i.e. assume P and not Q], and get a contradiction (such as 1 = 2).
The reason is obvious. If you can assume two things at the beginning (P and not Q as opposed to P alone or not Q alone), it is 100 times easier to start proving anything. Of course, getting a contradiction is not an easy matter.
Note: If you remember "not (if P, then Q) = P and not Q", some day you may look smarter than all others because they think that "not (if P, then Q) = if not P, then not Q".
6. I have some problem with Neunmalneun's statement: "If a cell A contains two candidates a and b and if the assumption that a in A is right leads to the elimination of b in a cell B that can be seen by A, then B does not contain b." From my own experience, when I start a chain, often I end up with some empty cell (no possible candidates), which is a contradiction. So I prefer to modify his statement as follows: "If a cell A contains two candidates a and b and if the assumption that a in A is right leads to a contradiction, then A does not contain a." This covers all cases.
M.K.
- _m_k
- Posts: 13
- Joined: 01 February 2007
by ravel » Mon Mar 19, 2007 1:48 pm
What Neunmalneun described here is another way of defining (extended) xy-chains, i.e.
Either A is b or (A is a => .. => X=b), therefore a cell B, that sees both A and X cannot be b.
He lets it open, with which methods the implication can be derived. If naked singles only, it is a pure xy-chain, but when i remember right, he is familiar with many advanced techniques like ALS and UR and likes to use them. In this case X also can be a group of cells, to which b is locked.
Either A is b or (A is a => .. => X=b), therefore a cell B, that sees both A and X cannot be b.
He lets it open, with which methods the implication can be derived. If naked singles only, it is a pure xy-chain, but when i remember right, he is familiar with many advanced techniques like ALS and UR and likes to use them. In this case X also can be a group of cells, to which b is locked.
- ravel
- Posts: 998
- Joined: 21 February 2006
by _m_k » Mon Mar 19, 2007 6:13 pm
ravel: Thank you for a clarification.
However, if that is the case, then it is exactly what I am claiming:
[B=b] => [A=a & X<>b] => ... => [X=empty (becuase X=b is the only choice)],
and this is a simpler explanation of B<>b.
But I will be honest: My explanation is simpler than all others, but I will be less inclined to try this unless B has bi-values.
M.K.
However, if that is the case, then it is exactly what I am claiming:
[B=b] => [A=a & X<>b] => ... => [X=empty (becuase X=b is the only choice)],
and this is a simpler explanation of B<>b.
But I will be honest: My explanation is simpler than all others, but I will be less inclined to try this unless B has bi-values.
M.K.
- _m_k
- Posts: 13
- Joined: 01 February 2007
by sirdave » Mon Mar 19, 2007 10:22 pm
_m_k wrote:3. Depth of recursion will be reduced if some solving techniques are employed in addition to the basic elimination. Typically, I prefer to include only hidden singles, because with this I can solve most puzzles without any recursion or with at most two level recursion.
Basic elimination + only hidden singles solves most puzzles without recursion or at most 2-level recursion?
How can that be possible in light of how extensive this section of the forum (Advanced solving techniques) is? What you mean by 'most puzzles'?
- sirdave
- 2010 Supporter
- Posts: 36
- Joined: 04 January 2006
by sirdave » Tue Mar 20, 2007 12:42 am
Havard wrote:my 2 cents: http://www.sudokuarchitect.com/forum/viewtopic.php?t=920
IMO, it's worth more than 2 cents: It should be perma-plaqued (burned into wood and varnished) and placed on every forum to be referred to whenever this subject comes up. A Don Murray on the U.K. forum coined the term 'What is and What may be' a few months ago to differentiate between pattern techniques (what is) vs. techniques such as forcing chains (what may be), but you posted the above in July 2006 which says much the same thing!
I only resort to forcing chains when all other techniques including nice loops have a escaped me and it is only one type of forcing chain- the classic double-implication forcing chain. Even then I'm hoping that once I get my official Carcul/Jeff Nice Loop Ph.D. or Anne Morelot ALS Masters, I won't need to resort to them anymore.
- sirdave
- 2010 Supporter
- Posts: 36
- Joined: 04 January 2006
by _m_k » Tue Mar 20, 2007 3:13 am
sirdave, sorry for not being precise. Here is what I was trying to say.
1. Do as much as you can using (a) basic eliminations, (b) hidden singles, and (c) some other techniques of your choice except for (contradiction) chains.
2. When no more progress can be made, pick any cell of your choice, and assume that this cell has a value chosen from possible candidates for this cell. Then, proceed again as in step 1. However, I prefer to use only (a) and (b) for this step.
3. One of the three things will happen:
(i) The puzzle is solved. Of course, whether you are satisfied or not is another matter.
(ii) You get a contradiction. Then, you can eliminate the value used in step 2 from the cell. Again, whether you accept this method or not is another matter.
(iii) No more progress can be made.
4. If you come to 3(iii), use recursion to do steps 2 and 3 above. Again, I prefer to use only (a) and (b) for these step.
It is true that all puzzles can be solved using the steps 1, 2, 3, and 4. However, practically speaking, the level of recursion becomes an important issue, and to a lesser degree, length of step 2. If you use in step 1 only (a) and (b) but no other techniques, then the level of recursion easily becomes 10 or more for very difficult puzzles.
On the other hand, if you include in (c) naked/hidden pairs, triples, quad, and locked candidates (but these are not included in step 2), then most puzzles can be solved by steps 1 and 2 only because you don’t get 3(iii), and even for difficult puzzles, one level of recursion is usually enough to solve them, and seldom two or more levels.
Remember that I am using only (a) and (b) for step 2 (contradiction) chains and step 3 recursion.
M.K.
1. Do as much as you can using (a) basic eliminations, (b) hidden singles, and (c) some other techniques of your choice except for (contradiction) chains.
2. When no more progress can be made, pick any cell of your choice, and assume that this cell has a value chosen from possible candidates for this cell. Then, proceed again as in step 1. However, I prefer to use only (a) and (b) for this step.
3. One of the three things will happen:
(i) The puzzle is solved. Of course, whether you are satisfied or not is another matter.
(ii) You get a contradiction. Then, you can eliminate the value used in step 2 from the cell. Again, whether you accept this method or not is another matter.
(iii) No more progress can be made.
4. If you come to 3(iii), use recursion to do steps 2 and 3 above. Again, I prefer to use only (a) and (b) for these step.
It is true that all puzzles can be solved using the steps 1, 2, 3, and 4. However, practically speaking, the level of recursion becomes an important issue, and to a lesser degree, length of step 2. If you use in step 1 only (a) and (b) but no other techniques, then the level of recursion easily becomes 10 or more for very difficult puzzles.
On the other hand, if you include in (c) naked/hidden pairs, triples, quad, and locked candidates (but these are not included in step 2), then most puzzles can be solved by steps 1 and 2 only because you don’t get 3(iii), and even for difficult puzzles, one level of recursion is usually enough to solve them, and seldom two or more levels.
Remember that I am using only (a) and (b) for step 2 (contradiction) chains and step 3 recursion.
M.K.
- _m_k
- Posts: 13
- Joined: 01 February 2007
by gsf » Tue Mar 20, 2007 5:08 am
sirdave wrote:Basic elimination + only hidden singles solves most puzzles without recursion or at most 2-level recursion?
How can that be possible in light of how extensive this section of the forum (Advanced solving techniques) is? What you mean by 'most puzzles'?
to date even the hardest 9x9 sudoku have at least one singles backdoor of size 2
http://forum.enjoysudoku.com/viewtopic.php?p=34684#p34684
- gsf
- 2014 Supporter
- Posts: 7306
- Joined: 21 September 2005
- Location: NJ USA
by Neunmalneun » Tue Mar 20, 2007 10:22 am
Sirdave:
"Also, in the end, it's all about solving elegance". I think that is the only question we disagree about. In the end Sudoku is (only) a game and everyone is allowed to play it by his or her own rules. I for instance don't use a PC for solving a Sudoku and my only ambition is to solve it between 10 U-Bahn stations on my way to work. So I don't look for an elegant way but only for an effective way to find the missing information in a grid. Though I am basically familiar to most of the advanced techniques (thank you, ravel!) without filtering I am barely capable of using colouring, swordfishes (let alone other fishes) or ASL patterns. Which leaves me with the basics, X-Wings, UR techniques and forcing chains which are easier to spot.
I don't mind guesswork at all and I can't see the moral distinction between patterns and chains. If you look for your missing key you would not care if your way to find it was elegant or if you looked into the same drawer for several times. You are just relieved when you found it in the end.
"I only resort to forcing chains when all other techniques including nice loops have a escaped me and it is only one type of forcing chain- the classic double-implication forcing chain." I can't see the logic here. If you eventually resort to forcing chains, why don't you use them before if (it gives you an easier solution)? That looks to me as if you deliberately avoid an earlier solution just for elegant's sake.
_m_k:
"If a cell A contains two candidates a and b and if the assumption that a in A is right leads to a contradiction, then A does not contain a." I totally agree with this statement. I don't see a contradition to my formulas, in my opinion it is a perfectly appropriate addition.
Kind regards to all
9x9
"Also, in the end, it's all about solving elegance". I think that is the only question we disagree about. In the end Sudoku is (only) a game and everyone is allowed to play it by his or her own rules. I for instance don't use a PC for solving a Sudoku and my only ambition is to solve it between 10 U-Bahn stations on my way to work. So I don't look for an elegant way but only for an effective way to find the missing information in a grid. Though I am basically familiar to most of the advanced techniques (thank you, ravel!) without filtering I am barely capable of using colouring, swordfishes (let alone other fishes) or ASL patterns. Which leaves me with the basics, X-Wings, UR techniques and forcing chains which are easier to spot.
I don't mind guesswork at all and I can't see the moral distinction between patterns and chains. If you look for your missing key you would not care if your way to find it was elegant or if you looked into the same drawer for several times. You are just relieved when you found it in the end.
"I only resort to forcing chains when all other techniques including nice loops have a escaped me and it is only one type of forcing chain- the classic double-implication forcing chain." I can't see the logic here. If you eventually resort to forcing chains, why don't you use them before if (it gives you an easier solution)? That looks to me as if you deliberately avoid an earlier solution just for elegant's sake.
_m_k:
"If a cell A contains two candidates a and b and if the assumption that a in A is right leads to a contradiction, then A does not contain a." I totally agree with this statement. I don't see a contradition to my formulas, in my opinion it is a perfectly appropriate addition.
Kind regards to all
9x9
- Neunmalneun
- Posts: 52
- Joined: 22 December 2005
by sirdave » Tue Mar 20, 2007 6:05 pm
gsf wrote:sirdave wrote:Basic elimination + only hidden singles solves most puzzles without recursion or at most 2-level recursion?
How can that be possible in light of how extensive this section of the forum (Advanced solving techniques) is? What you mean by 'most puzzles'?
to date even the hardest 9x9 sudoku have at least one singles backdoor of size 2
http://forum.enjoysudoku.com/viewtopic.php?p=34684#p34684
With all due respect, you have moved from stating that premise as a 'concept' and 'conjecture' (in your post that you show a link to above) to stating it as fact now.
- sirdave
- 2010 Supporter
- Posts: 36
- Joined: 04 January 2006
by gsf » Tue Mar 20, 2007 6:17 pm
sirdave wrote:gsf wrote:sirdave wrote:Basic elimination + only hidden singles solves most puzzles without recursion or at most 2-level recursion?
How can that be possible in light of how extensive this section of the forum (Advanced solving techniques) is? What you mean by 'most puzzles'?
to date even the hardest 9x9 sudoku have at least one singles backdoor of size 2
http://forum.enjoysudoku.com/viewtopic.php?p=34684#p34684
With all due respect, you have moved from stating that premise as a 'concept' and 'conjecture' (in your post that you show a link to above) to stating it as fact now.
the fact is that no puzzle has yet been found to refute the conjecture (that's why I said "to date")
that's the essence of a conjecture
no proof for it or against it yet
- gsf
- 2014 Supporter
- Posts: 7306
- Joined: 21 September 2005
- Location: NJ USA
