il me semble important de savoir déterminer s'il existe une solution (si la case cible est au milieu et qu'il n'y a aucun mur alors il n'y a pas de solution par exemple)
Ce n'est pas un problème si facile : pour déterminer si une position est impossible à atteindre, soit on cherche une solution et on en trouve pas (ce qui ne veut pas dire grand chose vu que l'arbre est infini). Soit on part de la fin et on fait la méthode « en arrière » :
Pour arriver à cette case, quels sont les directions possibles
Pour chacune des directions, quelles sont les cases concernées où je dois amener le pion pour pouvoir faire ce mouvement
Pour chaque case concernée, quelles sont les « cales » possibles ?
Pour chaque couple (pion,cale) avec un pion différent du pion initial, on a un nouvel objectif
appel récursif
Remarque : ici je ne prend pas en compte les murs, il faudrait ajouter, pour le premier mur rencontré dans chaque direction, un objectif.
On s'arrête quand on trouve :
Une solution triviale (le pion à déplacer est sur une des directions)
Un mouvement impossible : et là, comment le déterminer ? On revient au problème de départ, à priori, je n'ai pas de méthode simple pour déterminer un mouvement impossible ... Sauf si à une étape on ne change pas l'ensemble des objectifs à atteindre : ce qui veut dire que l'on est dans une « boucle de dépendance » du jeu qui ne terminera jamais.
comment t'assure-tu de ne pas boucler ?
Dans le code naïf proposé, on repasse parfois par les mêmes placements de pions, mais c'est en largeur, du coup ce n'est pas vraiment une boucle, seulement, on est certain d'avoir 16^n branches à l'étape n ce qui est très peu intéressant.
Étant donné qu'un placement est simplement un 4-uplet, on peut facilement faire un ensemble des positions déjà rencontrées, pour éviter de refaire les mêmes mouvements plusieurs fois. Je ne sais pas à quel est le gain réel de cette méthode, mais elle est facile à mettre en place.
Le coût d'une telle méthode est relativement moindre, puisqu'on va enregistrer des couples, et qu'à l'étape n on aura au pire un nombre de configuration de l'ordre de grandeur de 16^n, ce qui ne change donc pas la complexité spatiale du programme.
j'aurais plutôt tendance à créer un arbre de configuration (chaque nœud de l'arbre est un ensemble de 4 coordonnées)
C'est intéressant, mais la réponse attendue n'est pas le placement final des pions, mais bien la suite de mouvements qui y mène ... Donc si tu disposes seulement des placements, il te faut ensuite calculer les mouvements qui font la transition entre deux placements ... Alors que l'autre sens est « trivial » (calculer le placement final à partir des mouvements).
il est possible de faire de la mémoïsation pour encore tronçonner le parcours de ton arbre
Donc, cela rejoint la mise en place d'un ensemble de positions déjà vues, pour ne pas créer des branches inutiles. À moins qu'il existe un autre moyen de mémoïser ?
[^] # Re: Remarques
Posté par Aluminium95 . En réponse au journal Résolution naïve d'un jeu de société. Évalué à 2.
Ce n'est pas un problème si facile : pour déterminer si une position est impossible à atteindre, soit on cherche une solution et on en trouve pas (ce qui ne veut pas dire grand chose vu que l'arbre est infini). Soit on part de la fin et on fait la méthode « en arrière » :
Remarque : ici je ne prend pas en compte les murs, il faudrait ajouter, pour le premier mur rencontré dans chaque direction, un objectif.
On s'arrête quand on trouve :
Dans le code naïf proposé, on repasse parfois par les mêmes placements de pions, mais c'est en largeur, du coup ce n'est pas vraiment une boucle, seulement, on est certain d'avoir 16^n branches à l'étape n ce qui est très peu intéressant.
Étant donné qu'un placement est simplement un 4-uplet, on peut facilement faire un ensemble des positions déjà rencontrées, pour éviter de refaire les mêmes mouvements plusieurs fois. Je ne sais pas à quel est le gain réel de cette méthode, mais elle est facile à mettre en place.
Le coût d'une telle méthode est relativement moindre, puisqu'on va enregistrer des couples, et qu'à l'étape n on aura au pire un nombre de configuration de l'ordre de grandeur de 16^n, ce qui ne change donc pas la complexité spatiale du programme.
C'est intéressant, mais la réponse attendue n'est pas le placement final des pions, mais bien la suite de mouvements qui y mène ... Donc si tu disposes seulement des placements, il te faut ensuite calculer les mouvements qui font la transition entre deux placements ... Alors que l'autre sens est « trivial » (calculer le placement final à partir des mouvements).
Donc, cela rejoint la mise en place d'un ensemble de positions déjà vues, pour ne pas créer des branches inutiles. À moins qu'il existe un autre moyen de mémoïser ?