Here is a demonstration of the Dancing Links idea (

Wikipedia definition).

The idea is this: if you remove an item from a doubly-linked list, you can put it right back in as long as you hold on to it. And, if you remove items , you can put them right back *as long as you reverse the order exactly*, .

This is done as follows:

// Remove: `curr` is forgotten by neighbors
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
// Reinsert: 'curr' knows where to go, and steps right back in!
curr->next->prev = curr;
curr->prev->next = curr;
// Works over and over, as long as it's done in stack order:
// remove=push, reinsert=pop.
dancing_link_remove(A);
dancing_link_remove(B);
dancing_link_reinsert(B)
dancing_link_remove(C);
dancing_link_reinsert(C)
dancing_link_reinsert(A)

This works well where you’re drilling in to search but need to backtrack too — you can do so without the need to work with multiple copies.

And finally, this is demonstrated in git and as follows:

*Related*

Pingback: Exact Cover Problem and Knuth’s Algorithm X | Derek Illchuk - Computations