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:
“Our culture, therefore, must not omit the arming of the man. Let him hear in season, that he is born into the state of war, and that the commonwealth and his own well-being require that he should not go dancing in the weeds of peace, but warned, self- collected, and neither defying nor dreading the thunder, let him take both reputation and life in his hand, and, with perfect urbanity, dare the gibbet and the mob by the absolute truth of his speech, and the rectitude of his behaviour.”
—Ralph Waldo Emerson (1803–1882)
“The conclusion suggested by these arguments might be called the paradox of theorizing. It asserts that if the terms and the general principles of a scientific theory serve their purpose, i. e., if they establish the definite connections among observable phenomena, then they can be dispensed with since any chain of laws and interpretive statements establishing such a connection should then be replaceable by a law which directly links observational antecedents to observational consequents.”
—C.G. (Carl Gustav)