Загадка: Квадратният пъзел

Това е много подобно на проблема с Knight's Tour, който се отнася до преместването на кон около шахматната дъска без преразглеждане на същия площад. По принцип това е същият проблем, но с различни „Правила за преход“.

Ключовата оптимизация, която си спомням от справянето с Knights Tour рекурсивно, е да предприемете следващите си ходове в нарастващ ред според броя на наличните ходове на целевото поле. Това насърчава търсенето да се опитва да се движи плътно в една област и да я запълва, вместо да мащабира цялата дъска и да оставя малки островни квадратчета, които никога не могат да бъдат посетени. (Това е алгоритъмът на Warnsdorff.)

Също така се уверете, че сте взели предвид симетрията, където можете. Например, на най-простото ниво x и y на вашето начално поле трябва да достигнат само 5, тъй като (10,10) е същото като (1,1) със завъртяна дъска.

Реших да разгледам проблема и да видя дали мога да го разделя на 5x5 решения с края на решение на един скок от ъгъла на друго.

Първото предположение беше, че 5x5 е разрешимо. Това е и бързо.

Така че стартирах solve(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.

Четвърти квадрат може да бъде всяко валидно решение, защото крайната точка няма значение. Въпреки това картографирането на решението от 5x5 до 10x10 е по-трудно, тъй като квадратът започва от противоположния ъгъл. Вместо да превежда, изпълни solve(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]

Може ли някой да провери повторно методологията? Мисля, че това е валидно решение и метод за разбиване на проблема.

В крайна сметка измислих модифициран код на Python, за да преодолея проблема. Настроих кода за няколко часа и той вече намери половин милион решения за няколко часа.
Пълният набор от решения все още изисква пълно изчерпателно търсене, т.е. да оставите програмата да работи, докато приключи с всички комбинации. Въпреки това, достигането до "едно" легитимно решение може да бъде сведено до "линейно време".

Първо, неща, които научих:

1. Благодарение на отговора на Дейв Уеб и отговорът на ammoQ. Проблемът наистина е разширение на проблема с Хамилтоновия път, тъй като е NP-Hard. Няма "лесно" решение като начало. Има известна гатанка на Knight's Tour, която е просто същият проблем с различен размер на дъска/решетка и различни траверсни правила. Има много неща, казани и направени, за да се разработи проблемът и са създадени методологии и алгоритми.

2. Благодарение на отговора на Джо. Към проблема може да се подходи в смисъл отдолу нагоре и може да бъде разделен на разрешими подпроблеми. Решените подпроблеми могат да бъдат свързани в представа за входно-изходна точка (нечия изходна точка може да бъде свързана с входна точка на друг), така че основният проблем да може да бъде решен като конституция на проблеми с по-малък мащаб. Този подход е разумен и практичен, но не е завършен. Не може да гарантира намирането на отговор, ако такъв съществува.

След изчерпателно грубо търсене, ето ключови моменти, които разработих в кода:

• Алгоритъмът на Warnsdorff: Този алгоритъм е ключовата точка за достигане до удобен брой решения по бърз начин. Той просто заявява, че трябва да изберете следващото си движение към „най-малко достъпното“ място и да попълните списъка си „за отиване“ във възходящ ред или достъпност. Най-малко достъпно място означава мястото с най-малък брой възможни следващи ходове.

  По-долу е псевдокодът (от Wikipedia):

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

• Позиция Q е достъпна от позиция P, ако P може да се придвижи до Q с един ход на коня и Q все още не е посетено.
• Достъпността на позиция P е броят позиции, достъпни от P.

Алгоритъм:

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

• Проверка за острови: Приятно използване на знания за домейн тук се оказа полезно. Ако едно преместване (освен ако не е последното) би накарало който и да е от неговите съседи да се превърне в остров, т.е. недостъпен за никой друг, тогава този клон вече не се изследва. Спестява значително време (много грубо 25%) в комбинация с алгоритъма на Warnsdorff.

И ето моят код в 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...')

Благодаря на всички, които споделят своите знания и идеи.

Това е само пример за http://en.wikipedia.org/wiki/Hamiltonian_path проблем. Немската wikipedia твърди, че е 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 MB.

Можете да преброите точно броя на решенията с алгоритъм за динамично програмиране на линия.