It really depends on how much internal structure the problem has, but it can be quite fast -- for the right problem. You're trading a lot of book-keeping for the ability to learn about internal states. This is sort of like how CDCL for a SAT solver works, where you gain clauses that tell you how to avoid some areas of the problem space, but instead here you gain knowledge of all the combined solutions down in some pattern of rows/columns. There are plenty of cases where it doesn't pay out at all though, because the sub-problems aren't sufficiently separable, e.g. using it for something like n-queens you get no benefit.
@@ekmett Thank you for the swift reply ! I was primarily interested in this algorithm to generate floor plans or do some polyomino tilings; do you think it would be appropriate for this type of problem ? That said, I am very impressed by your coding skills and your ability to implement DXZ in such a short period of time. I honestly wish I could do the same but truth is it is way beyond my capacities. Would you know by chance a framework or a library that has that algorithm already implemented ?
@@nouv0 It should work quite well for that scenario. Unlike the crazy one-off line of sight sets left by the queens that I used as a contrary example, polyominos should have many combinations that yield the same sub-problem.
Just a question: was it really faster than DLX by several orders of magnitude as the authors state in the paper ?
It really depends on how much internal structure the problem has, but it can be quite fast -- for the right problem. You're trading a lot of book-keeping for the ability to learn about internal states. This is sort of like how CDCL for a SAT solver works, where you gain clauses that tell you how to avoid some areas of the problem space, but instead here you gain knowledge of all the combined solutions down in some pattern of rows/columns. There are plenty of cases where it doesn't pay out at all though, because the sub-problems aren't sufficiently separable, e.g. using it for something like n-queens you get no benefit.
@@ekmett Thank you for the swift reply ! I was primarily interested in this algorithm to generate floor plans or do some polyomino tilings; do you think it would be appropriate for this type of problem ? That said, I am very impressed by your coding skills and your ability to implement DXZ in such a short period of time. I honestly wish I could do the same but truth is it is way beyond my capacities. Would you know by chance a framework or a library that has that algorithm already implemented ?
@@nouv0 It should work quite well for that scenario. Unlike the crazy one-off line of sight sets left by the queens that I used as a contrary example, polyominos should have many combinations that yield the same sub-problem.
By way of evidence, IIRC, a couple of the examples in the DXZ paper were tetromino puzzles.