Загадка: квадратная загадка

Это очень похоже на задачу Knight's Tour , которая касается перемещения рыцаря вокруг шахматной доски. без пересмотра той же площади. По сути, это та же проблема, но с другими «Правилами обхода».

Оптимизация ключа, которую я помню после рекурсивного подхода к Рыцарскому туру, - это делать следующие ходы в порядке увеличения числа доступных ходов на поле назначения. Это побуждает поиск пытаться перемещаться плотно в одной области и заполнять ее, а не масштабировать всю доску и оставлять маленькие островные квадраты, которые никогда не будут посещаться. (Это алгоритм Варнсдорфа .)

Также убедитесь, что вы рассмотрели симметрию там, где можете. Например,

Я решил посмотреть на проблему и посмотреть, Я мог бы разбить его на решения 5х5 с окончанием решения одним прыжком от угла другого.

Первое предположение состояло в том, что 5x5 разрешимо. Это и быстро.

Так что я побежал решать (0,5) и посмотрел на результаты. Я нарисовал 10x10 пронумерованную сетку в Excel с 5x5 пронумерованной сеткой для перевода. Затем я просто искал результаты для #] (конечных ячеек), которые были бы отскоком от начала следующих 5x5. (Напр. для первого квадрата я искал «13]».)

Для справки:

10 x 10 grid                       5 x 5 grid 
 0  1  2  3  4 |  5  6  7  8  9     0  1  2  3  4
10 11 12 13 14 | 15 16 17 18 19     5  6  7  8  9
20 21 22 23 24 | 25 26 27 28 29    10 11 12 13 14
30 31 32 33 34 | 35 36 37 38 39    15 16 17 18 19
40 41 42 43 44 | 45 46 47 48 49    20 21 22 23 24
---------------+---------------
50 51 52 53 54 | 55 56 57 58 59
60 61 62 63 64 | 65 66 67 68 69
70 71 72 73 74 | 75 76 77 78 79
80 81 82 83 84 | 85 86 87 88 89
90 91 92 93 94 | 95 96 97 98 99

Вот возможное решение:

Первый квадрат: [0, 15, 7, 19, 16, 1, 4, 12, 20, 23, 8, 5, 17, 2, 10, 22, 14, 11, 3, 18, 6, 9, 24, 21, 13] ставит диагональный скачок до 5 (в 10x10) первого угол следующих 5 х 5.

Вторая площадь: [0, 12, 24, 21, 6, 9, 17, 2, 14, 22, 7, 15, 18, 3, 11, 23, 20, 5 , 8, 16, 19, 4, 1, 13, 10] помещает его с последним квадратом 25 в 10x10, что в двух прыжках от 55.

Третий квадрат: [0, 12, 24, 21, 6 , 9, 17, 5, 20, 23, 8, 16, 19, 4, 1, 13, 10, 2, 14, 11, 3, 18, 15, 7, 22] ставит его с последним квадратом 97 в 10x10, что в двух шагах от 94.

Четвертый квадрат может быть любым правильным решением, потому что конечная точка не имеет значения. Однако картирование решения от 5х5 до 10х10 сложнее, как квадрат начинается в противоположном углу. Вместо перевода побежал решить (24,5) и выбрал один случайным образом: [24, 9, 6, 21, 13, 10, 2, 17, 5, 20, 23, 8, 16, 1, 4, 12, 0, 15, 18, 3, 11, 14, 22, 7, 19]

Это должно быть возможно для всех программно, теперь, когда известно, что решения 5x5 действительны с законными перемещениями конечных точек в следующий угол 5x5. Число решений 5x5 было 552, что означает, что хранить решения для дальнейшего расчета и переназначения довольно легко.

Если я не сделал этого неправильно, это даст вам одно возможное решение (определенное выше 5x5 решений как от одного до четырех соответственно): [1244 Может ли кто-нибудь еще раз проверить методологию? Я думаю, что это правильное решение и метод решения проблемы.

23, 8, 16, 1, 4, 12, 0, 15, 18, 3, 11, 14, 22, 7, 19]

Это должно быть возможно для всех программно, теперь, когда известно, что решения 5x5 действителен с конечными точками, законно перемещается в следующий угол 5x5. Число решений 5x5 было 552, что означает, что хранить решения для дальнейшего расчета и переназначения довольно легко.

Если я не сделал этого неправильно, это даст вам одно возможное решение (определенное выше 5x5 решений как от одного до четырех соответственно): [1244 Может ли кто-нибудь еще раз проверить методологию? Я думаю, что это правильное решение и метод решения проблемы.

23, 8, 16, 1, 4, 12, 0, 15, 18, 3, 11, 14, 22, 7, 19]

Это должно быть возможно для всех программно, теперь, когда известно, что решения 5x5 действителен с конечными точками, законно перемещается в следующий угол 5x5. Число решений 5x5 было 552, что означает, что хранить решения для дальнейшего расчета и переназначения довольно легко.

Если я не сделал этого неправильно, это даст вам одно возможное решение (определенное выше 5x5 решений как от одного до четырех соответственно): [1244 Может ли кто-нибудь еще раз проверить методологию? Я думаю, что это правильное решение и метод решения проблемы.

Это означает, что хранить решения для дальнейшего вычисления и переназначения довольно легко.

Если я не сделал этого неправильно, это даст вам одно возможное решение (определенное выше 5x5 решений как от одного до четырех соответственно):

def trans5(i, col5, row5):
    if i < 5: return 5 * col5 + 50 * row5 + i
    if i < 10: return 5 + 5 * col5 + 50 * row5 + i
    if i < 15: return 10 + 5 * col5 + 50 * row5 + i
    if i < 20: return 15 + 5 * col5 + 50 * row5 + i
    if i < 25: return 20 + 5 * col5 + 50 * row5 + i

>>> [trans5(i, 0, 0) for i in one] + [trans5(i, 1, 0) for i in two] + [trans5(i, 0, 1) for i in three] + [trans5(i, 1, 1) for i in four]
    [0, 30, 12, 34, 31, 1, 4, 22, 40, 43, 13, 10, 32, 2, 20, 42, 24, 21, 3, 33, 11, 14, 44, 41, 23, 5, 27, 49, 46, 16, 19, 37, 7, 29, 47, 17, 35, 38, 8, 26, 48, 45, 15, 18, 36, 39, 9, 6, 28, 25, 50, 72, 94, 91, 61, 64, 82, 60, 90, 93, 63, 81, 84, 54, 51, 73, 70, 52, 74, 71, 53, 83, 80, 62, 92, 99, 69, 66, 96, 78, 75, 57, 87, 65, 95, 98, 68, 86, 56, 59, 77, 55, 85, 88, 58, 76, 79, 97, 67, 89]

Может ли кто-то один дважды проверить методология? Я думаю, что это правильное решение и метод решения проблемы.

Это означает, что хранить решения для дальнейшего вычисления и переназначения довольно легко.

Если я не сделал этого неправильно, это даст вам одно возможное решение (определенное выше 5x5 решений как от одного до четырех соответственно):

def trans5(i, col5, row5):
    if i < 5: return 5 * col5 + 50 * row5 + i
    if i < 10: return 5 + 5 * col5 + 50 * row5 + i
    if i < 15: return 10 + 5 * col5 + 50 * row5 + i
    if i < 20: return 15 + 5 * col5 + 50 * row5 + i
    if i < 25: return 20 + 5 * col5 + 50 * row5 + i

>>> [trans5(i, 0, 0) for i in one] + [trans5(i, 1, 0) for i in two] + [trans5(i, 0, 1) for i in three] + [trans5(i, 1, 1) for i in four]
    [0, 30, 12, 34, 31, 1, 4, 22, 40, 43, 13, 10, 32, 2, 20, 42, 24, 21, 3, 33, 11, 14, 44, 41, 23, 5, 27, 49, 46, 16, 19, 37, 7, 29, 47, 17, 35, 38, 8, 26, 48, 45, 15, 18, 36, 39, 9, 6, 28, 25, 50, 72, 94, 91, 61, 64, 82, 60, 90, 93, 63, 81, 84, 54, 51, 73, 70, 52, 74, 71, 53, 83, 80, 62, 92, 99, 69, 66, 96, 78, 75, 57, 87, 65, 95, 98, 68, 86, 56, 59, 77, 55, 85, 88, 58, 76, 79, 97, 67, 89]

Может ли кто-то один дважды проверить методология? Я думаю, что это правильное решение и метод решения проблемы.

Это всего лишь пример http://en.wikipedia.org/wiki/Hamiltonian_path проблема. Немецкая википедия утверждает, что это NP-хард.

Можно выполнить оптимизацию для проверки островов (т. Е. Не посещенных мест без действительных соседей) и возврата Траверса, пока остров не будет устранен. Это произойдет около «дешевой» стороны определенного дерева. Я думаю, вопрос в том, стоит ли сокращение затрат.

Я хотел посмотреть, смогу ли я написать программу, которая предложит все возможные решения.

#! /usr/bin/env perl
use Modern::Perl;

{
  package Grid;
  use Scalar::Util qw'reftype';

  sub new{
    my($class,$width,$height) = @_;
    $width  ||= 10;
    $height ||= $width;

    my $self = bless [], $class;

    for( my $x = 0; $x < $width; $x++ ){
      for( my $y = 0; $y < $height; $y++ ){
        $self->[$x][$y] = undef;
      }
    }

    for( my $x = 0; $x < $width; $x++ ){
      for( my $y = 0; $y < $height; $y++ ){
        $self->[$x][$y] = Grid::Elem->new($self,$x,$y);;
      }
    }

    return $self;
  }

  sub elem{
    my($self,$x,$y) = @_;
    no warnings 'uninitialized';
    if( @_ == 2 and reftype($x) eq 'ARRAY' ){
      ($x,$y) = (@$x);
    }
    die "Attempted to use undefined var" unless defined $x and defined $y;
    my $return = $self->[$x][$y];
    die unless $return;
    return $return;
  }

  sub done{
    my($self) = @_;
    for my $col (@$self){
      for my $item (@$col){
        return 0 unless $item->visit(undef);
      }
    }
    return 1;
  }

  sub reset{
    my($self) = @_;
    for my $col (@$self){
      for my $item (@$col){
        $item->reset;
      }
    }
  }

  sub width{
    my($self) = @_;
    return scalar @$self;
  }

  sub height{
    my($self) = @_;
    return scalar @{$self->[0]};
  }
}{
  package Grid::Elem;
  use Scalar::Util 'weaken';

  use overload qw(
    "" stringify
    eq equal
    == equal
  );

  my %dir = (
    #       x, y
    n  => [ 0, 2],
    s  => [ 0,-2],
    e  => [ 2, 0],
    w  => [-2, 0],

    ne => [ 1, 1],
    nw => [-1, 1],

    se => [ 1,-1],
    sw => [-1,-1],
  );

  sub new{
    my($class,$parent,$x,$y) = @_;
    weaken $parent;
    my $self = bless {
      parent => $parent,
      pos    => [$x,$y]
    }, $class;

    $self->_init_possible;

    return $self;
  }

  sub _init_possible{
    my($self) = @_;
    my $parent = $self->parent;
    my $width  = $parent->width;
    my $height = $parent->height;
    my($x,$y)  = $self->pos;

    my @return;
    for my $dir ( keys %dir ){
      my($xd,$yd) = @{$dir{$dir}};
      my $x = $x + $xd;
      my $y = $y + $yd;

      next if $y < 0 or $height <= $y;
      next if $x < 0 or $width  <= $x;

      push @return, $dir;
      $self->{$dir} = [$x,$y];
    }
    return  @return if wantarray;
    return \@return;
  }

  sub list_possible{
    my($self) = @_;
    return unless defined wantarray;

    # only return keys which are
    my @return = grep {
      $dir{$_} and defined $self->{$_}
    } keys %$self;

    return  @return if wantarray;
    return \@return;
  }

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

  sub pos{
    my($self) = @_;
    my @pos = @{$self->{pos}};
    return @pos if wantarray;
    return \@pos;
  }

  sub visit{
    my($self,$v) = @_;
    my $return = $self->{visit} || 0;

    $v = 1 if @_ == 1;
    $self->{visit} = $v?1:0 if defined $v;

    return $return;
  }

  sub all_neighbors{
    my($self) = @_;
    return $self->neighbor( $self->list_possible );
  }
  sub neighbor{
    my($self,@n) = @_;
    return unless defined wantarray;
    return unless @n;

    @n = map { exists $dir{$_} ? $_ : undef } @n;

    my $parent = $self->parent;

    my @return = map {
      $parent->elem($self->{$_}) if defined $_
    } @n;

    if( @n == 1){
      my($return) = @return;
      #die unless defined $return;
      return $return;
    }
    return  @return if wantarray;
    return \@return;
  }

  BEGIN{
    for my $dir ( qw'n ne e se s sw w nw' ){
      no strict 'refs';
      *$dir = sub{
        my($self) = @_;
        my($return) = $self->neighbor($dir);
        die unless $return;
        return $return;
      }
    }
  }

  sub stringify{
    my($self) = @_;
    my($x,$y) = $self->pos;
    return "($x,$y)";
  }

  sub equal{
    my($l,$r) = @_;
    "$l" eq "$r";
  }

  sub reset{
    my($self) = @_;
    delete $self->{visit};
    return $self;
  }
}

# Main code block
{
  my $grid = Grid->new();

  my $start = $grid->elem(0,0);
  my $dest  = $grid->elem(-1,-1);

  my @all = solve($start,$dest);
  #say @$_ for @all;
  say STDERR scalar @all;
}

sub solve{
  my($current,$dest,$return,@stack) = @_;
  $return = [] unless $return;
  my %visit;
  $visit{$_} = 1 for @stack;

  die if $visit{$current};

  push @stack, $current->stringify;

  if( $dest == $current ){
    say @stack;

    push @$return, [@stack];
  }

  my @possible = $current->all_neighbors;
  @possible = grep{
    ! $visit{$_}
  } @possible;

  for my $next ( @possible ){
    solve($next,$dest,$return,@stack);
  }

  return @$return if wantarray;
  return  $return;
}

Эта программа предложила более 100 000 возможных решений, прежде чем она была прекращена. Я отправил STDOUT в файл, и это было более 200 МБ.

Вы можете точно подсчитать количество решений с помощью алгоритма динамического программирования линии развертки.