Stanford Lecture: Dr. Don Knuth - Dancing Cells (2023)

This talk is sort of a sequel to “Dancing Links”, the Christmas Lecture of 2018, because there have been surprising new developments since then—stimulated by the work of Christine Solnon at INSA de Lyon.

When a computer program explores a large space of possibilities, it needs good data structures that are able to undo every tentative decision that has been made, thereby allowing new decisions to take their place.

The dancing links idea is a simple modification of a 60-year-old method (doubly linked lists), which is particularly suited to undoing. As a result, algorithms based on dancing links have become the method of choice for exploring the set of solutions to a huge variety of combinatorial problems.

The dancing cells idea, similarly, is a simple modification of a 30-year-old method (sparse-set representation), and it provides efficient support for that same wide class of applications. Indeed, programs based on dancing cells often turn out to be significantly faster than the analogous programs based on dancing links. And again, there is exquisite choreography!