On se rend compte assez vite qu’il n’y a pas tant d’états uniques grâce aux symétries. J’ai donc fait un double-sided breadth-first-search à la main (cherchant à partir du début et de la fin en même temps afin de trouver une intersection plus tôt).
Mais c’est quand même long... il faudra au moins 6 coups. Et pour la deuxième question, on se rend compte assez facilement que la réponse sera soit 1 soit 10.
Je laisse tomber pour l’instant par manque de temps. Bonne chance aux autres! Quelques questions qui m’intriguent: Comment généraliser pour n’importe quel entier positif n et k (ici n=10 et k=3).
Y a-t-il une formule pour calculer le nombre d’états uniques (dépendant seulement de n). Par exemple, les états 0011000111 et 1110001100 sont les mêmes et ne devraient pas être comptés deux fois (les chaînes ci-dessus devraient être circulaires).