In computer science, Dancing Links, also known as DLX, is the technique suggested by Donald Knuth to efficiently implement his Algorithm X. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku.
The name Dancing Links comes from the way the algorithm works, as iterations of the algorithm cause the links to "dance" with partner links so as to resemble an "exquisitely choreographed dance." Knuth credits Hiroshi Hitotsumatsu and Kōhei Noshita with having invented the idea in 1979, but it is his paper which has popularized it.
Read more about Dancing Links: Implementation
Famous quotes containing the words dancing and/or links:
“I’ve learned one thing about life. We’re a good deal like that ball, dancing on the fountain. We know as little about the forces that move us, and move the world around us, as that empty ball does.”
—Ardel Wray, Edward Dien, and Jacques Tourneur. Dr. Galbraith(James Bell)
“Ibsen is like this room where we are sitting, with all the tables and chairs. Do I care whether you have twenty or twenty-five links on your chain? Hedda Gabler, Nora and the rest: it is not that I want! I want Rome and the Coliseum, the Acropolis, Athens; I want beauty, and the flame of life.”
—Eleonora Duse (1859–1924)