Denis Berthier wrote:When you check a puzzle for uniqueness, can you avoid using recursive T&E?

BTW, if you (or others here) don't like the name T&E for the recursive search procedure defined at the start of in this thread, can you suggest any better name?

When

my program checks a puzzle for uniqueness, it uses Knuth's

Dancing Links technique. This is a fast depth-first, brute force backtracking method which is based on his Algorithm-X.

Since I use it as a verification and not as a part of the solving process, I do not see the relevance of your question. Because it is so fast, I don't

want to avoid it.

The recursive T&E you're describing sounds more like backtracking.

In my perception, the

unforgivable techniques are:

brute force/backtracking Try every possibility.

guessing: Make random placements, eliminate when it leads to an error, claim victory if it leads to the solution, undo when no definitive result.

T&E: Make random placements, eliminate when it leads to an error

bifurcation: Same as guessing or T&E, but limited to bivalue/bilocal candidates

recursive bifurcation: Same as backtracking, but also limited to bivalue/bilocal candidates.

I realize this list has no mutually exclusive elements, but this is how these terms are commonly used in Sudoku-world.

I've experimented with taking measurements in the DLX process, to see if it could shed some light on the difficulty level. These measurements were done:

Number of non-trivial constraints in the direct path towards the solution. The maximum I've encountered for regular Sudoku is 6. There's no correlation between this measurement and the difficulty, other than a non-trivial count of 0 means that the puzzle can be solved with singles only.

Nodes investigated. Again, no correlation with difficulty, but I found that a standard Sudoku with a unique solution requires no more than 2000 nodes to be checked. The average is about 200 for non-trivial sudokus. To speed up my puzzle generator, I'm using a limit of 1500. For Sudoku-X, these values are 10 times higher.