Right now I am working on my implementation of the D.Kuth DLX algorithm/data structure.
I know what is exact cover and how Dancing links works. But I have a question on his paper:
On page 5, he describes the implementation of the algorithm. And there, his "data object x" nodes have "C field" that points to the column object at the head of the relevant column. But I don't fully understand why he needs it and how he uses it? And the same goes for the "C filed" for the "column object".
typedef struct Data{
struct Data *left, *right, *up, *down;
struct Column *c;
} Data;
typedef struct Column{
struct Column *left, *right, *up, *down;
struct Data *c;
int size, name;
} Column;
The pointer you're talking about points to a header object that's used to indicate how many objects there are in the column (equivalently, how many 1s are in that column of the matrix). This is used so that the algorithm can heuristically determine which column to choose in the "choose a column deterministically" step, since you might want to do something like "choose the column with the fewest entries in it." The C fields make it easy to update the column headers when you splice a row out of the matrix: for each entry that's removed, follow the C pointer to the column header and decrement the counter there; for each entry that's reinserted, follow the C pointer to the column header and increment the counter there.