JasonLion wrote:I explored a breadth first multidigit template solver, but it took too much memory to be useful.
Errr, sorry if I induced you to try this. When I said that "the BFS form of the question is simpler in its formulation", I meant it with emphasis on the phrase "in its formulation". I didn't expect anyone would try to implement templateBFS directly.
Let me more precise about the questions I raised.
First, let it be clear that I'm speaking about the original template procedure, first introduced by Ruud and rediscovered by pjb, with the definition of a template as I formalised it above, consistent with those of Ruud and daj95376. I'm not speaking of the partial rookeries and partial templates also discussed in this thread (which now appear to be the notions through which the original concept has found a new life).
Background: all the known puzzles can be solved by T&E(2)  according to my definition of T&E (
http://forum.enjoysudoku.com/post61854.html#p61854 and next posts), which I consider as the proper formalisation of the usual notion.
Corollary: all the known puzzles can be solved by BFS (pruned by Singles) at maximum depth 2.
Corollary of the corollary: all the known puzzles can be solved by templateBFS (pruned by Singles) at maximum depth 2. So if we accept pruning, my question has little interest (except if maximal depth could be reduced to 1  which is unlikely).
But, consider the pure templateDFS algorithm based on templates without any reference to candidates and without any pruning (by elementary constraints propagation and/or Singles). I think this version of this algorithm can be extremely fast because it needs to compute only set intersections.
For a puzzle P, define
TD(P), the templatedepth of P, as the minimum number of digits such that:
there is a way of choosing templates for TD(P) digits and a way of ordering the remaining 9  TD(P) digits such that there is at each step a unique possibility for the templates for each of these remaining digits;
said in vaguer terms, after templates have been properly chosen for TD(P) digits, the puzzle can be solved by "templateSingles".
TD(P) is an intrinsic property of P.
TD(P) can also be described in a
conceptually (but not computationally) simpler way: TD(P) is the templateBFS depth of P (considering that single choices don't increase depth).
Additional background:
There is an easily provable relationship between the T&Edepth of a puzzle and its complexity in terms of braids:
 depth 0 = solvable by Singles
 depth 1 = solvable by braids
 depth 2 = solvable by Bbraids
There is an additional experimental result: depth 2 = solvable by B7braids, for all the known puzzles.
By analogy with the T&E case, my questions are:

what is the maximal templatedepth for all the minimal puzzles?
is there any relationship between templatedepth and difficulty (measured e.g. by SER)?(Notice that the above analogy is purely formal, as T&E excludes any form of guessing, whereas templateDFS or templateBFS do not.
Maybe a better analogy for templatedepth would be with backdoor size  the max value of which is 3 for all the known puzzles.
Unfortunately, there doesn't seem to be much correlation between backdoor size and difficulty.)