DlxLib is a C# class library that solves exact cover problems by implementing Donald E. Knuth's Algorithm X using the Dancing Links technique as described in his paper, Dancing Links.
Given a matrix of 0s and 1s, it finds all solutions where a solution identifies a subset of the rows in the matrix such that every column contains exactly one 1.
The difficulty is in representing a given problem as a matrix of 0s/1s. But if you can figure out how to do that, then DlxLib can find all the solutions.
See the following link for a very nice tutorial on how DLX works and a practical application (solving a pentomino puzzle):
CS575: Dancing Links - Colorado State University
The following example shows how to use DlxLib to find the first two (of three) solutions to the matrix in the original Dancing Links paper.
var matrix = new[,]
{
{1, 0, 0, 0},
{0, 1, 1, 0},
{1, 0, 0, 1},
{0, 0, 1, 1},
{0, 1, 0, 0},
{0, 0, 1, 0}
};
var dlx = new Dlx();
var firstTwoSolutions = dlx.Solve(matrix).Take(2);DlxLib is available as a NuGet package.
The documentation for the DlxLib API can be found here.
I have created a Wiki page where I encourage people to add links to things that they have done using DlxLib:
The first demo application shows DlxLib being used to solve 2 simple matrices. For each solution, the entire matrix is written to the console with the solution row indexes and the 1's in the solution rows highlighted in yellow. This makes it clear to see that the solution rows have the property that there is exactly one 1 in each column.
The second demo application shows DlxLib being used to solve the same 2 simple matrices as the first demo application. However, the solutions are displayed in a different manner - only the rows that comprise the solution are displayed and we display the column names that correspond to the 1's.
The third demo application is a WPF application which shows a 14 piece draughtboard puzzle being solved. It redraws the board for each SearchStep event. It takes 23,316 iterations to find the first solution!
See also the following project:
See also the following project:
- Knuth's Algorithm X (Wikipedia)
- Dancing Links (Wikipedia)
- Exact cover (Wikipedia)
- CS575: Dancing Links - Colorado State University
DlxLib is licensed under MIT. Refer to license.txt for more information.