Two coins on a graph

Un jeu de Jeff Erickson

Ce jeu se joue avec deux jetons (ou pièces de monnaie, d'où son nom) sur un graphe comme par exemple celui-ci :

Il s'agit d'un jeu à un seul joueur. Celui-ci place deux jetons sur des sommets bien précis du graphe, par exemple ceux-ci :

Bouger un jeton signifie le déplacer vers un sommet adjacent à celui où il se trouve actuellement. Dans ce jeu, chaque tour du jeu consiste à bouger simultanément les deux jetons. Par exemple voici un tour de jeu possible :

À tout moment, un jeton peut revenir en arrière (ici, le rouge) :

Les jetons peuvent également se croiser :

Le but du jeu est d'amener, par une succession de tels mouvements, les deux jetons sur un même sommet.

Avec le jeu ci-dessus, il y a une solution, si, si ! Pour rappel voici la position initiale des deux jetons :

Saurez-vous trouver cette solution ? Elle ne fait que 3 coups !

Par contre, ce jeu n'a pas de solution :

Saurez-vous le montrer ?

Exercice Python

Écrire une fonction Python qui accepte en entrée un graphe (non orienté) et deux de ses sommets, et qui renvoie le nombre minimal de coups permettant de résoudre le jeu sur ce graphe. S'il n'y a pas de solution la fonction peut renvoyer float('inf').

Et Herschel ?

Ce jeu a une solution (pas trop dure à trouver) :

Mais pas celui-là :