Algorithm-X-DLX

 view release on metacpan or  search on metacpan

examples/dlx.pl  view on Meta::CPAN

}

sub HELP_MESSAGE {
  my $script = $0;
  $script =~ s|^.*/||;
  print<<HELP

Usage: $script -[options] <input>

Option flags are:
 -p print solutions as a line with selected row indices
 -v print solutions by outputting the rows themselves
 -t print nodes inspected for each recursion level
 -s input is a sparse matrix

The first line of input states the problem matrix width (all columns), optionally 
followed by a space and the number of secondary columns therein, at the right.
All following lines are the matrix rows (space separated).

HELP
;

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

  $options->{max_solutions} = $max if defined $max;

  return $self->search($options)->{solutions};
}

sub search {
  my ($self, $options) = @_;
  $options ||= Options();
  
  if ($options->{random_engine}) {
    die "The option to select a random engine has been removed in Perl";
  }

  my $result = { profile => [], number_of_solutions => 0, solutions => [] };
  $self->{iterator} ||= $self->get_solver($options->{choose_random_column}, $result->{profile});

  while (my $solution = $self->{iterator}() ) {
    $result->{number_of_solutions}++;
    if ($options->{get_solutions}) {
      push @{$result->{solutions}}, $solution;
    }

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

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);

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

  $ prove examples/t/*

=head2 Example: dlx

L<examplesE<sol>dlx.pl|https://metacpan.org/dist/Algorithm-X-DLX/source/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 C<-p> is given, every solution is printed on its own line by giving the indices of the selected rows. 
With C<-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: 1

With C<-s>, input can be given as a sparse matrix.