
Dancing Cells
Donald Knuth delivers his 27th Annual Christmas Tree Lecture at Stanford, presenting a sequel to his 2018 talk on Dancing Links. He introduces dancing cells, a modification of the thirty-year-old sparse-set representation technique, built to solve the same problem dancing links addresses: how a computer program exploring a huge space of possibilities can efficiently undo tentative decisions and backtrack to try new ones. Knuth credits the recent developments to Christine Solnon's work at INSA de Lyon and walks through why programs built on dancing cells often run significantly faster than their dancing-links counterparts when searching for solutions to combinatorial problems. The talk runs ninety-three minutes and assumes some comfort with data structures and algorithmic search, rewarding anyone who wants to see a veteran computer scientist work through a concrete technical improvement step by step, with his characteristic attention to the elegance of the underlying choreography.