This repository implements Knuth's Algorithm X, which solves the exact cover problem, using a technique called "dancing links" (see the linked paper). The implementation is a port from this blog post's Go code to a C library. I added some logic to generalize it to arbitrary problem sizes.
get_matrix takes the number of secondary and primary columns as arguments and constructs the data structure. It
transfers ownership of the matrix to the caller by returning the pointer.
Add constraints (aka rows), by calling add_constraints. You have to construct the specific constraints for your
problem, see the 'main.c' file for an example how these look for the n-queens problem.
Call algorithm_x on the constructed matrix to get the number of possible solutions and use destroy_matrix to release
the resources.
The n-queens problem can be seen as a generalized version of an exact cover problem and is used to demonstrate the
functionality of the library.
The challenge is to place n queens on an n x n chessboard, without any queen attacking another queen.
The file 'main.c' demonstrates how to use the library to solve that problem. See the blog post linked above for some
explanation how the constraints are constructed.
For compilation run make all and execute with build/main [<number_of_queens>] (Default number of queens is 7).