stlab.adobe.com Adobe Systems Incorporated

dancing_links Class Reference
[Node Algorithms]

An optimized implementation of the 1-cover problem [class under review]. More...

#include <adobe/dancing_links.hpp>


Detailed Description

The implementation is based on the Dancing Links Algorithm paper published by Knuth:
http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz
This class is an implementation of the "1-cover" problem:
Given a matrix of 1s and 0s, is there a subset of the rows such that there is one and only one 1 in each column?
It turns out a lot of interesting problems can be encoded in such a way that the 1-cover algorithm can be used to solve them (For example, counting the number of possible solutions to a Sudoku puzzle). Knuth talks in general about exact-cover problems (placing dominoes on a chessboard, the N-queens problem, etc.), and how each of these are specializations of the 1-cover problem, and so can be solved by this algorithm.

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google