pjb wrote:Briefly, one takes the first pattern of number 1 and adds the 9 addresses to an array. One then takes the first pattern of number 2 and checks if any one of its 9 addresses coincides with one of those of the pattern for 1. If not, its 9 addresses are added to the array, otherwise it is discarded and the second pattern of number 2 is taken. By working through digits 1 to 9 using this process, one eventually ends up with all 81 addresses in the array, and the puzzle is solved.
I've just found this thread.
I'd formalise and summarise your method as follows, which makes it appear as
standard depth-first search (DFS) applied to templates.
If I'm right, then what's new (AFAIK, but I don't know POM) is the idea of applying DFS to templates instead of candidates.
Definition: a
template is a set of 9 cells such that no two of them see each other.
It is easy to see that there are 46,656 templates (as already mentioned by daj95376), independent of any particular puzzle; they can be pre-computed and ordered before any resolution starts.
Definition: two templates are
compatible if they are disjoint (as sets of cells).
As the test for set disjointness can be very fast, it doesn't seem useful to pre-compute this compatibility relation.
Definition:
a template for a digit k is a template all the cells of which are assigned value k.
Definition: given a puzzle P, a template T for a digit k is compatible with the clues of P if:
- all the clues for digit k in P are in cells of T,
- all the clues for other digits in P are in cells not in T.
Definition:
Sudoku problem: find 9 templates, one for each digit, such that:
- each of them is compatible with the clues,
- they are pairwise compatible.
Basic resolution procedure: depth-first-search (DFS), with maximum depth 9
for i=1 to 9
- choose the next template Ti (in the fixed vector of templates) for number i, compatible with the clues and with the previously chosen Tj's
- if no such template can be found, backtrack to the previous value of i
[add some exit condition]
Output (as usual for DFS):
Depending on the exit condition: either 0, 1, n, or all the solutions
Range of application:
any puzzle, with 0, 1 or more solutions
Optimisations:
- use this procedure only after all the eliminations and assertions that can be obtained from some predefined set of rules (for this, define the notion of compatible with a PM, in the obvious way, extending "compatible with a puzzle");
- choose more smartly the order of the digits (e.g. choose at each step the digit that has the fewest templates compatible with the current situation);
Not sure that any of this wouldn't degrade speed instead of improving it.
Questions (maybe close to already raised ones, but maybe different):
1) What is the smallest value of k such that, for all the minimal puzzles P, using only this basic procedure (excluding any rule application), but after a proper re-ordering of the digits, the full solution of P can be obtained, after templates have been chosen for only k or fewer digits, by a sequence of single-possibility choices (of templates for the remaining digits)?
Alternative formulation: applying BFS (breadth-first search) instead of DFS to templates, what is the maximal depth of search necessary to solve all the minimal puzzles?
2) What is the current largest known value of the minimum k for a minimal puzzle?
3) Is there any correlation between the difficulty of a minimal puzzle (say its SER) and its minimum k?
)
