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 :
Avec le jeu ci-dessus, il y a une solution, si, si ! Pour rappel voici la position initiale des deux jetons :
Par contre, ce jeu n'a pas de solution :
É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')
.
Ce jeu a une solution (pas trop dure à trouver) :
Mais pas celui-là :