7.2.2.1. Dancing links.
One of the chief characteristics of backtrack algorithms is the fact that they usually need to undo everything that they do to their data structures. In this section we’ll study some extremely simple link-manipulation techniques that modify and unmodify the structures with ease. We’ll also see that these ideas have many, many practical applications.
Suppose we have a doubly linked list, in which each node X has a predecessor and successor denoted respectively by LLINK(X) and RLINK(X). Then we know that it’s easy to delete X from the list, by setting
At this point the conventional wisdom is to recycle node X, making it ...
Get The Art of Computer Programming, Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
