Jouer au Solitaire avec Python et les objets

Exploration de la Partie I du sujet d’Informatique des Mines 2021 option MP
mardi 3 août 2021
par  Sébastien HOARAU

Le sujet d’Informatique du concours Mines et Ponts option MP donné en 2021 et qu’on peut télécharger à cette adresse : https://www.concoursminesponts.fr/r... propose une double étude du jeu du Solitaire.

Après un partie préliminaire pour introduire le jeu du Solitaire et une numérotation du support, une première partie de 17 questions, aborde la résolution via des méthodes de théorie des graphes.

Une deuxième partie de 13 questions s’intéresse à un Solitaire uni-dimensionnel via des méthodes de théorie des automates. Nous ne traiterons pas cette partie ici.

Un corrigé détaillé est proposé par Charignon et disponible au téléchargement :

Préliminaires

Dans cet article, nous allons parcourir les différentes questions notamment celles demandant de la programmation. Nous donnerons la version POO, la version Python fonctionnel et la version OCaml proposée par Charignon.

Commençons par montrer quelques exemples d’appels avec la POO :

Exemples de manipulations

Création d’un tablier européen et affichage

  1. >>> tablier_euro = Europeen()
  2. >>> print(tablier_euro)

Télécharger

6        50 51 52      
5     41 42 43 44 45
4  32 33 34 35 36 37 38
3  24 25 26 27 28 29 30
2  16 17 18 19 20 21 22
1      9 10 11 12 13
0         2  3  4
    0  1  2  3  4  5  6

Création d’un motif vierge sur tablier européen

  1. >>> M0 = Motif(tablier_euro)
  2. >>> print(M0)

Télécharger

6        ○  ○  ○       
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ○  ○  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Remplir l’encoche aux coordonnées 3, 3

  1. >>> M0.switch(3, 3)
  2. >>> print(M0)

Télécharger

6        ○  ○  ○       
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ○  ○  ○  ○
3  ○  ○  ○  ●  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Demander à l’encoche 3, 3 son numéro

  1. >>> M0.encoche(3, 3).num
  2. 27

Télécharger

L’encoche 27 est-elle remplie ?

  1. >>> M0.encoche(27).on()
  2. True

Télécharger

Demander au motif de vider son encoche 27

  1. >>> M0.switch(27)
  2. >>> M0.on(27)
  3. False

Télécharger

Partie I — Tablier et numérotation

Dans ce début de sujet, il est question des différentes formes de tablier ainsi que de la numérotation des encoches. Comme nous le voyons sur les exemples, une encoche est représentée par des coordonnées x, y et un numéro entier fonction des ces coordonnées.

Nous allons donc commencer par créer une classe Tablier, le support de nos Motifs. Nous pourrons créer un tablier européen ou unidimensionnel. Ce qui les différencie : la dimension et la façon de numéroter les encoches.

La classe Tablier va implanter la méthode __str__ qui permettra d’afficher les numéros des encoches.

  1. class Tablier:
  2.  
  3.     def __init__(self, h, w):
  4.         self.h = h
  5.         self.w = w
  6.  
  7.     def __str__(self):
  8.         # nous ne détaillons pas ici, voir le script complet

Télécharger

Les contraintes nous sont données par l’énoncé du sujet. Pour le tablier européen :

Nous numérotons l’encoche de coordonnées (x, y) ∈ ℕ2 dans le tablier européen par l’entier z = 8y + x ∈ ℕ. Nous notons l’ensemble des numéros d’encoches du tablier européen par :

E = 8y + x ; (x, y) ∈ ℕ2 avec 0 ≤ x, y ≤ 6 et |x − 3| + |y − 3| ≤ 4 ⊆ ℕ

Ce qui nous permet de spécialiser notre tablier :

  1. class Europeen(Tablier):
  2.    
  3.     def __init__(self):
  4.         self.size = 7
  5.         Tablier.__init__(self, self.size, self.size)
  6.    
  7.     def coords_to_num(self, x, y):
  8.         return 8*y + x
  9.    
  10.     def num_to_coords(self, num):
  11.         y, x = divmod(num, 8)
  12.         return x, y
  13.  
  14.     def inside(self, x, y):
  15.         return 0 <= x < self.size and 0 <= y < self.size and abs(x - 3) + abs(y - 3) <= 4

Télécharger

Question 2

Python Objet

Il s’agit de pouvoir dire si un entier donné est un numéro possible d’une encoche d’un tablier européen. Cette fonction est réalisée par la combinaison des méthodes num_to_coords et inside :

  1. class Europeen(Tablier):
  2.     # ...
  3.     def numero_interieur(self, z):
  4.         return self.inside(*self.num_to_coords(z))

Télécharger

Rappelons qu’en Python si t est un tuple, *t permet de décompacter t par exemple pour passer ses différentes composantes dans l’appel d’une fonction :

  1. def foo(a, b, c):
  2.     return a**3 + b**3 + c**3
  3.  
  4. t = 1, 2, 3
  5. foo(*t) == 36

Télécharger

Python fonctionnel

  1. def numero_interieur(z):
  2.     y, x = divmod(z, 8)
  3.     return 0 <= x <= 6 and 0 <= y <= 6 and abs(x - 3) + abs(y - 3) <= 4

Télécharger

OCaml

  1. let numero_interieur z =
  2.     let x, y = z mod 8, z / 8 in
  3.     0 <= x && x<= 6
  4.     &&0 <= y && y<= 6
  5.     && abs (x−3) + abs (y−3) <= 4
  6. ;;

Télécharger

Question 3

Python Objet

Obtenir la liste des numéros intérieurs d’un tablier européen. Nous allons commencer par créer une méthode coordonnees qui nous fournira la liste des coordonnées valides d’un tablier européen. Cette liste nous sera utile pour la suite.

Dès lors la liste des numéros valides sont construits à partir de ces coordonnées :

  1. class Europeen(Tablier):
  2.     # ...
  3.     def coordonnees(self):
  4.         return [(x, y) for x in range(self.size) for y in range(self.size) if self.inside(x, y)]
  5.  
  6.     def numeros(self):
  7.         return sorted(self.coords_to_num(x, y) for x, y in self.coordonnees())

Télécharger

A noter que dans cette version, on n’a pas besoin de savoir que les numéros vont jusqu’à 52 : on se contente de parcourir les coordonnées valides et on calcule les numéros qui en découlent.

Python fonctionnel

  1. NUMEROS_EUROPEENS = [n for n in range(53) if numero_interieur(n)]

OCaml

  1. let rec intervalle a b =
  2.     if a>b then [] else a::intervalle (a+1) b
  3. ;;
  4. let numeros_europeens =
  5.     List.filter numero_interieur (intervalle 0 53)
  6. ;;

Télécharger

Question 4

Nous terminons cette partie préliminaire avec une question sur les encoches voisines d’une encoche. En regardant la figure ci-dessous,

on constate que si z est le numéro d’une encoche valide sur un tablier européen alors les quatre voisines, lorsqu’elles existent, sont : z+1 (encoche à droite), z-1 (encoche à gauche), z+8 (encoche au-dessus), z-8 (encoche en-dessous).

Le script complet pour les classes de tablier :

Encoche et Motif

Cette section ne répond pas aux questions du sujet directement mais présente les classes Motif et Encoche pour modéliser le problème et préparer la suite des questions.

Encoche

Une encoche est définie par :

  • un tablier
  • des coordonnées x, y
  • un numéro
  • un état (vide ou plein)

On doit pouvoir créer une encoche en spécifiant ses coordonnées ou son numéro, en précisant obligatoirement un tablier et facultativement son état.
On doit pouvoir remplir ou vider cette encoche.

Le passage des coordonnées au numéro et vice versa va se faire par deux méthodes qui vont s’appuyer sur les méthodes du tablier.

Voici une première définition de la classe Encoche :

  1. class Encoche:
  2.  
  3.     def __init__(self, tablier, *args, etat=VIDE):
  4.         self.tablier = tablier
  5.         if len(args) == 2:
  6.             self.x, self.y = args
  7.             self.num = self.to_num(self.x, self.y)
  8.         else:
  9.             self.num = args[0]
  10.             self.x, self.y = self.to_coords(self.num)
  11.         self.etat = etat
  12.    
  13.     def to_num(self, x, y):
  14.         return self.tablier.coords_to_num(x, y)
  15.    
  16.     def to_coords(self, num):
  17.         return self.tablier.num_to_coords(num)
  18.    
  19.     def switch(self):
  20.         self.etat = 1 - self.etat

Télécharger

Pour ce qui est de l’affichage, une encoche va se présenter sous la forme d’un jeton plein (●) ou vide (○).

On se donne une constante :

JETONS = ’○’, ’●’

Et une méthode :

  1. class Encoche:
  2.     # ...
  3.     def jeton(self):
  4.         return JETONS[self.etat]

Télécharger

Motif

Un motif est un ensemble d’encoches sur un certain tablier. On doit pouvoir créer un motif :

  • vierge (toutes les encoches sont vides) : M0 = Motif(euro)
  • copie d’un motif existant : M0bis = Motif(euro, M0)
  • en spécifiant une liste d’encoches à remplir, par leurs coordonnées ou leur numéro :  M1 = Motif(euro, [12, (2, 3), (6, 2), 52]

Début de notre classe Motif :

  1. class Motif:
  2.    
  3.     def __init__(self, tablier, motif=None):
  4.         self.tablier = tablier
  5.         if isinstance(motif, Motif):
  6.             self.encoches = {(x, y):Encoche(tablier, x, y, etat=motif.encoche(x, y).etat) for x, y in motif.encoches}
  7.         else:
  8.             coordonnees = self.tablier.coordonnees()
  9.             self.encoches = {(x, y):Encoche(tablier, x, y, etat=VIDE) for x, y in coordonnees}
  10.             if motif is not None:
  11.                 for encoche_id in motif:
  12.                     if isinstance(encoche_id, int):
  13.                         encoche_id = (encoche_id, )
  14.                     self.encoche(*encoche_id).etat = PLEIN

Télécharger

Un motif possède donc un attribut encoches qui est un dictionnaire dont les clés sont des coordonnées valides pour le tablier du motif et les valeurs associées des encoches.

Lors de la création, si le deuxième paramètre est manquant, on considère qu’il faut créer un motif vierge. Sinon, soit il s’agit d’un motif et on en fait alors une copie, soit il s’agit d’une liste de coordonnées et de numéros qui correspondent aux encoches à remplir.

Avant de continuer et de répondre aux questions du sujet, notez que l’affichage se fait par une méthode __str__ similaire à celle du tablier mais on remplaçant le numéro par le jeton de l’encoche :

  1. class Motif:
  2.     # ...
  3.     def __str__(self):
  4.         s = ''
  5.         w, h = self.tablier.w, self.tablier.h
  6.         width = len(str(self.to_num(w, h)))
  7.         for y in range(h-1, -1, -1):
  8.             s += f'{y} '
  9.             for x in range(w):
  10.                 if self.inside(x, y):
  11.                     s += f' {self.encoche(x, y).jeton():2}'
  12.                 else:
  13.                     s += '   '
  14.             s += '\n'
  15.         s += f"  {' '.join(f'{x:{width}}' for x in range(w))}"
  16.         return s

Télécharger

Exemple

Le motif présenté en section 1.2 Motifs du sujet pourrait se créer comme ceci :

  1. >>> M0 = Motif(euro, [17, 18, 20, 29])
  2. >>> print(M0)

Télécharger

6         ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ○  ○  ○  ○
3  ○  ○  ○  ○  ○  ●  ○
2  ○  ●  ●  ○  ●  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Partie I — Q5 à 10 : des puissances de 2 pour coder un motif

Dans la suite, on encode un motif par un entier m qui est la somme de puissances de 2 par les numéros des encoches présentes dans le motif.

On peut alors rajouter une méthode encode à notre objet Encoche qui retourne la valeur 2num qui se calcule aussi en décalant de num position vers la gauche l’entier 1 :

  1. class Encoche:
  2.     # ...
  3.     def encode(self):
  4.         return 1 << self.num

Télécharger

On peut donc ajouter une méthode num à un motif, qui retourne la somme des encodages des encoches pleines :

  1. class Motif:
  2.     # ...
  3.     def num(self):
  4.         return sum(encoche.encode() for encoche in self.encoches.values() if encoche.on())

Télécharger

L’exemple du sujet, section 1.2

  1. >>> M0 = Motif(euro, [17, 18, 20, 29])
  2. >>> M0.num()
  3. 538312704
  4. >>> print(M0)

Télécharger

6        ○  ○  ○       
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ○  ○  ○  ○
3  ○  ○  ○  ○  ○  ●  ○
2  ○  ●  ●  ○  ●  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Dans la suite, le sujet parle d’un type motif qui sera un entier (notre num) et d’un type ponctuel qui est un motif à une seule encoche.

Question 5

Elle demande d’écrire une fonction qui, pour un entier donné z numéro valide d’une encoche, retourne le motif ponctuel associé. Il s’agit simplement pour nous de construire un motif comme ceci :

Python Objet

  1. >>> ponctuel = Motif(euro, [z])

Python fonctionnel

  1. def numero_vers_ponctuel(z):
  2.     return 1 << z

Télécharger

OCaml

  1. let numero_vers_ponctuel z : ponctuel =
  2.     1 lsl z;;

Télécharger

Question 6

Il s’agit cette fois de construire un motif de plusieurs encoches pleines :

Python Objet

  1. >>> motif = Motif(euro, [z0, ... zn])

Python fonctionnel

  1. def numeros_vers_motif(l):
  2.     return sum(1 << z for z in l)

Télécharger

OCaml

  1. let numeros_vers_motifs l : motif =
  2.     List.fold_left
  3.     (lor)
  4.     0
  5.     (List.map numero_vers_ponctuel l)
  6. ;;

Télécharger

Question 7

Python Objet

  1. >>> motif_europeen = Motif(euro, euro.numeros())
  2. >>> motif_europeen.num()
  3. 7950016668712476
  4. >>> print(motif_europeen)

Télécharger

6        ●  ●  ●       
5     ●  ●  ●  ●  ●
4  ●  ●  ●  ●  ●  ●  ●
3  ●  ●  ●  ●  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6

Python fonctionnel

  1. >>> MOTIF_EUROPEEN = numeros_vers_motif(NUMEROS_EUROPEENS)
  2. >>> MOTIF_EUROPEEN
  3. 7950016668712476

Télécharger

OCaml

  1. let motif_europeen = numeros_vers_motifs numeros_europeens;;

Question 8

Le sujet demande de prouver la correction d’une fonction booléenne est_ponctuel qui retourne True ssi le motif passé en argument est ponctuel.

Python Objet

  1. class Motif:
  2.     # ...
  3.     def est_ponctuel(self):
  4.         m = self.num()
  5.         return m > 0 and m & m-1 == 0

Télécharger

Python fonctionnel

  1. def est_ponctuel(m):
  2.     return m > 0 and m & m-1 == 0

Télécharger

OCaml

  1. let est_ponctuel (m:motif) : bool =
  2.     (m>0) && ((m land (m−1)) = 0) ;;

Télécharger

Correction

m s’écrit en binaire : b52...b0. Chaque bi vaut 0 si i n’est pas un entier de NUMEROS_EUROPEENS et 0 ou 1 fonction de l’appartenance de i au motif encodé par m.

Si m est ponctuel alors m est non nul (puisque 0 n’est pas un numéro valide) la situation est :

positions :        j
m binaire :   0..0 1 0..0
m-1 binaire : 0..0 0 1..1
m & m-1 :     0..0 0 0..0

Réciproquement supposons que m > 0 et m & m-1 = 0. Si m > 0 alors m possède au moins un 1. Supposons qu’il en possède un 2e, on a donc une situation comme celle-ci (j > k) :

positions :        k      j
m binaire :   .... 1 0..0 1 0..0
m-1 binaire : .... 1 0..0 0 1..1
m & m-1 :     .... 1 0..0 0 0..0

On constate que m & m-1 ne vaut pas 0, ce qui contredit l’hypothèse. Donc m possède un et un seul 1 ; il est donc ponctuel.

Ceci prouve la correction de la fonction est_ponctuel.

Question 9

La question porte sur l’écriture d’une fonction inclus qui prend en paramètre un motif m et un ponctuel p et qui retourne True ssi le ponctuel p est inclus dans m. On demande aussi une preuve de correction de la fonction.

Python Objet

En POO deux solutions s’offrent à nous :

  • Définir un opérateur > (greater than en anglais d’où le nom de l’opérateur __gt__) pour les motifs :
    1. class Motif:
    2.     # ...
    3.     def __gt__(self, p):
    4.         num = p.num()
    5.         return self.num() & num == num

    Télécharger

  • Définir une méthode inclus :
    1. class Motif:
    2.     # ...
    3.     def inclus(self, p):
    4.         num = p.num()
    5.         return self.num() & num == num

    Télécharger

Notons que cette fonction prend n’importe quel motif en paramètre, pas uniquement un ponctuel :

  1. >>> M = Motif(euro, [(3,5), (1, 1)])
  2. >>> print(M)

Télécharger

6        ○  ○  ○       
5     ○  ○  ●  ○  ○
4  ○  ○  ○  ○  ○  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ●  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6
  1. >>> M2 = Motif(euro, M)
  2. >>> M2.switch(38)
  3. >>> print(M2)

Télécharger

6        ○  ○  ○
5     ○  ○  ●  ○  ○
4  ○  ○  ○  ○  ○  ○  ●
3  ○  ○  ○  ○  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ●  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6
  1. >>> M2 > M
  2. True
  3. >>> M2.inclus(M)
  4. True

Télécharger

Python fonctionnel

  1. def inclus(m, p):
  2.     return m & p == p

Télécharger

OCaml

Dans le corrigé de Charignon il est donné :

  1. let inclus (m:motif) (p:ponctuel) : bool =
  2.     m land p <> 0
  3. ;;

Télécharger

qui ne fonctionne que pour un ponctuel effectivement.

Correction

La preuve de correction est simple, le et bit à bit de deux séries de bits ne va garder des 1 qu’aux positions communes. Si l’un des motifs contient toutes les positions d’un autre alors le et ne va garder que celles là et donc être égal au plus petit des deux motifs.

Question 10

Il est temps de s’intéresser aux coups pour réaliser une partie c’est à dire passer d’un motif à un autre. Le but du jeu étant, en général de partir d’un motif initial pour atteindre un motif final (en un minimum de coups).

Cette question demande d’écrire une fonction qui, à partir d’un ponctuel p (qui, rappelons le, dans le sujet initial est un entier de la forme 2i où i est un numéro intérieur valide d’encoche) calcule le ponctuel obtenu par translation à gauche de l’encoche initiale. La fonction retourne 0 si jamais la translation fait sortir du tablier.

Dans le cas de la modélisation fonctionnelle (en Python comme en OCaml), la fonction voisin_g va se servir de la réponse à la question 4 (le voisin de gauche du numéro z vaut z-1) et du fait que passer de 2z à 2z-1 revient à faire un décalage à droite de 1.

La validité du voisin est réalisée par le test d’inclusion au motif plein.

Python fonctionnel

  1. def voisin_g(p):
  2.     g = p >> 1
  3.     return g if inclus(MOTIF_EUROPEEN, g) else 0

Télécharger

OCaml

  1. let valide (p:ponctuel) =
  2.     inclus motif_europeen p;;
  3.  
  4. let voisin_g (p:ponctuel) : ponctuel =
  5.     let res = p lsr 1 in
  6.     if valide res then res
  7.     else 0
  8. ;;

Télécharger

Python Objet

Pour cette question, la modélisation diverge de la modélisation fonctionnelle. En effet, ici il ne s’agit pas de retourner juste le numéro mais bien un objet Motif.

Le calcul d’un motif voisin va passer par le système de coordonnées. On commence par définir une constante :

  1. DIRECTIONS = {'N':(0,1), 'S':(0,-1), 'E':(1,0), 'W':(-1,0)}

On peut alors définir une méthode générique voisin qui prend une direction en paramètre et une identification d’encoche ie des coordonnées ou un numéro. Si la translation dans la direction donnée est valide alors on retourne le nouveau motif sinon on retourne None :

  1. class Motif:
  2.     #...
  3.     def voisin(self, direction, *args):
  4.         new_motif = None
  5.         direction = direction.upper()
  6.         if direction in DIRECTIONS:
  7.             x, y = args if len(args) == 2 else self.to_coords(args[0])
  8.             dx, dy = DIRECTIONS[direction]
  9.             nx, ny = x+dx, y+dy
  10.             if self.on(x, y) and self.off(nx, ny):
  11.                 new_motif = Motif(self.tablier, self)
  12.                 new_motif.switch(x, y)
  13.                 new_motif.switch(nx, ny)
  14.         return new_motif

Télécharger

Les méthodes on et off intégrent un test de validité :

  1. class Motif:
  2.     #...
  3.     def inside(self, *args):
  4.         x, y = args if len(args) == 2 else self.to_coords(args[0])
  5.         return self.tablier.inside(x, y)
  6.  
  7.     def on(self, *args):
  8.         return self.inside(*args) and self.encoche(*args).on()
  9.  
  10.     def off(self, *args):
  11.         return self.inside(*args) and self.encoche(*args).off()

Télécharger

Exemple d’utilisation de voisin

  1. >>> M = Motif(euro, [(3,5), (1, 1)])
  2. >>> print(M)

Télécharger

6        ○  ○  ○       
5     ○  ○  ●  ○  ○
4  ○  ○  ○  ○  ○  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ●  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6
  1. >>> M2 = M.voisin('E', 1, 1)
  2. >>> print(M2)

Télécharger

6        ○  ○  ○       
5     ○  ○  ●  ○  ○
4  ○  ○  ○  ○  ○  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ●  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6
  1. >>> M3 = M2.voisin('N', 10)
  2. >>> print(M3)

Télécharger

6        ○  ○  ○
5     ○  ○  ●  ○  ○
4  ○  ○  ○  ○  ○  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ○  ○  ●  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Partie I — Q11 à 13 : coups simples et composés

Question 11

On cherche, à partir d’un motif m et d’un ponctuel p de ce motif, la liste des motifs atteignables ie les couples m’, p’ où p’ est la translation dans une des directions possibles du voisin de p dans cette direction et m’ le motif m privé de p mais auquel on a ajouté p’.

Dans sa modélisation fonctionnelle, l’algorithme du coup simple est le suivant :

  • le ponctuel de départ doit faire partie du motif (sinon c’est qu’il n’y a pas de fiche et on ne peut donc pas faire de coups)
  • on va calculer 2 étapes de voisins dans chacune des 4 directions
  • un coup est effectif si aucun des voisins est nul (on ne sort pas du tablier) et si le premier voisin est inclus dans le motif (la fiche qu’on saute) et le second voisin ne l’est pas (emplacement libre)
  • dès lors le nouveau motif est obtenu en :
    • supprimant le ponctuel de départ (par un ou exclusif entre le ponctuel et le motif) : on enlève la fiche de départ
    • supprimant le ponctuel correspondant au premier voisin : la fiche qu’on saute disparaît
    • ajoutant le ponctuel du second voisin (par un ou normal) : la fiche vient dans la nouvelle encoche

Python fonctionnel

  1. def coup_simple(m, p):
  2.     coups = []
  3.     if inclus(m, p):
  4.         for voisin in (voisin_g, voisin_d, voisin_h, voisin_b):
  5.             v = voisin(p)
  6.             vv = voisin(v)
  7.             if v and vv and inclus(m, v) and not inclus(m, vv):
  8.                 coups.append((((m ^ p) ^ v) | vv, vv))
  9.     return coups

Télécharger

OCaml

  1. let coup_simple ((m,p) : motif∗ponctuel) =
  2.  
  3.     let coup voisin =
  4.     (∗ Entrée : voisin, une des quatre fonctions voisin_g, voisin_d, voisin_h, voisin_b.
  5.     Sortie : liste [ (m', p')] si le coup est possible, [] sinon ∗)
  6.     let case_suivante = voisin p in
  7.     let case_dapres = voisin case_suivante in
  8.     if (inclus m case_suivante) && not (inclus m case_dapres) && case_dapres<>0 then [m−p−case_suivante+case_dapres, case_dapres]
  9.     else []
  10.     in
  11.     List.flatten (List.map coup [voisin_g; voisin_d; voisin_h; voisin_b] )
  12. ;;

Télécharger

Python Objet

Comme nous l’avons déjà dit à la question précédente, la modélisation objet diverge. Le principe du coup simple reste le même (construire la liste des motifs atteignables en jouant un coup depuis une encoche pleine vers chacune des directions possibles parmi Nord, Sud, Est, Ouest) :

En réalité, dans la version objet, la fonction voisin de la question précédente n’est pas très utile. Ce qu’il nous faut c’est une fonction qui effectue un coup dans une direction, à partir des coordonnées d’une encoche pleine. La fonction retourne un couple : motif, arrivee ou motif est soit None si le coup n’est pas possible soit le motif résultant du coup joué et arrivee est le couple de coordonnées de l’encoche d’arrivée.

Nous appelons simple cette méthode :

  1. class Motif:
  2.     # ...
  3.     def simple(self, direction, x, y):
  4.         motif = None
  5.         dx, dy = DIRECTIONS[direction]
  6.         voisin = x+dx, y+dy
  7.         arrivee = x+2*dx, y+2*dy
  8.         if self.on(*voisin) and self.off(*arrivee):            
  9.             motif = Motif(self.tablier, self)
  10.             motif.switch(x, y)
  11.             motif.switch(*voisin)
  12.             motif.switch(*arrivee)
  13.         return motif, arrivee

Télécharger

La méthode coup_simple va alors créer la liste des tous les motifs résultats des coups valides dans chacune des directions :

  1. class Motif:
  2.     # ...
  3.     def coup_simple(self, *args):
  4.         coups = []
  5.         if self.on(*args):
  6.             x, y = self.to_coords(*args)
  7.             for direction in DIRECTIONS:
  8.                 motif, arrivee = self.simple(direction, x, y)
  9.                 if motif is not None:
  10.                     coups.append((motif, arrivee))
  11.         return coups

Télécharger

Exemple d’application

  1. >>> M = Motif(euro, [28, 29, 37, 30])
  2. >>> print(M)

Télécharger

6        ○  ○  ○       
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ○  ○  ●  ○
3  ○  ○  ○  ○  ●  ●  ●
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6
  1. >>> coups = M.coup_simple(29)
  2. >>> print(coups[0][0])

Télécharger

6        ○  ○  ○
5     ○  ○  ○  ○  ●
4  ○  ○  ○  ○  ○  ○  ○
3  ○  ○  ○  ○  ●  ○  ●
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6
  1. >>> print(coups[1][0])
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ○  ○  ●  ○
3  ○  ○  ○  ●  ○  ○  ●
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Question 12

Cette question est l’extension de la précédente à une succession de déplacements simples. Partant d’un motif initial et d’un ponctuel (l’encoche qu’on souhaite faire bouger) on va mettre dans une file les motifs créés par coups simples à partir des motifs et des encoches arrivées retirés de la file.

Il s’agit donc d’un parcours en largeur des motifs accessibles depuis le motif initial. La version OCaml est récursive, la version Python itérative.

Python fonctionnel

  1. def coup_compose(m, p):
  2.     coups = []
  3.     if inclus(m, p):
  4.         a_traiter = coup_simple(m, p)
  5.         while a_traiter:
  6.             coup = a_traiter.pop(0)
  7.             coups.append(coup)
  8.             for voisin in coup_simple(*coup):
  9.                 if voisin not in a_traiter and voisin not in coups:
  10.                     a_traiter.append(voisin)        
  11.     return coups

Télécharger

OCaml

  1. let coup_compose (c:motif∗ponctuel) =
  2.  
  3.     let rec aux l =
  4.     if l=[] then []
  5.     else
  6.     let nv_couples = List.flatten (List.map coup_simple l) in
  7.     nv_couples @ aux nv_couples
  8.  
  9.     in
  10.     aux [c]
  11. ;;

Télécharger

Python Objet

  1. class Motif:
  2.     # ...
  3.     def coup_compose(self, *args):
  4.         coups = []
  5.         if self.on(*args):
  6.             a_traiter = self.coup_simple(*args)
  7.             while a_traiter:
  8.                 coup, arrivee = a_traiter.pop(0)
  9.                 coups.append((coup, arrivee))
  10.                 for voisin in coup.coup_simple(*arrivee):
  11.                     if voisin not in a_traiter and voisin not in coups:
  12.                         a_traiter.append(voisin)        
  13.         return coups

Télécharger

Exemple

  1. >>> M = Motif(euro, [17, 18, 20, 29, 36, 27])
  2. >>> print(M)

Télécharger

6        ○  ○  ○       
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ○  ●  ○  ○
3  ○  ○  ○  ●  ○  ●  ○
2  ○  ●  ●  ○  ●  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Notons, qu’on aura 2 configurations avec arrivée en 3,4 et 2 configurations avec arrivée en 5,4.

  1. >>> coups = M.coup_compose(17)
  2. >>> coups
  3. [(<__main__.Motif at 0x25ba11c4160>, (3, 2)),
  4.  (<__main__.Motif at 0x25ba11c4730>, (3, 4)),
  5.  (<__main__.Motif at 0x25ba124a100>, (5, 2)),
  6.  (<__main__.Motif at 0x25ba12645b0>, (5, 4)),
  7.  (<__main__.Motif at 0x25ba1193f10>, (5, 4)),
  8.  (<__main__.Motif at 0x25ba1195d00>, (5, 2)),
  9.  (<__main__.Motif at 0x25ba1196430>, (3, 4)),
  10.  (<__main__.Motif at 0x25ba11c4700>, (3, 2))]

Télécharger

Voici les deux motifs dont l’arrivée est 3, 4 :

6        ○  ○  ○       
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ●  ●  ○  ○
3  ○  ○  ○  ○  ○  ●  ○
2  ○  ○  ○  ○  ●  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6
6        ○  ○  ○       
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ●  ○  ○  ○
3  ○  ○  ○  ●  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Question 13

Obtenir tous les coups jouables à partir d’un motif, en jouant n’importe quel fichet jouable. Les trois versions sont semblables :

Python Objet

  1. class Motif:
  2.     # ...
  3.     def mouvements(self):
  4.         return [m1 for (x, y) in self.encoches for (m1, _) in self.coup_compose(x, y)]

Télécharger

Python fonctionnel

  1. def mouvements(m):
  2.     return [m1 for p in [numero_vers_ponctuel(z) for z in NUMEROS_EUROPEENS] for (m1, _) in coup_compose(m, p)]

Télécharger

OCaml

  1. let mouvements (m:motif) : motif list =
  2.  
  3.     let rec aux (p:ponctuel) =
  4.     if p = 1 lsl 53 then []
  5.     else (if inclus m p then coup_compose (m,p) else [] )
  6.     @ aux (2∗p)
  7.     in
  8.     List.map fst (aux 4)
  9. ;;

Télécharger

Partie I — Q14 à 17 : partie de longueur minimale

Dans cette partie, la programmation OCaml ne sera plus fonctionnelle pure puisqu’une structure dictionnaire avec modification en place sera utilisée.

Le but des quatre dernières questions de cette première partie est de pouvoir calculer le nombre de coups minimum pour passer d’une configuration initiale mi à une configuration finale mf.

Nouvel Objet : Solitaire

Pour la version Python Objet, puisqu’on parle de partie, nous introduisons un nouvel objet Solitaire qui modélise une partie de solitaire sur tablier européen.

L’objet embarque donc un tablier, un motif initial, un motif final et une liste des motifs qui est la résolution du problème c’est-à-dire la succession de motifs partant du motif initial pour aller jusqu’au motif final en appliquant une série de coups simples.

La constante VIDE_43 représente l’ensemble de tous les numéros intérieurs sauf le 43 et PLEIN_35 représente le singleton {35}. La vidéo suivante : https://www.youtube.com/watch?v=5X2... montre qu’il existe une solution pour une configuration initiale avec un trou en 43 et une configuration d’arrivée avec un unique fichet en 35.

  1. class Solitaire:
  2.  
  3.     def __init__(self, initial=VIDE_43, final=PLEIN_35):
  4.         self.tablier = tb.Europeen()
  5.         self.initial = Motif(self.tablier, initial)
  6.         self.final = Motif(self.tablier, final)
  7.         self.current_id = 0
  8.         self.partie = [self.initial]
  9.    
  10.     def __str__(self):
  11.         return self.partie[self.current_id].__str__()
  12.  
  13.     def goal(self):
  14.         print(self.final)

Télécharger

  1. >>> jeu = Solitaire()
  2. >>> print(jeu)

Télécharger

6        ●  ●  ●
5     ●  ●  ○  ●  ●
4  ●  ●  ●  ●  ●  ●  ●
3  ●  ●  ●  ●  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
  1. >>> jeu.goal()
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ●  ○  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Question 14

Mémoriser une entrée dans un dictionnaire, si cette dernière n’est pas encore présente et retourner True si le dictionnaire a été modifié. Nous présentons la méthode ajoutée à la classe Solitaire : la version Python fonctionnel n’est plus vraiment fonctionnel et identique.

Python Objet

Notons qu’on objet Motif ne peut pas être clé d’un dictionnaire : on y mettra donc son code binaire comme calculé par la méthode num() introduite au début de la section précédente.

  1. class Solitaire:
  2.     # ...
  3.     def add_and_mem(self, dico, motif, s):
  4.         num = motif.num()
  5.         if num not in dico:
  6.             dico[num] = s
  7.             return True
  8.         return False

Télécharger

OCaml

  1. let ajoute_et_pas_mem (d: dico) (s:int) (m:motif) =
  2.     let dedans = Hashtbl.mem d m in
  3.     if not dedans then Hashtbl.add d m s ;
  4.     dedans
  5. ;;

Télécharger

Question 15

Il s’agit d’associer à un motif sa distance minimale au motif initial. Le principe est simple : si s est associé au motif m alors s+1 sera associé à tous les motifs atteignables depuis m par un coup composé (les motifs appartenant donc à m.mouvements()).

Python Objet

  1. class Solitaire:
  2.     # ...
  3.     def strate(self, dico, s, motifs):
  4.         ajoutes = []
  5.         for m in motifs:
  6.             for new_m in m.mouvements():
  7.                 if self.add_and_mem(dico, new_m, s):
  8.                     ajoutes.append(new_m)
  9.         return ajoutes

Télécharger

On peut, si on est à l’aise utiliser la version en compréhension :

  1. class Solitaire:
  2.     # ...
  3.     def strate(self, dico, s, motifs):
  4.         return [new_m for m in motifs for new_m in m.mouvements() if self.add_and_mem(dico, new_m, s)]

Télécharger

OCaml

  1. let strate (d:dico) s (l:motif list) =
  2.     let nv_motifs = List.flatten (List.map mouvements l) in
  3.  
  4.     let rec aux = function
  5.     | []> []
  6.     | m::suite when Hashtbl.mem d m −> aux suite
  7.     | m::suite −> Hashtbl.add d m s; m :: aux suite
  8.     in
  9.     aux nv_motifs
  10. ;;

Télécharger

Question 16

On arrive à la fonction ultime : celle qui va parcourir le graphe des configurations jusqu’à atteindre la configuration finale. Dans la version objet les deux configurations sont des propriétés de notre objet Solitaire, la méthode partie minimale n’a donc pas d’autre paramètre.

Python Objet

Si on applique l’hypothèse du sujet, on peut se passer du try.

  1. class Solitaire:
  2.     # ...
  3.     def minimale(self):
  4.         d_resultat = {}
  5.         d_a_traiter = {self.initial.num():0}
  6.         file_a_traiter = [self.initial]
  7.         num_final = self.final.num()
  8.         while num_final not in d_resultat and file_a_traiter:
  9.             m = file_a_traiter.pop(0)
  10.             num = m.num()
  11.             s = d_a_traiter.pop(num)
  12.             if num not in d_resultat:
  13.                 d_resultat[num] = s
  14.             file_a_traiter.extend(self.strate(d_a_traiter, s+1, [m]))
  15.         try:
  16.             return d_resultat[num_final]
  17.         except:
  18.             KeyError('Motif final inatteignable')

Télécharger

OCaml

  1. let partie_minimale mi mf =
  2.     let d = Hashtbl.create 42 in
  3.     Hashtbl.add d mi 0 ;
  4.  
  5.     let rec aux sphere dist =
  6.     (∗ sphere : ensemble des motifs à distance dist de mi.)
  7.     if Hashtbl.mem d mf then Hashtbl.find d mf
  8.     else if sphere = [] then failwith "motif final non accessible"
  9.     else
  10.     let sphere_suivante = strate d (dist+1) sphere in
  11.     aux sphere_suivante (dist+1)
  12.     in
  13.     aux [mi] 0
  14. ;;

Télécharger

Question 17

Telle quelle, non la fonction partie_minimale de l’énoncé ne répond pas à la question 1 : en effet rien n’est précisé sur la façon dont on ajoute les motifs dans la fonction strate. Hors, il est primordial de gérer les motifs par une file, ce qui est fait dans nos versions (on ajoute en fin de liste par un extend dans strate et on retire en tête par un pop(0)).

On considère la graphe dont les sommets sont les motifs et il y a un arc orienté d’un motif m1 vers un motif m2 si m2 ∈ m1.mouvements().

Voici un exemple :
Mi est la configuration initiale qui donne M0, M1, plus deux autres qui sont identiques par transposition et que nous n’avons pas représentées pour simplifier.

Puis de M0 on atteint M2 et de M1 on atteint Mf la configuration finale. On constate donc qu’un parcours de ce graphe qui ne serait pas en largeur risque de passer par M2 pour atteindre Mf et dès lors associer la distance 3. La distance minimale étant 2, en passant par M1.

                                    Mi
                                  ○ ○ ○       
                                ● ● ○ ○ ○
                              ○ ● ● ○ ○ ○ ○
                              ○ ○ ○ ○ ○ ○ ○
                              ○ ○ ○ ○ ○ ○ ○
                                ○ ○ ○ ○ ○
                                  ○ ○ ○
                            /              \
                        M0                     M1
                      ○ ○ ○                  ○ ○ ○       
                    ○ ● ○ ○ ○              ● ○ ○ ○ ○
                  ○ ○ ● ○ ○ ○ ○          ○ ● ○ ○ ○ ○ ○
                  ○ ● ○ ○ ○ ○ ○          ○ ○ ● ○ ○ ○ ○      ...
                  ○ ○ ○ ○ ○ ○ ○          ○ ○ ○ ○ ○ ○ ○
                    ○ ○ ○ ○ ○              ○ ○ ○ ○ ○
                      ○ ○ ○                  ○ ○ ○
                        |                      |
                        M2                     Mf
                      ○ ○ ○                  ○ ○ ○       
                    ○ ○ ○ ○ ○              ○ ○ ○ ○ ○
                  ○ ○ ○ ○ ○ ○ ○          ○ ○ ○ ○ ○ ○ ○
                  ○ ● ● ○ ○ ○ ○    ->    ○ ○ ○ ● ○ ○ ○      ...
                  ○ ○ ○ ○ ○ ○ ○          ○ ○ ○ ○ ○ ○ ○
                    ○ ○ ○ ○ ○              ○ ○ ○ ○ ○
                      ○ ○ ○                  ○ ○ ○

Conclusion et Références

Ce sujet bien construit autour du jeu du solitaire était intéressant. A noter que le jeu est très fortement combinatoire et il ne faut pas espérer pouvoir trouver le nombre de coups pour passer d’une vraie configuration initiale (en général où le tablier est complètement plein à part 1 encoche) vers une configuration finale constituée d’un unique fichet.

D’après Wikipédia :

Bien que le but affiché du jeu soit en général de démarrer avec un trou au centre du plateau pour finir avec un unique pion à la même place, cet objectif est impossible à atteindre avec le plateau européen. Hans Zantema en a fait une démonstration élégante qui tient en quelques lignes, basée sur la numérotation suivante du plateau de jeu avec les lettres A, B et C (une lettre par diagonale, en alternant les lettres) :

     A B C
   A B C A B
 A B C A B C A
 B C A B C A B
 C A B C A B C
   B C A B C
     A B C

Si on commence avec un trou au centre du plateau, alors il y a au début du jeu 12 positions A, 12 positions B et 12 positions C couvertes par des pions. On peut vérifier également qu’après chaque coup, le nombre de positions A couvertes augmente ou diminue de un, ce qui est vrai aussi pour le nombre de positions B et C. Donc après un nombre de coups pair, il y a un nombre pair de positions A couvertes, et de même pour les positions B et C ; et après un nombre de coups impair, il y a un nombre impair de positions A couvertes, et de même pour les positions B et C. Comme le plateau européen comporte 37 trous, après avoir retiré le pion central il faudrait 35 coups pour arriver à un seul pion, donc le nombre de positions A, B et C couvertes devrait être impair, ce qui impossible avec un seul pion. Le meilleur score atteignable dans cette configuration est de finir avec deux pions sur le plateau.

En fait sur un solitaire à 37 trous, il n’est possible de gagner que si le premier trou est dans l’une des cases marquées d’un X sur le diagramme suivant3 :

     X O X
   O O X O O
 X O O X O O X
 O X X O X X O
 X O O X O O X
   O O X O O
     X O X

Historique

L’origine du jeu du Solitaire reste floue. Il pourrait s’agir d’une évolution à un joueur du jeu médiéval Poules et Renard dont le support rappelle le tablier anglais à 33 trous et dont le système de prise en sautant est similaire.

Des références au jeu apparaissent fin 17e dans la revue Mercure Galante, puis en 1710 dans le premier volume des Mémoires de l’Académie de Berlin par G.W. Leibniz. Edouard Lucas en fait le thème de sa cinquième récréation mathématiques en 1891 (p. 121-173). Il donne plusieurs théorèmes qui prouvent l’impossibilité de terminer avec un unique fichet si on commence avec un unique trou central. A noter la numérotation différente de celle du sujet des Mines :

En 2009 le jeu fait le sujet d’un défi proposé en langage C et C++ par le site developpez.com. Un travail intéressant serait donc de compléter la classe Solitaire pour pouvoir résoudre un problème donné.

Script complet

Le script Python utilisé dans cet article est disponible ici :
Vous pouvez tester :

  1. >>> jeu = Solitaire()
  2. >>> jeu.minimale()

Télécharger

Qui va tenter de trouver le nombre de coups minimal pour passer de :

6        ●  ●  ●
5     ●  ●  ○  ●  ●
4  ●  ●  ●  ●  ●  ●  ●
3  ●  ●  ●  ●  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6

à

6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ●  ○  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

N’attendez pas d’obtenir la solution :). Lors de la résolution, le script affiche le nombre de motifs explorés.

Exemple de solution

Quelques méthodes ont été ajoutées pour pouvoir lire un fichier texte donnant sur la première lignes le numéro du trou pour la configuration initiale et celui de l’unique encoche pleine de la configuration finale puis la suite des mouvements pour y arriver. L’idée était d’avoir la partie décrite dans cette vidéo :

Vous pouvez tester la solution (dès lors la partie sera chargée dans la propriété partie et en faisant jeu.bk() et jeu.fd() vous pourrez naviguer) :

  1. In [1]: %run solitaire
  2. In [2]: jeu = Solitaire()
  3. In [3]: jeu.load('solution.txt')

Télécharger

6        ●  ●  ●       
5     ●  ●  ○  ●  ●    
4  ●  ●  ●  ●  ●  ●  ● 
3  ●  ●  ●  ●  ●  ●  ● 
2  ●  ●  ●  ●  ●  ●  ● 
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
1/1
6        ●  ●  ●
5     ●  ●  ●  ○  ○
4  ●  ●  ●  ●  ●  ●  ●
3  ●  ●  ●  ●  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
2/2
6        ●  ●  ●
5     ●  ○  ○  ●  ○
4  ●  ●  ●  ●  ●  ●  ●
3  ●  ●  ●  ●  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
3/3
6        ●  ●  ●
5     ●  ●  ○  ●  ○
4  ●  ●  ○  ●  ●  ●  ●
3  ●  ●  ○  ●  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
4/4
6        ●  ●  ●
5     ○  ○  ●  ●  ○
4  ●  ●  ○  ●  ●  ●  ●
3  ●  ●  ○  ●  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
5/5
6        ●  ●  ●
5     ○  ●  ○  ○  ○
4  ●  ●  ○  ●  ●  ●  ●
3  ●  ●  ○  ●  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
6/6
6        ○  ●  ●
5     ○  ○  ○  ○  ○
4  ●  ●  ●  ●  ●  ●  ●
3  ●  ●  ○  ●  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
7/7
6        ○  ●  ●
5     ○  ○  ●  ○  ○
4  ●  ●  ●  ○  ●  ●  ●
3  ●  ●  ○  ○  ●  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
8/8
6        ○  ●  ●
5     ○  ○  ●  ●  ○
4  ●  ●  ●  ○  ○  ●  ●
3  ●  ●  ○  ○  ○  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
9/9
6        ○  ○  ●
5     ○  ○  ○  ●  ○
4  ●  ●  ●  ●  ○  ●  ●
3  ●  ●  ○  ○  ○  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
10/10
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ●  ●  ●  ●  ●  ●  ●
3  ●  ●  ○  ○  ○  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
11/11
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ●  ●  ●  ●  ●  ●  ●
3  ●  ●  ●  ○  ○  ●  ●
2  ●  ●  ○  ●  ●  ●  ●
1     ●  ○  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
12/12
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ●  ●  ●  ●  ●  ●  ●
3  ●  ●  ●  ○  ●  ●  ●
2  ●  ●  ○  ●  ○  ●  ●
1     ●  ○  ●  ○  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
13/13
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ●  ●  ○  ●  ●  ●  ●
3  ●  ●  ○  ○  ●  ●  ●
2  ●  ●  ●  ●  ○  ●  ●
1     ●  ○  ●  ○  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
14/14
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ●  ●  ○  ●  ○  ●  ●
3  ●  ●  ○  ○  ○  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ○  ●  ○  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
15/15
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ○  ●  ●
3  ●  ●  ○  ○  ○  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ○  ●  ○  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
16/16
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ●  ●  ○  ○  ○  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ○  ●  ○  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
17/17
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ○  ●  ○  ○  ●  ●
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ○  ●  ○  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
18/18
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ○  ●  ○  ●  ○  ○
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ○  ●  ○  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
19/19
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ○  ○  ○  ●  ○  ○
2  ●  ●  ○  ●  ●  ●  ●
1     ●  ●  ●  ○  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
20/20
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ●  ●  ○  ●  ○  ●  ●
1     ●  ●  ●  ●  ●
0        ●  ●  ●
   0  1  2  3  4  5  6
21/21
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ●  ●  ●  ●  ○  ●  ●
1     ●  ○  ●  ●  ●
0        ○  ●  ●
   0  1  2  3  4  5  6
22/22
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ●  ●  ●  ●  ●  ●  ●
1     ●  ○  ●  ○  ●
0        ○  ●  ○
   0  1  2  3  4  5  6
23/23
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ●  ○  ○  ○  ○  ○
2  ●  ○  ●  ●  ●  ●  ●
1     ○  ○  ●  ○  ●
0        ○  ●  ○
   0  1  2  3  4  5  6
24/24
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ●  ○  ○  ○  ●  ○
2  ●  ○  ●  ●  ●  ○  ●
1     ○  ○  ●  ○  ○
0        ○  ●  ○
   0  1  2  3  4  5  6
25/25
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ●  ○  ○  ○  ●  ○
2  ●  ○  ●  ○  ○  ●  ●
1     ○  ○  ●  ○  ○
0        ○  ●  ○
   0  1  2  3  4  5  6
26/26
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ●  ○  ○  ○  ●  ○
2  ●  ○  ●  ○  ●  ○  ○
1     ○  ○  ●  ○  ○
0        ○  ●  ○
   0  1  2  3  4  5  6
27/27
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ●  ○  ○  ○  ●  ○
2  ●  ●  ○  ○  ●  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6
28/28
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ●  ●  ●  ○  ○
3  ○  ●  ○  ○  ○  ●  ○
2  ○  ○  ●  ○  ●  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6
29/29
6        ○  ○  ○
5     ○  ○  ○  ○  ○
4  ○  ○  ○  ●  ○  ○  ○
3  ○  ○  ○  ○  ○  ○  ○
2  ○  ○  ○  ○  ○  ○  ○
1     ○  ○  ○  ○  ○
0        ○  ○  ○
   0  1  2  3  4  5  6

Une exploration plus profonde avec notamment l’utilisation d’une recherche en faisceau est proposée ici : Exploration du Solitaire


Documents joints

Texte - 183 octets
Zip - 2.7 ko

Commentaires