view release on metacpan or  search on metacpan

examples/npieces/NPieces.pm  view on Meta::CPAN

package NPieces;

use strict;
use warnings;

use Algorithm::X::DLX;
use Algorithm::X::ExactCoverProblem;
use Carp;

use constant { None => 0, Knight => 1, Queen => 2 };

sub new {
  my ($class, %args) = @_;

  my $self = bless {
    width_    => $args{width}   || 0,
    height_   => $args{height}  || 0,
    knights_  => $args{knights} || 0,
    queens_   => $args{queens}  || 0,
    problem_  => undef,
    row_data_ => [],
    iterator_ => undef
  }, $class;

  return $self->_initialize();
}

sub _initialize {
  my ($self) = @_;

  # Columns
  #   P*A: (x,y) attacked by piece i?
  #   P*A: placing piece i at (x,y) ok?
  #   P: piece i used?
  #
  # Total: (2A+1)P
  # Secondary: 2AP
  my $A = $self->{width_}   * $self->{height_};
  my $P = $self->{knights_} + $self->{queens_};

  $self->{problem_}  = Algorithm::X::ExactCoverProblem->new((2 * $A + 1) * $P, undef, 2 * $A * $P);

  for (my $yx = 0; $yx < $A; $yx++) {

    my $x = $yx % $self->{width_};
    my $y = int($yx / $self->{width_});

    for (my $p = 0; $p < $P; $p++) {
      my $piece = ($p < $self->{knights_}) ? Knight : Queen;
      push @{$self->{row_data_}}, { piece => $piece, x => $x, y => $y };

      my @columns;
      push @columns, map { col_attack($A, $p, $_) } @{$self->attacks($piece, $x, $y)};
      push @columns, col_piece($P, $A, $p);
      push @columns, col_put($P, $A, $p, $yx);

      for (my $p2 = 0; $p2 < $P; $p2++) {
        push @columns, col_attack($A, $p2, $yx) if ($p2 != $p);
      }

      if ($p > 0 && ($p - 1 < $self->{knights_}) == ($piece == Knight)) {
        push @columns, map { col_put($P, $A, $p - 1, $_) } ($yx + 1 .. $A - 1);
      }

      @columns = sort { $a <=> $b } @columns;
      $self->{problem_}->add_row(\@columns);
    }
  }

  $self->{iterator_} = Algorithm::X::DLX->new($self->{problem_})->get_solver();

  return $self;
}

sub size {