The New Sudoku Players' Forum

[nickrainbow]

Can someone please explain the "chain rule"

Nick

[QBasicMac]

As I understand it, it is a form of T&E whereby you take a cell and select one of its candidates and assume the cell has that value. Then you proceed to see ramfications, but only considering that same candidate. Your hope is to reach a conclusion that this all leads to an impossible condidion and thus the candidate can be erased from the original cell.

Mac

[Jeff]

As I understand it, it is a form of T&E whereby you take a cell and select one of its candidates and assume the cell has that value. Then you proceed to see ramfications, but only considering that same candidate. Your hope is to reach a conclusion that this all leads to an impossible condidion and thus the candidate can be erased from the original cell.

Mac, you are right. What you have described there is the T&E way of finding forcing chains. However, there is also a non-T&E way to find these chains by identification of nice loops in a bilocation/bivalue plot. Please try it, it is good fun.

[emm]

Nick – perhaps you are now wiser about chains, perhaps not.

You might also get help from the SadMan website . Click there.

There's a discussion on finding the simplest chains - XY wings - if you're interested. Click here also.


Jeff – how is this non T&E?

[Jeff]

Jeff – how is this non T&E?

Cell by cell inspection (bifurcation) is T&E. Pattern (Nice loop) recognition is non-T&E.

[Bob Hanson]

As I understand it, it is a form of T&E
whereby you take a cell and select one of its candidates and assume the
cell has that value. Then you proceed to see ramfications, but only
considering that same candidate. Your hope is to reach a conclusion that
this all leads to an impossible condidion and thus the candidate can be
erased from the original cell.

Mac, you are right. What you have described there is the T&E way of
finding forcing chains. However, there is also a non-T&E way to find these
chains by identification of nice loops in a bilocation/bivalue plot. Please try
it, it is good fun.

I will argue that everything done in solving Sudoku is some form of
"packaged" Trial and Error.

Take, for instance a simple naked 23 pair in a row:

{23 23 345 56 789 89...}

How do explain that the "possibility" of 3 of "345" can be eliminated? Most
likely you will say something like, "Well, if that cell were 3, then the first
two cells could not be 3, but then they both would have to be 2 -- a logical
inconsistency. Therefore, we can remove the possibility of 3 from that
third cell."

How is this different from picking a cell and saying, "If this cell were 3, then...."

Most of us would say it's different because we could SEE this --- it wasn't a
random selection. We spotted the 23 23 and that clued us in.

I suggest what this means is that we have incorporated into our
"repertoire" some simple shortcuts to trial and error.

How is this different from ANY other chain-based analysis? If I say that
there is a 2-valued cell combined with a conjugate pair --- that is, 3D
chain analysis --- that produces a logical inconsistency, that's really no
different fundamentally than seeing a 23 23 naked pair. It's just more
involved.

Is it now Trial and Error because of that? Nah. Sure.

We could look at {23 23 345 ....} many different ways:

a. naked 23 23 pair
b. two short single-cell chains doubly weakly linked
c. two almost-locked sets A=23, B=23, doubly locked on 2 and 3

Any one of these observations will lead us to the conclusion that the 3 in
345 can be eliminated. But (a) is a "standard technique", (b) is "Y-cycles"
or "chain analysis", and (c) is bennys's "new thing."

I'm just saying that Trial and Error is, in fact, what it is all about. The fun
of Sudoku (for me) is in enjoying the success of careful observation.

Someone else may be different and enjoy just picking a number and
trying it out, using just singles analysis. To each his/her own, I say.

[Ruud]

We could look at {23 23 345 ....} many different ways:

a. naked 23 23 pair
b. two short single-cell chains doubly weakly linked
c. two almost-locked sets A=23, B=23, doubly locked on 2 and 3

There is a fourth way of looking at this, which I more and more consider to be the "Great Unifying Theory of Sudoku": constraint subsets

- Take 2 constraints with no candidates in common (the A-set):
- > candidates of both the {2,3} cells.

- Take 2 constraints that include all candidates of the A-set (this is the B-set):
- > all candidates for digit 2 in that row, all candidates for digit 3 in that row.

- Eliminate every candidate in the B-set that does not belong to the A-set.

Same result.

- Did you know that constraint subsets subsumes at least (but probably not limited to) the following techniques?

1. Naked singles (set size = 1)
2. Hidden singles (set size = 1)
3. Locked candidates a.k.a. line-box interactions (set size = 1, line vs box)
4. Disjoint subsets (hidden, naked)
5. X-wing, swordfish, etc.
6. Fishy cycles.

I really begin to appreciate this theory of constraint subsets. It ROCKS.

Ruud.

[Jeff]

I will argue that everything done in solving Sudoku is some form of "packaged" Trial and Error.
Take, for instance a simple naked 23 pair in a row: {23 23 345 56 789 89...}

How do explain that the "possibility" of 3 of "345" can be eliminated? Most likely you will say something like, "Well, if that cell were 3, then the first two cells could not be 3, but then they both would have to be 2 -- a logical inconsistency. Therefore, we can remove the possibility of 3 from that third cell."

How is this different from picking a cell and saying, "If this cell were 3, then...."

Thanks Bob for sharing your thoughts. I will try to explain it with an open mind that everyone has his own standard for T&E. To me, 'trial' means testing each possibility in turn and 'error' means backtracking when a contradiction is revealed. Again, your statement describes a T&E way to justify the removal of a candidate due to a naked pair. In reality, this line of thinking would only be performed once or twice when the technique is first used. I used the word 'justify' to stress that this T&E approach is a proof rather than a recognition. No one would justify a naked pair during each of its deductions. Once the theory of a technique is understood, there is no need for any justification since a known recognisable pattern has been established. We simply sail directly to the result every time when such a pattern is identified.

Most of us would say it's different because we could SEE this --- it wasn't a random selection. We spotted the 23 23 and that clued us in.

I suggest what this means is that we have incorporated into our "repertoire" some simple shortcuts to trial and error.

You are right; we are all applying techniques which are short cuts to T&E. It is up to each individual whether he would still regard these short cuts as T&E. To me, these shortcuts are pattern recognition with no T&E elements and I would be very reluctant to still call them T&E.

How is this different from ANY other chain-based analysis? If I say that there is a 2-valued cell combined with a conjugate pair --- that is, 3D chain analysis --- that produces a logical inconsistency, that's really no different fundamentally than seeing a 23 23 naked pair. It's just more involved. Is it now Trial and Error because of that? Nah. Sure.

Sorry, I am not sure because it depends on whether you need to test all possibilities and see the inconsistency before a deduction is made. The principle is the same for a naked pair, a chain or any other established techniques. The BUG principle is a good example. When a BUG pattern is recognised, elimination(s) can be performed following a set of rules. No one will go through the proof that Nick67 has provided during the development of the BUG principle every time.

I don't regard a pattern recognition technique as T&E just because it was originally developed via a T&E approach. If this is the case, then nearly every set pattern technique would be T&E, including x-wing, swordfish, etc.

I'm just saying that Trial and Error is, in fact, what it is all about. The fun of Sudoku (for me) is in enjoying the success of careful observation.

Someone else may be different and enjoy just picking a number and trying it out, using just singles analysis. To each his/her own, I say.

You might like to view our differences as personal preference of terminology. For example, '3D' is used in '3D chain analysis' to describe nothing more than what are known as double implication chains. To you, 3D must have some significant meaning which I am not aware of or is insignificant to me. Nevertheless, no one should let the use of terminology to steer us away from enjoying the fun of sudoku, whether it is in technique development or grid solving using established techniques, both of which require the success of careful observation.

[Myth Jellies]

I maintain that you can use T&E to replace any of our "logical" or non-T&E methods; however, just because you can replace those methods with T&E, that does not in any way mean that those methods are T&E.

Once you prove the implication that pattern P implies result Q, then whenever you see pattern P from then on, you can assert Q. The proven implication is valid regardless of how it was proven. When you perform a proof, it is certainly always legitimate to prove the implication, P -> Q, by proving the contrapositive, (not Q) -> (not P).

When you solve a puzzle using "logical" methods, you DO NOT try to prove that a cell equals N or doesn't equal N. Instead you use what implications you know to positively assert that a cell equals N or doesn't equal N.

When solving a puzzle, if you ever assume that a cell does or does not contain a particular value without the benefit of some supporting implication, you have entered the realm of T&E.

If you accept this definition of "logical" methods versus T&E, then I believe Jeff's nice loop recognition falls in the "logical" category.

[emm]

Personally I think it’s a mistake to introduce the word logic into a discussion on T&E – even if it is ‘apostrophised’! To my mind, whichever way you define T&E, it’s logic is never an issue – it may in fact be considered the very basis of logic. All it means is making an assumption, testing it by logical steps and drawing a conclusion. The conclusion is either that the assumption was true or that it was false. The 'error' part just means repeating the process if the assumption was false.

Jeff’s contention is that while the process of finding a pattern involves T&E – assumption, reasoning, conclusion - the recognition itself and the subsequent eliminations are done on autopilot as it were. I use T&E to find an Xwing. Then I switch into non-T&E and make eliminations. I don’t have to reason why, I just have to know the rule and how to put it into practice. I am not using T&E at that point because I’m not assuming or reasoning, just concluding.

I agree. However, I don’t think it follows that that makes the technique non-T&E. If assumption, deduction and conclusion are implicit in it’s proof, then it’s a T&E technique and that isn’t changed just because it’s put into practice automatically. The solver may use it by methodically plotting the steps, or because she’s seen it before or maybe through brilliant intuition – it doesn’t change the integrity or nature of the proof. (Seems strange for me to be using proofs to argue with Jeff!)

A lot of this is semantics I know. Unfortunately T&E is a term that creates confusion, has negative connotations and gets a lot of bad press – which is funny when you consider that it’s the basis of all the logical techniques used here.

If this is the case, then nearly every set pattern technique would be T&E, including x-wing, swordfish, etc.

Well, maybe they would!

[Ruud]

I agree with Jeff's position that, though you may be able to explain a technique with T&E, that does not mean it has originated from it.

As Bob pointed out, there are many ways to reach the same conclusion, and there are also different ways to explain the same path of reasoning.

As I pointed out earlier, the constraint subset theory can explain a lot of different techniques. This theory has no T&E basis, but pure mathematics. Same result, different reasoning.

I'm not sure whether all pattern recognition techniques are "shortcuts" (in the field of AI, they're called "heuristics"). If you look at the solving technique explanations found in books and on many websites, all of them still explain the reasoning behind every pattern. As long as there is the need to explain this reasoning, they are not heuristics, in my opinion.

Not too far off-topic, I'm sometimes wondering why so many people are T&E-fobic.

Ruud.

[tso]

We're T&E phobic because so many use the term perjoritively, often implying that our methods are cheating, that we're not solving the puzzle the way it's "supposed" to be solved. Everything beyond the newbies understanding is labled "guessing", but they want to solve it "logically". Get back in line, stay in step!

I won't attempt to definitively define T&E other than to say that it is a method to find something -- it is not the something that is found. You could choose to take all the patterns that you are familiar with from naked singles to BUG to comprehensive forcing chains, etc. look for them in a rigid way and in a rigid order -- eliminating the stink of T&E from your search. Using a set algorithm, you avoid T&E. You also suck any enjoyment out of the puzzle by converting "solving" to "housekeeping" -- with the additional benifit of avoiding annoying new discoveries, messy epiphanies and unexpected deductions -- all then nasty by-products of actually *thinking*.

All the fun happens outside your comfort zone. Turn off your cruise control and drive.

That being said, I feel that the idea is to continually push back the point at which you need to actually engage your mind. I often use software to quickly solve the "easy parts" -- don't judge me, you all do it to some degree. You let Simple Sudoku calculate the candidate lists. It's only different by degree to let SS solve to the point where it stalls. There was a time when we *all* would have wanted to put in those candidate lists by hand -- it was fun at the time, we were somehow figuring something out. It's just housekeeping now.

[QBasicMac]

As I understand it, it is a form of T&E whereby...

I will argue that everything done in solving Sudoku is some form of "packaged" Trial and Error. Take, for instance...

Excellent point!

I, a T&E lover, should know better. T&E always involves taking all possible cases of a cell and making that many copies of the solution-so-far and proceeding down each to determine if it leads to a solution. True T&E imagines every puzzle to possibly have multiple solutions and thus must test all, even when a solution is found.

Of course, if you are a believer in the "Uniqueness" idea, then whenever any guess leads to a solution, you imagine you solved the puzzle and can quit testing candidates. But to me, that is sloppy. If you are going to do T&E, you MUST attempt to solve every path. Lots of puzzles to solve for the price of one! Yeah!

Anyway, I can see that applying the idea that any temporary guess is a form of T&E and thus every pattern such as hidden pairs is a form of T&E is not reasonable. Mainly, the aspect of making copies and following all paths is missing. Only the aspect of picking a cell to examine is in common.

So I hereby retract "it is a form of T&E" because it is redundant and pointless.

bilocation/bivalue

I have ignored that so far. Actually, I don't much enjoy complicated stuff and switch to T&E as soon as I get stuck. Lazy in a way, even though T&E is more work. But it always works. However, I have finally incorporated X-Wing and Swordfish into my toolbox of reasonable things to look for before T&E and I guess I will study the bilocation/bivalue stuff to evaluate it. Thanks for the recommendation.

[Thanks to others in this thread that I failed to quote, too]

Mac

[Bob Hanson]

As I pointed out earlier, the constraint subset theory can
explain a lot of different techniques. This theory has no T&E basis, but pure
mathematics. Same result, different reasoning.

Ruud and I are definitely on the same wevelength here. I've called it
"intersections" of sets; Ruud has called it "constraint subset theory". I
agree completely that this is A, if not THE, most fundamental idea in
solving Sudoku. I'm not 100% sure it covers all the logical chain stuff that
now I see almost-locked sets does. But I wouldn't be surprised if Ruud can
conceptualize all that in such terms as well. I've discussed this also at
http://www.stolaf.edu/people/hansonr/sudoku/12rules.htm

The "3D" idea just comes from the 3D viewing illustrated at
http://www.stolaf.edu/people/hansonr/sudoku. To me that was a
way of teasing out the tangle of chains. Glenn Fowler's page, that
describes "X-cycles" and "Y-cycles" got me going on this. The idea being,
why not combine them? Thus, 3D. Basically, what we see as marks on a
9x9 grid can be seen as the projection of marks in a 9x9x9 cube.
But, right, it's the same thing by any name.