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.