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:
“We have dancing ... from soon after sundown until a few minutes after nine o’clock.... Occasionally the boys who play the female partners in the dances exercise their ingenuity in dressing to look as girlish as possible. In the absence of lady duds they use leaves, and the leaf-clad beauties often look very pretty and always odd enough.”
—Rutherford Birchard Hayes (1822–1893)
“An alliance is like a chain. It is not made stronger by adding weak links to it. A great power like the United States gains no advantage and it loses prestige by offering, indeed peddling, its alliances to all and sundry. An alliance should be hard diplomatic currency, valuable and hard to get, and not inflationary paper from the mimeograph machine in the State Department.”
—Walter Lippmann (1889–1974)