libexact is a software library for solving combinatorial exact covering problems. It implements essentially the backtrack algorithm and the dancing links data structure described in “Donald E. Knuth, Dancing Links, Millennial Perspectives in Computer Science (J. Davies, B. Roscoe, and J. Woodcock, Eds.), Palgrave, Basingstoke, England, 2000, pp. 187–214“ (preprint).
The library is written in C, with an honest attempt to conform to the ISO/IEC 9899:1999 standard (C99), and should work on most modern operating systems (e.g. Linux, FreeBSD, Sun Solaris, Mac OS X, Tru64 UNIX and Microsoft Windows).
libexact is currently at version 1.0 (first public release, June 30, 2008).
Downloads:
On most UNIX systems libexact can be compiled by simply running the command make. Testing the library by running the test executable test is strongly recommended. Please note that some of the tests do take some time to complete.
libexact is licensed under the GNU General Public License, version 2, or (at your option) any later version. No guarantees or warranties are made concerning the correctness of this software. Any use is at your own risk.
Copyright © 2008 Petteri Kaski, Olli Pottonen.
Petteri Kaski, petteri.kaski(at)aalto.fi, Aalto University Department of Information and Computer Science
Olli Pottonen, olli.pottonen(at)iki.fi, School of Mathematics and Physics, The University of Queensland