CODEWITHSUNDEEP
calgorithmknuth
Dragno
Dragno

Reputation: 3124

An explanation of terms for D.Knuth's dancing links algorithm

I have downloaded from D.Knuth's website the DLX algorithm. In the first section in which D.Knuth gives an overview of the problem, separates the columns to "primary" and other columns. Which are these "primary" columns? Thanks in advance.

Upvotes: 1

Views: 323

Answers (1)

user555045
user555045

Reputation: 64903

It's a slight generalization of Exact Cover. As noted on the relevant wikipedia page, this generalization makes a distinction between "primary columns", for which the rules are the same as in the basic Exact Cover ("exactly one"), and "secondary columns", which are "at most one". The reason for this generalization is that it can be handled directly and efficiently by Dancing Links while converting it to an equivalent normal Exact Cover problem is less efficient.

There are more details in Knuths paper about Dancing Links.

Upvotes: 2

Related Questions