Solitaire et complexes

Présentation du solitaire

L’article qui suit est très inspiré de l’article A Solitaire Game and its Relation to a Finite Field de N. G. de Bruijn. J’ai choisi de remplacer l’utilisation du corps ${\mathbb{F}}_4$ par l’anneau $\mathbb{Z}[j]$ qui est sans doute plus familier des étudiants de première année.

Le jeu du solitaire est un jeu sur plateau bien connu. Des pions sont disposés dans des trous disposés sur un plateau. L’objectif est de déplacer les pions (cf. ci-dessous) de manière à ce qu’il ne reste plus qu’un pion à la fin.

Il existe plusieurs variantes de ce jeu tenant à la disposition des trous sur le plateau et aux positions initiales des jetons dans ces trous. On distinguera dans cet article les deux variantes suivantes. Vous pouvez même y jouer (cliquer ou appuyer sur les pions)! ¹

Solitaire anglais

Solitaire français

Repérage

Pour ce qui suit, on va repérer les emplacements des trous à l’aide de coordonnées. On utilise des axes centrés sur le trou central mais ceci importe peu en fait. Voici par exemple le repérage des trous pour la version française du solitaire.

Mouvements

On peut déplacer un pion vers un trou pour supprimer un autre pion en utilisant un des 4 déplacements suivants (vers la droite, la gauche, le bas ou le haut).

L’anneau $\mathbb{Z}[j]$

On introduit maintenant quelques objets mathématiques. On rappelle que $j$ est une racine cubique de l’unité et que, par conséquent,

On considère alors l’ensemble suivant.

On prouve aisément que $\mathbb{Z}[j]$ est un anneau pour les lois usuelles. Comme $j$ et $j^{-1}=-1-j$ appartiennent à $\mathbb{Z}[j]$, $j^n$ appartient également à $\mathbb{Z}[j]$ pour tout $n\in \mathbb{Z}$. Plus précisément :

• si $n\equiv 0[3]$, $j^n=1$ ;
• si $n\equiv 1[3]$, $j^n=j$ ;
• si $n\equiv 2[3]$, $j^n=j^2=-1-j$.

On peut notamment définir une fonction Python calculant les coordonnées de $j^n$ dans la base $(1,j)$.

def coord(n):
    if n % 3 == 0:
        return (1, 0)
    if n % 3 == 1:
        return (0, 1)
    if n % 3 == 2:
        return (-1, -1)

On dira que $u\in \mathbb{Z}[j]$ et $v\in \mathbb{Z}[j]$ sont congrus modulo 2 et on notera $u\equiv v[2]$ s’il existe $w\in \mathbb{Z}[j]$ tel que $u=v+2w$. De manière équivalente, $u=a+bj$ et $v=c+d$ sont congrus modulo 2 si $a\equiv c[2]$ et $b\equiv d[2]$ (au sens de la congruence usuelle sur les entiers).

Deux invariants

On s’intéresse maintenant à deux quantités qui possèdent des propriétés de conservation au cours du jeu. On note $S$ l’ensemble des coordonnées des pions à un moment du jeu et on pose :

Ce qui précède montre que, quelque soit $S$, $A(S)$ et $B(S)$ sont des éléments de l’anneau $\mathbb{Z}[j]$. On peut donc également définir deux fonctions Python qui calculent les coordonnées de $A(S)$ et $B(S)$ dans la base $(1,j)$.

def A(S):
    c = [coord(k + l) for k, l in S]
    return sum(a for a, b in c), sum(b for a, b in c)


def B(S):
    c = [coord(k - l) for k, l in S]
    return sum(a for a, b in c), sum(b for a, b in c)

Nous allons d’abord regarder l’effet sur $A(S)$ et $B(S)$ d’un mouvement d’un pion vers la droite. Supposons que $(k_0,{\ell }_0)$ et $(k_0+1,{\ell }_0)$ appartiennent à $S$ mais que $(k_0+2,{\ell }_0)$ n’appartienne pas à $S$. Si cette dernière position est l’emplacement d’un trou, on peut déplacer le pion en position $(k_0,{\ell }_0)$ vers la position $(k_0+2,{\ell }_0)$. Notons $S^{\prime }$ la configuration ainsi obtenue. Si on récapitule :

• un pion a disparu en $(k_0,{\ell }_0)$ ;
• un pion a disparu en $(k_0+1,{\ell }_0)$ ;
• un pion est apparu en $(k_0+2,{\ell }_0)$.

Finalement,

On laisse le lecteur vérifier qu’il en est de même lors du mouvement d’un pion vers la gauche, le haut ou le bas. Finalement, la classe de congruence modulo 2 de $A(S)$ et $B(S)$ reste la même tout au long d’une partie.

Positions finales gagnantes possibles

Notons $P$ l’ensemble des emplacements des trous et $S$ la configuration initiale, c’est-à-dire l’ensemble des positions initiales des pions. Si le joueur a gagné, il ne reste plus qu’un pion sur le plateau en une certaine position $(k,\ell )\in P$. D’après ce qui précéde, cette position finale doit vérifier $A(\{(k,\ell )\})\equiv A(S)[2]$ et $B(\{(k,\ell )\})\equiv B(S)[2]$. On constate alors qu’il existe assez peu de positions finales possibles.

A l’aide de Python

On peut tout d’abord employer Python pour tester tous les emplacements des trous.

def possible(S, P):
    def mod(t): return t[0] % 2, t[1] % 2
    A0 = mod(A(S))
    B0 = mod(B(S))
    return [(k, l) for k, l in P
        if mod(A([(k, l)])) == A0 and mod(B([(k, l)])) == B0]

Solitaire anglais

S = [(k, l) for k in range(-3, 4) for l in range(-3, 4)
     if (abs(k) <= 1 or abs(l) <= 1) and (k, l) != (0, 0)]
P = S + [(0, 0)]

print(possible(S, P))

Les positions gagnantes finales possibles sont $(-3,0),(0,-3),(0,3),(3,0),(0,0)$.

Solitaire français

S = [(k, l) for k in range(-3, 4) for l in range(-3, 4)
     if (abs(k) + abs(l) <= 4) and (k, l) != (0, 1)]
P = S + [(0, 1)]

print(possible(S, P))

Les positions gagnantes finales possibles sont $(-3,-1),(0,-1),(0,2),(3,-1)$.

A la main

On peut également déterminer les positions gagnantes finales possibles “à la main”.

Pour calculer les valeurs de $A$ et $B$ pour la configuration initiale, on peut remarquer que trois pions consécutifs disposés horizontalement ou verticalement ont une contribution nulle aux sommes définissant $A$ et $B$ puisque $1+j+j^2=0$.

Solitaire anglais

En utilisant cette dernière remarque, on calcule aisément $A(S)=B(S)=-1\equiv 1[2]$.

Une éventuelle position finale gagnante $(k,\ell )\in P$ doit donc vérifier $j^{k+\ell }\equiv 1[2]$ et $j^{k-\ell }\equiv 1[2]$. Or on rappelle que

• si $n\equiv 0[3]$, $j^n=1\equiv 1[2]$ ;
• si $n\equiv 1[3]$, $j^n=j\not\equiv 1[2]$ ;
• si $n\equiv 2[3]$, $j^n=j^2=-1-j\not\equiv 1[2]$.

On en déduit que $k+\ell \equiv 0[3]$ et $k-\ell \equiv 0[3]$, puis que $2k\equiv 0[3]$ et $2\ell \equiv 0[3]$ et enfin que $k\equiv 0[3]$ et $\ell \equiv 0[3]$. Mais, puisque $(k,\ell )\in P$, les seules possibilités sont $(-3,0),(0,-3),(0,3),(3,0),(0,0)$.

Solitaire français

Comme précédemment, on calcule facilement $A(S)=1-j\equiv 1+j[2]$ et $B(S)=2+j\equiv j[2]$ et on rappelle à nouveau que

• si $n\equiv 0[3]$, $j^n=1\equiv 1[2]$ ;
• si $n\equiv 1[3]$, $j^n=j\equiv j[2]$ ;
• si $n\equiv 2[3]$, $j^n=j^2=-1-j\equiv 1+j[2]$.

Une éventuelle position finale gagnante $(k,\ell )\in P$ doit donc vérifier $k+\ell \equiv 2[3]$ et $k-\ell \equiv 1[3]$. Ainsi $2k\equiv 0[3]$ et $2\ell \equiv 1[3]$. Puisque $2\equiv -1[3]$, $k\equiv 0[3]$ et $\ell \equiv -1[3]$. A nouveau, puisque $(k,\ell )\in P$, les seules possibilités sont $(-3,-1),(0,-1),(0,2),(3,-1)$.

On peut également remarquer que si la position laissée libre initialement, n’est pas la position $(0,1)$ mais la position centrale $(0,0)$, on constate que $A(S)=B(S)=0$. Mais $j^n$ ne peut jamais être congru à $0$ modulo $2$ donc il n’y a aucune possibilité de gagner !