Re: Remarques

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ⁿ branches à l'étape n ce qui est très peu intéressant.

Par boucle j'entends : comment vérifie tu que tu n'a pas de cycle dans ton arbre.

É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.

C'est gratuit quand c'est l'essence de ton arbre et je vois pas d'autre manière de garantir que tu n'ai pas de cycle dans ton arbre.

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).

C'est un calcul trivial (déterminer un coup à partir de 2 configurations est très simple), d'une complexité linéaire. Donc ça ne change pas grand chose à ce niveau là.

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 ?

Il en existe peut être d'autre, mais c'est ce que j'avais en tête.

Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)