Exact cover problems may be solved by using a backtracking algorithm, such as Algorithm X. One technique to implement Algorithm X is called Dancing Links.
It’s interesting to see it’s used in a few published solutions to the puzzles. While I’m not going to explain the implementation in this post, I’d like to compile a list of puzzles solvable by Algorithm X or its variants for those interested in practising:
I also read from here that it may be used in the optimisation puzzle Number Shifting, but I haven’t tried it myself. (Edit on 10 November 2022: I’ve tried it on the initial levels and it works.)
Interesting but very hard for me. I got quite rapidly a working dancing links implementation (a very elegant algorithm by the way) but I am banging my head when setting constraints. So far, I have solved sudoku, nqueens, dominoes and shikaku using DLX. I may succeed with futoshiki if I read what Knuth says about it at least one hundred times.
I am clueless with the rest. Did you solve all of them with DLX ?
Yes, I did. More accurately, I solved them using Algorithm X or some variants of it.
Have you tried implementing any variants of the algorithm? Knuth mentions some variants in his “The Art of Computer Programming”. For example, in some of the puzzles, I have to use Algorithm C to solve what Knuth calls “XCC problems”.
I need to read the whole chapter (not exactly suitable for reading on the beach though ). I have effectively noticed that there are variants to handle multiplicity for instance (the dreaded 16 queens problem).
Just curious: (if you solved some of these puzzles also without DLX):
How much speedup did you experience with Algo X + DLX vs a simple backtracking with a traditional matrix representation?
I still have three to go on your list and it has been an amazing Algorithm X experience. Kakuro Solver stretched my Algorithm X Solver to the absolute limit more than any of the others. I had to use every single feature I have built into my Algorithm X toolbox.
I have questions I hope you might shed some light on, but I’ll wait until I finish the last 3 puzzles (and Number Shifting of course) and then go back through the early ones and see if features I added later in the journey change my thoughts on anything.
By the way, my Algorithm X Solver doesn’t even use dancing links. I’m hoping to swap out my engine for DLX eventually, but I’ll just have to add that to my list of to-dos.
I’ve rewritten my Kakuro solver using Algorithm X. The time to finish all the 10 tests and 10 validators offline is reduced from 2.9 seconds (original code) to 0.28 seconds (revised code). I haven’t studied in detail how much of the time reduction is attributable to the algorithm though, given that I’ve made other optimisations e.g. in the generation of candidates.
I’ve also added Breaking Bifid to the list of puzzles.
My 2 cents on Killer Sudoku Extreme Challenge. Significant reduction must be performed logically before the puzzle can be solved with backtracking. I mentioned on the puzzle comments tab that the entire puzzle can be done with no guessing or backtracking. Because of the significant amount of logic that must be discovered before any solution is even possible with backtracking, I suggest any puzzler that has gotten that far go ahead and finish off the puzzle 100% logically - no backtracking at all.
). I have effectively noticed that there are variants to handle multiplicity for instance (the dreaded 16 queens problem).