Dancing Links

Dance of the edge is a technique for effectively managing lists in computer science. It allows an uncomplicated way to remove items in lists or rider.

For example, the element B have a list of the predecessor and the successor of A C. Each element has a reference to his predecessor and his successor: In the case of B A is B.links and C reached by B.rechts. A typical operation, to remove from the list B is:

B.links.rechts: = B.rechts; B.rechts.links: = B.links;

That is B.links, so A is replaced, replacing the element that was previously the successor of his successor, namely C. Accordingly, no longer receives B.rechts, ie C, the predecessor A. From A or C from B is now to reach. B is removed from the list.

The idea behind the dance of the edges is now that in B after removal still the information is stored to make removal reversed:

B.links.rechts: = B; B.rechts.links: = B;

Particularly useful is this principle for backtracking algorithms that achieve a certain status according to the principle of trial and error, and this must be undone if it is not solving the problem.

This technique was first introduced in 1979 by Hirosi Hitotumatu and Kohei Noshita. It owes its name Donald Knuth, the systematic change of the references looked like a dance. With their help, you can solve with the Dancing Links algorithm, the problem of exact registration.