Bonjour à tous, je viens de terminer (enfin je pense un programme qui résout le fameux Taquin ('8-puzzle') en utilisant le A* pour parcourir le graphe. J'ai vraiment cherché, cherché, mais je n'arrive pas à trouver une réponse claire.

Certains jeux sont solubles, d'autres non, je dirais 'de base' (test des permutations paires et impaires notamment). Quand je teste mon programme avec une map que j'ai créée en partant d'un taquin résolu, tout va bien jusqu'à atteindre une complexité qui fait qu'il ne trouve pas de solution... à une case près ! En fait je me demande si je ne repasse pas par un état connu.... tous les états possibles sont 'fermés'.

Donc ma question : le A* permet-il TOUJOURS de trouver un chemin (à condition que le taquin soit soluble) ou peut-il échouer selon la complexité du puzzle ? Je m'arrache les cheveux sur cette map depuis une semaine....

Merci d'avance
(ps, j'ai bien mis des règles pour tester les poids des états déjà fermés par rapport à un nouveau potentiel).