[johnsonjo]

Reading the wiki for Constraint Satisfaction Problems (CSP) brought back good memories of the time I decided to use Knuth’s Dancing Links and Algorithm X (DLX)[1] to solve sudoku (which apparently can be modeled as a CSP as well) for my Object Oriented class when I was still an Undergrad at University. I really wish I would have generalized my Algorithm X program (like Knuth did) to solve any of the possible exact cover constraint problems, but a lot of what was going on in his paper was unclear to me at the time and I didn’t see that he solved it more generally until later. It was really quite fun to finally see the program working and it was surprising how quick the program ran given that DLX is basically a brute force search backtracking algorithm.

I don’t know much of CSPs to know whether Knuth’s Dancing Links or his DLX was used all that often for them. I’m guessing an exact cover problem is one such CSP, but it seems that CSPs also use backtracking which it seemed to me that Dancing Links and sparse matrices were a good combo for that. Anyone have thoughts or inputs or corrections on whether what I said is correct about CSPs?

[1]: https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X