# But du projet

Écrire une activité élève permettant la résolution du jeu Rush Hour


# Présentation du jeu

*Rush Hour* (*Heure de pointe* en anglais), est un casse-tête dont le
but est de faire sortir d'un terrain de jeu rectangulaire une voiture,
alors que le chemin vers la sortie est encombrée par d'autres véhicules.
Chaque véhicule se déplace soit horizontalement, soit verticalement
(mais pas les deux).

Outre le plateau de jeu, le casse-tête contient une quarantaine de
cartes représentant chacune une configuration à résoudre.

Pour en savoir plus :
[Wikipedia](https://fr.wikipedia.org/wiki/Rush_hour_(casse-tête)).

- Faites sortir la voiture rouge en un nombre minimal de mouvements

<img src="terrain.jpg" width=200px/>

- La liste des véhicules

<img src="rush001.jpg" width=200px/>

- La définition d'un problème.

<img src="rush002.jpg" width=200px/>

- La solution du problème précédent

<img src="rush005.jpg" width=200px/>



Le jeu se déroule sur un plateau de 6 lignes et 6 colonnes. la voiture
rouge est toujours sur la troisième ligne, et elle doit sortir par la
droite du plateau.

# Quelques configurations à résoudre

<img src="Probleme1.png" width=200px/>  

<img src="Probleme2.png" width=200px/>  

<img src="Probleme38.png" width=200px/>   

<img src="Probleme39.png" width=200px/>  

<img src="Probleme40.png" width=200px/>



# Représentation des configurations

Le jeu se déroule sur un plateau de __6 lignes et 6 colonnes__. la voiture rouge est toujours sur la troisième ligne, et elle doit sortir par la droite du plateau.

Une __configuration__ est définie par la liste des véhicules, leur position et leur orientation (verticale ou horizontale).

On doit pouvoir créer un plateau vide, y ajouter un véhicule, vérifier qu’une configuration est valide (pas de véhicules qui se chevauchent, la voiture rouge sur la troisième ligne).


# Fonctions utiles

Il sera utile de pouvoir créer la liste de tous les mouvements possibles à partir d’une configuration donnée.

On doit pouvoir aussi vérifier facilement que deux configurations sont identiques (__ce test est à faire très souvent dans le programme de résolution, c’est important qu’il soit efficace__).

# Méthode de résolution


Le principe de résolution est le suivant :

```
SI la position courante est finale :
    Afficher la liste des mouvements qui a permis d’y arriver.
SINON
    faire la liste de tous les mouvements élémentaires possibles depuis cette configuration
ne gardez dans cette liste que les mouvements qui amènent dans une position qui n’a pas encore été rencontrée 
POUR chacun de ces mouvements restants :
    calculez la nouvelle configuration 
    # qu’il faudra étudier par la suite, sauf si on trouve une solution avant.
```

# Une recherche de solution particulière

La recherche de la solution la plus courte consiste à parcourir
l’arbre de toutes les configurations possibles (les noeuds de l’arbre
sont des configurations, les branches sont les mouvements qui
permettent de passer d’une configuration à la suivante). Pour trouver
la ou les solutions les plus courtes, il faut parcourir cet arbre des
configurations possibles en largeur d’abord. Pour cela, la méthode la
plus courante est d’utiliser une file.

Pour notre problème, si la file ne contient au départ que la
configuration initiale, on va commencer par y entrer les
configurations qu’on peut obtenir en un seul mouvement. On commencera
donc à traiter ces configurations, en mettant en attente au fond de la
file toutes les configurations de longueur deux qu’on rencontrera en
les traitant.

Lorsqu’on trouvera une solution, on aura alors la garantie qu’elle est
la plus courte (attention, il peut exister plusieurs solutions
minimales de même taille !).

Mais attention, si on se contente de sauvegarder les configurations
dans la file, on connaîtra la longueur de la solution la plus courte,
mais on n’aura pas la liste des mouvements qui y conduit. Chaque
élément de la file devra donc être une configuration et une liste de
mouvements.

Certaines configurations n’ont pas de solutions : votre programme
devra pouvoir vous l’indiquer.
