The New Sudoku Players' Forum

[denis_berthier]

The T&E-depth of a resolution rule

1) BACKGROUND:
I'll refer to the precise definitions of the following concepts I've introduced long ago on the forums and in my publications (as these publications are widely available, I don't recall the definitions here):

===> a resolution rule, as a first-order logical formula, with some syntactic restrictions, written in the language of Sudoku, in the form:
pattern => elimination of a candidate / assertion of a value
(references: [HLS, June 2007] and all my further publications)

===> T&E(T, n) (for a resolution theory T with the confluence property and for n ≥ 0), as a precise procedure; T&E(n) is the special case where T = Singles (+ ECP, i.e. eliminations by a direct contradiction with a decided value).
(references:
- on this forum: http://forum.enjoysudoku.com/fully-supersymmetric-chains-t5591-150.htm, 26 Sept. 2008
http://forum.enjoysudoku.com/abominable-trial-and-error-and-lovely-braids-t6390.htm, 14 oct. 2008
- books: [CRT, 2011] and all my further publications)
Note: The previous definition of T&E available at that time was: suppose C (a candidate) is true; it this leads to a contradiction, eliminate C.

===> the T&E(T)-depth of a puzzle; in particular, its T&E-depth.
The T&E-depth is a (very broad) universal classification of all the instances of all the finite binary CSPs. It is invariant under the CSP isomorphisms.
Until recently, all the known 9x9 Sudoku puzzles had T&E-depth ≤ 2. But I found that a puzzle (Loki) created by mith in his serach for hardest puzzles wrt SER was indeed the first with T&E-depth = 3: http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1048.html


In this first post, I'll use the precise definitions of the above concepts to (trivially) define the T&E-depth of a resolution rule.



2) DEFINITION:
The T&E-depth of a resolution rule R is the depth n of the T&E(Singles, n) procedure required to get all the expected eliminations/assertions of R in any resolution state where the pattern and only the pattern of R is assumed to be satisfied.

Remarks:
1) as all my definitions, this is invariant under Sudoku isomorphisms. This is essential, as it will allow drastic simplifications in the computation of any particular T&E-depth.
2) some particular cases of the pattern may require fewer levels of T&E, but that doesn't change the depth of the rule itself, as the definitions says: "in any resolution state".
3) some particular eliminations may also require only fewer levels, but that doesn't change the depth of the rule itself, as the definition says: "all the expected contradictions".
For remarks 2 and 3, see the Naked Quads example.
4) In a given puzzle, the applicability of a resolution rule R of T&E-depth n doesn't imply that the T&E-depth of the puzzle is (at least) n. There are always many resolution paths and some of them may totally avoid using this rule or may use only a special case of R.
5) A similar definition, with similar remarks could be based on gT&E(n) = T&E(W1, n) instead of T&E(n).


3) FIRST EXAMPLES:
A Single has T&E-depth 0
A braid has T&E-depth 1 (independent of its length). All the special cses of braids (bivalue, chains, z-chains, t-whips, whips) have T&E-depth 1.
A B-braid has T&E-depth 2 (independent of its total length and of the lengths of its inner braids)

Note: a g-braid or g-whip has T&E-depth 2, but g-T&E-depth 1.

[denis_berthier]

.
THE NAKED-QUADS-IN-A-ROW EXAMPLE:
Before dealing with more complex patterns, let's see how this applies to the most familiar ones.

1) COMPUTATION OF THE T&E-DEPTH:
I've already applied the following technique on several patterns in this forum, but, as a first and easy example, here is a way of computing the T&E-depth of the Naked-Quads-in-a-row rule.
First, and this is a situation that will occur most of the time: we know in advance what the targets can be. As a result, we can assume that the first level of T&E consists of supposing one of the targets is True.

The most general resolution state is (the presence of all the candidates 123456789 in a cell is equivalent to nothing being supposed about it).

Code: Select all

+-------------------------------+-------------------------------+-------------------------------+
! 1234      1234      123456789 ! 1234      123456789 123456789 ! 1234      123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+


Notice that, in order to be complete, we should also analyse the different possible positions for the 4 cells of the Quad.

Now, for the target (by digit symmetries) we can assume it is number 1 in any of the other cells of the row. Again, there are several possibilities, but I shall analyse only one.
So, at the first level of T&E, we assume the target:

Code: Select all

+-------------------------------+-------------------------------+-------------------------------+
! 234       234       1         !  234      123456789 123456789 ! 234       123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+


Level 2 of T&E: assume that r1c1=2 (it can't be 1).

Code: Select all

+-------------------------------+-------------------------------+-------------------------------+
! 2         34        1         ! 34        123456789 123456789 ! 34        123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+


Level 3 of T&E: assume that r1c2=3 (it can't be 1 or 2).

Code: Select all

+-------------------------------+-------------------------------+-------------------------------+
! 2         3         1         ! 4         123456789 123456789 ! 4         123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+


The contradiction appears: number 4 has to be in two cells of row r1.

Conclusion (after checking all the other possibilities): The T&E-depth of the Naked-Quads rule is 3



2) SPECIAL CASE:
As an extreme example of remark 2 of the first post, consider the cyclic special case of the NQ:

Code: Select all

+-------------------------------+-------------------------------+-------------------------------+
! 12        23        123456789 ! 34        123456789 123456789 ! 41        123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
+-------------------------------+-------------------------------+-------------------------------+


It is obvious that assigning 1 to any of the other cells will immediately result in a contradiction. So, this special case has T&E-depth 1. This is also consitent with the possible view of this pattern has a bivalue-chain[4].

Note that this special case doesn't change the T&E-depth of the general NQ.

[denis_berthier]

.
Exercises for the reader:
1) Prove that the T&E-depth of the Naked Triplets rule is 2.
2) Prove that the T&E-depth of the Naked Pairs rule is 1.
3) Extend these results to Hidden and Super-Hidden Subsets (Fish patterns)

[denis_berthier]

.
THE TRIDAGON ELIMINATION RULE EXAMPLE:
Based on previous definitions of a "trivalue oddagon" or "Thor's Hammer" pattern (which is not a resolution rule in and of itself), I've introduced a formulation of a "tridagon elimination rule": http://forum.enjoysudoku.com/the-tridagon-rule-t39859.html
If you follow the proof of eliminations I gave there (reviewing all the possible cases modulo isomorphisms, you will see that it also proves that the tridagon elimination rule has T&E-depth 4

[denis_berthier]

.
For very interesting examples of exotic patterns possibly associated with resolution rules with large T&E-depth, see mith's specific thread: http://forum.enjoysudoku.com/chromatic-patterns-t39885.html

In the present thread, I'm more interested in theoretical basis for dealing with such patterns. I don't think the vague notion of a chromatic number based on numbers of cells and different from the classical notion of chromatic number in graph theory can bring anything new to the discussion.
Because the resolution state is fundamentally a graph of candidates with direct contradiction links, T&E-depth is related to the classical chromatic number in obvious ways.

Also, notice I've defined only the T&E-depth of a resolution rule, not of a pattern. I'll say more on this topic later.

[denis_berthier]

.
First, let me recall my global philosophy about classification or rating: there can't be any unique classification/rating system. Any such system depends on one's goals and even with fixed general goals, there remains many possible systems.

This "relativism" doesn't mean that all such systems are "equal". Some are clearly better than others:
- because they are intrinsic (e.g. invariant under Sudoku isomorphisms);
- and/or because they are founded in logic (instead of on arbitrary choices of rules/procedures);
- and/or because they can classify/rate all the Sudoku puzzles (or still better all the logic puzzles of some general type);
- and/or because they don't involve exotic patterns that apply only in rare cases.

But in any case, this "relativism" implies that one must be aware that adding a new resolution rule or (more generally a new resolution method, e.g. some exotic pattern of some form of T&E) in an existing classification/rating system requires some interpretation of this new rule/method in the original system. This is the only way the impact of the new rule/method can be estimated wrt to the original classification/rating system.
I know, traduttore traditore. But there's no way to avoid this.


Some examples of rating systems are SER, gsf's rating, q1, q2...

But what I'll consider here is my usual very broad universal classification:
- T&E(0) (~ solvable by Singles)
- T&E(1) (~ solvable by braids)
- T&E(2) (~ solvable by B-braids)
...
together with the sub-classifications specific to each T&E-level:
- the Bn hierarchy inside T&E(1)
- the BnB=T&E(Bn, 1) hierarchy inside T&E(2)
- the BnBB=T&E(Bn, 2) hierarchy inside T&E(3)
...

This universal classification doesn't take into account any generic or application-specific pattern that is not directly related to it - not even Subsets.
My view is, with respect to this classification, such patterns are short-circuits that allow to downgrade a puzzle form one level to a lower one (the downgrading depending on the puzzle).
This applies to the simplest patterns (such as Triplets) as well as to the most complex ones (such as sk-loops or Tridagons).

For an example of a Swordfish that brings down a puzzle from T&E(2) to T&E(0), i.e. Singles, see section 8.8.2 of [PBCS].
For an example of an sk-loop that brings down a puzzle from from B3B to gB=B1B, see section 13.6 of [PBCS].
For lots of examples of Tridagons that bring down a puzzle from T&E(3) to much lower levels, see this thread: http://forum.enjoysudoku.com/the-tridagon-rule-t39859.html
For an example of eleven's replacement method (not a resolution rule) that brings down a puzzle from W6 to Z4 (both within T&E(1)) see here: http://forum.enjoysudoku.com/post316286.html?hilit=replacement#p316286


Of course, it works both ways. You can start from any other classification/rating system. If you introduce anything new into it (e.g. some form of T&E), you create (puzzle-dependent) short-circuits between its levels. Example: the standard SER vs a version of SER without uniqueness; for an example by mith, see the end of this post: http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1243.html

[denis_berthier]

.
Someone asked me by email how the T&E-depth of a resolution rule (as defined in this thread) relates to the minimal T&E-depth necessary for proving that a pattern P is contradictory (as I have done in many posts related to anti-tridagons or k-digit patterns).
The answer is trivial:
the T&E-depth of a contradictory pattern P is defined as the T&E-depth of the resolution rule: P => FALSE