Lien vers le devoir sur github classroom

Présentation

Pour ce dernier de TP, qui nous occupera pendant 3 séances, nous nous intéressons à la résolution de certains casse-têtes impliquant de déplacer des parties mobiles jusqu’à atteindre une configuration exigée. Un exemple de telle casse-tête est le Rubik’s Cube, mais nous en verrons d’autres.

En fait notre but va être d’utiliser un algorithme, un solveur, capable de résoudre plusieurs casse-têtes différents, avec des solutions les plus courtes possibles. Afin d’être le plus général possible, le solveur fait un minimum d’hypothèses sur le casse-tête qu’il doit résoudre. Spécifiquement, le solveur va avoir besoin :

  • d’une position de départ pour le casse-tête,
  • d’une fonction qui à chaque position atteignable, énumère les positions atteignables en un seul mouvement élémentaire,
  • de pouvoir déterminer si une position est gagnante ou finale, c’est-à-dire qu’atteindre cette position est une solution du casse-tête,
  • afin d’améliorer les temps de recherche d’une solution, il demande aussi une fonction qui a une position, donne le nombre de mouvements nécessaires pour résoudre le problème depuis cette position.

En fait, connaître le nombre exact de mouvements nécessaires permettrait de trouver très facilement la plus petite suite de mouvements résolvant le problème. En général, calculer cette fonction est donc aussi difficile que de résoudre complètement le problème. Du coup, on se contentera d’une fonction qui sous-estime le nombre de mouvements encore nécessaires. Par exemple, la fonction constante 0 est une fonction qui sous-estime le nombre de mouvements nécessaires, mais elle est très peu précise. Plus la fonction que nous donnons est précise, et plus le solveur sera efficace.

Pour résumer, il nous faut donc définir la configuration initiale, la fonction de mouvement, et une heuristique fournissant une sous-estimation du nombre de mouvements restants.

Voici quelques exemples de problèmes que nous pourrons ainsi résoudre :

  • le taquin. La position initiale est choisie aléatoirement. Un mouvement consiste à échanger la case vide avec une case adjacente. Une position est finale si les cases sont dans l’ordre, avec la case vide dans le coin inférieur droit. Une heuristique simple est le nombre de cases qui ne sont pas à leur place définitive. Si vous ne connaissez pas, vous pouvez essayer ici.
  • Les tours de Hanoï. La position initiale consiste à \(n\) disques de largueurs distinctes empilés dans l’ordre sur le premier emplacement. Un mouvement consiste à déplacer un seul disque du haut d’une pile vers le haut d’une autre pile, de sorte que chaque pile reste ordonnée. On ne peut avoir qu’une pile sur chacun des trois emplacements. La position finale est d’avoir tous les disques sur le 3e emplacement. Une heuristique simple est le nombre de disques qui ne sont pas sur le 3e emplacement. Vous pouvez essayer ici.
  • Rush Hour. La position initiale est une configuration de véhicules (des rectangles de largeur ou de hauteur 1) sur une grille. Un mouvement consiste à faire avancer ou reculer un véhicule sur sa ligne ou sa colonne, sans empiéter sur les autres véhicules. La position finale est lorsque le véhicule rouge est adjacent au bord droit de la grille. Une heuristique est le nombre de véhicules entre le véhicule rouge et le bord droit.
  • Ou encore : le Rubik’s cube, Klotski, FreeCell, Sokoban,…

Nous n’allons pas programmer l’algorithme de résolution. Il est fourni dans les sources présents sur le dépot git initial du projet. Plutôt, nous allons nous intéresser à programmer un ou plusieurs casse-têtes. Autrement dit votre travail est de choisir un de ces casse-têtes, et de le modéliser en créant les classes adéquates, de façon à pouvoir utiliser le solveur fourni pour afficher les solutions. À titre d’exemple, le programme pour la résolution des tours de Hanoï est fourni dans le dépot initial.

Ce projet est libre. Contrairement aux précédents TP, il n’y a pas de questions intermédiaires. Vous devez choisir un ou plusieurs casse-têtes, parmi ceux présentés ci-dessus ou bien venant d’ailleurs (il faut que ce soit un casse-tête exigeant une suite de mouvements). Pour chaque casse-tête, nous voulons :

  • une modélisation des positions et des mouvements, ainsi qu’une heuristique pour l’estimation du nombre de mouvements nécessaires. C’est la partie principale du travail.
  • une fonction d’affichage pour visualiser les positions,
  • la résolution d’une instance du casse-tête,
  • optionnellement, on peut vouloir importer des positions à résoudre depuis un fichier, écrire des solutions dans un fichier,
  • optionnellement, on peut aussi réaliser un affichage graphique, ou même une application permettant à l’utilisateur de jouer, avec un option de résolution automatique.

Mais avant cela, il manque une petite partie au solveur pour pouvoir fonctionner. Le solveur retourne la solution sous la forme d’une suite de mouvements représentés par la classe Path, mais celle-ci n’est pas complète. Plus exactement, c’est une classe abstraite, à laquelle il manque les implémentations. Une instance de Path<T> est une séquence de valeurs de type T pouvant être vide. Étant donnée une séquence sequence représentant les éléments e1, e2,..., en, on appelle e1 la tête de sequence, et e2,..., en la queue de sequence. On peut aussi ajouter un élément e0 à sequence : ainsi sequence.append(e0) est la séquence e0, e1, e2,... en. append ajoute donc un élément au début de la séquence. Les instances de Path<T> sont immutables, append et tail ne doivent donc pas modifier this.

Tâche 1

Compléter Path en créant deux extensions, EndOfPath (représentant une séquence sans élément) et ContinuingPath (représentant une séquence avec au moins un élément). La méthode forEach doit exécuter le consommateur sur tous les éléments de la séquence, dans l’ordre depuis l’élément de tête.

Tâche 2

Modéliser un ou plusieurs casse-têtes, et utiliser le solveur pour le résoudre.

Conseils et précisions importantes

  • Les classes des positions et des mouvements doivent être immutables, sinon le solveur ne fonctionnera pas correctement. Autrement dit, on travaillera quasiment uniquement avec des propriétés finales. On ne modifiera pas les listes ou autres structures de données après leur création. Pour cela, on réalisera des copies, par exemple pour copier une liste list on peut écrire new ArrayList<>(list).

  • Il faudra redéfinir la méthode equals dans les classes des positions. L’algorithme utilise massivement le test d’égalité, s’il n’est pas correct les temps de calculs sont horriblement longs. Il faudra aussi définir la méthode hashCode. Pour calculer le hashCode d’un objet, utiliser la méthode Objects.hashCode avec en paramètre tous les hashCodes des propriétés de cet objet qui sont testées par le test d’égalité. Attention, ne jamais utiliser la méthode hashCode ou la méthode equals d’une Deque : convertissez la deque en liste puis prenez son hashCode.

  • Le temps de calcul effectif de l’algorithme est très dépendant de la méthode hashCode. Hanoi montre une façon de réduire les calculs lors des tests d’égalités et du calcul de hashCode en encodant toute la configuration dans un seul entier long, et en utilisant ensuite simplement une comparaison des deux entiers longs. Pour cela il faut une bijection entre les instances et les entiers long, ce qui n’est pas toujours facile ou possible. Par contre il est toujours possible de calculer une fois pour toute le hashCode à la création de l’objet (puisque ce dernier ne devra pas changer ensuite) et de le stocker dans une propriété.

  • Les classes des positions et des mouvements doivent redéfinir toString pour produire un affichage décent.

  • N’hésitez pas à créer de nombreuses classes simples, plutôt qu’une seule classe compliquée. N’hésitez pas à créer de nombreuses méthodes simples, plutôt qu’une méthode compliquée.

  • Commencer par vous demander comment les configurations du casse-tête peuvent être représentées. Comment les mouvements peuvent être représentés. Il faut, avec une configuration et un mouvement, pouvoir calculer la configuration obtenue facilement. Quel encodage des configurations le permet ?

  • Vous pouvez aussi refaire Hanoï différement, du moment que vous utilisez une représentation complètement différente.

  • pour Rush Hour, le répertoire resources contient un ficher définissant plein d’instances différentes. Chaque instance est définie par un nom, la dimension de la grille, et la liste des véhicules au format “x y axis length” ou axis détermine si le véhicule est dans l’axe vertical ou horizontal. Le premier véhicule est le véhicule rouge.

  • pour le taquin, si vous générez une instance aléatoire, il y a une chance sur deux qu’elle n’ait pas de solution. Par ailleurs, l’ensemble des solutions est très grand, et sans une très bonne heuristique, l’algorithme ne terminera pas dans un délai de temps raisonnable. Il est préférable de partir d’une instance mélangée (on part de la solution et on applique des mouvements aléatoires avec Helpers.randomize par exemple). C’est le cas aussi du Rubik’s cube.

Présentation des sources fournies

La suite du sujet présente les différentes classes fournies.

Le solveur

Le solveur est donné dans le package solver, et utilise les packages path et tools.

La classe Solver contient l’algorithme de résolution. Pour information, il s’agit d’une implémentation de l’algorithme A*, mais vous n’avez absolument pas besoin de comprendre son fonctionnement pour faire le projet.

  • Solver est paramétré par deux paramètres de types. P représente le type des positions ou configurations du casse-tête (on utilisera indifférement les termes position et configuration), autrement dit l’état du casse-tête après un certain nombre de mouvements. M représente le type des mouvements qui peuvent s’appliquer au casse-tête (par exemple : déplacer tel pièce de telle case à telle case, ou faire un déplacement vers le haut, cela dépend du casse-tête particulier bien sûr).

  • Le constructeur prend en paramètre la position initiale du casse-tête, à partir de laquelle on veut le résoudre. Le constructeur ne calcule rien à ce stade.

  • La méthode solve() résoud le casse-tête en trouvant une plus courte séquence de mouvements transformant la configuration initiale en une configuration victorieuse. Il se peut que le casse-tête n’ait pas de solution. La méthode peut donc ne rien retourner, ou retourner la séquence des mouvements de type Path<M>, donc elle retourne une option de type Optional<Path<M>>. Cette méthode doit être appelée une seule fois.

  • la méthode getNbCheckedMoves() retourne le nombre de configurations testées par le solveur. C’est une mesure de la difficulté du problème, mais c’est aussi une mesure de votre heuristique d’estimation du nombre de mouvements nécessaires. Meilleure est l’heuristique, plus petit sera le nombre de configurations testées (et donc le temps de calcul).

L’interface Position définit ce qu’est une configuration d’un casse-tête. Elle est paramétrée par le type M des mouvements s’appliquant à ce casse-tête. Pour être une position, il faut avoir 4 méthodes :

  • isWinning() décide si la position est victorieuse, autrement dit si c’est la solution du casse-tête.

  • possibleMoves() retourne les mouvements pouvant s’appliquer à la position actuelle. Ce sont donc les mouvements pouvant être légalement effectués, et permettant d’obtenir une autre position. Les mouvements sont donnés sous la forme d’un Stream.

  • apply(M move) prend en argument un des mouvements légaux retournés par possibleMoves, et fournit la position correspondante après effectuer ce mouvement. Attention apply ne doit pas modifier this.

  • score() est l’heuristique permettant de sous-estimer le nombre de mouvements encore nécessaires depuis cette position. Une heuristique triviale est de toujours retourner 0, mais attention, la qualité de l’heuristique influe beaucoup sur le temps de calcul de la solution optimale.

La contrainte de généricité de Position est particulièrement complexe. Pour l’expliquer, il faut comprendre qu’il est important de préciser que apply doit retourner une position de la même classe, et non par une position arbitraire. Si apply retournait Position<M> nous perdrions la connaissance précise de la nature du casse-tête à résoudre, et si ce casse-tête possède des méthodes spécifiques que nous souhaitons utiliser (typiquement pour analyser la configuration finale victorieuse après la résolution), nous ne pourrions plus les utiliser.

Il nous faut donc aussi un paramètre pour la classe des positions dont il est question, donc Position a deux paramètres : Position<P,M>. Ainsi, on peut déclarer que Hanoi implémente Position<Hanoi,HanoiMove>.

Se pose maintenant une autre contraite. Il faut que le retour d’apply soit identifié lui-aussi comme une position. Or pour l’instant dans l’interface Position, P n’est pas contraint. On ajoute donc la contrainte que P étend l’interface Position<P,M>. Ainsi la déclaration de Position devient : Position<P extends Position<P,M>, M>. On a renommer P en This, pour expliciter qu’il va s’agir de la classe implémentant l’interface (tout comme this fait référence à l’objet instance de la classe).

La classe PartialSolution encode une solution partielle dans le solveur, c’est-à-dire une configuration et la suite de mouvements ayant permis de l’obtenir depuis la configuration initiale. Cette classe ne vous est pas utile.

Enfin, la classe Helpers contient des méthodes statiques qui peuvent vous être utiles.

  • solveAndShow résoud une configuration et imprime dans la sortie la solution complète, en détaillant chaque mouvement et chaque configuration traversée.

  • showPath affiche la séquence de mouvements d’une solution.

  • randomize applique une suite de mouvements aléatoires depuis une configuration initiale fournie. Typiquement, on l’utilise pour générer des instances en partant de la configuration initiale. Ceci assure que la configuration peut être résolu, lorsque les mouvements sont réversibles (ce qui n’est pas le cas de Sokoban par exemple, il faudrait pour cela définir les mouvements inverses de Sokoban, qui sont de tirer les caisses).

Path

Le package path contient la classe abstraite Path, et vous devrez y ajouter les deux extensions de Path.

Tools

Le package tools contient des classes utilisées par le solveur. Vous ne devriez pas en avoir besoin. Pour information, le solveur utiliser une structure de données appelées file de priorité. L’implémentation fournie dans le JDK n’est pas tout à fait conforme au besoin du solveur. PriorityQueue et LifoPriorityQueue permettent d’ajouter les propriétés supplémentaires nécessaires au solver. RandomSelector est un collecteur de Stream permettant de choisir un élément uniformément aléatoirement dans un Stream. Si vous voulez apprendre à créer vos propres collecteurs, vous pouvez étudier cette classe (mais d’abord, maîtrisez les itérateurs !).

Hanoi

Le package hanoi contient une modélisation du problème des tours de Hanoï. Une configuration, représentée par la classe Hanoi, est donnée par le nombre de disques size, et par une liste de trois piles stacks contenant les disques représentés par les entiers de 0 à size-1.

Un mouvement, représenté par la classe HanoiMove, consiste en deux entiers : l’indice de la pile dont on retire le disque supérieur, et l’indice de la pile dans laquelle on place ce disque.

On note la présence de deux constructeurs dans Hanoi. Le premier n’est pas surprenant, il définit la configuration initiale du casse-tête. Le deuxième est liée à la méthode apply qui exécute un mouvement. On note qu’il est privé, uniquement utilisé par apply, il travaille à partir d’une configuration de départ et des informations du mouvement.

La méthode isWinning ne nécessite pas d’explication, si ce n’est l’emploi de notre propre méthode pour l’égalité des Deque. En effet ArrayDeque ne redéfinit pas equals, qui est donc un test d’identité. On convertit la Deque en liste car la méthode equals des listes compare bien toutes les paires d’éléments de même coordonnée.

Pour générer les mouvements possibles, on génère tous mouvements à partir des paires de deux entiers entre 0 et 2 (inclus), et on garde les mouvements valides. On utilise donc une méthode isValid pour tester qu’un mouvement est valide.

L’heuristique score est plus subtile que celle présentée ci-dessus. On trouve le plus grand disque qui n’est pas encore en position finale. Ce disque devra bouger au moins une fois. Tous les disques qui sont posés au-dessus devront faire au moins 2 déplacements. Tous les disques plus petits de la troisième pile devront faire au moins 2 déplacements. Tous les disques de l’autre pile devront bouger encore une fois.

Le reste de la classe contient les redéfinitions de toString, equals et hashCode. Notez comment on calcule le hashCode une seule fois lors de l’initialisation de l’objet, pour gagner du temps de calcul.