view release on metacpan or  search on metacpan

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

        $state_stack[$level] = [$c, $r];
        $level++;

        if (@state_stack == $level) {
          push @state_stack, [undef, undef];
        } else {
          $state_stack[$level] = [undef, undef];
        }

      } else {
        if ($c != $r) {
          pop @placed;

          for (my $j = $self->L($r); $j != $r; $j = $self->L($j) ) {
            $self->uncover_column($j);
          }
        }
        $self->uncover_column($c);
        $level--;
      }
    }
  };
}

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.