python - programmers - lua programming challenges

Riddle: The Square Puzzle

Question

El último par de días, me he abstenido de los estudios de maestría y me he centrado en este (aparentemente simple) rompecabezas:

Existe esta cuadrícula de 10 * 10 que constituye un cuadrado de 100 lugares disponibles para ir. El objetivo es comenzar desde una esquina y atravesar todos los lugares con respecto a algunas "reglas de recorrido" simples y alcanzar el número 100 (o 99 si eres programador y comenzar con 0)

Las reglas para atravesar son:
1. Dos espacios saltan a lo largo del eje vertical y horizontal.
2. Un salto espacial a lo largo de las diagonales.
3. Puedes visitar cada plaza solo una vez

Para visualizar mejor, aquí hay un ejemplo de recorrido válido (hasta el 8º paso):
Ejemplo de travesía http://img525.imageshack.us/img525/280/squarepuzzle.png

Manualmente, he estado trabajando en este rompecabezas por aburrimiento. Durante años, he intentado resolverlo a mano de vez en cuando, pero nunca he ido más allá del 96. ¿Suena fácil? Pruébate y ve por ti mismo :)

Por lo tanto, para resolver el problema, he desarrollado un programa corto (alrededor de 100 líneas de código) en Python. Soy un principiante en este idioma. Quería ver qué puedo hacer.
El programa simplemente aplica una técnica exhaustiva de resolución de intentos y errores. En otras palabras: la fuerza bruta primero la búsqueda.

Mi pregunta surge de aquí en adelante: el programa, desafortunadamente, no puede resolver el problema porque el espacio del estado es tan grande que la búsqueda nunca termina con la búsqueda de una solución. Puede llegar al número 98 (e imprimir eso) sin mucha dificultad, pero no es una solución completa.
El programa también imprime la longitud del árbol de búsqueda que ha cubierto hasta ahora. En un par de minutos, la lista transversal de, por ejemplo, el elemento 65 se cubre hasta el final, para un solo camino. Este número disminuye en períodos de tiempo exponencialmente crecientes. He ejecutado el código durante bastante tiempo y no pude superar la barrera de los 50 y ahora estoy convencido.

Parece que este enfoque simple no será suficiente a menos que lo ejecute para siempre. Entonces, ¿cómo puedo mejorar mi código para que sea más rápido y más eficiente y así pueda encontrar soluciones?

Básicamente, estoy deseando ver ideas sobre cómo:

1. Capturar y explotar el conocimiento del dominio específico de este problema.

2. Aplicar técnicas de programación / trucos para superar el agotamiento.

   ..y finalmente darse cuenta de una solución sustancial.

Gracias por adelantado.

Revisión
Gracias a Dave Webb por relacionar el problema con el dominio al que pertenece:

Esto es muy similar al problema de Knight''s Tour que se relaciona con el movimiento de un caballero alrededor de un tablero de ajedrez sin volver a visitar el mismo cuadro. Básicamente es el mismo problema pero con diferentes "Reglas de Traverse".

Answer 1

Decidí ver el problema y ver si podía dividirlo en soluciones 5x5 con el final de una solución a un salto de la esquina de otro.

El primer supuesto fue que 5x5 es solucionable. Es y rápido.

Así que corrí resolver (0,5) y miré los resultados. Dibujé una cuadrícula numerada 10x10 en Excel con una cuadrícula numerada 5x5 para la traducción. Luego, solo busqué en los resultados para #] (celdas de terminación) que serían un salto desde el inicio del próximo 5x5. (ej. para la primera casilla, busqué "13]".)

Para referencia:

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

Aquí hay una posible solución:

Primer cuadrado: [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] lo coloca en un salto diagonal hasta 5 (en 10x10) la primera esquina de la siguiente 5 x 5.

Segundo cuadrado: [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] lo coloca con el último cuadrado de 25 en el 10x10, que está a dos saltos de distancia de 55.

Tercer cuadrado: [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] lo coloca con el último cuadrado de 97 en el 10x10, que está a dos saltos de 94.

Cuarto cuadrado puede ser cualquier solución válida, porque el punto final no importa. Sin embargo, el mapeo de la solución de 5x5 a 10x10 es más difícil, ya que el cuadrado comienza en la esquina opuesta. En lugar de traducir, corrí resolver (24,5) y escogí uno al azar: [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]

Esto debería ser posible para todos programáticamente, ahora que se sabe que las soluciones 5x5 son válidas con los puntos finales que se mueven legalmente a la siguiente esquina 5x5. El número de soluciones 5x5 fue de 552, lo que significa que almacenar las soluciones para un mayor cálculo y reasignación es bastante fácil.

A menos que haya hecho esto mal, esto le brinda una posible solución (definida anteriormente como soluciones de 5x5 como una a cuatro respectivamente):

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]

¿Puede alguien verificar la metodología? Creo que esta es una solución válida y un método para solucionar el problema.

Answer 2

Este es solo un ejemplo del problema http://en.wikipedia.org/wiki/Hamiltonian_path . La wikipedia alemana dice que es NP-duro.

Answer 3

Esto es muy similar al problema de Knight''s Tour , que se relaciona con el movimiento de un caballero alrededor de un tablero de ajedrez sin volver a visitar la misma casilla. Básicamente es el mismo problema pero con diferentes "Reglas de Traverse".

La optimización clave que recuerdo de abordar el Tour de los Caballeros recursivamente es tomar tus siguientes movimientos en orden creciente de la cantidad de movimientos disponibles en la casilla de destino. Esto fomenta la búsqueda para tratar de moverse densamente en un área y rellenarla en lugar de hacer zoom en todo el tablero y dejar pequeñas casillas de islas que nunca se pueden visitar. (Este es el algoritmo de Warnsdorff .)

También asegúrate de haber considerado la simetría donde puedas. Por ejemplo, en el nivel más simple, la xey de su cuadro de inicio solo necesita subir hasta 5 ya que (10,10) es lo mismo que (1,1) con la tabla girada.

Answer 4

Finalmente, he encontrado el código Python modificado para superar el problema. He sintonizado el código durante un par de horas y ya ha encontrado medio millón de soluciones en un par de horas.
El conjunto completo de soluciones aún requiere una búsqueda exhaustiva, es decir, dejar que el programa se ejecute hasta que finalice con todas las combinaciones. Sin embargo, alcanzar "una" solución legítima se puede reducir a "tiempo lineal".

Primero, cosas que he aprendido:

1. Gracias a la respuesta de Dave Webb y la respuesta de ammoQ . El problema es de hecho una extensión del problema de la ruta hamiltoniana, ya que es NP-Hard. No hay una solución "fácil" para empezar. Hay un famoso enigma de Knight''s Tour que es simplemente el mismo problema con un tamaño diferente de tabla / cuadrícula y diferentes reglas de desplazamiento. Se han dicho y hecho muchas cosas para elaborar el problema y se han ideado metodologías y algoritmos.

2. Gracias a la respuesta de Joe . El problema se puede abordar de manera ascendente y se puede reducir a problemas secundarios solucionables. Los subproblemas resueltos pueden conectarse en una noción de punto de entrada-salida (el punto de salida de uno puede conectarse a otro punto de entrada) para que el problema principal pueda resolverse como una constitución de problemas de menor escala. Sin embargo, este enfoque es sólido y práctico, pero no está completo. No se puede garantizar encontrar una respuesta si existe.

Tras una búsqueda exhaustiva de fuerza bruta, aquí están los puntos clave que he desarrollado en el código:

• El algoritmo de Warnsdorff : este algoritmo es el punto clave para alcanzar un número práctico de soluciones de una manera rápida. Simplemente establece que, debe elegir su próximo movimiento al lugar "menos accesible" y completar su lista de "para ir" con orden ascendente o accesibilidad. Lugar menos accesible significa el lugar con el menor número de movimientos posibles.

  A continuación se muestra el pseudocódigo (de Wikipedia):

Algunas definiciones:

• Se puede acceder a una posición Q desde una posición P si P puede moverse a Q con un solo movimiento de caballero, y Q aún no se ha visitado.
• La accesibilidad de una posición P es el número de posiciones accesibles desde P.

Algoritmo:

establezca P para que sea una posición inicial aleatoria en el tablero marque el tablero en P con el número de movimiento "1" para cada número de movimiento de 2 al número de cuadrados en el tablero, sea S el conjunto de posiciones accesibles desde la posición de entrada establezca P para que sea la posición en S con acceso mínimo marque el tablero en P con el número de movimiento actual devuelva el tablero marcado - cada casilla se marcará con el número de movimiento en el que se visita.

• Comprobación de islas : un buen aprovechamiento del conocimiento de dominio aquí resultó ser útil. Si un movimiento (a menos que sea el último) causaría que cualquiera de sus vecinos se convierta en una isla, es decir, no sea accesible por ningún otro, esa rama ya no se investiga. Ahorra una cantidad considerable de tiempo (muy aproximadamente el 25%) combinado con el algoritmo de Warnsdorff.

Y aquí está mi código en Python, que resuelve el enigma (en un grado aceptable considerando que el problema es NP-Hard). El código es fácil de entender ya que me considero a nivel de principiante en Python. Los comentarios son sencillos para explicar la implementación. Las soluciones se pueden mostrar en una cuadrícula simple mediante una GUI básica (directrices en el código).

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

Gracias a todos los que compartieron sus conocimientos e ideas.

Answer 5

Podría contar la cantidad de soluciones exactamente con un algoritmo de programación dinámica de línea de barrido.

Answer 6

Quería ver si podía escribir un programa que ofreciera todas las soluciones posibles.

#! /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;
}

Este programa produjo más de 100,000 soluciones posibles antes de que se terminara. Envié STDOUT a un archivo, y tenía más de 200 MB.

Answer 7

Se puede realizar una optimización para buscar islas (es decir, espacios no visitados sin vecinos válidos) y volver a salir de la travesía hasta que se elimine la isla. Esto ocurriría cerca del lado "barato" de un determinado árbol transversal. Supongo que la pregunta es si la reducción vale la pena el gasto.