Déplacer des pièces dans une grille - Lycée Baudelaire (Annecy)

On s'intéresse au problème suivant : des pièces de monnaie sont placées sur une grille et on souhaite les déplacer pour arriver à une position cible. La règle pour déplacer les pièces est qu'on doit les déplacer une à la fois et que lorsqu'on place une pièce elle doit être adjacente à deux autres pièces.
Deux types d'adjacence sont étudiées, "l'adjacence du roi" où une pièce est adjacente aux huit pièces autour et "l'adjacence rectiligne" qui ne comptent que les quatre adjacences verticales et horizontales.
Pour ces deux adjacences,
• Y a-t-il des paires position de départ/position d'arrivée qui ne peuvent pas être résolues ?
• Peut-on facilement voir qu'une paire est impossible à résoudre et comment caractériser de telles paires ?
Aussi, que se passerait-il si on étendait les notions d'adjacence :
• Diagonales + horizontales, mais pas de verticales ?
• Rectiligne, mais à distance 1 ou 2 ?
• Des adjacences plus bizarre comme l'adjacence du cavalier ?
• Et que se passerait-il si chaque pièce se voyait attribuer une adjacence propre (roi ou rectiligne) ?