The New Sudoku Players' Forum

[Mauricio]

I believe the only real difference between T&E eliminations and other chains is the way you look for them. Any T&E elimination may be traced back and then written as a chain. How does that make it any more logical/valid? Take for example the XY-wing. You say "A={12}, B={13}, C={23} => D <> 3", I say "if D=3 => B=1 & C=2 => no possible candidate in A => D<>3". All eliminations we make, using any technique, are because "if that candidate is true, then there would be a contradiction elsewhere in the puzzle". The cells we need to consider to reach that contradiction may be defined as a pattern. Isn't this then the most basic logic in sudoku solving? The one simple rule from which all other techniques can be derived.

That is exactly what I was thinking, but I could not find the right words to say it. I cannot agree more.

[ravel]

- using resolution rules is exactly like searching a proof of a theorem; once you find the proof, you can completely forget the paths you tried and that led to nothing;
- in T&E, dead ends always remain part of the proof.

Why ?
The common understanding of using t&e is, you assume something (e.g. a cell has a certain value), show that it it leads to a contradiction, and you have proved, that this something is false (therefore you e.g can eliminate the assumed candidate). This is not a dead end, but a solution step. If this leads to an dead end (you dont get a contradiction, but are stuck again), just forget it, you cant make use of it.
Now it could happen, that the assumption directly leads to a sloution. This situation can be disputed just like uniqueness methods. If it is given, that the puzzle has a unique solution, you have a proof, because you have the only possible solution - and the assumption must be true.
So, in any case, what dead ends remain part of the proof ?

[denis_berthier]

And if you are looking for very long chains, you don't need a mechanism to keep track of all the links? This mechanism might be your own memory, or a sheet of extra paper.

Most of the chains will be short.
For longer chains, depending on your memory, you need to draw arrows or use other techniques.
This is a king of search, but not at the same level.
You may have to erase arrows, but you will never change the basic date (values and candidates) until you have found a pattern that allows it.

Any T&E elimination may be traced back and then written as a chain.

As proven by my T&E theorem, this is not the case for T&E with no depth limit.

[denis_berthier]

The common understanding of using t&e is, you assume something (e.g. a cell has a certain value), show that it it leads to a contradiction, and you have proved, that this something is false (therefore you e.g can eliminate the assumed candidate). This is not a dead end, but a solution step. If this leads to an dead end (you dont get a contradiction, but are stuck again), just forget it, you cant make use of it.
Now it could happen, that the assumption directly leads to a sloution. This situation can be disputed just like uniqueness methods. If it is given, that the puzzle has a unique solution, you have a proof, because you have the only possible solution - and the assumption must be true.
So, in any case, what dead ends remain part of the proof ?

That's a matter of vocabulary. You're right that "dead end" is not a good term. In the definition, I meant a "no solution" situation.
In full T&E, if you are stuck again, you don't forget it, you keep on recursively making hypotheses.

[RW]

And if you are looking for very long chains, you don't need a mechanism to keep track of all the links? This mechanism might be your own memory, or a sheet of extra paper.

Most of the chains will be short.
For longer chains, depending on your memory, you need to draw arrows or use other techniques.
This is a king of search, but not at the same level.
You may have to erase arrows, but you will never change the basic date (values and candidates) until you have found a pattern that allows it.

So it is less T&E if the solver uses some other symbols than the digits 1-9? And what about my technique when I never write anything in the grid except the digits I am sure to be true, even though I make lots of assumptions and mentally assign values to cells?

Any T&E elimination may be traced back and then written as a chain.

As proven by my T&E theorem, this is not the case for T&E with no depth limit.

Your theorem proved it by saying that T&E can find a solution in multisolution puzzles. Please note that I said T&E elimination, not solution. T&E cannot be used to eliminate any more candidates than any other technique in a multisolution puzzle. I don't see how your other proof would prove anything. If a cell has at least two candidates, then all but one may be eliminated by chains. If you consider T&E with no depth limit, then you should also include nested chains with no depth limit, which gives them exactly the same power.

RW

[Mauricio]

Mauricio
puzzle ==> solution is at best a function, not a resolution rule.
It doesn't tell you what to do in any precise situation.

Or you did not understand what I meant. I meant something particular, like this:
Puzzle =

Code: Select all

. . .|. . .|. . 1
. . .|. . 2|. 3 .
. . 2|. 4 .|. . .
-----+-----+-----
. . .|. 5 .|. 6 .
. . .|7 . .|8 . 9
. . 3|. . .|. 4 2
-----+-----+-----
. 2 .|. . 6|4 . .
5 . 8|. . .|. . .
6 3 .|8 . .|. 5 .

implies solution =

Code: Select all

4 7 6|3 9 5|2 8 1
8 5 9|1 7 2|6 3 4
3 1 2|6 4 8|9 7 5
-----+-----+-----
9 8 1|2 5 4|7 6 3
2 4 5|7 6 3|8 1 9
7 6 3|9 8 1|5 4 2
-----+-----+-----
1 2 7|5 3 6|4 9 8
5 9 8|4 1 7|3 2 6
6 3 4|8 2 9|1 5 7

My particular puzzle mean exactly that, a particular puzzle. I never meant to solve every particular puzzle.

So, is this a resolution rule? if not, why not?

Edit: ah, now I see that you did not quote me correctly:

• Particular puzzle==>Particular solution

that it is not the same as puzzle=>solution...

[ravel]

[That's a matter of vocabulary. You're right that "dead end" is not a good term. In the definition, I meant a "no solution" situation.
In full T&E, if you are stuck again, you don't forget it, you keep on recursively making hypotheses.

Ok, i read your t&e (full T&E) defintion now. Its not common sense. For a player it is definitely stupid. It would mean, that if i use T&E, i NEVER would be allowed to look, what would happen, when a cell would contain a candidate without proving it right or wrong until the end. Its weird for me to discuss this, but now i unfortunately started it.
So your "dead end" is a "no solution" situation, that what we call a contradiction (normally what we are looking for). And the problem you have with it is, that this is part of the proof ? It is better, when i look for a abcdefghijk-chain, because when i find none, i can forget it and it is not part of the proof ?
But what, when i do "normal" t&e, i.e. try this and that, just like you might try to find this or that kind of chain in this or that way ? For me its only the question, what - for my skills and possibilities - is more fun and more effective.
Theoretically i cant find a basic difference.

[Red Ed]

Getting back to Denis' opening questions (reformatted from the original) ...

1. How can we compare the complexities of two resolution rules?
2. How can we compare the complexities of two resolution techniques associated to the same resolution rule?
3. Is there a simple relation between the logical syntactic complexity of a rule and the difficulty of spotting its instantiations?
4. Given a resolution rule, which technique is best fitted to spot its occurrences in a real grid?
5. What are the relevant properties of a resolution rule? (being based on a homogeneous pattern, being 2D,…)
6. What are the relevant properties of a resolution technique? (being based on a resolution rule; for a chain: being more or less extensible in both directions, being based on a target cell, …)

I'll offer some thoughts on #1 above. Recall that we're doing condition => action type rules. I'm going to focus solely on the condition. So, here are two natural questions that we might ask:

1. In how many places in the grid might we have to look to apply the resolution rule?
2. At each place in the grid, how difficult is it to verify that the condition applies?

Here, I'm thinking of the "grid" as being the pencilmarked grid expressed as candidate(n,r,c) predicates without any other information.

Naked Single

Let's try to answer those questions for the Naked Single resolution rule with condition: candidate(n1,r,c) AND NOT(candidate(n2,r,c)) AND ... NOT(candidate(n9,r,c)), and I'm taking n1,n2,...,n9 to be distinct. Then, with respect to the two questions above:

1. There are 81 choices for (r,c) and 9 for n1, so 729 places to look in total.
2. This is tricky! We could say that there are 9 terms to check, or just 1 minterm (multi-input AND) to evaluate, or 16 logical operations to perform, or ... what? How about (for a strawman) we just count the minimal number of appearances of a candidate() predicate that can be achieved by any logical rewriting of the condition. So, in this case, it's 9.

My intuition, flawed as it may be, is that the product of these numbers could be a good overall complexity figure. Or maybe, for aesthetics, the log (base 9) of that, giving complexity(naked single) = 4.

Naked Pair

Let's say that the condition is the logical OR of the following three expressions:

• NOT(candidate(n3,r,c1)) AND ... NOT(candidate(n9,r,c1)) AND NOT(candidate(n3,r,c2)) AND ... NOT(candidate(n9,r,c2))
• similar for two cells in a column
• similar for two cells in a row

Then:

1. I think that there are 810 ways of picking the two cells and 36 ways of picking the two digits, so 29160 places to look in total.
2. The way I've written it above, there are 42 instances of a candidate() predicate. That's an upper bound; I'm sure that more efficient rewritings exist.

Putting this together, the product is 1224720, which has log(base 9) = 6.38ish[/b]. So complexity(naked pair) < 6.4.

Conclusion

Beats me. What do you think?

[ravel]

Do you talk about sudokus without givens ?

[gsf]

Let's try to answer those questions for the Naked Single resolution rule with condition: candidate(n1,r,c) AND NOT(candidate(n2,r,c)) AND ... NOT(candidate(n9,r,c)), and I'm taking n1,n2,...,n9 to be distinct. Then, with respect to the two questions above:

1. There are 81 choices for (r,c) and 9 for n1, so 729 places to look in total.
2. This is tricky! We could say that there are 9 terms to check, or just 1 minterm (multi-input AND) to evaluate, or 16 logical operations to perform, or ... what? How about (for a strawman) we just count the minimal number of appearances of a candidate() predicate that can be achieved by any logical rewriting of the condition. So, in this case, it's 9.

My intuition, flawed as it may be, is that the product of these numbers could be a good overall complexity figure. Or maybe, for aesthetics, the log (base 9) of that, giving complexity(naked single) = 4.

tricky indeed, but its about time for some fun
right off there will be a tug of war between complexity of an empty grid (no clues, all candidates possible in all cells) vs. a grid with some clues
e.g., the average number of candidates/cell for |sudogen0.txt|=10,000, not counting clue cells, is 2.7
but say we ignore that
then there's the issue of bitmask representations that can lead to parallel operations (which may lead to operation weights)
e.g., with candidates represented as 9 bits, one wouldn't scan the grid 9 times, once for each candidate
one would scan once and check each cell for one candidate, and then determine the candidate value
so naked singles could take 81 candidate mask(r,c) ops, and then a check for 1 bit set
(the scan would have to differentiate between solved and unsolved cells too)

for r,c if unsolved(r,c) and !(mask(r,c)&(mask(r,c)-1)) then value(mask(r,c)) is a naked single

this looks like O(9^2) or strawman 2
so I guess I'm saying that a complexity measure should take into account that not all operations are equal
or maybe that the predicates chosen may have a non-trivial effect on how complexity is measured
e.g., measures limited to candidate(n,r,c) might end up doing loops inside out in a less efficient manner

[denis_berthier]

Any T&E elimination may be traced back and then written as a chain.

As proven by my T&E theorem, this is not the case for T&E with no depth limit.

Your theorem proved it by saying that T&E can find a solution in multisolution puzzles. Please note that I said T&E elimination, not solution. T&E cannot be used to eliminate any more candidates than any other technique in a multisolution puzzle. I don't see how your other proof would prove anything. If a cell has at least two candidates, then all but one may be eliminated by chains. If you consider T&E with no depth limit, then you should also include nested chains with no depth limit, which gives them exactly the same power.
RW

If you change all the definitions, what's left to discuss?
I don't know what a nested chain is.
I consider chains as patterns, exactly like Pairs or Jelllyfish. As a pattern, a chain has a well defined type and a well defined length.
I therefore can give no meaning to your claim that nested chains with no depth limit (and probably no specified type) is like T&E.

[denis_berthier]

Particular puzzle==>Particular solution

You can undoubtedly write this as a logical formula.
And you can come out with a sudoku resolution theory that will contain billions of billions of such rules.
I'll invite you for dinner when you've finished writing it ;)

What we are interested in is general resolution rules, that apply a priori to any puzzle. I wrote somewhere that, in order to respect the obvious symmetries of the game, no constant symbol should appear in a resolution rule.

[denis_berthier]

Theoretically i cant find a basic difference.

The theoretical difference is between finding a predefined pattern and applying the associated rule on one hand and making ad hoc reasoning on the other.

If there was no difference, can you explain why everybody is looking for new resolution rules (new kinds of fish, new chains,…)?
Why shouldn't we merely use T&E?

[Mauricio]

And you can come out with a sudoku resolution theory that will contain billions of billions of such rules.
I'll invite you for dinner when you've finished writing it ;)

My intention was not to do that, but instead to expose the dangers of using a subjective word (rationality) in an objective way.

[denis_berthier]

Red Ed, gsf
I agree with Red Ed's assumption that the complexity of a rule is mainly in its condition part.
Finding that NS is simpler that NP is not very surprising. (The numerical values are not really meaningful, it is a matter of scaling.)
If we did the computation for NT and NQ, we'd find still higher complexities.

Now let me raise the question: in the scale you have chosen, what would the complexity of HP (Hidden Pairs) and SHP(Super Hidden Pairs = X-Wing) be?
Based on the logical formulæ, they should be the same as that of NP (because these rules are obtained by a mere permutation of n, r, c).
But are they really the same for a human player?
Of course they are not, unless we have appropriate graphical representations that will make the equivalence obvious. That's why I designed the extended Sudoku board.

Let me take a more general example. Is a pair of conjugate candidates more or less complex than a bivalue cell? Again, from a purely logical POV, they should have the same complexity (conjugate is bivalue in either of the rn-, cn- or bn- spaces). From a player's POV, that may be the topic for unending debates.

Another problem arises when we try to do such computations for more complex patterns, e.g. for chains (and that led me to give up the idea of putting such things in my book): it becomes very difficult to evaluate the number of possibilities for each cell. Worst case analysis would give an unrealistic complexity measure and mean case analysis is nearly unfeasible. I think, even if it doesn't faithfully reflect complexity for a human, any progress on this would be valuable.

Finally, I'm not sure a notion of complexity can be attached to a resolution rule itself. It may have to be attached separately to each of the resolution techniques implementing it, and it will depend on the representations used for this implementation.