Un jeu de pions

Édouard Lucas est un mathématicien français qui a vécu durant la seconde moitié du 19^e 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] + [2] * n + [-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 :