NAME
Algorithm::DLX::Examples - Application of Algorithm::DLX to various exact cover problems
DESCRIPTION
Algorithm::DLX comes without any documentation towards the modules usage, so take a look at these examples all of which are included in the examples directory.
The modules can also solve generalized exact cover problems (see Knuth's paper). The columns of the matrix should be sorted so that all secondary columns are on the left, before primary columns. Beside dlx, N-queens is a good example of this.
Running examples/...
These modules are not installed. Extract the examples directory from the distribution and put the resp. script's directory into @INC where necessary.
Testing examples
All example modules come with their resp. tests, which are not run at installation time. You would have to call them manually.
$ prove examples/t/*Example: dlx
examples/dlx.pl is a simple command-line program that reads an exact cover problem from stdin and solves it.
The first line of stdin contains the number of columns, and the following lines contain the rows of the matrix.
Output can be controlled by flags. By default, only the number of solutions is printed. If -p is given, every solution is printed on its own line by giving the indices of the selected rows. With -v, the full rows are printed.
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: 1With -s, input can be given as a sparse matrix.
examples$ ./dlx.pl -ps < data/knuth_example_sparse.txt
3 0 4
solutions: 1To solve a generalized exact cover problem, put the number of secondary columns on the first line, after the number of all columns. The default value is zero, in other words, a regular exact cover problem.
examples$ ./dlx.pl -pv < data/generalized_example.txt
0 1 1
solutions: 1Example: Sudoku
This program can solve and generate various types of Sudokus. See example/sudoku/README.md for details.
examples/sudoku$ perl -I. sudoku.pl < ../data/sudoku.txtExample: N-queens
Place N queens on an NxN chessboard so that they don't attack each other. This is a good example of a generalized exact cover problem: each diagonal must contain at most one queen, but zero is ok.
examples/nqueens$ perl -I. nqueens.pl 8 12
Solutions for n=8: 92
Solutions for n=12: 14200
examples/nqueens$ perl -I. nqueens.pl -v 1 2 3 4
Solutions for n=1: 1
Q
Solutions for n=2: 0
Solutions for n=3: 0
Solutions for n=4: 2
..Q.
Q...
...Q
.Q..
.Q..
...Q
Q...
..Q.Example: Langford pairings
See https://en.wikipedia.org/wiki/Langford_pairing.
examples/langford$ perl -I. langford.pl -v 1 2 3 4 5
Solutions for n = 1: 0
Solutions for n = 2: 0
Solutions for n = 3: 1
3 1 2 1 3 2
Solutions for n = 4: 1
4 1 3 1 2 4 3 2
Solutions for n = 5: 0Example: N-pieces
Generalized version of N-queens: place N knights and Q queens on an AxB board. Quite slow, unfortunately.
examples/npieces$ perl -I. npieces.pl 8 8 5 5
Solution 1
NN......
....Q...
......Q.
NN......
N.......
.......Q
.....Q..
..Q.....
<snip>
Solutions for 8x8, N=5, Q=5: 16Example: Polyominoes
The code can solve any polyomino puzzle, but for now the executable simply prints all solutions to Scott's pentomino problem:
examples/polyomino$ perl -I. polyomino.pl | head -n8
LLXCCVVV
LXXXCVZZ
LNXCCVZY
LNT ZZY
NNT WYY
NTTTWWFY
PPPWWFFF
PPIIIIIFDISCLAIMER
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 his.
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