=========
Rush Hour
=========

But du projet
=============

* Écrire un programme qui résoud un problème 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)>`_.

.. figure:: ./terrain.jpg
   :scale: 12 %
   :alt: alt

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


.. figure:: ./rush001.jpg
   :scale: 25 %
   :alt: alt

   La liste des véhicules.

.. figure:: ./rush002.jpg
   :scale: 25 %
   :alt: alt

   La définition d'un problème.

.. figure:: ./rush005.jpg
   :scale: 25 %
   :alt: alt

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





Travail demandé
===============

Écrire un programme permettant de saisir une configuration de *Rush Hour*, et fournissant en sortie une liste minimale de mouvements permettant de faire sortir la voiture rouge. 

Quelques pistes
===============
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 configurtion 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 possibles depuis cette configuration : un mouvement est un mouvement élémentaire d'un
  véhicule (une seule case à la fois). 
* On ne garde dans cette liste que les mouvements qui amènent dans une position qui n'a pas encore été rencontrée 
  (voyez-vous pourquoi ?)
* 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*. 

Une *file* (*queue* en anglais) est une structure de données linéaire dans laquelle les éléments sont introduits par la «queue», et ressortis par la «tête» selon la règle du «premier entré, premier sorti» (*FIFO* pour *First In, First Out* en anglais). Pour plus d'information, voir `ici <https://fr.wikipedia.org/wiki/File_(structure_de_donn%C3%A9es)>`_.

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. 

Quelques configurations à résoudre
----------------------------------

.. figure:: ./Probleme1.png
   :scale: 25 %
   :alt: alt

.. figure:: ./Probleme2.png
   :scale: 25 %
   :alt: alt

.. figure:: ./Probleme38.png
   :scale: 25 %
   :alt: alt

.. figure:: ./Probleme39.png
   :scale: 25 %
   :alt: alt

.. figure:: ./Probleme40.png
   :scale: 25 %
   :alt: alt

	  
Extensions envisageables
------------------------

#. Représentation graphique des mouvements
   
 
      
Progression possible
====================

#. semaine 1 : Saisie d'une configuration, liste des mouvements possibles. 
#. semaines 2 et 3 : Résolution du casse-tête. 
#. semaine 4 : Recherche de solution particulière (+ Représentation graphique facultatif). 


Matériel fourni
===============

Rien
      
