NAME
Algorithm::X::DLX - Solve exact cover problems with Algorithm-X and Dancing Links
DESCRIPTION
The ubiquitous implementation of Donald Knuth's Algorithm X with dancing links. Algorithm X is a clever way to execute a brute force search, aiming to find the solutions for any specific exact cover problem. The dancing links technique (DLX) for generic backtracking was published by Hiroshi Hitotsumatsu and Kōhei Noshita in 1979 already.
DISCLAIMER
Author of the originating C++ sources, of which this distribution is mostly a direct translation, is Johannes Laire at https://github.com/jlaire/dlx-cpp. Even all the examples, tests and most of the documentation are by him.
There only are two notable deviations from the original:
The backtracking in Algorithm::X::DLX is done iteratively, without recursion. So it's possible to process huge matrices without worrying about memory.
It's still possible to compare performances between selecting random colummns with lowest node count and just picking the first one (left most) of these by providing the option
choose_random_column, but the ability to further differentiate and select a specific random engine withrandom_enginehas been removed. It now just uses the Perl standard random engine on your system.
SYNOPSIS
use Algorithm::X::DLX;
my $problem = Algorithm::X::ExactCoverProblem->new($width, \@input_rows, $secondary_column_count);
my $dlx = Algorithm::X::DLX->new($problem);
my $result = $dlx->search();
foreach my $row_indices (@{$result->{solutions}}) {
...
Or better, especially with searches taking a very long time
my $iterator = $dlx->get_solver();
while (my $row_indices = &$iterator()) {
...The Example applications provided under examples/...
There are scripts and modules for various exact cover problems:
N-queens, Langford, Sudoku, N-pieces and Pentominoes
examples/dlx.pl
And a more generic script that makes use of this lib.
examples$ ./dlx.pl -pv < data/knuth_example.txt
1 0 0 1 0 0 0
0 0 1 0 1 1 0
0 1 0 0 0 0 1
solutions: 1DEPENDENCIES
COPYRIGHT AND LICENSE
The following copyright notice applies to all the files provided in this distribution, unless explicitly noted otherwise.
This software is copyright (c) 2025 by Steffen Heinrich
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.
SEE ALSO
Donald E. Knuth, Stanford University 2000 Dancing Links
Introduction to Exact Cover Problem and Algorithm X
Peter Pfeiffer BSc, Linz 2023 Uncovering Exact Cover Encodings