Algorithm-X-DLX

 view release on metacpan or  search on metacpan

README  view on Meta::CPAN

 Applies the usual D. Knuth's Algorithm X with dancing links technique (DLX, iteratively!), 
 to find all solutions to an exact cover problem.
 
 https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

 DISCLAIMER: 
 This distribution is a translation of the cpp sources at 
    https://github.com/jlaire/dlx-cpp
 into Perl.
    Johannes Laire is the original author of all these libs, alltogether with their comprehensive examples and tests.
 
 Steffen Heinrich, Feb. 2025
 

examples/sudoku/SudokuSolver.pm  view on Meta::CPAN

  $dlx_options->{max_solutions} = $dlx_options->{choose_random_column} ? 1 : 2;

  my $problem = Algorithm::X::ExactCoverProblem->new(4 * $type->size(), \@matrix);
  my $dlx = Algorithm::X::DLX->new($problem);
  my ($dlx_result) = $dlx->search($dlx_options)->{solutions};

  # Collect solutions
  my @solutions;
  
  foreach my $rows (@$dlx_result) {
    my @solved = @{$sudoku->{values_}}; # Copy original sudoku
    foreach my $i (@$rows) {
      if (exists($row_position{$i})) {
        $solved[$row_position{$i}] = $row_digit{$i} + 1;
      }
    }
    push @solutions, Sudoku->new($sudoku->type, \@solved); # Store solved sudoku
  }

  if (!@solutions) {
    croak "No solution";

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

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

lib/Algorithm/X/Examples.pod  view on Meta::CPAN

  LNT  ZZY
  NNT  WYY
  NTTTWWFY
  PPPWWFFF
  PPIIIIIF

entire L<output|https://metacpan.org/dist/Algorithm-X-DLX/source/examples/polyomino/solutions-to-scotts-pentomino.txt>

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

=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