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.

../../_images/rush_hour.gif

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
+------+
|AA   O|
|P  Q O|
|PXXQ O 
|P  Q  |
|B   CC|
|B RRR |
+------+
plateau.recule("Q")
+------+
|AA Q O|
|P  Q O|
|PXXQ O 
|P     |
|B   CC|
|B RRR |
+------+
plateau.est_gagnant()
False

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

Plateau(40)
+------+
|OAA B |
|OCD BP|
|OCDXXP 
|QQQE P|
|  FEKK|
|HHFII |
+------+

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 class 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:

!flake8 rush_hour.py
!pytest rush_hour.py
# Affichage du code pour correction
import inspect
print(inspect.getsource(RushHour.solution))