The New Sudoku Players' Forum

[Carcul]

Hi Jeff.

Single implication network
An open path that has one implication stream that starts with a candidate selected in one node and propagates until a contradiction is revealed, eg. one digit appears 2 times in a unit.(...) There is currently no known technique for non-T&E identification of such an open path.

Interestingly, I have recently identified an example of such a "Single Implication Network" (where the contradiction is no place for a candidate in an unit), combining known logical arguments. However, it was not very easy to spot. But I think we should be carefull when saying that there is no technique for the identification of a given type of contradiction: in my opinion, a better afirmation would be "although Single Implication Networks can be identified through known techniques, such an identification can be a very difficult (but not impossible) process".

Regards, Carcul

[Jeff]

Hi Jeff.

Single implication network
An open path that has one implication stream that starts with a candidate selected in one node and propagates until a contradiction is revealed, eg. one digit appears 2 times in a unit.(...) There is currently no known technique for non-T&E identification of such an open path.

.............However, it was not very easy to spot. But I think we should be carefull when saying that there is no technique for the identification of a given type of contradiction: in my opinion, a better afirmation would be "although Single Implication Networks can be identified through known techniques, such an identification can be a very difficult (but not impossible) process".

Hi Carcul, But, is it a non-T&E technique though? I know it's difficult to define T&E in this case. Any chance to demonstrate the process under reference?

[Carcul]

But, is it a non-T&E technique though?

In my case, it was not T&E.

Any chance to demonstrate the process under reference?

Sorry, I am not following you: what process?

Carcul

[Jeff]

"although Single Implication Networks can be identified through known techniques, such an identification can be a very difficult (but not impossible) process".

Hi Carcul, I meant to say: What is the known technique and can a domonstration be made for such a very difficult process?

[Carcul]

Ok. The technique was similar to a multiple implication nice loop, more exactly the construction of two chains of links from the same node that end with weak links and same label in the same unit. Better than words is a demonstration. Consider the puzzle posted by Gsf in the thread "Simple example of a POM vulnerable pairs operation", and, after some eliminations we get:

Code: Select all

 178   2789 3   | 4     158  1578| 6    12789 129   
 14678 5    1267| 167   1368 9   | 2348 12478 1234 
 14678 4789 1679| 2     1368 1678| 3489 14789 5   
----------------+----------------+-----------------
 2     6    8   | 59    7    45  | 1    3     49     
 134   34   15  | 8     149  12  | 2459 6     7     
 9     47   157 | 3     146  1246| 2458 2458  24     
----------------+----------------+-----------------
 5     2379 2679| 1679  1469 1467| 2349 1249  8     
 3678  3789 4   | 15679 2    1578| 359  159   1369   
 68    1    269 | 569   4589 3   | 7    2459  2469   


Now, we can write the following (complicated) Single Implication Network:

[r1c8](-1-[r1c156])-1-[r146c9]-2,4,9-[r9c9](-6-[r9c34])-6-[r9c1](-8-[r9c5]=8=[r8c6]-8-[r1c6])-8-[r1c1]-7-[r1c6]-5-[r4c6](-4-[r4c9]-9-[r1c9]-2-[r1c2])=5=[r4c4]-5-[r9c4]-9-[r9c3]-2-[r7c2]

and we have two weak links labelled "2" connected to both "2s" of column 2, which means that if r1c8=1 then column 2 would have no "2", which is a contradiction. So, r1c8<>1.

Regards, Carcul

[Jeff]

Now, we can write the following (complicated) Single Implication Network:

[r1c8](-1-[r1c156])-1-[r146c9]-2,4,9-[r9c9](-6-[r9c34])-6-[r9c1](-8-[r9c5]=8=[r8c6]-8-[r1c6])-8-[r1c1]-7-[r1c6]-5-[r4c6](-4-[r4c9]-9-[r1c9]-2-[r1c2])=5=[r4c4]-5-[r9c4]-9-[r9c3]-2-[r7c2]

and we have two weak links labelled "2" connected to both "2s" of column 2, which means that if r1c8=1 then column 2 would have no "2", which is a contradiction. So, r1c8<>1.

Hi Carcul, This is one very complicated network and does the job to eliminate a "1" from r1c8. BTW, what technique did you use to identify this single implication network to qualify that the identification process was non-T&E. For example, the non-T&E technique for identification of nice loops is the b/b plot, according to my own standard of T&E of course.

[jfigueras]

To determine the complexity of a technique, simply count the number of operations required to carry it out. If that number is proportional to a simple power of N, the complexity is polynomial; if it's some number to the Nth power, that makes the technique exponential.

Full backtracking is the best example of an exponential technique in sudoku. Limited backtracking (e.g. Nishio) can be polynomial, but doesn't always succeed. Looking for pairs is polynomial (proportional to N^2).
Thanks with anticipation.

This completely misconstrues the meaning of complexity. Complexity measure is related to the dependence of the number of operations on program SIZE, not the number of operations required to handle a specific case. For example, a binary tree, in which each node has two branches, grows exponentially, namely as 2**n, and the number of operations required to search over this tree will likewise grow exponentially with the size of the tree, but for any specific example of such a tree, only a finite number of operations will be required. Simply counting the number of operations without taking into account how that number depends upon the size of the problem gives no information about complexity.

Also, the use of backtracking doe not per se make a problem exponential. A Sudoku matrix that is solvable by pure logic doesn't magically become of exponential order if a backtracking algorithm is used for its solution. With regard to T&E (trial and error) ALL backtracking algorithms by their very nature are T&E--you follow a path through the search tree, and if the path ends in failure, you backup to some previous decision point and try again. If that isn't trial-and-error, I don't know what is. One can deduce that "guessing", also known as T&E, is simply a limited example of backtracking. Backtracking is a technique (heuristic) useful for solving a wide variety of search problems whether those problems are of polynomial or exponential order with respect to size.

John

[Jeff]

Interestingly, I have recently identified an example of such a "Single Implication Network" (where the contradiction is no place for a candidate in an unit), combining known logical arguments. However, it was not very easy to spot. But I think we should be carefull when saying that there is no technique for the identification of a given type of contradiction: in my opinion, a better afirmation would be "although Single Implication Networks can be identified through known techniques, such an identification can be a very difficult (but not impossible) process"........

Now, we can write the following (complicated) Single Implication Network:

[r1c8](-1-[r1c156])-1-[r146c9]-2,4,9-[r9c9](-6-[r9c34])-6-[r9c1](-8-[r9c5]=8=[r8c6]-8-[r1c6])-8-[r1c1]-7-[r1c6]-5-[r4c6](-4-[r4c9]-9-[r1c9]-2-[r1c2])=5=[r4c4]-5-[r9c4]-9-[r9c3]-2-[r7c2]

and we have two weak links labelled "2" connected to both "2s" of column 2, which means that if r1c8=1 then column 2 would have no "2", which is a contradiction. So, r1c8<>1.

Hi Carcul, Having read John’s response above on backtracking vs T&E, I have given more thoughts on this complicated network. I think the b/b plot will navigate the route to be taken until a contradiction is found without any backtracking. However, if no contradiction could be found before the b/b plot was exhausted, then the non-conclusive network would have to be abandoned; still no backtracking would be performed though. Equally, the same can be said for some complicated nice loops as well. So, I think you are right; I would have to alter the wording for the definition of "Single Implication Network".

[castalia]

This completely misconstrues the meaning of complexity. Complexity measure is related to the dependence of the number of operations on program SIZE, not the number of operations required to handle a specific case.

No, an algorithm's complexity refers to the number of operations it requires as a function of the input size N. If an algorithm is of polynomial complexity, then the number of operations (or, similarly, the run time) is proportional to some power of N. If it's exponential, then the number of operations is proportional to some number to the Nth power. For more precise details, consult Knuth's 3 volumes or Herbert Wilf's very readable "Algorithms and Complexity".

But the real point here is not to debate how different people use the same terms in different ways. Rather, it's to understand whether there's any defensible partitioning of sudoku techniques into "acceptable" and "unacceptable" categories. My view is that such a partitioning is indeed desirable, and that these categories are mapped to polynomial and exponential techniques, respectively.

It's unfortunate, but entirely understandable, that simple guidelines on sudoku often stress that solutions should be arrived at by "logic" and without the use of "trial and error". Well, any solution method that adheres to the rule of sudoku could be considered "logical", and even such simple techniques as singles could be considered trial and error (since "trying" to place that single anywhere else in the unit would violate the rule of sudoku and therefore result in "error").

Fortunately, mathematics is not ambiguous on this point. If you can develop solution methods that are of demonstrated polynomial complexity (such as Eppstein's nonrepetitive path and cycle techniques), then you've made a real contribution.

Mark

[Jeff]

Fortunately, mathematics is not ambiguous on this point. If you can develop solution methods that are of demonstrated polynomial complexity (such as Eppstein's nonrepetitive path and cycle techniques), then you've made a real contribution.

Hi Mark, But, how can the complexity, (T&E or non-T&E index) for other techniques other than Eppstein's nonrepetitive path and cycle be determined for practical application?

[Myth Jellies]

[r1c8](-1-[r1c156])-1-[r146c9]-2,4,9-[r9c9](-6-[r9c34])-6-[r9c1](-8-[r9c5]=8=[r8c6]-8-[r1c6])-8-[r1c1]-7-[r1c6]-5-[r4c6](-4-[r4c9]-9-[r1c9]-2-[r1c2])=5=[r4c4]-5-[r9c4]-9-[r9c3]-2-[r7c2]

Correct me if I am wrong, but this looks like a one-direction implication network, which only means anything if you assume r1c8 = 1. I don't know if these other T&E definitions would admit such practices, but they would not pass my simple rule.

It's unfortunate, but entirely understandable, that simple guidelines on sudoku often stress that solutions should be arrived at by "logic" and without the use of "trial and error". Well, any solution method that adheres to the rule of sudoku could be considered "logical", and even such simple techniques as singles could be considered trial and error (since "trying" to place that single anywhere else in the unit would violate the rule of sudoku and therefore result in "error").

I think you are right that if you adopt, or are forced into, a wide open definition of a trial and you are not allowed to make a distiction between a search for a relatively simple pattern versus arbitrarily assigning the content of a cell; then we should really be creating a thread about what we feel are acceptable procedures rather than what constitutes T&E.

Personally, I don't see why you can't make a distinction between these two types of trials. If you can't make that distinction, then how can you make a distinction between finding the puzzle vs solving the puzzle. In essence, the phrase, trial, represents everything, and thus becomes meaningless.

Bowing to the possibility I could be wrong about all I have written above, I will once again offer my simple rule for "non-guessing" vs "guessing" sudoku solving techniques. Non-guessing techniques never assume either truth or falsehood about any candidate or group of candidates. Evidence obtained by breaking this rule cannot help but be tainted by the assumption. None of our currently accepted basic methods force the solver to break this rule to apply the deduction.

As far as some of our advanced techniques go, by this definition...

NxN swordfish are non-guessing

Colors, multi-colors, etc. are non-guessing so long as no unwarranted assumption is made regarding any particular color representing true or false.

XY-Wings are non-guessing

Turbot Fish are non-guessing

Forcing chains, X-Cycles, XY-Cycles are non-guessing so long as the chain pattern is equally effective at making the reduction if the cells are true or false.

ALS XZ-Rule is non-guessing.

Grouping and/or Filleting augmentations to non-guessing rules are also non-guessing.

Uniqueness+1 and BUG+1 deductions are non-guessing. Plus more candidates deductions can possibly be tainted depend on the situation and how they are used.

Implication chains and networks deductions are tainted if they only apply when certain candidates have certain values.

Bifurcation is a guessing method.

Limited Bifurcation is a guessing method--no matter what limits you put on it.

Sherlock is a guessing method.

Backdoor Pairs is a guessing method.

Finally, tainted evidence is often forgiven so long as a non-guessing alternative is readily apparent. Thus, if you identify your naked pair reductions by noting that placing a naked pair candidate in one of the other cells in the group leads to a crash, rather than simply removing the naked pair candidates from all other cells in the group; almost no one is going to complain.

Nishio, as it is usually performed, is a guessing method. However Nishio could be accomplished by taking a solution pattern template built via symmetry and implication rules, and killing all patterns in cells that do not have the nishio digit as a candidate. It's not really a readily apparent alternative, however some may feel inclined to forgive its use for this and other reasons.

[Jeff]

[r1c8](-1-[r1c156])-1-[r146c9]-2,4,9-[r9c9](-6-[r9c34])-6-[r9c1](-8-[r9c5]=8=[r8c6]-8-[r1c6])-8-[r1c1]-7-[r1c6]-5-[r4c6](-4-[r4c9]-9-[r1c9]-2-[r1c2])=5=[r4c4]-5-[r9c4]-9-[r9c3]-2-[r7c2]

Correct me if I am wrong, but this looks like a one-direction implication network, which only means anything if you assume r1c8 = 1. I don't know if these other T&E definitions would admit such practices, but they would not pass my simple rule.

Hi MJ, You are right, this is a single implication network with one implication stream. The only argument that could possibly separate it from T&E may be that it doesn't require any backtracking.

[Carcul]

Hi Jeff.

This is one very complicated network and does the job to eliminate a "1" from r1c8.

This is not very complicated (I have more complicated examples, even in the same puzzle): but, of course, if you would think in identifying this with the traditional b/b plot then I would agree with you.

BTW, what technique did you use to identify this single implication network to qualify that the identification process was non-T&E. For example, the non-T&E technique for identification of nice loops is the b/b plot, according to my own standard of T&E of course.

Each one of us as his own definition of T&E (that's why I don't see the purpose of this thread, but that is another issue): for me, and using the words of Tso in another thread, if a deduction can be made "in the head" then it is not T&E. Obviously, as I am not sadomasochistic, for the deduction above I have not draw a b/b plot: instead, I constructed the links and implications in my head and arrive to the conclusion. But you may be asking: "Why, in God's name, did you start in that cell with that candidate?". And the answer is: because from r1c8=1 a locked set emerges that forces r9c9=6, r9c1=8, etc, etc. If you (or others) want to classify this as T&E, please feel free, but I will not agree. If we are to limit ourselves with the limitations of the b/b plot, then solving extremely hard puzzles would not certainly be possible. Also, is my opinion that, in this kind of puzzles we cannot expect to use simple logical arguments.

Regards, Carcul

[Jeff]

Single implication network
An open path that has one implication stream that starts with a candidate selected in one node and propagates until a contradiction is revealed, eg. one digit appears 2 times in a unit.(...) There is currently no known technique for non-T&E identification of such an open path..

Hi carcul, I hope you are not offended as that is not my intention. I started this thread trying to understand the relationship between complexity and T&E, not to promote my own opinion for T&E or to disagree with others. Personally, I think your network is great and I only questioned it because I needed to clarify in my own mind that the last statement in the above definition for "Single Implication Network" was reasonable. I just thought that you would be kind enough to share the technique you have used; that’s all.

[Carcul]

Hi Jeff.

No, of course I am not offended. I just wanted to clarify as much as possible my way of thinking, but sometimes I don't select the appropriate words for that.

I started this thread trying to understand the relationship between complexity and T&E,

Ok, now I understand the purpose of the thread, and I must say that I also have been thinking in the relationship complexity/T&E: both of these concepts are certainly subjective, and that must be taken in account in this discussion.

Regards, Carcul