Rush Hour-résoudre le jeu

Voici ma réponse. Il résout le grand maître puzzle en un peu moins de 6 secondes.

Il utiliser une largeur de recherche (BFS). Le truc est de chercher une disposition de carte que vous avez déjà vue dans des recherches précédentes et d'annuler cette séquence. En raison de la BFS si vous avez vu cette mise en page avant que vous avez déjà obtenu là un chemin plus court alors laissez ce squence continuer à essayer de le résoudre plutôt que celui plus long.

#!perl

# Program by Rodos rodos at haywood dot org

use Storable qw(dclone);
use Data::Dumper;

print "Lets play Rush Hour! \n";


# Lets define our current game state as a grid where each car is a different letter.
# Our special car is a marked with the specific letter T
# The boarder is a * and the gloal point on the edge is an @.
# The grid must be the same witdh and height 
# You can use a . to mark an empty space

# Grand Master
@startingGrid = (
 ['*','*','*','*','*','*','*','*'],
 ['*','.','.','A','O','O','O','*'],
 ['*','.','.','A','.','B','.','*'],
 ['*','.','T','T','C','B','.','@'],
 ['*','D','D','E','C','.','P','*'],
 ['*','.','F','E','G','G','P','*'],
 ['*','.','F','Q','Q','Q','P','*'],
 ['*','*','*','*','*','*','*','*']
);

# Now lets print out our grid board so we can see what it looks like.
# We will go through each row and then each column.
# As we do this we will record the list of cars (letters) we see into a hash

print "Here is your board.\n";

&printGrid(\@startingGrid);

# Lets find the cars on the board and the direction they are sitting

for $row (0 .. $#startingGrid) {
    for $col (0 .. $#{$startingGrid[$row]} ) {

        # Make spot the value of the bit on the grid we are looking at
        $spot = $startingGrid[$row][$col];

        # Lets record any cars we see into a "hash" of valid cars.
        # If the splot is a non-character we will ignore it cars are only characters
        unless ($spot =~ /\W/) {

            # We will record the direction of the car as the value of the hash key.
            # If the location above or below our spot is the same then the car must be vertical.
            # If its not vertical we mark as it as horizonal as it can't be anything else!

            if ($startingGrid[$row-1][$col] eq $spot || $startingGrid[$row+1] eq $spot) {
                $cars{$spot} = '|';
            } else {
                $cars{$spot} = '-';
            }
        }
    }
}

# Okay we should have printed our grid and worked out the unique cars
# Lets print out our list of cars in order

print "\nI have determined that you have used the following cars on your grid board.\n";
foreach $car (sort keys %cars) {
    print " $car$cars{$car}";
}
print "\n\n";

end;

&tryMoves();

end;

# Here are our subroutines for things that we want to do over and over again or things we might do once but for 
# clatiry we want to keep the main line of logic clear

sub tryMoves {

    # Okay, this is the hard work. Take the grid we have been given. For each car see what moves are possible
    # and try each in turn on a new grid. We will do a shallow breadth first search (BFS) rather than depth first. 
    # The BFS is achieved by throwing new sequences onto the end of a stack. You then keep pulling sequnces
    # from the front of the stack. Each time you get a new item of the stack you have to rebuild the grid to what
    # it looks like at that point based on the previous moves, this takes more CPU but does not consume as much
    # memory as saving all of the grid representations.

    my (@moveQueue);
    my (@thisMove);
    push @moveQueue, \@thisMove;

    # Whlst there are moves on the queue process them                
    while ($sequence = shift @moveQueue) { 

        # We have to make a current view of the grid based on the moves that got us here

        $currentGrid = dclone(\@startingGrid);
        foreach $step (@{ $sequence }) {
            $step =~ /(\w)-(\w)(\d)/;
            $car = ; $dir = ; $repeat = ;

            foreach (1 .. $repeat) {
                &moveCarRight($car, $currentGrid) if $dir eq 'R';
                &moveCarLeft($car,  $currentGrid) if $dir eq 'L';
                &moveCarUp($car,    $currentGrid) if $dir eq 'U';
                &moveCarDown($car,  $currentGrid) if $dir eq 'D';
            }
        }

        # Lets see what are the moves that we can do from here.

        my (@moves);

        foreach $car (sort keys %cars) {
            if ($cars{$car} eq "-") {
                $l = &canGoLeft($car,$currentGrid);
                push @moves, "$car-L$l" if ($l);
                $l = &canGoRight($car,$currentGrid);
                push @moves, "$car-R$l" if ($l);
            } else {
                $l = &canGoUp($car,$currentGrid);
                push @moves, "$car-U$l" if ($l);
                $l = &canGoDown($car,$currentGrid);
                push @moves, "$car-D$l" if ($l);
            }
        }

        # Try each of the moves, if it solves the puzzle we are done. Otherwise take the new 
        # list of moves and throw it on the stack

        foreach $step (@moves) {

            $step =~ /(\w)-(\w)(\d)/;
            $car = ; $dir = ; $repeat = ;

            my $newGrid = dclone($currentGrid);

            foreach (1 .. $repeat) {
                &moveCarRight($car, $newGrid) if $dir eq 'R';
                &moveCarLeft($car, $newGrid) if $dir eq 'L';
                &moveCarUp($car, $newGrid) if $dir eq 'U';
                &moveCarDown($car, $newGrid) if $dir eq 'D';
            }

            if (&isItSolved($newGrid)) {
                print sprintf("Solution in %d moves :\n", (scalar @{ $sequence }) + 1);
                print join ",", @{ $sequence };
                print ",$car-$dir$repeat\n";
                return;
            } else {

                # That did not create a solution, before we push this for further sequencing we want to see if this
                # pattern has been encountered before. If it has there is no point trying more variations as we already
                # have a sequence that gets here and it might have been shorter, thanks to our BFS

                if (!&seen($newGrid)) {
                    # Um, looks like it was not solved, lets throw this grid on the queue for another attempt
                    my (@thisSteps) = @{ $sequence };
                    push @thisSteps, "$car-$dir$repeat";
                    push @moveQueue, \@thisSteps;
                }
            }            
        }
    }
}    

sub isItSolved {

    my ($grid) = shift;

    my ($row, $col);
    my $stringVersion;

    foreach $row (@$grid) {
        $stringVersion .= join "",@$row;
    }

    # We know we have solve the grid lock when the T is next to the @, because that means the taxi is at the door
    if ($stringVersion =~ /\T\@/) {
        return 1;
    }
    return 0;
}    

sub seen {

    my ($grid) = shift;

    my ($row, $col);
    my $stringVersion;

    foreach $row (@$grid) {
        $stringVersion .= join "",@$row;
    }

    # Have we seen this before?
    if ($seen{$stringVersion}) {
        return 1;
    }
    $seen{$stringVersion} = 1;
    return 0;
}    

sub canGoDown {

    my ($car) = shift;

    return 0 if $cars{$car} eq "-";

    my ($grid) = shift;

    my ($row, $col);


    for ($row = $#{$grid}; $row >= 0; --$row) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[++$row][$col] eq ".") {
                    ++$l;
                }
                return $l;
            }
        }
    }
    return 0;
}

sub canGoUp {

    my ($car) = shift;

    return 0 if $cars{$car} eq "-";

    my ($grid) = shift;

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[--$row][$col] eq ".") {
                    ++$l;
                } 
                return $l;
            }
        }
    }
    return 0;
}

sub canGoRight {

    my ($car) = shift;

    return 0 if $cars{$car} eq "|";

    my ($grid) = shift;

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[$row][++$col] eq ".") {
                    ++$l;
                } 
                return $l;
            }
        }
    }
    return 0;
}

sub canGoLeft {

    my ($car) = shift;

    return 0 if $cars{$car} eq "|";

    my ($grid) = shift;

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[$row][--$col] eq ".") {
                    ++$l;
                } 
                return $l;
            }
        }
    }
    return 0;
}

sub moveCarLeft {

    # Move the named car to the left of the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving left requires sweeping left to right.

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only horizontal cards can move left
    die "Opps, tried to move a vertical car $car left" if $cars{$car} eq "|";

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car left into an occupied spot\n" if $grid->[$row][$col-1] ne ".";
                $grid->[$row][$col-1] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}

sub moveCarRight {

    # Move the named car to the right of the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving right requires sweeping right to left (backwards).

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only horizontal cards can move right
    die "Opps, tried to move a vertical car $car right" if $cars{$car} eq "|";

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car right into an occupied spot\n" if $grid->[$row][$col+1] ne ".";
                $grid->[$row][$col+1] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}


sub moveCarUp {

    # Move the named car up in the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving right requires sweeping top down.

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only vertical cards can move up
    die "Opps, tried to move a horizontal car $car up" if $cars{$car} eq "-";

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car up into an occupied spot\n" if $grid->[$row-1][$col] ne ".";
                $grid->[$row-1][$col] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}

sub moveCarDown {

    # Move the named car down in the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving right requires sweeping upwards from the bottom.

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only vertical cards can move up
    die "Opps, tried to move a horizontal car $car down" if $cars{$car} eq "-";

    my ($row, $col);    

    for ($row = $#{$grid}; $row >=0; --$row) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car down into an occupied spot\n" if $grid->[$row+1][$col] ne ".";
                $grid->[$row+1][$col] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}

sub printGrid {

    # Print out a representation of a grid

    my ($grid) = shift; # This is a reference to an array of arrays whch is passed as the argument

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
                print $grid->[$row][$col], " ";
        }
        print "\n";
    }
}

il y a en fait un papier du MIT qui fait spécifiquement référence à L'Heure de pointe (j'ai utilisé le terme de recherche" puzzles à glissières")

Vous devriez recurse (votre "retour en arrière" de la solution). C'est probablement la seule façon de résoudre des puzzles comme celui-ci; la question Est de savoir comment le faire rapidement.

Comme vous l'avez remarqué, l'espace de recherche sera grande, mais pas trop grand, si vous avez une taille raisonnable conseil d'administration. Par exemple, vous avez dessiné une grille de 6x6 avec 12 voitures dessus. En supposant que chaque voiture est de taille 2, cela donne 5 espaces / per, donc au plus 5^12 = 244.140.625 positions potentielles. Cela correspond même à un entier de 32 bits. Donc on la possibilité est d'allouer un tableau énorme, une fente par position potentielle, et utiliser la memoization pour s'assurer que vous ne répétez pas une position.

la prochaine chose à noter est que la plupart de ces positions" potentielles " ne sont pas, en fait, possible (ils impliqueraient des voitures se chevauchant). Ainsi, à la place, utilisez une table de hachage pour garder la trace de chaque position que vous avez visitée. Cela aura une petite mémoire aérienne par entrée, mais il sera probablement plus efficace de l'espace que la solution de" tableau énorme". Cela prendra cependant un peu plus de temps pour chaque accès.

comme le dit le papier du MIT dans réponse de @Daniel , le problème est PSPACE-complet, ce qui signifie que beaucoup des trucs utilisés pour réduire la complexité des problèmes NP ne peut probablement pas être utilisé.

cela dit, l'une ou l'autre des deux solutions ci-dessus au problème des positions répétées devrait fonctionner pour les petites grilles. Tout sera déterminé par la taille du problème, et la quantité de mémoire de votre ordinateur; mais l'exemple que vous avez affichée doit être pas mal du tout, même pour un pc ordinaire.

vient de finir d'écrire mon implémentation et d'expérimenter avec elle. Je suis d'accord avec polygenelubricants que l'espace d'état est vraiment petit pour le jeu classique (6x6 conseil d'administration). Cependant, j'ai essayé une implémentation de recherche intelligente ( a* search ). J'étais curieux au sujet de la réduction de l'espace d'état exploré par rapport à un BFS simple.

a * algorithme peut être considéré comme une généralisation de la recherche BFS. La décision de la voie à explorer est déterminé par un score qui combine la longueur du chemin (c.-à-d. le nombre de mouvements) et une limite inférieure sur le nombre de mouvements restants. La façon dont j'ai choisi de calculer cette dernière, est d'obtenir la distance de la voiture rouge de la sortie, puis ajouter 1 pour chaque véhicule dans le chemin, il doit être déplacé au moins une fois afin de dégager la voie. Quand je remplace le calcul de la limite inférieure par une constante 0, j'obtiens un comportement BFS régulier.

après inspection de quatre puzzles de cette liste , j'ai trouvé Qu'une recherche de* explore en moyenne 16% moins d'États qu'un BFS régulier.

je pense que la récursion est une mauvaise idée, sauf si vous gardez une trace de ce que vous avez déjà visité; vous pourriez finir par se reproduire infiniment en déplaçant une voiture d'avant en arrière.

peut-être que c'est un bon début: représenter et stocker chaque État de la carte comme un graphe non dirigé. Ensuite, pour chaque mouvement possible, vérifiez avec les états passés pour vous assurer que vous ne frappez pas juste le même état à nouveau.

maintenant faites un autre graphe non-dirigé où les noeuds représentent les États et les arêtes représentent la capacité à passer d'un état à un autre par le déplacement d'une voiture. Explorer les états jusqu'à ce que l'un d'eux est une solution. Suivez ensuite les bords du début à trouver une trajectoire déplacer.

j'ai écrit un solveur sudoku. Bien que les détails sont complètement différents, je pense que le problème est similaire. D'une part, essayer de faire des heuristiques intelligentes dans un solveur sudoku est beaucoup plus lent qu'une solution de force brute. Essayer chaque mouvement, avec quelques heuristiques simples et pas de duplicata est la voie à suivre. Il est un peu plus difficile de vérifier s'il y a des doubles États du tableau à l'Heure de pointe, mais pas beaucoup.

si vous regardez le tableau dans votre échantillon, il n'y a que 4 valide se déplace. À tout moment, il n'y aura que quelques mouvements valides.

à chaque niveau de récursion, copiez l'état du tableau et essayez chaque mouvement valide sur le tableau. Pour chaque case vide, déplacer chaque voiture sur place. Si le nouvel état du tableau n'est pas dans la liste de l'histoire, alors recommencer un autre niveau. Par liste d'histoire, j'entends donner à chaque niveau de récursion accès à chaque carte qui a conduit à cet état, probablement dans une liste liée. Utilisez des coups de fouet pour jeter rapidement inégal Unis.

la clé pour cela est d'avoir un État de carte simple qui peut être facilement copié et modifié. Probablement un tableau avec un int par carré disant quelle voiture couvre ce carré, s'il y en a. Ensuite, vous avez juste besoin d'itérer à travers les carrés et de comprendre les mouvements juridiques. Un coup légal signifie cases vides entre les carrés et une voiture orientée vers elle.

comme pour sudoku, la pire option possible serait un algorithme génétique.