view release on metacpan or  search on metacpan

lib/Algorithm/X/DLX.pm  view on Meta::CPAN

      }
    }
  };
}

sub Options {
  return  {
    choose_random_column => 0,
    get_solutions => 1,
    max_solutions => ~0,
  #  random_engine => undef,
  }
}

# acquire some matrix methods
sub cover_column   { return shift()->{A_}->cover_column(@_) }
sub uncover_column { return shift()->{A_}->uncover_column(@_) }
sub Y { return shift()->{A_}->Y(@_) }
sub S { return shift()->{A_}->S(@_) }
sub R { return shift()->{A_}->R(@_) }
sub L { return shift()->{A_}->L(@_) }
sub D { return shift()->{A_}->D(@_) }

1;

__END__

=encoding UTF-8

=head1 NAME

Algorithm::X::DLX - Solve exact cover problems with Algorithm-X and Dancing Links

=head1 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 I<exact cover problem>.
The dancing links technique (DLX) for generic backtracking was published by Hiroshi Hitotsumatsu and Kōhei Noshita in 1979 already.

=head1 DISCLAIMER

Author of the originating C++ sources, of which this distribution is mostly a direct translation, 
is Johannes Laire at L<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:

=over

=item * The backtracking in Algorithm::X::DLX is done iteratively, without recursion.
So it's possible to process huge matrices without worrying about memory.

=item * 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 C<choose_random_column>, but the ability to further differentiate...

=back

=head1 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()) {
    ...
  

=head1 The Example applications provided under examples/...

There are scripts and modules for various exact cover problems: 

N-queens, Langford, Sudoku, N-pieces and Pentominoes

See L<Algorithm::X::Examples>.

=head2 L<examplesE<sol>dlx.pl|https://metacpan.org/dist/Algorithm-X-DLX/source/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: 1

=head1 DEPENDENCIES

=over 5

=item * L<Carp>

=back

=head1 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.

=head1 SEE ALSO

Donald E. Knuth, Stanford University 2000 L<Dancing Links|http://arxiv.org/pdf/cs/0011047v1> 

L<Introduction to Exact Cover Problem and Algorithm X|https://www.geeksforgeeks.org/introduction-to-exact-cover-problem-and-algorithm-x/>

Peter Pfeiffer BSc, Linz 2023 L<Uncovering Exact Cover Encodings|https://epub.jku.at/obvulihs/download/pdf/9260418>

=cut