Ctrl+K

Problème 2: Rush Hour

Problème 2: Rush Hour#

La voiture rouge est coincée dans un embouteillage; comment déplacer les véhicules pour la faire sortir? Ci-dessous le défi 1 :

Une image du jeu Rush Hour

Quel rapport avec les parcours de graphes? Saurez-vous faire résoudre par l’ordinateur le défi 40 en un nombre minimum du coups?

Dans cette feuille, vous découvrirez le modèle et deux mini applications interactives pour le jeu RushHour qui vous sont fournis. Il ne restera «plus qu’à» implanter l”«Intelligence Artificielle» pour résoudre le jeu.

Un modèle pour RushHour#

Quelques exemple d’utilisation programmatique#

from rush_hour import Plateau

plateau = Plateau(['A2R00','X2R21','C2R44','R3R52','O3D05','P3D10','Q3D13','B2D40']); plateau

plateau.recule("Q")

plateau.est_gagnant()

Chargement du 40ème défi de RushHour (voir les fichiers dans RushHourDefis) :

Plateau(40)

Un exemple d’interface utilisateur minimale#

from ipywidgets import interact_manual
from rush_hour import Plateau
plateau = Plateau(['A2R00','X2R21','C2R44','R3R52','O3D05','P3D10','Q3D13','B2D40']); plateau
@interact_manual
def step(voiture=plateau.voitures.keys(), distance=[0,-1,1]):
    global plateau
    plateau2 = plateau.avance(voiture, distance)
    if plateau2:
        plateau = plateau2
    return plateau

Une application graphique basée sur les widgets de Jupyter#

from rush_hour_application import RushHourApplication
A = RushHourApplication()
A

À vous de jouer!#

Implantez la méthode solution dans la classe RushHour pour déterminer une séquence minimale de coup permettant de résoudre un défi, puis utilisez la ci-dessous pour résoudre le défi 40 de Rush Hour.

Indication

Considérez le graphe dont les sommets sont les états possibles du plateau et les arêtes les déplacements de voiture!

from rush_hour import RushHour
solution = RushHour.solution(40)

assert RushHour.est_solution(40, solution)

Pour évaluer la qualité du code:

from utils import code_checker, show_source
code_checker("flake8 rush_hour.py")

code_checker("pytest rush_hour.py")

from utils import show_source
show_source(RushHour.solution)
Contenu