libexact

libexact is a software library for solving combinatorial exact covering problems. As an example of such a problem, consider the following sudoku puzzle (courtesy of Gordon Royle and the University of Western Australia; see here):

.......1.
4........
.2.......
....5.4.7
..8...3..
..1.9....
3..4..2..
.5.1.....
...8.6...

An equivalent task (in the form understood by libexact) is to find a set of columns in the following 256-by-303 matrix such that every row is covered exactly once, that is, such that every row has exactly one black pixel.

The unique solution (as computed by libexact) and the corresponding solution of the sudoku puzzle are displayed in red below:

693784512
487512936
125963874
932651487
568247391
741398625
319475268
856129743
274836159

For the sudoku solver application, see the file examples/example-sudoku.c in the libexact source archive.