Algorithm-X-DLX

 view release on metacpan or  search on metacpan

examples/dlx.pl  view on Meta::CPAN

getopts('pvst', \my %opts)
  or HELP_MESSAGE();

my $opt_verbose         = $opts{v};
my $opt_print_solutions = $opts{p} || $opts{v};
my $opt_sparse          = $opts{s};
my $opt_print_tree      = $opts{t};

chomp(my $line = <STDIN>);
my ($width, $secondary_columns) = split ' ', $line;

my @input_rows;
while (defined($line = <STDIN>)) {
  chomp($line);

  my @row;
  if ($opt_sparse) {
    @row = sort { $a <=> $b } split ' ', $line;

  } else {
    @row = split ' ', $line;
  }
  push @input_rows, \@row if @row;
}

my $problem = $opt_sparse ? Algorithm::X::ExactCoverProblem->new($width, \@input_rows, $secondary_columns)
                          : Algorithm::X::ExactCoverProblem->dense(\@input_rows, $secondary_columns);

my $dlx = Algorithm::X::DLX->new($problem);

my $result = $dlx->search();

for my $row_indices (@{$result->{solutions}}) {
  if ($opt_print_solutions) {
    if ($opt_verbose) {
      for my $i (@$row_indices) {
        print_range(\@{$input_rows[$i]});

examples/dlx.pl  view on Meta::CPAN

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
;
  exit(1);
}

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

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

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

package Algorithm::X::ExactCoverProblem;

use strict;
use warnings;

require 5.06.0;

use Carp;

# Constructor with width and secondary_columns
sub new {
  my ($class, $width, $rows_ref, $secondary_columns) = @_;
  $width             = 0 unless defined $width;
  $secondary_columns = 0 unless defined $secondary_columns;

  my $self = bless {
    rows_               => [],
    width_              => $width,
    secondary_columns_  => $secondary_columns,
  }, $class;
  
  if ($secondary_columns > $width) {
    croak("secondary_columns > width");
  }
  
  if (defined $rows_ref) {
    foreach my $row (@$rows_ref) {
      $self->add_row($row);
    }
  }
  
  return $self;
}

# Factory method for a dense ExactCoverProblem (binary matrix)
sub dense {
  my ($class, $bit_rows_ref, $secondary_columns) = @_;
  
  if (!@$bit_rows_ref) {
    return $class->new(0, undef, $secondary_columns);
  }

  my $width = scalar @{$bit_rows_ref->[0]};
  my $problem = $class->new($width, undef, $secondary_columns);

  foreach my $bits (@$bit_rows_ref) {
    if (scalar @$bits != $width) {
      croak("rows have different lengths");
    }
    
    my @row;
    for (my $i = 0; $i < @$bits; ++$i) {
      if ($bits->[$i] != 0 && $bits->[$i] != 1) {
        croak("dense matrix must contain only 0s and 1s");

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

sub width {
  my ($self) = @_;
  return $self->{width_};
}

sub rows {
  my ($self) = @_;
  return $self->{rows_};
}

sub secondary_columns {
  my ($self) = @_;
  return $self->{secondary_columns_};
}

sub add_row {
  my ($self, $row_ref) = @_;
  
  my @row = sort { $a <=> $b } @$row_ref;
  foreach my $x (@row) {
    if ($x >= $self->{width_}) {
      croak("column out of range");
    }

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

  push @{$self->{rows_}}, \@row;
}

# Override stringification
use overload
    '""' => \&stringify;

sub stringify {
  my ($self) = @_;
  my $output = $self->width() . ' ' . $self->secondary_columns() . "\n";
  foreach my $row (@{$self->rows()}) {
    $output .= join(' ', @$row) . "\n";
  }
  return $output;
}

1;

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

Algorithm::X::Examples - Application of Algorithm-X to various exact cover problems

=head1 DESCRIPTION

The modules under Algorithm::X come without a detailed documentation towards their usage, 
specifically on how to turn a problem into a matrix.
Pls. refer to the sources under the distro's L<examples/|https://metacpan.org/dist/Algorithm-X-DLX/source/examples/> directory and their usages given below.

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.

=head1 Running examples/...

These modules are not installed. 
Extract the C<examples> directory from the distribution and put the resp. script's directory into C<@INC> where necessary.

=head2 Testing examples

All example modules come with their resp. tests, which are not run at installation time. 
You would have to call them manually.

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

  0 1 0 0 0 0 1
  
  solutions: 1

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

  examples$ ./dlx.pl -ps < data/knuth_example_sparse.txt
  3 0 4
  solutions: 1

To 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: 1

=head2 Example: Sudoku

This program can solve and generate various types of Sudokus.
If something is worth doing, it's worth doing well.

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

=item * Cell (I<x>, I<y>) needs to contain a digit.

=item * Column I<x> needs to contain digit I<d>.

=item * Row I<y> needs to contain digit I<d>.

=item * Region I<i> needs to contain digit I<d>.

=back

The first one can actually be either a secondary or a primary column; if all other conditions are met, every cell will naturally contain I<at most one> digit.

Each row of the matrix hits exactly one column of each type.

For the standard 9x9 Sudoku, all regions are 3x3 squares. But it is straight-forward to generalize this so that the regions can form an arbitrary partition of the grid to subsets of size n. This also makes it possible to create Sudokus of any size; w...

=head3 Usage

The executable tries to infer as much as possible from the input data, requiring no flags or meta data about the Sudoku types. It expects to find Sudokus separated by empty lines. Empty cells can be either dots (C<'.'>) or zeros (C<'0'>). All non-zer...

The given Sudokus will be solved, unless they are invalid or unsolvable; in that case, an error message is printed. A completely empty Sudoku will be replaced with a randomly generated (and usually quite difficult) one, which is also solved.

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

    nodes   => [],
  };
  bless $self, $class;

  my $root = $self->create_node(~0, ~0);
  croak "Root ID mismatch" unless $root == $self->root_id();

  for my $x (0 .. $problem->width() - 1) {
    my $id = $self->create_node($x, ~0);
    $self->{col_ids}[$x] = $id;
    if ($x >= $problem->secondary_columns()) {
      $self->{nodes}[$id]{r} = $root;
      $self->{nodes}[$id]{l} = $self->L($root);
      $self->{nodes}[$self->L($root)]->{r} = $id;
      $self->{nodes}[$root]->{l} = $id;
    }
  }

  for my $y (0 .. $#{$problem->rows()}) {
    $self->add_row($y, $problem->rows()->[$y]);
  }