Résolution du problème du 8 puzzle

1. Présentation du problème

On cherche à trouver une solution au problème du 8 puzzle. Le problème consiste à partir d'une situation initiale :
7 8 6
2 4
5 1 3
et à déterminer les différents mouvements de la case blanche qui ne peut être permutée qu'avec une case qui lui est adjacente. On cherche donc à obtenir la situation suivante :
1 2 3
8 4
7 6 5

2. Recherche en largeur d'abord

Dans un premier temps, vous ecrirez un algorithme d'exploration en largeur d'abord. L'état initial sera obtenu après un nombre aléatoire de permutations. Vous déterminerez combien d'états vous generez pour trouver la solution. Une trace de la solution est demandée, i. e vous donnerez façon optionnelle tous les états générés et obligatoirement le chemin entre l'état initial et l'état final.

3. Recherche à l'aide de l'algorithme A*

Modifier votre programme de façon à utiliser l'algorithme A*. Comme dans le cas précédent vous déterminerez le nombre d'états que vous avez générés et vous fournirez une trace de la solution. Cet algorithme est-il plus efficace que le precedent ?

Voici une applet qui utilise cet algorithme.