mathimagics wrote:It took my DFS solver 275,416 visits to find the first solution (which took 5m 30s). To enumerate all solutions (of which there are 2,748,444) took 12 million visits and nearly 2 hours.

I'm an idiot (v3, or is that v4?)!

For weakly-specified puzzles, the order of DFS move selection certainly does matter. If I adopt the simple expediency of testing the available moves from the middle one first, then mid +/- 1, 2 etc then I will find the first solution, and the second, far more quickly.

For the allegedly pathological case in question, DFS = 15 (!) was sufficient to determine non-U'ness, and .01s the time!

For complete enumeration both DFS visit count and time are, of course, unaltered.

Urrgh! I really could kick myself ...