Загадка: квадратная головоломка

Ответ 1

В конце концов, я воспользовался модифицированным кодом Python для решения проблемы. Я заработал код на пару часов, и через пару часов он уже нашел полмиллиона решений.
Для полного набора решений по-прежнему требуется полный исчерпывающий поиск, т.е. Запуск программы до тех пор, пока она не закончится со всеми комбинациями. Однако достижение "законного" решения может быть сведено к "линейному времени".

Во-первых, все, что я узнал:

• Спасибо Dave Webb answer и отзыв ammoQ. Проблема действительно является расширением проблемы Гамильтонова пути, поскольку она NP-Hard. С самого начала не существует "простого" решения. Существует известная загадка Knight Tour, которая представляет собой ту же проблему с другим размером платы/сетки и различными правилами траверса. Есть много вещей, которые было сказано и сделано для разработки проблемы, и были разработаны методологии и алгоритмы.

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

После исчерпывающего поиска грубой силы, вот ключевые моменты, которые я разработал для кода:

• Алгоритм Warnsdorff: Это алгоритм является ключевым моментом для достижения к удобному числу решений в быстрый способ. В нем просто говорится, что вы должен выбрать ваш следующий шаг к "наименее доступное" место и население ваш "идти" с восходящим порядок или доступность. Наименее доступное место означает место с наименьшее количество возможных движется.

  Ниже приведен псевдокод (из Википедии):

Некоторые определения:

• Позиция Q доступна из позиции P, если P может перемещаться в Q одним движением рыцаря, а Q еще не был посещен.
• Доступность позиции P - это количество позиций, доступных из P.

Алгоритм:

установите P как случайную начальную позицию на доске отметьте плату на P с номер перемещения "1" для каждого перемещения число от 2 до числа квадратов на доске, пусть S - множество позиции, доступные с входа положение P в качестве позиции в S с минимальной доступностью доска на P с текущим движением число возвращает отмеченную доску - каждый квадрат будет отмечен ходом номер, на котором он был посещен.

• Проверка на наличие островов: Хороший опыт использования знаний домена оказался полезным. Если движение (если оно не является последним) приведет к тому, что любой из его соседей станет островом, то есть недоступным каким-либо другим, то эта ветвь больше не будет исследована. Экономит значительное количество времени (примерно на 25%) в сочетании с алгоритмом Варнсдорфа.

И вот мой код в Python, который решает загадку (в приемлемой степени, учитывая, что проблема NP-Hard). Код легко понять, поскольку я считаю себя на уровне начинающих в Python. Комментарии объясняются просто, объясняя реализацию. Решения могут отображаться на простой сетке с помощью базового GUI (рекомендации в коде).

# Solve square puzzle
import operator

class Node:
# Here is how the squares are defined
    def __init__(self, ID, base):
        self.posx = ID % base
        self.posy = ID / base
        self.base = base
    def isValidNode(self, posx, posy):
        return (0<=posx<self.base and 0<=posy<self.base)

    def getNeighbors(self):
        neighbors = []
        if self.isValidNode(self.posx + 3, self.posy): neighbors.append(self.posx + 3 + self.posy*self.base)
        if self.isValidNode(self.posx + 2, self.posy + 2): neighbors.append(self.posx + 2 + (self.posy+2)*self.base)
        if self.isValidNode(self.posx, self.posy + 3): neighbors.append(self.posx + (self.posy+3)*self.base)
        if self.isValidNode(self.posx - 2, self.posy + 2): neighbors.append(self.posx - 2 + (self.posy+2)*self.base)
        if self.isValidNode(self.posx - 3, self.posy): neighbors.append(self.posx - 3 + self.posy*self.base)
        if self.isValidNode(self.posx - 2, self.posy - 2): neighbors.append(self.posx - 2 + (self.posy-2)*self.base)
        if self.isValidNode(self.posx, self.posy - 3): neighbors.append(self.posx + (self.posy-3)*self.base)
        if self.isValidNode(self.posx + 2, self.posy - 2): neighbors.append(self.posx + 2 + (self.posy-2)*self.base)
        return neighbors


# the nodes go like this:
# 0 => bottom left
# (base-1) => bottom right
# base*(base-1) => top left
# base**2 -1 => top right
def solve(start_nodeID, base):
    all_nodes = []
    #Traverse list is the list to keep track of which moves are made (the id numbers of nodes in a list)
    traverse_list = [start_nodeID]
    for i in range(0, base**2): all_nodes.append(Node(i, base))
    togo = dict()
    #Togo is a dictionary with (nodeID:[list of neighbors]) tuples
    togo[start_nodeID] = all_nodes[start_nodeID].getNeighbors()
    solution_count = 0


    while(True):
        # The search is exhausted
        if not traverse_list:
            print "Somehow, the search tree is exhausted and you have reached the divine salvation."
            print "Number of solutions:" + str(solution_count)
            break

        # Get the next node to hop
        try:
            current_node_ID = togo[traverse_list[-1]].pop(0)
        except IndexError:
            del togo[traverse_list.pop()]
            continue

        # end condition check
        traverse_list.append(current_node_ID)
        if(len(traverse_list) == base**2):
            #OMG, a solution is found
            #print traverse_list
            solution_count += 1
            #Print solution count at a steady rate
            if(solution_count%100 == 0): 
                print solution_count
                # The solution list can be returned (to visualize the solution in a simple GUI)
                #return traverse_list


        # get valid neighbors
        valid_neighbor_IDs = []
        candidate_neighbor_IDs = all_nodes[current_node_ID].getNeighbors()
        valid_neighbor_IDs = filter(lambda id: not id in traverse_list, candidate_neighbor_IDs)

        # if no valid neighbors, take a step back
        if not valid_neighbor_IDs:
            traverse_list.pop()
            continue

        # if there exists a neighbor which is accessible only through the current node (island)
        # and it is not the last one to go, the situation is not promising; so just eliminate that
        stuck_check = True
        if len(traverse_list) != base**2-1 and any(not filter(lambda id: not id in traverse_list, all_nodes[n].getNeighbors()) for n in valid_neighbor_IDs): stuck_check = False

        # if stuck
        if not stuck_check:
            traverse_list.pop()
            continue

        # sort the neighbors according to accessibility (the least accessible first)
        neighbors_ncount = []
        for neighbor in valid_neighbor_IDs:
            candidate_nn = all_nodes[neighbor].getNeighbors()
            valid_nn = [id for id in candidate_nn if not id in traverse_list]
            neighbors_ncount.append(len(valid_nn))
        n_dic = dict(zip(valid_neighbor_IDs, neighbors_ncount))
        sorted_ndic = sorted(n_dic.items(), key=operator.itemgetter(1))

        sorted_valid_neighbor_IDs = []
        for (node, ncount) in sorted_ndic: sorted_valid_neighbor_IDs.append(node)



        # if current node does have valid neighbors, add them to the front of togo list
        # in a sorted way
        togo[current_node_ID] = sorted_valid_neighbor_IDs


# To display a solution simply
def drawGUI(size, solution):
    # GUI Code (If you can call it a GUI, though)
    import Tkinter
    root = Tkinter.Tk()
    canvas = Tkinter.Canvas(root, width=size*20, height=size*20)
    #canvas.create_rectangle(0, 0, size*20, size*20)
    canvas.pack()

    for x in range(0, size*20, 20):
        canvas.create_line(x, 0, x, size*20)
        canvas.create_line(0, x, size*20, x)

    cnt = 1
    for el in solution:
        canvas.create_text((el % size)*20 + 4,(el / size)*20 + 4,text=str(cnt), anchor=Tkinter.NW)
        cnt += 1
    root.mainloop()


print('Start of run')

# it is the moment
solve(0, 10)

#Optional, to draw a returned solution
#drawGUI(10, solve(0, 10))

raw_input('End of Run...')

Спасибо всем, кто делится своими знаниями и идеями.

Ответ 2

Это очень похоже на проблему

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

Также убедитесь, что вы рассмотрели симметрию, где можете. Например, на самом простом уровне x и y вашего начального квадрата нужно увеличить до 5, поскольку (10,10) совпадает с (1,1) при вращении платы.

Ответ 3

Я решил посмотреть на проблему и посмотреть, могу ли я сломать ее в решениях 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 x 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 решений как один-четыре соответственно):

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]

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

#! /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 МБ.

Ответ 7

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