2
$\begingroup$

Right now I am working on my implementation of Knuth's DLX algorithm.

I did understand the exact cover problem. But I didn't fully understand how Dancing links works. Here is Knuth's paper. The question is about the solutions presented in the paper. I don't understand how these solutions make sense taking into account the matrix that he uses.

Matrix for the exact cover problem

     A B C D E F G
  1  0 0 1 0 1 1 0
  2  1 0 0 1 0 0 1
  3  0 1 1 0 0 1 0
  4  1 0 0 1 0 0 0
  5  0 1 0 0 0 0 1
  6  0 0 0 1 1 0 1

And solutions are:

A D
B G
C E F

But how come these solutions are valid? Isn't it supposed to be answered like A B E? Where in each row there is only one 1.

$\endgroup$
2
$\begingroup$

Knuth is trying to cover the columns using rows. The solution you describe consists of rows 4, 5, 1, in this order (counting from 1). Each row is represented by its 1-columns. For example, row 4 is 1001000, and its 1-columns are AD.

$\endgroup$
  • $\begingroup$ I am confused. In the exact cover problem, you have two sets of the coordinates and you just threw away all colliding values until you have only ones that do not collide. But here logic is different. Can you please provide an example how A D variant is correct? $\endgroup$ – Soul Bruteflow Jan 26 '17 at 10:35
  • $\begingroup$ The A D variant is not correct - it's a misinterpretation. It's a single solution consisting of three rows: AD corresponds to row 4, BG corresponds to row 5, and CEF corresponds to row 1. $\endgroup$ – Yuval Filmus Jan 26 '17 at 11:12
  • $\begingroup$ Thank you very much for the response and explanations. I finally understood how it works. Because rows don't have their own names, but columns are. And we need a row name to print. We combine column names and print them. So 1 becomes CEF, 2 becomes ADG etc. And the answer (AD, BG, CEF) is 4, 5, 1. $\endgroup$ – Soul Bruteflow Jan 26 '17 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.