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

Question

В последние пару дней я воздерживался от обучения в магистратуре и сосредоточился на этой (казалось бы простой) головоломке:

---

Эта сетка 10 * 10 представляет собой квадрат из 100 доступных мест. Цель состоит в том, чтобы начать с угла и пройти через все места относительно некоторых простых «правил обхода» и достичь номера 100 (или 99, если вы программист, и начинать с 0 вместо :)

Правила прохождения:
1. Два пробела прыгают вдоль вертикальной и горизонтальной оси
2. Один космический прыжок по диагонали
3. Вы можете посетить каждый квадрат только один раз

Чтобы лучше визуализировать, вот правильный пример хода (до восьмого шага):
Пример Траверса http://img525.imageshack.us/img525/280/squarepuzzle.png

---

Вручную, я работал над этой загадкой от скуки. В течение многих лет я время от времени пытался решить ее вручную, но я никогда не выходил за рамки 96. Звучит легко? Попробуйте сами и убедитесь сами:)

Таким образом, для решения этой проблемы я разработал короткую (около 100 строк кода) программу на Python. Я новичок в этом языке, я хотел посмотреть, что я могу сделать.
Программа просто применяет исчерпывающую технику решения проблем и ошибок. Другими словами: первый перебор глубины грубой силы.

С этого момента у меня возникает вопрос: программа, к сожалению, не может решить проблему, потому что пространство состояний настолько велико, что поиск никогда не заканчивается, когда ты не находишь решение. Он может подняться до номера 98 (и печатает его) без особых трудностей, тем не менее, не является полным решением. Программа также распечатывает длину дерева поиска, которое оно покрыло до сих пор. Через пару минут список обхода, скажем, от 65-го элемента покрывается до конца, всего за один единственный путь. Это число уменьшается в экспоненциально увеличивающиеся периоды времени. Я довольно долго запускал код и не смог преодолеть 50 барьеров, и теперь я убежден.

Кажется, этого простого подхода будет недостаточно, если я не запусту его навсегда. Итак, как я могу улучшить свой код, чтобы он был быстрее и эффективнее, чтобы он предлагал решения?

В принципе, я с нетерпением жду, чтобы увидеть идеи о том, как:

1. Захват и использование знаний в области , специфичных для этой проблемы

2. Применение методов / приемов программирования для преодоления истощения

   .. и, наконец, реализовать существенное решение.

Заранее спасибо.

---

Редакция
Спасибо Дейву Уэббу за то, что он связал проблему с доменом, которому он принадлежит:

Это очень похоже на рыцарское Тур проблема, которая связана с перемещением рыцарь вокруг шахматной доски без пересмотреть ту же площадь. В принципе это та же проблема, но с разные "Правила Траверса".

---

Answer 1

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

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

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

Answer 2

Я решил посмотреть на проблему и посмотреть, смогу ли я разбить ее на решения 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]

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

Answer 3

В конце концов, я решил изменить код Python, чтобы преодолеть эту проблему. Я настроил код на пару часов, и он уже нашел полмиллиона решений за пару часов.
Полный набор решений все еще требует полного исчерпывающего поиска, то есть, чтобы программа работала, пока не завершится со всеми комбинациями. Однако достижение «легитимного» решения может быть сведено к «линейному времени».

Первое, чему я научился:

1. Благодаря Дейву Уэббу и ammoQ . Проблема действительно является расширением задачи о гамильтоновом пути, поскольку она является NP-Hard. Для начала не существует «простого» решения. Существует известная загадка Knight's Tour , которая представляет собой просто ту же проблему с другим размером доски / сетки и различными правилами перемещения. Для решения проблемы сказано и сделано много вещей, и были разработаны методологии и алгоритмы.

2. Благодаря ответ Джо . Проблема может быть рассмотрена снизу вверх и может быть разбита на решаемые подзадачи. Решенные подзадачи могут быть связаны в понятии точки входа-выхода (одна точка выхода может быть связана с точкой входа друг друга), так что основная проблема может быть решена как совокупность задач меньшего масштаба. Этот подход здравый и практичный, но не полный. Он не может гарантировать, что найдет ответ, если он существует.

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

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

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

---

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

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

Алгоритм:

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

---

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

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

# 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...')

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

Answer 4

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

Answer 5

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

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

Answer 6

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

Answer 7

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