JasonLion wrote:I explored a breadth first multi-digit 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 template-BFS 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 template-BFS (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 template-DFS 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 template-depth 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 "template-Singles".
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 template-BFS depth of P (considering that single choices don't increase depth).
Additional background:
There is an easily provable relationship between the T&E-depth of a puzzle and its complexity in terms of braids:
- depth 0 = solvable by Singles
- depth 1 = solvable by braids
- depth 2 = solvable by B-braids
There is an additional experimental result: depth 2 = solvable by B7-braids, for all the known puzzles.
By analogy with the T&E case, my questions are:
-
what is the maximal template-depth for all the minimal puzzles?-
is there any relationship between template-depth and difficulty (measured e.g. by SER)?(Notice that the above analogy is purely formal, as T&E excludes any form of guessing, whereas template-DFS or template-BFS do not.
Maybe a better analogy for template-depth 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.)
)
