Un jeu de pions

Édouard Lucas est un mathématicien français qui a vécu durant la seconde moitié du 19e siècle. Outre ses travaux de recherche, essentiellement en théorie des nombres, il est particulièrement connu pour ses ouvrages de divertissements mathématiques. Il existe à ma connaissance un premier ouvrage, en 4 volumes, les «Récréations mathématiques» (dont les deux deniers ont été publiés à titre posthume), ainsi qu’un autre ouvrage, en un seul volume :  «Arithmétique amusante», publié lui aussi à titre posthume.

L’objet de ce billet est un casse tête paru dans le second volume des récréations mathématiques sous le nom : un jeu de pions.

Les pages suivantes sont issues d’une édition de 1883 (a priori, la première) :

Voici la retranscription du texte de Lucas :

On place sur les cases d’une bande formée d’un nombre
impair de carrés un nombre égal de pions blancs et noirs,
séparés par une case vide ; tous les pions blancs se trouvant à
gauche, et les pions noirs à droite. Il s’agit de faire passer les
pions blancs à la place des pions noirs, en profitant de la case
vide.
On adopte les règles suivantes : Les pions peuvent avancer d’une
case, en allant toujours de gauche à droite, pour les pions blancs ;
et en sens inverse, pour les pions noirs. Un pions peut franchir
un pion d’une autre couleur, dans le sens de son mouvement
exigé, pour venir se placer sur la case vide immédiatement
voisine.
Si l’on suppose d’abord deux pions blancs b, b, et deux pions
noirs n,n, séparés par une case vide que nous désignerons tou-
jours par un point, on opérera d’après le tableau suivant ; la
[ Schéma ]
colonne numérique à gauche indique la suite des coups, la
colonne numérique à droite distingue, par les chiffres 1 et 2, le
pas ou avance d`une seule case, du saut ou avance de deux
cases.
Le problème se trouve ainsi résolu en 9 positions ; et l`on
observe que la colonne de droite est symétrique, c’est-à-dire
qu’elle donne les mêmes chiffres en la lisant de bas en haut ou
de haut en bas ; de plus, le rectangle qui indique les diverses
positions est symétrique par rapport au centre.
Si l’on suppose trois pions blancs et trois pions noirs, on échange
les deux systèmes, d’après les règles indiquées, conformément au
tableau suivant sur lequel on petit encore faire les remarques qui
précèdent.
[Schéma]
Le nombre des positions est égal à 16, le nombre des pas à 6 et
le nombre des sauts à 9. Pour le cas de quatre pions blancs et de
quatre pions noirs, nous donnerons seulement la moitié du
tableau des positions, l’autre moitié s’en déduit par symétrie.
[Schéma]
Le nombre des positions est 25 ; le nombre des pas est égal
à 8 et le nombre des sauts à 16. En général, le problème est tou-
jours possible, et si l’on suppose p pions blancs et p pions noirs,
le nombre total des positions est (p+1)^2 ;
le nombre des pas est 2p ;
le nombre des sauts est p^2.
En ajoutant le nombre des pas au double du nombre des sauts
on trouve 2p(p+1); c’est ce que l’on doit obtenir si l’on
remarque que, pour occuper la case assignée, chaque pion doit
avancer de p+1 cases, et par suite les 2p pions doivent exécuter
2p(p+1) déplacements d’une case.

Plutôt que d’observer le déplacement des pions, je trouve plus facile d’observer le «déplacement» de la case vide. On peut de plus «signer» ce déplacement : -2 ou -1 sont des déplacements vers la gauche de la case vide, et 1 et 2 sont des déplacements à droite de la case vide.  En listant les  déplacements à faire, on observe la symétrie dont parle Lucas, et la régularité des déplacements (ainsi que du signe) :

Pour un pion blanc et un pion noir : -1,2,1
Pour deux pions blancs et deux pions noirs :  1, -2, -1, 2, 2, -1, -2, 1
Pour trois pions blancs et trois pions noirs :  -1, 2, 1, -2, -2, -1, 2, 2, 2, -1, -2, -2, 1, 2, -1

Le programme Python (v3) suivant donne la liste des déplacements de la case vide à faire, en fonction du nombre de pions blancs :

def moves(n):
    s=1
    r=[-1,]+n*[2,]+[-1,]
    for i in range(n-1,0,-1) :
        r=[s,]+i*[-2*s,]+r+i*[-2*s,]+[s,]
        s=-s
    return r

Les «déplacements» de la case libre sont maintenant facile à obtenir :

=> moves(2)
[1, -2, -1, 2, 2, -1, -2, 1]

Il est facile avec cet outil d’afficher les positions des jetons  pendant le jeu :

def affichage(n) :
  plateau=list(n*"b"+"."+n*"n")
  seq=moves(n)
  pos=n
  for dep in seq:
    print("".join(plateau))
    plateau[pos],plateau[pos+dep]=plateau[pos+dep],plateau[pos]
    pos=pos+dep
  print("".join(plateau))

Voyons le résultat :

=> affichage(2)
bb.nn
bbn.n
b.nbn
.bnbn
nb.bn
nbnb.
nbn.b
n.nbb
nn.bb

=> affichage(3)
bbb.nnn
bb.bnnn
bbnb.nn
bbnbn.n
bbn.nbn
b.nbnbn
.bnbnbn
nb.bnbn
nbnb.bn
nbnbnb.
nbnbn.b
nbn.nbb
n.nbnbb
nn.bnbb
nnnb.bb
nnn.bbb

Avec un peu de travail en plus (et en utilisant l’interface python-asymptote), on obtient une représentation graphique du jeu. Voici une partie pour 5 pions blancs et 5 pions noirs :

Featuring WPMU Bloglist Widget by YD WordPress Developer