Le système est composé de n caisses et 4 charriots qui reçoivent des ordres tour à tour. L'état du système peut donc être représenté par les trois éléments suivants :

Les valeurs négatives pour les positions des caisses servent à indiquer que ces dernières sont chargées sur un charriot. Ainsi, la valeur -1 signifie que la caisse est sur le charriot 0. La valeur -2 signifie que la caisse est sur le charriot 1, et ainsi de suite.

L'ensemble des états forme un graphe orienté. C'est-à-dire que deux états peuvent être reliès entre eux par une flèche qui indique le sens de transformation. Un extrait d'un tel graphe pour un problème à 3 caisses est affiché ci-contre.

Pour éviter les boucles infinies, il est indispensable que dans un programme on ne repasse pas par un état précédemment visité.

Chaque noeud de ce graphe (qui représente un état du système) peut être connecté à un maximum de 4 enfants. Ceci vient du fait qu'il n'y a que 4 instructions possibles pour un charriot : ne rien faire, aller à droite, aller à gauche et prendre/poser une caisse. C'est un maximum car certaines instructions sont impossibles à réaliser dans certains cas. Par exemple, on ne peut prendre une caisse s'il n'y en a pas en face du charriot, et on ne peut pas déplacer un charriot à droite s'il y en a déjà un autre à cette emplacement.

Le coût d'une action peut s'afficher sur la flèche du graphe. Un déplacement (< ou >) coûte 1, tandis qu'une pose/prise (#) coûte 2. De plus, quand on arrive sur un état où c'est au charriot 1 de recevoir la prochaine instruction, c'est qu'on a terminé un cycle, et ceci coûte 10.

Le moyen le plus simple, pour trouver le chemin le moins cher, serait de tous les essayer et de garder le meilleur. Mais pour être sûr de prendre tous les chemins, il faut au moins être passé une fois par tous les états. Combien y a-t-il d'états pour le problème de 3 caisses ?

La première caisse a 7 positions possibles : les 4 charriots et les 3 places normales des caisses. La seconde caisse n'a plus que 6 positions possibles puisque l'une d'entre elles est déjà occuppée par la première. Ainsi, juste pour les caisses, on se retrouve avec 7*6*5 = 210 configurations.

Il faut ensuite compter les configurations des charriots. Pour les deux du haut, il n'y en a que 3 : AB-, A-B et -AB. Donc pour les 4 caisses, on se retrouve avec 9 configurations.

Enfin, un état dépend aussi de l'indice du charriot qui attend le prochain ordre. Cela multiplie encore le nombre de configurations par 4. Au total, on a 210*9*4 = 7560 états différents. Imaginez le nombre de chemins qu'il peut exister au sein d'un graphe de cette taille.

Mais, si la solution se trouve à 3 états du départ, puisqu'il n'y a pas plus de 4 flèches partant de chaque noeud, on aurait seulement un maximum de 4*4*4 = 64 chemins à tester. Malheureusement, comme on ne sait pas si le chemin trouvé est le meilleur on doit chercher un nombre beaucoup plus grand de chemins.

L'idée qui nous vient alors est que l'on pourrait mémoriser le coût du plus court chemin examiné jusque là et arrêter de poursuivre un nouveau chemin si son coût actuel est déjà plus grand. Et l'idée est bonne puisque pour trouver le programme le moins cher qui remet dans l'ordre les caisses BCA, nous allons analyser 23'679 chemins différents.

Prenons un exemple. Dans le graphe ci-dessus, on a représenté des états et des coûts pour passer de l'un à l'autre. Le but est de trouver le chemin le moins cher qui relie A à G. On part de l'état A et on met dans un sac tous les chemins (avec leur coût) qui partent de cet état.
(AB,7) (AC,3) (AD,1)

Tant qu'il y a quelque chose dans ce sac, on procède comme suit :

Cela nous donne ceci : On a donc trouvé la solution, il s'agit de ACFEG pour un coût total de 14.

Cet algorithme est plutôt pas mal, mais il existe une technique qui permet de n'analyser que 11'177 chemins différents dans le problème qui en demande 23'679.

C'est moins de la moitié ! La page suivante explique cette technique.