Mathimagics wrote:Here are a few more test cases for you: (...)
The first one, it handled in 1.40 seconds.
For the other two, with no results after ~3 hours each, I killed the processes.
Does your "traversals" code work well with those two, too ?
I had experimented with a SAT solver but found it unpromising, initially. I will have to revisit that.
For situations where DLX performs adequately, a SAT solver would probably (?) be slower.
This one ... MiniSat ... uses something called "conflict driven clause learning", that can keep it from getting bogged down in areas where DLX code can get stuck for a long long time.
Can you explain "uses DLX to set the clues"?
For my DLX code, at least ... there's an inital setup of nodes and "links" (and so on), that would reflect the "pencil mark problem" for an empty sudoku grid. Then when you ask it to solve a particular puzzle, it goes through a phase where it treats each "clue" in the same way that it would treat a "guess" in the search loop. At that point, the nodes & links that are still in play, reflect the (starting) pencil mark problem for the puzzle itself -- clue cells filled, "line of sight" eliminations made ... only so many cell values remaing in each house, and so on. It's that "state" that gets converted into a SAT problem.
For DLX code in general, there's no reason that things should always work in that way.
You could a set up a special "exact cover" problem, for each puzzle, for example, and pass it to a "universal" DLX implementation.
[ Maybe that's what you're doing (?) ]