Question about Knuth's "Dancing Links" / DLX algorithm (in Python)

Question

I've been reading quite a bit about the "Exact Cover" problem and Knuth's solution using heavily linked lists. I think I understand about 70% of it, but still confused on how the linked-lists "cover" and "uncover" are supposed to work.

Knuth's paper: https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf

What I understand / have coded already:

• 72 bits wide. 12 columns for the pieces with 1 bit for in that piece's column, and then 60 columns of 1's and (mostly) 0's representing the piece's shape. So 72 bits wide (as a single Python int) by 1,928 rows (every valid move of every piece against every square)

• All the nodes with 0's have been removed and remaining link pointers adjusted

• Entirely linked-lists, per Knuth. My data structure looks just like that on page 5 of Knuth's paper: I have the regular data nodes, the column heading nodes, the main "h" node, and everything is cross linked, left/right, up/down, etc., so I completed the Sparse Matrix doubly linked lists, both left/right and up/down.

• For nodes, I've written the remove node and add-back a node.

Where I'm stuck:

• When they say to "cover" a column, I'm a bit confused. Do I delete (unlink) just the column-heading node for that column, from the list of column header nodes? Or do I remove all the nodes in that column?

• I'm more confused about Rows. When they say to "cover a row", I'm not sure what changes to make to my data structures. There's no "row" headers to tweak like there are for columns, and I'm pretty sure that's not an omission. There aren't any "row headers", just column headers. So if I want to temporarily remove a row, what do I change? Do I cycle through all the nodes in that row and remove them all one-by-one? Then add them all back one by one if I backtrack? Seems like a lot to be removing and adding back, so I'm pretty sure this is the part I'm not understanding.

Happy to answer/edit to make the question clearer. Since my code is lengthy and a mess, I'm not planning to post it at this time (unless folks really think it would help, but it's linked lists, exactly like Knuth showed, so I think the code would be a distraction.

So, when using Knuth's linked lists (with column headings), how do you "cover" a column, and more importantly, how do you "cover" a ROW??

Thanks, Mark

Answer 1

When they say to "cover" a column, I'm a bit confused. Do I delete (unlink) just the column-heading node for that column, from the list of column header nodes? Or do I remove all the nodes in that column?

The latter -- each column must have exactly one incident row belonging to an exact cover, so those nodes cannot be used in the current subtree.

I'm more confused about Rows. When they say to "cover a row"

I couldn't find that text in Knuth's article. Presumably what is meant is that, when you descend in the solution tree by choosing a row to add to the cover, you need to cover all of its incident columns.

Perhaps a cleaner way to put it is that, when you choose a row, you need to remove all other rows at distance 2 in the bipartite graph corresponding to the incidence matrix.