logo solitaire

Le jeu du Solitaire⚓︎

Introduction⚓︎

Jeu de plateau à un joueur (comme son nom l'indique), son origine est incertaine. Il se joue sur un plateau appelé aussi tablier, le plus souvent en bois mais des versions en pierre existent dans lequel on trouve des trous ou encoches où peuvent venir se nicher des fichets¹. Ces fichets prennent différentes formes : pions, fichets, mais sur les jeux modernes se sont des boules le plus souvent.

Quelques exemples de jeux

exemple1 exemple2 exemple3

But du jeu

Le but du jeu est, partant d'un motif initial c'est-à-dire d'un ensemble d'encoches pleines d'obtenir un motif final en vidant certaines encoches, selon la règle : un pion peut sauter au-dessus d'un pion voisin (au-dessus, au-dessous, à gauche ou à droite) pour arriver dans une encoche vide. Le pion sauté est retiré du plateau.

Il existe différents Solitaire, fonction de la forme du tablier et du nombre d'encoches qu'il possède. En voici quelques uns, les deux plus connus étant le Solitaire Anglais à 33 encoches et le Solitaire Européen à 37 encoches :

Divers tabliers

divers solitaires

européen, XVII^e siècle, 37 trous ;
J. C. Wiegleb, 1779, Allemagne, 45 trous ;
asymétrique 3-3-2-2, xxe siècle ;
anglais, 33 trous ;
diamant, 41 trous ;
triangulaire, 15 trous.

Auteur : Júlio Reis, source : wikimedia

Historique⚓︎

Certains font remonter l'origine du Solitaire à 43 av. J.-C. avec le poète Ovide. Mais :

Ce qu’Ovide évoque, dans L'Art d'aimer (Ars Amatoria) et les Tristes (Tristia), c’est un jeu d’alignement, du type morpion, mérelles ou jeu du moulin.

Source : Wikipédia
Les références médiévales quant à elles parlent d'un autre jeu, de type capture mais à deux joueurs (toujours d'après Wikipédia) :

Les références médiévales (Roman d'Alexandre, vers 1340 ; inventaire du roi d’Angleterre Édouard IV, au xve siècle, où le jeu Fox and Geese n'est jamais que le renard et les poules) désignent des jeux de chasse pour deux joueurs. Le jeu nommé « renard » dans la longue liste des jeux énumérés par Rabelais dans Gargantua (1534) est encore ce même jeu du renard et des poules.

Il s'agit bien d'un jeu de prise en sautant et il se pourrait que le Solitaire soit un dérivé à 1 joueur de ce jeu.

Dame de qualité jouant au Solitaire Gravure²

Fin 17e début 18e, des références au jeu du Solitaire sont trouvées dans la revue Mercure Galant. En 1710 G.W. Leibniz en consacre un paragraphe dans le Volume 1 des Mémoires de l'Académie des Sciences de Berlin. Leibniz joue à une variante de son cru, qu'il décrit dans une lettre adressée à M. de Montmort :

Le jeu nommé le Solitaire m'a plu assez. Je l'ai pris d'une manière renversée, c'est-à-dire qu'au lieu de défaire un composé de pièces selon la loi de ce jeu, qui est de sauter dans une place vide et d'ôter la pièce sur laquelle on saute, j'ai cru qu'il serait beau de rétablir ce qui a été défait, en remplissant un trou sur lequel on saute ; et par ce moyen on pourrait se proposer de former une telle ou telle figure proposée, si elle est faisable [...]
Des études plus mathématiques au 19e et 20e siècle. L'extrait de la lettre de Leibniz est tiré des Récréations Mathématiques, d'Édouard Lucas 1891.

Objectif⚓︎

Cet article a pour objectif d'explorer la recherche de solutions du Solitaire en programmation Python et en utilisant la POO. Il pourra servir de travail préparatoire à un enseignant de Lycée (Terminale NSI ou CPGE) pour la mise au point d'une ou plusieurs activités. Les thèmes abordés sont :

La Programmation Orientée Objet en Python
Graphes, parcours (en largeur et en profondeur), beam search

L'inspiration vient de diverses sources :

Le sujet d'Informatique du concours Mines et Ponts de 2021 option MP et dont le corrigé a été exploré dans cet article : Jouer au Solitaire avec Python et les Objets
Le Défi C et C++ : Recherche de solution du Solitaire proposé par le site developpez.com
La 5^e récréation mathématique d'Édouard Lucas

Les problèmes d'Édouard Lucas⚓︎

Le mathématicien consacre un chapitre entier à l'étude du solitaire européen (37 encoches) qu'il numérote comme ceci :

numérotation E. Lucas

Grâce à Python et à la programmation orientée objet, nous allons modéliser ces problèmes et tenter de les résoudre.

Modéliser les motifs de départ et d'arrivée⚓︎

Dans le Défi C et C++ l'entrée du programme est un fichier texte du genre :

  xxx
  xxx
xxxxxxx
xxx.xxx
xxxxxxx
  xxx
  xxx

où les caractères espaces indiquent l'absence d'encoche, les x représentent les encoches pleines et les . les encoches vides. Ici, la configuration finale est systématiquement la configuration duale c'est-à-dire la configuration où toutes les encoches initialement pleines se retrouvent vides et réciproquement. Mais cela limite les cas d'études puisque la configuration finale est imposée. D'autant que pour le solitaire européen il est prouvé que le passage d'une configuration à la configuration duale est impossible.

Nous optons donc pour la lecture de deux fichiers. Dans le but de simplifier les appels, nous imposons que ces deux fichiers partagent une partie du nom. Par exemple EL01 pour Édouard Lucas Problème n°1 consistera en deux fichiers textes : EL01I.txt codant la configuration initiale et EL01F.txt pour la configuration finale. De plus, si nous gardons les x et les . pour les encoches pleines et vides, l'espace peu lisible pourra être remplacée par n'importe quel autre caractère.

Voici à titre d'exemple les fichiers pour le problème n°I :

EL01I.txtEL01F.txt

EEEEEEEEE
EEE...EEE
EE..x..EE
E..xxx..E
E...x...E
E...x...E
EE.....EE
EEE...EEE
EEEEEEEEE

EEEEEEEEE
EEE...EEE
EE.....EE
E.......E
E...x...E
E.......E
EE.....EE
EEE...EEE
EEEEEEEEE

La première fonction utilitaire de notre outil sera donc create_file qui permet de créer facilement les fichiers textes des problèmes de E. Lucas. Voici par exemple l'appel pour la création du fichier EL01I.txt :

>>> create_file('EL01', [35, 43, 44, 45, 46, 55])

Et celui pour le fichier EL01F.txt :

>>> create_file('EL01', [44], 'F')

Et ça selon la description de E. Lucas lui-même :

probleme I

Comme nous le voyons l'auteur fourni la solution par une suite de coups simples (un unique saut pour un fichet) comme des fractions : le numéro au numérateur est le fichet qui effectue le saut, le numéro au dénominateur indique l'encoche d'arrivée. Étant sous-entendu que le fichet sauté est retiré du jeu.

Nous adopterons une notation différente : les coordonnées (x, y) du fichet qui bouge et une lettre pour nommer la direction du saut. N pour Nord, S pour Sud, E pour Est et W (que l'on confond moins avec le chiffre 0 que O) pour Ouest.

Résoudre un problème⚓︎

Une fois les fichiers texte créés, nous voulons pouvoir, dans un interprète Python interactif effectuer diverses actions :

Créer un problème en lui-donnant la partie du nom commune aux deux fichiers et afficher l'objectif du problème :

>>> p1 = Solitaire('EL01')
>>> p1.goal()

---------- Initial ----------     ----------- Final -----------
8                                 8
7           ○  ○  ○               7           ○  ○  ○
6        ○  ○  ●  ○  ○            6        ○  ○  ○  ○  ○
5     ○  ○  ●  ●  ●  ○  ○         5     ○  ○  ○  ○  ○  ○  ○
4     ○  ○  ○  ●  ○  ○  ○         4     ○  ○  ○  ●  ○  ○  ○
3     ○  ○  ○  ●  ○  ○  ○         3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○            2        ○  ○  ○  ○  ○
1           ○  ○  ○               1           ○  ○  ○
0                                 0
   0  1  2  3  4  5  6  7  8         0  1  2  3  4  5  6  7  8

Résoudre le problème (la réponse True signifie que le problème a effectivement été résolu):
Résolution en largeurRésolution en profondeurRésolution par beam search
>>> p1.largeur() True
>>> p1.profondeur() True
>>> p1.beam_search() True

Puisque le problème a été résolu, on peut afficher les motifs et les coups joués ou juste la liste des coups :

La liste des coupsLa trace complète

>>> p1.coups()
['4,5:E', '4,3:N', '3,5:E', '6,5:W', '4,6:S']

>>> p1.trace()

Nous donne (cliquez pour déplier):

Les 6 coups du problème I

--- motif 1/6 None:
8
7           ○  ○  ○
6        ○  ○  ●  ○  ○
5     ○  ○  ●  ●  ●  ○  ○
4     ○  ○  ○  ●  ○  ○  ○
3     ○  ○  ○  ●  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 2/6 (4, 5):E
8
7           ○  ○  ○
6        ○  ○  ●  ○  ○
5     ○  ○  ●  ○  ○  ●  ○
4     ○  ○  ○  ●  ○  ○  ○
3     ○  ○  ○  ●  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 3/6 (4, 3):N
8
7           ○  ○  ○
6        ○  ○  ●  ○  ○
5     ○  ○  ●  ●  ○  ●  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 4/6 (3, 5):E
8
7           ○  ○  ○
6        ○  ○  ●  ○  ○
5     ○  ○  ○  ○  ●  ●  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 5/6 (6, 5):W
8
7           ○  ○  ○
6        ○  ○  ●  ○  ○
5     ○  ○  ○  ●  ○  ○  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 6/6 (4, 6):S
8
7           ○  ○  ○
6        ○  ○  ○  ○  ○
5     ○  ○  ○  ○  ○  ○  ○
4     ○  ○  ○  ●  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8

Nous laissons temporairement les problèmes de E. Lucas pour présenter les objets que nous allons utiliser dans la suite. Nous reviendrons alors sur la résolution automatique.

Modéliser un problème⚓︎

La classe `Solitaire`⚓︎

Un objet Solitaire possède les propriétés suivantes :

initial : le motif initial
final le motif final
w : la largeur du tablier
h : la hauteur du tablier
coordonnees : les coordonnées valides du tablier
partie : la liste des motifs qui vont du motif initial (1er élément de la liste) au motif final par une succession de motifs obtenus par un coup valide à partir du précédent
current_id : l'indice d'un motif dans la liste partie, initialisé à 0
explored : un entier initialisé à 0 et qui va nous permettre de compter les motifs explorés lors de la résolution

La création d'une instance se fait en deux temps :

lecture des deux fichiers texte dont on donne la racine des noms à la création ; cette étape nous fournit deux dictionnaires et vérifie la cohérence des fichiers (a-t-on bien 2 solitaires de même dimensions ? les coordonnées admissibles sont-elles les mêmes ?). On initialise alors les dimensions w et h ainsi que des coordonnées admissibles (il s'agit des clés des dictionnaires).

Par exemple voici le dictionnaire obtenu pour le fichier EL01I.txt :

{(3, 1): 0, (4, 1): 0, (5, 1): 0, (2, 2): 0, (3, 2): 0, (4, 2): 1,
 (5, 2): 0, (6, 2): 0, (1, 3): 0, (2, 3): 0, (3, 3): 1, (4, 3): 1, 
 (5, 3): 1, (6, 3): 0, (7, 3): 0, (1, 4): 0, (2, 4): 0, (3, 4): 0, 
 (4, 4): 1, (5, 4): 0, (6, 4): 0, (7, 4): 0, (1, 5): 0, (2, 5): 0, 
 (3, 5): 0, (4, 5): 1, (5, 5): 0, (6, 5): 0, (7, 5): 0, (2, 6): 0, 
 (3, 6): 0, (4, 6): 0, (5, 6): 0, (6, 6): 0, (3, 7): 0, (4, 7): 0, 
 (5, 7): 0}

Création des motifs initial et final ; initialisation des autres propriétés

classe Solitaire

class Solitaire:

def __init__(self, racine_fichier, rep=DEFAULT_REP):
    init_filename = f'{rep}/{racine_fichier}I.txt'
    final_filename = f'{rep}/{racine_fichier}F.txt' 
    w, h, dico_initial = self.load(init_filename)
    w2, h2, dico_final = self.load(final_filename)
    if w == w2 and h == h2 and dico_initial.keys() == dico_final.keys():
        self.w, self.h = w, h
        self.coordonnees = dico_initial.keys()
        self.initial = Motif(self, dico_initial)
        self.final = Motif(self, dico_final)
        self.current_id = 0
        self.partie = [(self.initial, None, '')]
        self.explored = 0
    else:
        raise Exception('Fichiers incohérents')

Avant de présenter la classe Motif, voici une fonction bien pratique pour la suite de notre étude : solution, rattachée à un objet Solitaire, permet de tester qu'une liste de coups modélisés par les couples des numéros de l'encoche de départ et de l'encoche d'arrivée est une solution au problème.

Tester une solution d'E. Lucas

E. Lucas dans son livre parle de ses enfants Paul et Madeleine qui, agés de 6 et 7 ans, testaient pour lui les solutions aux exercices simples. Uné méthode solution permet d'entrer des coups sous la forme de couple de numéros (comme fournis par l'auteur des récréations) ; la fonction retourne True si et seulement si les coups conduisent effectivement à une solution c'est-à-dire que le dernier motif obtenu est bien le motif final :

>>> p1 = Solitaire('EL01')
>>> p1.solution([(45,65), (43,45), (35,55), (65,45), (46,44)])
True

La classe `Motif`⚓︎

Le motif ou encore configuration c'est l'ensemble des encoches. En termes de propriétés le motif est assez minimaliste :

solitaire qui est une référence vers l'objet Solitaire auquel appartient le motif ; c'est notamment le solitaire qui fournit les dimensions
encoches un dictionnaire dont les clés sont des coordonnées admissibles et les valeurs 0 ou 1 qui modélise une encoche vide ou pleine du tablier.

classe Motif

class Motif:

def __init__(self, solitaire, dico):
    self.solitaire = solitaire
    h = solitaire.h
    self.encoches = {(x, h-1-y):dico[x, y]) for x, y in dico}

Attention

Vous aurez noté que les ordonnées sont construites à l'envers : de l'indice le plus grand vers l'indice le plus faible. Cela est dû au système de coordonnées adopté pour numéroter le tablier du solitaire et qui donne les Y de bas en haut alors que lors de la lecture du fichier texte les numéros de ligne (donc les Y) vont croissant de haut en bas.

L'objet Motif implémente surtout pas mal de méthodes notamment pour la résolution d'un problème. Voyons quelques exemples.

Manipulations d'un `Motif`⚓︎

Supposons que m référence le motif initial du problème I. Nous allons voir d'abord quelques manipulations à la main. Elles ne sont pas essentielles à la résolution automatique mais dans ce genre d'exploration, il est important de pouvoir manipuler les objets créés, les visualiser.

Initialisation d'un motif

Il n'est pas vraiment prévu de créer un motif seul puisque le constructeur d'un Motif demande une référence vers un objet Solitaire ; le plus simple est de passer par la création d'un Solitaire, via un fichier texte :

>>> p1 = Solitaire('EL01')
>>> m = p1.initial

Afficher un motif

>>> print(m)

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

Remplir/Vider une encoche

Par les coordonnées ou le numéro (donné par 10*abscisse + ordonnée)

>>> m.switch(4, 5)
>>> m.switch(32)
>>> print(m)

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

Créer et modifier la copie d'un motif

>>> m2 = m.copy()
>>> print(m2)

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

# transforme m2 en son dual
>>> for encoche in m2.encoches.values():
...     encoche.switch()
>>> print(m2)

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

# m n'a pas changé
>>> print(m)

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

Jouer un coup simple...

... en donnant une direction soit un caractère parmi 'NSEW' et les coordonnées ou le numéro d'une encoche pleine. L'action retourne un couple : le nouveau motif et les coordonnées de l'encoche d'arrivée :

>>>  m.joue_un_coup('N', 4, 3)
(<__main__.Motif at 0x1e4ad92f9d0>, (4, 5))
# m n'a pas été affecté
>>> print(m)

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

>>>  m3, arrivee = m.joue_un_coup('N', 4, 3)
>>> print(m3)

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

La classe `Encoche`⚓︎

Existait dans une première version de notre solitaire ; a été simplifiée en un simple entier 0 ou 1.

Résolution automatique : principe général⚓︎

Un parcours de graphe⚓︎

Le principe de la résolution est basique il s'agit de partir du motif initial, de construire tous les motifs atteignables c'est-à-dire ceux obtenus par un coup valide. E. Lucas donne toujours ses solutions par des successions de coups simples ie un unique saut. Dans le sujet des Mines 2021, il est aussi question de coups composés : succession de coups simples où le fichet à l'arrivée est celui qui effectue le nouveau saut et ainsi de suite.

Notre résolution effectuera des coups composés, même si parfois (souvent) ils sont réduits à un seul saut et donc correspondent à un coup simple.

On appellera graphe d'exploration le graphe dont les sommets sont constitués de l'ensemble des motifs atteignables et les arcs orientés, vont d'un motif M_a vers un motif M_b s'il existe un coup simple ou composé permettant de passer de M_a à M_b.

Graphe d'exploration

Ci-dessous une partie du graphe d'exploration du problème n°I d'E. Lucas. Les motifs teintés de mauves sont terminaux (pas de continuation possible). On y voit le motif final et on constate que plusieurs chemins y mènent. Si on ne considère que les coups simples, il est assez trivial de voir que toutes les solutions sont équivalentes puisque le nombre de coups simples est égal à la différence d'encoches pleines entre la configuration finale et la configuration initiale. Dans le sujet des Mines, l'idée était de comptabiliser un coup composé comme 1 et donc de rechercher le chemin optimal.

Note : tous les ars n'ont pas été représentés

On remarque que ce graphe est presqu'un arbre : certains motifs peuvent avoir plusieurs arcs entrants. Mais on parlera quand même de branche pour un chemin entre deux motifs.

graphe P1

Parcours en profondeur

Le Backtracking consiste à explorer le graphe par un parcours en profondeur : on part du motif initial et on suit une des branches jusqu'à atteindre le motif final où une impasse. Dans le cas d'une impasse, on remonte au dernier motif où un choix était possible et on descend dans une autre branche.

Avantage

Avec de la chance on peut atteindre la configuration finale en explorant qu'une toute petite partie du graphe.

Inconvénients

On peut ne pas obtenir la solution optimale si on compte les coups composés.
Explosion combinatoire si l'ordre de sélection des branches n'est pas favorable

Parcours en largeur

Dans le sujet des Mines, comme on peut passer d'un motif à un autre par un coup composé, certaines branches sont plus courtes que d'autres pour atteindre le motif final. En conséquence, pour avoir la certitude d'obtenir le plus court chemin, on effectue un parcours en largeur : tous les motifs qui se trouvent à 1 coup du motif initial, puis à 2 coups etc. jusqu'à tomber sur le motif final (s'il est atteignable bien sûr).

Avantage

On est certain de tomber sur la solution la plus courte si on compte les coups composés comme 1 seul coup.

Inconvénient

L'exploration va traiter le graphe entier. Sur des problèmes non triviaux l'explosion combinatoire est à prévoir.

Solution 1 : le parcours en largeur⚓︎

Principe de l'algorithme

On explore 1 à 1 les motifs rangés dans une structure de file initialisée avec le motif initial. On stocke dans une structure résultat les motifs explorés avec comme information associée le motif dont ils sont issus, les coordonnées de l'encoche qui a effectué les sauts et les directions des différents sauts
Tant que la file possède un motif et qu'on n'a pas rencontré le motif final :
1. on retire le 1er élément de la file
2. si le motif en question ne fait pas partie de notre résultat on le rajoute
3. on calcule tous les motifs atteignables (on mémorisera aussi l'encoche et les directions jouées pour atteindre chacun de ces motifs)
4. on ajoute à la file les motifs qui n'y sont pas déjà
quand on sort de notre boucle, si le motif final a été atteint, on construit le chemin en remontant vers le motif initial et on retourne True sinon on retourne False.

Avant de nous pencher sur les opérations à effectuer sur les motifs pour calculer les motifs atteignables, voyons les structures dont nous avons parlé : la file et la structure _résultat.

La file⚓︎

Il s'agit bien d'une file au sens de structure FIFO. Implémentée par une simple liste Python sur laquelle on fera des append pour ajouter d'un côté de la liste et des pop(0) pour retirer de l'autre... Bien sûr ce n'est pas la solution la plus optimale : on aura avantage à utiliser un module comme dequeue ou coder une structure de file.

Les éléments de cette file sont des objets Motif. Mais pour chaque motif nous avons aussi besoin de savoir de quel motif il vient, par le mouvement de quelle encoche et avec quels sauts. A chaque motif on associe donc un triplet (m, (x, y), directions) dans un dictionnaire Python. Et là se pose une première difficulté : les clés d'un dictionnaire doivent être des objets hashable. Il nous faut donc une sorte d'encodage ou de signature d'un motif vers un objet non mutable, un int par exemple. C'est ce que nous donne le codage adopté dans le sujet des Mines :

\[\Sigma_{n} 2^n\]

où n est le numéro d'une encoche pleine du motif.

Encodage d'un motif

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

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

Solution 2 : le parcours en profondeur⚓︎

Il suffit de changer la structure de file par une pile. Dans ce parcours, la limite du nombre de motifs voisins à explorer n'a pas de sens puisqu'on va explorer jusqu'à tomber sur la solution.

L'ordre de rangement des motifs par contre est fondamental : la qualité de l'heuristique a un impact énorme sur la performance comme nous le verrons.

Maintenant que nous avons vu le principe général les structures utilisées, nous allons repartir du bas : comment à partir d'un motif, on obtient l'ensemble des motifs atteignables.

Résolution automatique : les diverses opérations⚓︎

Cette section détaille toutes les méthodes nécessaire à la résolution automatique. Elle est assez longue et peut éventuellement être ignorée dans une lecture rapide de l'article pour aller directement à la section des résultats.

Jouer un coup⚓︎

Étant donnée une encoche (par ses coordonnées ou son numéro), ainsi qu'une direction (par 'NSEW'), il s'agit de retourner None si le coup n'est pas valide ou le couple formé du nouveau motif et des coordonnées de l'encoche d'arrivée :

joue_un_coup

class Motif:
    # ...
    def joue_un_coup(self, direction, *args):
        x, y = to_coords(*args)
        motif = None
        dx, dy = DIRECTIONS[direction.upper()]
        voisin = x+dx, y+dy
        arrivee = x+2*dx, y+2*dy
        if self.on(*voisin) and self.off(*arrivee):            
            motif = self.copy()
            motif.switch(x, y)
            motif.switch(*voisin)
            motif.switch(*arrivee)
        return motif, arrivee

Explications

ligne 4 : on calcule les coordonnées de l'encoche qui va bouger
ligne 5 : le nouveau motif, None pour l'instant car on ne sait pas encore s'il va réellement exister
ligne 6 : on récupère le couple des variations à faire sur x et y en fonction de la direction donnée
ligne 7 : on calcule les coordonnées du voisin immédiat, l'encoche qui va être sautée et donc vidée
ligne 8 : on calcule les coordonnées de l'encoche d'arrivée celle qui va être remplie
ligne 9 : la condition pour que le coup soit jouable :
- le voisin immédiat doit être dans les coordonnées valides et plein
- l'arrivée doit être dans les coordonnées valides et vide
ligne 10 : les conditions sont réunies, on crée une copie du motif qui réalise le coup
ligne 11 à 13 : on change les états des encoches concernées
ligne 14 : on retourne le nouveau motif et les coordonnées de l'encoche d'arrivée (qui servira d'encoche de départ dans le cas d'un coup composé)

Coup simple⚓︎

Il nous faut obtenir la liste des coups possibles dans chacune des directions. La méthode coup_simple calcule la liste des triplets (m, d, (x, y)) où m est le nouveau motif obtenu par le coup joué dans la direction d depuis l'encoche de coordonnées (x, y).

coup_simple

class Motif:
    # ...
    def coup_simple(self, *args):
        coups = []
        if self.on(*args):
            x, y = to_coords(*args)
            for direction in DIRECTIONS:
                motif, arrivee = self.joue_un_coup(direction, x, y)
                if motif is not None:
                    coups.append((motif, direction, arrivee))
        return coups 

Exemple de coup simple

>>> print(m)

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

>>> m.coup_simple(4, 5)
[(<__main__.Motif at 0x1e4ad8f5100>, 'N', (4, 7)),
 (<__main__.Motif at 0x1e4aefa8160>, 'E', (6, 5)),
 (<__main__.Motif at 0x1e4aef950a0>, 'W', (2, 5))]

Coup composé⚓︎

Comme pour le coup simple, on part d'une encoche mais cette fois, on s'autorise plusieurs sauts d'affilée. Ici la direction sera donc une chaîne de direction simple. On retrouve le principe de la file de la résolution globale :

on commence par ranger dans une file les coups simples obtenus depuis l'encoche concernée
tant que la file n'est pas vide, on retire un élément et :
- on stocke dans la liste résultat des coups possibles le triplet constitué du motif, de la direction et des coordonnées de l'arrivée
- on calcule les coups simples possibles à partir de chacun de ces coups et on stocke dans la file le triplet motif obtenu, la direction qui est la direction de l'élément retiré à laquelle on concatène la direction du nouveau coup et bien sûr les coordonnées de l'arrivée

Ce qui donne :

coup_compose

class Motif:
    # ...
    def coup_compose(self, *args):
        coups = []
        if self.on(*args):
            a_traiter = self.coup_simple(*args)
            while a_traiter:
                coup, direction, arrivee = a_traiter.pop(0)
                coups.append((coup, direction, arrivee))
                for motif, one_dir, arr in coup.coup_simple(*arrivee):
                    voisin = motif, direction+one_dir, arr
                    if voisin not in a_traiter and voisin not in coups:
                        a_traiter.append(voisin)        
        return coups

Exemple de coup composé

>>> print(m2)

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

>>> m2.coup_compose(43)
[(<__main__.Motif at 0x1e4ae9b47f0>, 'N', (4, 5)),
 (<__main__.Motif at 0x1e4aeeb9370>, 'NN', (4, 7)),
 (<__main__.Motif at 0x1e4aefad550>, 'NE', (6, 5)),
 (<__main__.Motif at 0x1e4aefaa3d0>, 'NW', (2, 5))]

Notez que coup_compose fournit aussi le coup simple vers le Nord. Dans certains test, nous pourrons désactiver la recherche par coups composés qui peut augmenter le nombre de motifs explorés.

Mouvements⚓︎

A partir d'un motif m, on souhaite obtenir la liste des triplets (m', (x, y), d) où : m' est un motif atteignable depuis m en jouant le coup simple/composé depuis l'encoche de coordonnées (x, y) et dans les directions de la chaîne des directions simples d.

mouvements

class Motif:
    # ...
    def mouvements(self):
        return [(m1, (x, y), directions) for (x, y) in self.encoches 
                                for (m1, directions, _) in self.coup_simple(x, y)]

Exemple de mouvements

>>> print(m2)

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

>>> m2.mouvements()
[(<__main__.Motif at 0x1e4aeef8460>, (4, 4), 'S'),
 (<__main__.Motif at 0x1e4aeebf580>, (4, 3), 'N')]

`solve` : le coeur de la résolution⚓︎

Le dictionnaire d_pred associe un triplet (m', (x, y), d) au numéro d'un motif m tel que : (m, (x, y), d) in m'.mouvements(). C'est ce dictionnaire qu'on va vider progressivement en suivant l'ordre des motifs de notre file, pour créer un dictionnaire d_resultat :

solve

class Solitaire:
    # ...
    def solve(self):
        d_resultat = {}
        d_pred = {self.initial.num():(None, None, '')}
        file_a_traiter = [self.initial]
        num_final = self.final.num()
        while num_final not in d_resultat and file_a_traiter:
            m = file_a_traiter.pop(0)
            num = m.num()
            pred, coords, directions = d_pred.pop(num)
            if num not in d_resultat:
                d_resultat[num] = pred, coords, directions
            file_a_traiter.extend(self.strate(d_pred, [m]))
        if num_final in d_resultat:
            self.create_path(d_resultat)
            return True
        else:
            return False

La méthode strate sert à mettre à jour le dictionnaire d_pred et à retourner dans une liste les motifs effectivement obtenus (la liste peut être vide s'il n'y a plus d'extension possible à partir du motif courant) : ces motifs viennent se ranger dans la file d'attente (file_a_traiter).

La version proposée dans le script final a évolué et propose trois méthodes de résolutions qui remplacent la méthode solve (rebaptisée largeur) : largeur, profondeur et beam_search.

Premiers résultats et amélioration nécessaire⚓︎

Voici les résultats de notre programme sur les 6 premiers problèmes de E. Lucasavec un parcours en largeur.

P1P2P3P4P5P6

Enoncé et solution de E.Lucas

Charger le problème et afficher l'objectif⚓︎

>>> p1 = Solitaire("EL01")
>>> p1.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ○  ○               7           ○  ○  ○          
6        ○  ○  ●  ○  ○            6        ○  ○  ○  ○  ○       
5     ○  ○  ●  ●  ●  ○  ○         5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ●  ○  ○  ○         4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ●  ○  ○  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○            2        ○  ○  ○  ○  ○       
1           ○  ○  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p1.solution([(45, 65), (43, 45), (35, 55), (65, 45), (46, 44)])
True
>>> p1.coups()
['4,5:E', '4,3:N', '3,5:E', '6,5:W', '4,6:S']

Notre solution⚓︎

>>> p1b = Solitaire('EL01')
>>> p1b.solve()
True
>>> p1b.coups()
['4,5:E', '4,3:N', '3,5:E', '6,5:W', '4,6:S']
>>> p1b.explored
17

La trace complète

>>> p1.trace()

--- motif 1/6 None:
8                            
7           ○  ○  ○          
6        ○  ○  ●  ○  ○       
5     ○  ○  ●  ●  ●  ○  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ●  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 2/6 (4, 5):E
8                            
7           ○  ○  ○          
6        ○  ○  ●  ○  ○       
5     ○  ○  ●  ○  ○  ●  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ●  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 3/6 (4, 3):N
8                            
7           ○  ○  ○          
6        ○  ○  ●  ○  ○       
5     ○  ○  ●  ●  ○  ●  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 4/6 (3, 5):E
8                            
7           ○  ○  ○          
6        ○  ○  ●  ○  ○       
5     ○  ○  ○  ○  ●  ●  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 5/6 (6, 5):W
8                            
7           ○  ○  ○          
6        ○  ○  ●  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 6/6 (4, 6):S
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8

Enoncé et solution de E.Lucas

Charger le problème et afficher l'objectif⚓︎

>>> p2 = Solitaire("EL02")
>>> p2.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ○  ○               7           ○  ○  ○          
6        ○  ○  ●  ○  ○            6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○         5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ●  ●  ●  ●  ●  ○         4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ●  ○  ○  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ●  ○  ○            2        ○  ○  ○  ○  ○       
1           ○  ○  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p2.solution([(43, 41), (45, 43), (24, 44), (44, 42), (64, 44), (41, 43), (43, 45), (46, 44)])
True
>>> p2.coups()
['4,3:S', '4,5:S', '2,4:E', '4,4:S', '6,4:W', '4,1:N', '4,3:N', '4,6:S']

Notre solution⚓︎

>>> p2b = Solitaire('EL02')
>>> p2b.solve()
True
>>> p2b.coups()
['4,5:N', '4,3:N', '2,4:EN', '6,4:W', '4,7:SS', '4,2:N']
>>> p2b.explored
45

La trace complète

>>> p2.trace()

--- motif 1/7 None:
8                            
7           ○  ○  ○          
6        ○  ○  ●  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○    
4     ○  ●  ●  ●  ●  ●  ○    
3     ○  ○  ○  ●  ○  ○  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 2/7 (4, 5):N
8                            
7           ○  ●  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ●  ●  ●  ●  ●  ○    
3     ○  ○  ○  ●  ○  ○  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 3/7 (4, 3):N
8                            
7           ○  ●  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○    
4     ○  ●  ●  ○  ●  ●  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 4/7 (2, 4):EN
8                            
7           ○  ●  ○          
6        ○  ○  ●  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ○  ●  ●  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 5/7 (6, 4):W
8                            
7           ○  ●  ○          
6        ○  ○  ●  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 6/7 (4, 7):SS
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ●  ○  ○  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 7/7 (4, 2):N
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8

Enoncé et solution de E.Lucas

Charger le problème et afficher l'objectif⚓︎

>>> p3 = Solitaire("EL03")
>>> p3.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ○  ○               7           ○  ○  ○          
6        ○  ○  ○  ○  ○            6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○         5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ●  ●  ●  ○  ○         4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ●  ●  ●  ●  ●  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○            2        ○  ○  ○  ○  ○       
1           ○  ○  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p3.solution([(53, 55), (55, 35), (33, 53), (63, 43), (44, 42), (35, 33), (23, 43), (42, 44)])
True
>>> p3.coups()
['5,3:N', '5,5:W', '3,3:E', '6,3:W', '4,4:S', '3,5:S', '2,3:E', '4,2:N']

Notre solution⚓︎

>>> p3b = Solitaire('EL03')
>>> p3b.solve()
True
>>> p3b.coups()
['4,4:S', '2,3:E', '5,3:NWSE', '6,3:W', '4,2:N']
>>> p3b.explored
412

La trace complète

>>> p3.trace()

--- motif 1/6 None:
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○    
4     ○  ○  ●  ●  ●  ○  ○    
3     ○  ●  ●  ●  ●  ●  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 2/6 (4, 4):S
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○    
4     ○  ○  ●  ○  ●  ○  ○    
3     ○  ●  ●  ○  ●  ●  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 3/6 (2, 3):E
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○    
4     ○  ○  ●  ○  ●  ○  ○    
3     ○  ○  ○  ●  ●  ●  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 4/6 (5, 3):NWSE
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ●  ●  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 5/6 (6, 3):W
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ●  ○  ○  ○    
2        ○  ○  ●  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 6/6 (4, 2):N
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8

Enoncé et solution de E.Lucas

Charger le problème et afficher l'objectif⚓︎

>>> p4 = Solitaire("EL04")
>>> p4.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ○  ○  ○          
6        ○  ●  ●  ●  ○            6        ○  ○  ○  ○  ○       
5     ○  ○  ●  ●  ●  ○  ○         5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ●  ○  ●  ○  ○         4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○            2        ○  ○  ○  ○  ○       
1           ○  ○  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p4.solution([(45, 25), (37, 35), (57, 37), (34, 36), (37, 35), (25, 45), (46, 66), (54, 56), (66, 46), (46, 44)])
True
>>> p4.coups()
['4,5:W', '3,7:S', '5,7:W', '3,4:N', '3,7:S', '2,5:E', '4,6:E', '5,4:N', '6,6:W', '4,6:S']

Notre solution⚓︎

>>> p4b = Solitaire('EL04')
>>> p4b.solve()
True
>>> p4b.coups()
['4,5:E', '5,7:S', '5,4:N', '3,7:ES', '6,5:WW', '4,6:WSE']
>>> p4b.explored
792

La trace complète

>>> p4.trace()

--- motif 1/7 None:
8                            
7           ●  ●  ●          
6        ○  ●  ●  ●  ○       
5     ○  ○  ●  ●  ●  ○  ○    
4     ○  ○  ●  ○  ●  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 2/7 (4, 5):E
8                            
7           ●  ●  ●          
6        ○  ●  ●  ●  ○       
5     ○  ○  ●  ○  ○  ●  ○    
4     ○  ○  ●  ○  ●  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 3/7 (5, 7):S
8                            
7           ●  ●  ○          
6        ○  ●  ●  ○  ○       
5     ○  ○  ●  ○  ●  ●  ○    
4     ○  ○  ●  ○  ●  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 4/7 (5, 4):N
8                            
7           ●  ●  ○          
6        ○  ●  ●  ●  ○       
5     ○  ○  ●  ○  ○  ●  ○    
4     ○  ○  ●  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 5/7 (3, 7):ES
8                            
7           ○  ○  ○          
6        ○  ●  ●  ○  ○       
5     ○  ○  ●  ○  ●  ●  ○    
4     ○  ○  ●  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 6/7 (6, 5):WW
8                            
7           ○  ○  ○          
6        ○  ●  ●  ○  ○       
5     ○  ●  ○  ○  ○  ○  ○    
4     ○  ○  ●  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 7/7 (4, 6):WSE
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ○  ○  ○  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8

Enoncé et solution de E.Lucas

Charger le problème et afficher l'objectif⚓︎

>>> p5 = Solitaire("EL05")
>>> p5.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ●  ○               7           ○  ○  ○          
6        ○  ○  ●  ○  ○            6        ○  ○  ○  ○  ○       
5     ○  ●  ●  ●  ●  ●  ○         5     ○  ○  ○  ●  ○  ○  ○    
4     ○  ○  ○  ●  ○  ○  ○         4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ●  ○  ○  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ●  ●  ●  ○            2        ○  ○  ○  ○  ○       
1           ●  ●  ●               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p5.solution([(31, 33), (51, 53), (43, 63), (41, 43), (33, 53), (63, 43), (44, 42), (46, 44), (25, 45), (45, 43), (65, 45), (42, 44), (44, 46), (47, 45)])
True
>>> p5.coups()
['3,1:N', '5,1:N', '4,3:E', '4,1:N', '3,3:E', '6,3:W', '4,4:S', '4,6:S', '2,5:E', '4,5:S', '6,5:W', '4,2:N', '4,4:N', '4,7:S']

Notre solution⚓︎

>>> p5b = Solitaire('EL05')
>>> p5b.solve()
True
>>> p5b.coups()
['3,1:NE', '3,5:W', '5,5:W', '4,7:SW', '4,1:NE', '5,1:N', '6,3:WN', '1,5:EE', '6,5:W']
>>> p5b.explored
8085

La trace complète

>>> p5.trace()

--- motif 1/10 None:
8                            
7           ○  ●  ○          
6        ○  ○  ●  ○  ○       
5     ○  ●  ●  ●  ●  ●  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ●  ○  ○  ○    
2        ○  ●  ●  ●  ○       
1           ●  ●  ●          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 2/10 (3, 1):NE
8                            
7           ○  ●  ○          
6        ○  ○  ●  ○  ○       
5     ○  ●  ●  ●  ●  ●  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ●  ○  ○    
2        ○  ○  ●  ●  ○       
1           ○  ●  ●          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 3/10 (3, 5):W
8                            
7           ○  ●  ○          
6        ○  ○  ●  ○  ○       
5     ●  ○  ○  ●  ●  ●  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ●  ○  ○    
2        ○  ○  ●  ●  ○       
1           ○  ●  ●          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 4/10 (5, 5):W
8                            
7           ○  ●  ○          
6        ○  ○  ●  ○  ○       
5     ●  ○  ●  ○  ○  ●  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ●  ○  ○    
2        ○  ○  ●  ●  ○       
1           ○  ●  ●          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 5/10 (4, 7):SW
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ●  ●  ○  ○  ○  ●  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ●  ○  ○    
2        ○  ○  ●  ●  ○       
1           ○  ●  ●          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 6/10 (4, 1):NE
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ●  ●  ○  ○  ○  ●  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ○  ●  ○    
2        ○  ○  ○  ●  ○       
1           ○  ○  ●          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 7/10 (5, 1):N
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ●  ●  ○  ○  ○  ●  ○    
4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ○  ○  ●  ●  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 8/10 (6, 3):WN
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ●  ●  ○  ●  ○  ●  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 9/10 (1, 5):EE
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ○  ●  ●  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 10/10 (6, 5):W
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8

Enoncé et solution de E.Lucas

Charger le problème et afficher l'objectif⚓︎

>>> p6 = Solitaire("EL06")
>>> p6.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ●  ○               7           ○  ○  ○          
6        ○  ●  ●  ●  ○            6        ○  ○  ○  ○  ○       
5     ○  ●  ●  ●  ●  ●  ○         5     ○  ○  ○  ●  ○  ○  ○    
4     ●  ●  ●  ●  ●  ●  ●         4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○            2        ○  ○  ○  ○  ○       
1           ○  ○  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p6.solution([(55, 53), (74, 54), (53, 55), (55, 57), (57, 37), (35, 33), (14, 34), (33, 35), (36, 56), (44, 46), (56, 36), (25, 45), (37, 35), (35, 55), (65, 45)])
True
>>> p6.coups()
['5,5:S', '7,4:W', '5,3:N', '5,5:N', '5,7:W', '3,5:S', '1,4:E', '3,3:N', '3,6:E', '4,4:N', '5,6:W', '2,5:E', '3,7:S', '3,5:E', '6,5:W']

Notre solution⚓︎

>>> p6b = Solitaire('EL06')
>>> p6b.solve()
True
>>> p6b.coups()
['3,5:S', '4,5:S', '6,4:W', '4,6:ES', '7,4:WN', '1,4:EE', '3,3:ENNWS', '2,5:E']
>>> p6b.explored
80679

La trace complète

>>> p6.trace()

--- motif 1/9 None:
8                            
7           ○  ●  ○          
6        ○  ●  ●  ●  ○       
5     ○  ●  ●  ●  ●  ●  ○    
4     ●  ●  ●  ●  ●  ●  ●    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 2/9 (3, 5):S
8                            
7           ○  ●  ○          
6        ○  ●  ●  ●  ○       
5     ○  ●  ○  ●  ●  ●  ○    
4     ●  ●  ○  ●  ●  ●  ●    
3     ○  ○  ●  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 3/9 (4, 5):S
8                            
7           ○  ●  ○          
6        ○  ●  ●  ●  ○       
5     ○  ●  ○  ○  ●  ●  ○    
4     ●  ●  ○  ○  ●  ●  ●    
3     ○  ○  ●  ●  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 4/9 (6, 4):W
8                            
7           ○  ●  ○          
6        ○  ●  ●  ●  ○       
5     ○  ●  ○  ○  ●  ●  ○    
4     ●  ●  ○  ●  ○  ○  ●    
3     ○  ○  ●  ●  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 5/9 (4, 6):ES
8                            
7           ○  ●  ○          
6        ○  ●  ○  ○  ○       
5     ○  ●  ○  ○  ●  ○  ○    
4     ●  ●  ○  ●  ○  ●  ●    
3     ○  ○  ●  ●  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 6/9 (7, 4):WN
8                            
7           ○  ●  ○          
6        ○  ●  ○  ●  ○       
5     ○  ●  ○  ○  ○  ○  ○    
4     ●  ●  ○  ●  ○  ○  ○    
3     ○  ○  ●  ●  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 7/9 (1, 4):EE
8                            
7           ○  ●  ○          
6        ○  ●  ○  ●  ○       
5     ○  ●  ○  ○  ○  ○  ○    
4     ○  ○  ○  ○  ●  ○  ○    
3     ○  ○  ●  ●  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 8/9 (3, 3):ENNWS
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ●  ●  ○  ○  ○  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8
--- motif 9/9 (2, 5):E
8                            
7           ○  ○  ○          
6        ○  ○  ○  ○  ○       
5     ○  ○  ○  ●  ○  ○  ○    
4     ○  ○  ○  ○  ○  ○  ○    
3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ○  ○  ○  ○       
1           ○  ○  ○          
0                            
   0  1  2  3  4  5  6  7  8

Explosion combinatoire⚓︎

Avec P6 on constate que le nombre de motifs explorés atteint déjà une taille conséquente, compte tenu qu'il s'agit d'un problème simple. Une solution consiste à ne pas explorer tous les motifs d'un niveau.

Solution 3 : limiter la largeur de l'arbre⚓︎

Le principe très simple consiste à associer à un motif un score généralement nommé coût heuristique et de ne sélectionner pour la recherche que les n meilleurs candidats. Plus n est grand, moins on ignore de candidats mais plus la taille de l'arbre exploré est grande, et plus n est petit plus la recherche va aller vite en ignorant des candidats mais en contre-partie la garantie de trouver la solution n'est plus vraie : il s'agit d'un algorithme glouton. Si n est \(\infty\) alors la recherche redevient un parcours en largeur classique.

Le score que nous utilisons est le rapport entre le nombre d'encoches pleines et le nombre d'encoches bloquées (ie ne pouvant pas bouger).

score

def blocked(self, x, y):
    return all(not self.coup_possible(d, x, y) for d in DIRECTIONS)

def score(self):
    nb_pleins, nb_blocked = 0, 1
    for encoche in self.encoches.values():
        if encoche.on():
            nb_pleins += 1
            if self.blocked(encoche.x, encoche.y):
                nb_blocked += 1
    return nb_pleins / nb_blocked

Solution 3 bis : le beam search⚓︎

En français recherche en faisceau. Dans la solution n°3, le parcours en largeur limite à n les voisins de chacun des motifs d'un niveau. Le nombre de motifs restent donc exponentiel de l'ordre de \(n^{p}\) où p est la profondeur de l'arbre.

Le principe du beam search est de limiter à n chaque niveau. Et d'augmenter progressivement le n jusqu'à trouver la solution.

beam search

class Solitaire:
    # ...

    def beam(self, n, d_pred, sauf=None):
        d_resultat = {}
        gen = [self.initial]
        next_gen = []
        num_final = self.final.num()
        while num_final not in d_resultat and gen:
            next_gen = sorted(self.strate(d_pred, gen), key=lambda t: t.score(sauf), reverse=True)
            for m in gen:
                self.explored += 1
                num = m.num()
                pred, coords, directions = d_pred[num]
                if num not in d_resultat:
                    d_resultat[num] = pred, coords, directions
            gen = [next_gen[i] for i in range(min(n, len(next_gen)))]
        if num_final in d_resultat:
            self.create_path(d_resultat)
            return True
        else:
            return False

    def beam_search(self, n=2):
        num_initial = self.initial.num() 
        d_pred = {num_initial:(None, None, '')}
        while not self.beam(n, d_pred):
            d_pred = {num_initial:(None, None, '')}
            n *= 2
        return n

Les problèmes 7 à 12⚓︎

Ils sont plus difficiles, et la recherche naïve par un parcours en largeur n'aboutit pas.

P7P8P9P10P11P12

Enoncé et solution de E.Lucas

Charger le problème et afficher l'objectif⚓︎

>>> p7 = Solitaire("EL07")
>>> p7.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ●  ○               7           ○  ○  ○          
6        ●  ○  ●  ○  ●            6        ○  ○  ○  ○  ○       
5     ○  ○  ●  ●  ●  ○  ○         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ●  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ○  ●  ●  ●  ○  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ●  ○  ●  ○  ●            2        ○  ○  ○  ○  ○       
1           ○  ●  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p7.solution([(54, 52), (52, 32), (22, 42), (33, 53), (41, 43), (43, 63), (74, 54), (62, 64), (45, 65), (54, 74), (66, 64), (74, 54), (35, 33), (54, 34), (33, 35), (47, 45), (45, 25), (14, 34), (26, 24), (24, 44)])
True
>>> p7.coups()
['5,4:S', '5,2:W', '2,2:E', '3,3:E', '4,1:N', '4,3:E', '7,4:W', '6,2:N', '4,5:E', '5,4:E', '6,6:S', '7,4:W', '3,5:S', '5,4:W', '3,3:N', '4,7:S', '4,5:W', '1,4:E', '2,6:S', '2,4:E']

Enoncé et solution de E.Lucas

Charger le problème et afficher l'objectif⚓︎

>>> p8 = Solitaire("EL08")
>>> p8.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ●  ○               7           ○  ○  ○          
6        ○  ●  ●  ●  ○            6        ○  ○  ○  ○  ○       
5     ○  ●  ○  ●  ○  ●  ○         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ●  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ●  ○  ●  ○  ●  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ●  ●  ●  ○            2        ○  ○  ○  ○  ○       
1           ○  ●  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p8.solution([(64, 62), (44, 64), (74, 54), (46, 66), (66, 64), (64, 44), (44, 46), (47, 45), (24, 26), (26, 46), (46, 44), (44, 24), (14, 34), (42, 22), (22, 24), (24, 44), (44, 42), (41, 43), (62, 42), (42, 44)])
True
>>> p8.coups()
['6,4:S', '4,4:E', '7,4:W', '4,6:E', '6,6:S', '6,4:W', '4,4:N', '4,7:S', '2,4:N', '2,6:E', '4,6:S', '4,4:W', '1,4:E', '4,2:W', '2,2:N', '2,4:E', '4,4:S', '4,1:N', '6,2:W', '4,2:N']

Enoncé et solution de E.Lucas

Charger le problème et afficher l'objectif⚓︎

>>> p9 = Solitaire("EL09")
>>> p9.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ●  ○               7           ○  ○  ○          
6        ○  ●  ●  ●  ○            6        ○  ○  ○  ○  ○       
5     ○  ●  ●  ●  ●  ●  ○         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ●  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ●  ●  ●  ●  ●  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ●  ●  ●  ○            2        ○  ○  ○  ○  ○       
1           ○  ○  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p9.solution([(53, 51), (32, 52), (51, 53), (44, 42), (23, 43), (42, 44), (63, 43), (25, 23), (45, 25), (43, 45), (55, 35), (35, 33), (33, 13), (13, 15), (15, 35), (35, 37), (37, 57), (57, 55), (55, 53), (74, 54), (53, 55), (65, 45), (46, 44)])
True
>>> p9.coups()
['5,3:S', '3,2:E', '5,1:N', '4,4:S', '2,3:E', '4,2:N', '6,3:W', '2,5:S', '4,5:W', '4,3:N', '5,5:W', '3,5:S', '3,3:W', '1,3:N', '1,5:E', '3,5:N', '3,7:E', '5,7:S', '5,5:S', '7,4:W', '5,3:N', '6,5:W', '4,6:S']

Enoncé et solution de E.Lucas

p10

Charger le problème et afficher l'objectif⚓︎

>>> p10 = Solitaire("EL10")
>>> p10.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ●  ○               7           ○  ○  ○          
6        ○  ●  ●  ●  ○            6        ○  ○  ○  ○  ○       
5     ○  ●  ●  ●  ●  ●  ○         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ●  ●  ●  ●  ●  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ●  ●  ●  ○            2        ○  ○  ○  ○  ○       
1           ○  ●  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p10.solution([(53, 51), (51, 31), (55, 75), (75, 73), (73, 53), (64, 44), (35, 37), (37, 57), (57, 55), (55, 35), (34, 36), (46, 26), (14, 34), (26, 24), (23, 25), (44, 24), (25, 23), (32, 34), (53, 33), (34, 32), (31, 33), (23, 43), (42, 44)])
True
>>> p10.coups()
['5,3:S', '5,1:W', '5,5:E', '7,5:S', '7,3:W', '6,4:W', '3,5:N', '3,7:E', '5,7:S', '5,5:W', '3,4:N', '4,6:W', '1,4:E', '2,6:S', '2,3:N', '4,4:W', '2,5:S', '3,2:N', '5,3:W', '3,4:S', '3,1:N', '2,3:E', '4,2:N']

Enoncé et solution de E.Lucas

p11

Charger le problème et afficher l'objectif⚓︎

>>> p11 = Solitaire("EL11")
>>> p11.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ○  ●  ○               7           ○  ○  ○          
6        ●  ●  ●  ●  ●            6        ○  ○  ○  ○  ○       
5     ○  ●  ●  ●  ●  ●  ○         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ●  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○    
3     ○  ●  ●  ●  ●  ●  ○         3     ○  ○  ○  ○  ○  ○  ○    
2        ●  ●  ●  ●  ●            2        ○  ○  ○  ○  ○       
1           ○  ●  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p11.solution([(53, 51), (32, 52), (51, 53), (54, 52), (74, 54), (44, 42), (52, 32), (22, 42), (41, 43), (24, 22), (43, 23), (22, 24), (62, 64), (64, 44), (34, 54), (14, 34), (66, 64), (64, 44), (56, 54), (35, 33), (54, 34), (33, 35), (35, 55), (47, 45), (55, 35), (25, 45), (26, 46), (46, 44)])
True
>>> p11.coups()
['5,3:S', '3,2:E', '5,1:N', '5,4:S', '7,4:W', '4,4:S', '5,2:W', '2,2:E', '4,1:N', '2,4:S', '4,3:W', '2,2:N', '6,2:N', '6,4:W', '3,4:E', '1,4:E', '6,6:S', '6,4:W', '5,6:S', '3,5:S', '5,4:W', '3,3:N', '3,5:E', '4,7:S', '5,5:W', '2,5:E', '2,6:E', '4,6:S']

Enoncé et solution de E.Lucas

p12

Charger le problème et afficher l'objectif⚓︎

>>> p12 = Solitaire("EL12")
>>> p12.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ○  ○  ○          
6        ○  ●  ●  ●  ○            6        ○  ○  ○  ○  ○       
5     ●  ●  ●  ●  ●  ●  ●         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ○  ○  ○  ○  ○  ○  ○    
2        ○  ●  ●  ●  ○            2        ○  ○  ○  ○  ○       
1           ●  ●  ●               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p12.solution([(42, 62), (54, 52), (51, 53), (74, 54), (54, 52), (62, 42), (73, 53), (32, 52), (31, 51), (43, 63), (51, 53), (63, 43), (56, 54), (75, 55), (54, 56), (35, 55), (47, 45), (45, 65), (57, 55), (65, 45), (37, 35), (34, 32), (13, 33), (15, 13), (43, 23), (13, 33), (32, 34), (24, 26), (34, 36), (26, 46), (46, 44)])
True
>>> p12.coups()
['4,2:E', '5,4:S', '5,1:N', '7,4:W', '5,4:S', '6,2:W', '7,3:W', '3,2:E', '3,1:E', '4,3:E', '5,1:N', '6,3:W', '5,6:S', '7,5:W', '5,4:N', '3,5:E', '4,7:S', '4,5:E', '5,7:S', '6,5:W', '3,7:S', '3,4:S', '1,3:E', '1,5:S', '4,3:W', '1,3:E', '3,2:N', '2,4:N', '3,4:N', '2,6:E', '4,6:S']

problème	larg. inf	larg n/nb	profondeur	bs n/nb
1	23	14	12	2/11
2	150	66	23	16/169
3	540	3/198	35	16/201
4	1029	166	4953	4/55
5	10195	980	6277	32/658
6	83558	2939	22	4/87
7	606160	25303	1913	8/255
8	77381	11883	492	16/524
9	-	259223	20401	16/647
10	-	235548	83677	64/2613
11	-	2890929		4/158
12	-	1065923		256/13917

La deuxième colonne donne le nombre de motifs explorés sans limitation c'est-à-dire lors du parcours en largeur classique et la troisième donne la même information mais avec une limite à 2 motifs par niveau sauf pour les cas où 2 n'a pas donné de solution (on donne alors la valeur de la limite pour laquelle une solution a été trouvée).

Dans la quatrième colonne figure le nombre d'exploration lors de la recherche en profondeur. Cette recherche donne de bons résultats sur certains problèmes (2, 3, 6, 7, 8, 9).

Et la dernière colonne donne les résultats du beam search : la valeur de n qui a permis de trouver une solution et le nombre total de motifs explorés (les motifs ont été explorés plusieurs fois pour n > 2). On constate que cet algorithme est de loin le plus efficace.

Suite des problèmes : de 13 à 30⚓︎

En guise de conclusion, nous terminons par les derniers problèmes de E. Lucas.

Ils ont en commun (sauf le dernier) le motif de départ qui est constitué des 37 encoches pleines exceptées la centrale 44 qui est vide. Chaque problème doit alors créer un motif propre, chacun ayant un nom assez poétique donné par E. Lucas (Adam et Eve dans le Paradis Terrestre, Trois cavaliers cernés par seize soldats, La Pyramide ...) :

P13P14P15P16P17P18P19P20P21P22P23P24P25P26P27P28P29P30

Enoncé et solution de E.Lucas

p13

Charger le problème et afficher l'objectif⚓︎

>>> p13 = Solitaire("EL13")
>>> p13.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ●  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ●  ●  ●  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ○  ○  ●  ○  ○  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ●  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p13.solution([(64, 44), (62, 64), (42, 62), (22, 42), (24, 22), (26, 24), (46, 26), (66, 46), (64, 66), (34, 54), (54, 52), (52, 32), (32, 34), (24, 44)])
True
>>> p13.coups()
['6,4:W', '6,2:N', '4,2:E', '2,2:E', '2,4:S', '2,6:S', '4,6:W', '6,6:W', '6,4:N', '3,4:E', '5,4:S', '5,2:W', '3,2:N', '2,4:E']

Enoncé et solution de E.Lucas

p14

Charger le problème et afficher l'objectif⚓︎

>>> p14 = Solitaire("EL14")
>>> p14.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ○  ○  ○  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ●  ●  ●  ●  ●  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ○  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p14.solution([(42, 44), (22, 42), (24, 22), (63, 43), (33, 53), (65, 63), (62, 64), (42, 62), (26, 24), (46, 26), (34, 36), (55, 35), (36, 34), (53, 55), (56, 54)])
True
>>> p14.coups()
['4,2:N', '2,2:E', '2,4:S', '6,3:W', '3,3:E', '6,5:S', '6,2:N', '4,2:E', '2,6:S', '4,6:W', '3,4:N', '5,5:W', '3,6:S', '5,3:N', '5,6:S']

Enoncé et solution de E.Lucas

p15

Charger le problème et afficher l'objectif⚓︎

>>> p15 = Solitaire("EL15")
>>> p15.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ○  ●  ○  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ○  ●  ●  ●  ○  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ●  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p15.solution([(24, 44), (36, 34), (55, 35), (25, 45), (33, 35), (53, 33), (23, 43), (56, 36), (36, 34), (73, 53), (65, 63), (53, 73), (51, 53), (32, 52), (53, 51)])
True
>>> p15.coups()
['2,4:E', '3,6:S', '5,5:W', '2,5:E', '3,3:N', '5,3:W', '2,3:E', '5,6:W', '3,6:S', '7,3:W', '6,5:S', '5,3:E', '5,1:N', '3,2:E', '5,3:S']

Enoncé et solution de E.Lucas

p16

Charger le problème et afficher l'objectif⚓︎

>>> p16 = Solitaire("EL16")
>>> p16.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ●  ○  ●  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ○  ○  ●  ○  ○  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ○  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ●  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p16.solution([(64, 44), (52, 54), (33, 53), (54, 52), (66, 64), (46, 66), (44, 46), (24, 44), (26, 24), (46, 26), (14, 34), (22, 24), (34, 14), (42, 22), (62, 42), (64, 62)])
True
>>> p16.coups()
['6,4:W', '5,2:N', '3,3:E', '5,4:S', '6,6:S', '4,6:E', '4,4:N', '2,4:E', '2,6:S', '4,6:W', '1,4:E', '2,2:N', '3,4:W', '4,2:W', '6,2:W', '6,4:S']

Enoncé et solution de E.Lucas

p17

Charger le problème et afficher l'objectif⚓︎

>>> p17 = Solitaire("EL17")
>>> p17.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ○  ○  ●  ○  ○       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ○  ●  ○  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ●  ●  ○  ●  ●  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ●  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ○  ○  ●  ○  ○       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p17.solution([(24, 44), (54, 34), (74, 54), (42, 44), (44, 64), (46, 44), (34, 54), (54, 74), (62, 42), (63, 43), (32, 34), (22, 24), (25, 45), (26, 46), (56, 54), (66, 64)])
True
>>> p17.coups()
['2,4:E', '5,4:W', '7,4:W', '4,2:N', '4,4:E', '4,6:S', '3,4:E', '5,4:E', '6,2:W', '6,3:W', '3,2:N', '2,2:N', '2,5:E', '2,6:E', '5,6:S', '6,6:S']

Enoncé et solution de E.Lucas

p18

Charger le problème et afficher l'objectif⚓︎

>>> p18 = Solitaire("EL18")
>>> p18.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ●  ○  ●  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ○  ○  ○  ○  ○  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ●  ○  ●  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p18.solution([(42, 44), (45, 43), (64, 44), (43, 45), (66, 64), (46, 66), (26, 46), (46, 44), (24, 26), (44, 24), (22, 42), (24, 22), (41, 43), (62, 42), (43, 41), (64, 62)])
True
>>> p18.coups()
['4,2:N', '4,5:S', '6,4:W', '4,3:N', '6,6:S', '4,6:E', '2,6:E', '4,6:S', '2,4:N', '4,4:W', '2,2:E', '2,4:S', '4,1:N', '6,2:W', '4,3:S', '6,4:S']

Enoncé et solution de E.Lucas

p19

Charger le problème et afficher l'objectif⚓︎

>>> p19 = Solitaire("EL19")
>>> p19.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ○  ●  ○  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ○  ○  ○  ○  ○  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ●  ○  ●  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p19.solution([(64, 44), (34, 54), (42, 44), (44, 64), (36, 34), (56, 36), (26, 46), (46, 44), (65, 45), (24, 26), (44, 24), (22, 42), (24, 22), (41, 43), (62, 42), (43, 41), (64, 62)])
True
>>> p19.coups()
['6,4:W', '3,4:E', '4,2:N', '4,4:E', '3,6:S', '5,6:W', '2,6:E', '4,6:S', '6,5:W', '2,4:N', '4,4:W', '2,2:E', '2,4:S', '4,1:N', '6,2:W', '4,3:S', '6,4:S']

Enoncé et solution de E.Lucas

p20

Charger le problème et afficher l'objectif⚓︎

>>> p20 = Solitaire("EL20")
>>> p20.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ○  ○  ○  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ○  ●  ○  ●  ○  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ○  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p20.solution([(46, 44), (43, 45), (23, 43), (25, 23), (45, 25), (42, 44), (63, 43), (43, 45), (65, 63), (45, 65), (22, 42), (26, 24), (66, 46), (62, 64), (42, 62), (24, 22), (46, 26), (64, 66)])
True
>>> p20.coups()
['4,6:S', '4,3:N', '2,3:E', '2,5:S', '4,5:W', '4,2:N', '6,3:W', '4,3:N', '6,5:S', '4,5:E', '2,2:E', '2,6:S', '6,6:W', '6,2:N', '4,2:E', '2,4:S', '4,6:W', '6,4:N']

Enoncé et solution de E.Lucas

p21

Charger le problème et afficher l'objectif⚓︎

>>> p21 = Solitaire("EL21")
>>> p21.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ○  ○  ○  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ○  ○  ●  ○  ○  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ○  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p21.solution([(64, 44), (62, 64), (42, 62), (22, 42), (24, 22), (26, 24), (46, 26), (66, 46), (64, 66), (34, 54), (54, 52), (52, 32), (32, 34), (24, 44), (45, 65), (43, 45), (35, 55), (65, 45), (46, 44)])
True
>>> p21.coups()
['6,4:W', '6,2:N', '4,2:E', '2,2:E', '2,4:S', '2,6:S', '4,6:W', '6,6:W', '6,4:N', '3,4:E', '5,4:S', '5,2:W', '3,2:N', '2,4:E', '4,5:E', '4,3:N', '3,5:E', '6,5:W', '4,6:S']

Enoncé et solution de E.Lucas

p22

Charger le problème et afficher l'objectif⚓︎

>>> p22 = Solitaire("EL22")
>>> p22.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ●  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ○  ○  ○  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ○  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p22.solution([(24, 44), (32, 34), (52, 32), (35, 33), (32, 34), (55, 35), (57, 55), (65, 45), (63, 65), (43, 63), (36, 56), (35, 55), (55, 57), (13, 33), (15, 13), (33, 35), (35, 15), (73, 53), (75, 73), (53, 55), (55, 75)])
True
>>> p22.coups()
['2,4:E', '3,2:N', '5,2:W', '3,5:S', '3,2:N', '5,5:W', '5,7:S', '6,5:W', '6,3:N', '4,3:E', '3,6:E', '3,5:E', '5,5:N', '1,3:E', '1,5:S', '3,3:N', '3,5:W', '7,3:W', '7,5:S', '5,3:N', '5,5:E']

Enoncé et solution de E.Lucas

p23

Charger le problème et afficher l'objectif⚓︎

>>> p23 = Solitaire("EL23")
>>> p23.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ○  ○  ○          
6        ●  ●  ●  ●  ●            6        ○  ○  ○  ○  ○       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ●  ●  ●  ●  ●  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ●  ○  ○  ○  ○  ○  ●    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ○  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p23.solution([(24, 44), (32, 34), (53, 33), (34, 32), (31, 33), (52, 32), (33, 31), (45, 43), (64, 44), (43, 45), (56, 54), (35, 55), (54, 56), (66, 64), (63, 65), (26, 24), (23, 25), (37, 35), (47, 45), (57, 55)])
True
>>> p23.coups()
['2,4:E', '3,2:N', '5,3:W', '3,4:S', '3,1:N', '5,2:W', '3,3:S', '4,5:S', '6,4:W', '4,3:N', '5,6:S', '3,5:E', '5,4:N', '6,6:S', '6,3:N', '2,6:S', '2,3:N', '3,7:S', '4,7:S', '5,7:S']

Enoncé et solution de E.Lucas

p24

Charger le problème et afficher l'objectif⚓︎

>>> p24 = Solitaire("EL24")
>>> p24.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ○  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ●  ○  ●  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ○  ○  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ●  ○  ●  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ○  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p24.solution([(42, 44), (62, 42), (64, 62), (44, 64), (41, 43), (74, 54), (46, 44), (44, 64), (66, 46), (64, 66), (47, 45), (24, 44), (44, 46), (26, 24), (46, 26), (14, 34), (22, 24), (24, 44), (44, 42), (42, 22)])
True
>>> p24.coups()
['4,2:N', '6,2:W', '6,4:S', '4,4:E', '4,1:N', '7,4:W', '4,6:S', '4,4:E', '6,6:W', '6,4:N', '4,7:S', '2,4:E', '4,4:N', '2,6:S', '4,6:W', '1,4:E', '2,2:N', '2,4:E', '4,4:S', '4,2:W']

Enoncé et solution de E.Lucas

p25

Charger le problème et afficher l'objectif⚓︎

>>> p25 = Solitaire("EL25")
>>> p25.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ○  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ○  ●  ○  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ○  ○  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ●  ○  ●  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ○  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p25.solution([(42, 44), (45, 43), (24, 44), (43, 45), (64, 44), (56, 54), (54, 34), (36, 56), (34, 36), (15, 35), (57, 55), (37, 57), (35, 37), (13, 15), (33, 13), (31, 33), (51, 31), (53, 51), (73, 53), (75, 73), (55, 75)])
True
>>> p25.coups()
['4,2:N', '4,5:S', '2,4:E', '4,3:N', '6,4:W', '5,6:S', '5,4:W', '3,6:E', '3,4:N', '1,5:E', '5,7:S', '3,7:E', '3,5:N', '1,3:N', '3,3:W', '3,1:N', '5,1:W', '5,3:S', '7,3:W', '7,5:S', '5,5:E']

Enoncé et solution de E.Lucas

p26

Charger le problème et afficher l'objectif⚓︎

>>> p26 = Solitaire("EL26")
>>> p26.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ○  ●          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ●  ○  ○  ○  ○  ○  ●    
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ●  ○  ○  ○  ○  ○  ●    
2        ●  ●  ●  ●  ●            2        ●  ○  ○  ○  ●       
1           ●  ●  ●               1           ●  ○  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p26.solution([(42, 44), (63, 43), (51, 53), (31, 51), (33, 31), (53, 33), (23, 43), (35, 33), (33, 53), (14, 34), (44, 24), (46, 44), (26, 46), (24, 26), (47, 45), (66, 46), (54, 56), (46, 66), (74, 54), (75, 55), (45, 65), (53, 55), (55, 75)])
True
>>> p26.coups()
['4,2:N', '6,3:W', '5,1:N', '3,1:E', '3,3:S', '5,3:W', '2,3:E', '3,5:S', '3,3:E', '1,4:E', '4,4:W', '4,6:S', '2,6:E', '2,4:N', '4,7:S', '6,6:W', '5,4:N', '4,6:E', '7,4:W', '7,5:W', '4,5:E', '5,3:N', '5,5:E']

Enoncé et solution de E.Lucas

p27

Charger le problème et afficher l'objectif⚓︎

>>> p27 = Solitaire("EL27")
>>> p27.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ○  ○  ○          
6        ●  ●  ●  ●  ●            6        ●  ○  ○  ○  ●       
5     ●  ●  ●  ●  ●  ●  ●         5     ○  ○  ●  ○  ●  ○  ○    
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ●  ●  ●  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ○  ○  ○  ●  ○  ○  ○    
2        ●  ●  ●  ●  ●            2        ○  ○  ●  ○  ○       
1           ●  ●  ●               1           ●  ●  ●          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p27.solution([(46, 44), (65, 45), (57, 55), (37, 57), (54, 56), (57, 55), (45, 65), (52, 54), (32, 52), (34, 32), (36, 34), (15, 35), (22, 42), (13, 33), (34, 32), (14, 34), (75, 55), (55, 53), (74, 54), (53, 55), (73, 53), (52, 54), (32, 52), (62, 42)])
True
>>> p27.coups()
['4,6:S', '6,5:W', '5,7:S', '3,7:E', '5,4:N', '5,7:S', '4,5:E', '5,2:N', '3,2:E', '3,4:S', '3,6:S', '1,5:E', '2,2:E', '1,3:E', '3,4:S', '1,4:E', '7,5:W', '5,5:S', '7,4:W', '5,3:N', '7,3:W', '5,2:N', '3,2:E', '6,2:W']

Enoncé et solution de E.Lucas

p28

Charger le problème et afficher l'objectif⚓︎

>>> p28 = Solitaire("EL28")
>>> p28.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ○  ○  ○          
6        ●  ●  ●  ●  ●            6        ○  ○  ●  ○  ○       
5     ●  ●  ●  ●  ●  ●  ●         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ○  ○  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ○  ●  ○  ○  ○  ●  ○    
2        ●  ●  ●  ●  ●            2        ○  ○  ○  ○  ○       
1           ●  ●  ●               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p28.solution([(46, 44), (25, 45), (37, 35), (45, 25), (15, 35), (34, 36), (26, 46), (54, 34), (65, 45), (57, 55), (45, 65), (75, 55), (74, 54), (54, 56), (47, 45), (66, 46), (52, 54), (32, 52), (34, 32), (14, 34), (62, 42), (42, 44), (73, 53), (54, 52), (22, 42), (13, 33), (34, 32), (45, 43), (31, 33), (43, 23), (41, 43), (51, 53), (43, 63)])
True
>>> p28.coups()
['4,6:S', '2,5:E', '3,7:S', '4,5:W', '1,5:E', '3,4:N', '2,6:E', '5,4:W', '6,5:W', '5,7:S', '4,5:E', '7,5:W', '7,4:W', '5,4:N', '4,7:S', '6,6:W', '5,2:N', '3,2:E', '3,4:S', '1,4:E', '6,2:W', '4,2:N', '7,3:W', '5,4:S', '2,2:E', '1,3:E', '3,4:S', '4,5:S', '3,1:N', '4,3:W', '4,1:N', '5,1:N', '4,3:E']

Enoncé et solution de E.Lucas

p29

Charger le problème et afficher l'objectif⚓︎

>>> p29 = Solitaire("EL29")
>>> p29.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ○  ●  ○          
6        ●  ●  ●  ●  ●            6        ○  ○  ○  ○  ○       
5     ●  ●  ●  ●  ●  ●  ●         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ○  ○  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ○  ○  ○  ○  ○  ○  ○    
2        ●  ●  ●  ●  ●            2        ○  ○  ○  ○  ○       
1           ●  ●  ●               1           ○  ●  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p29.solution([(46, 44), (25, 45), (37, 35), (45, 25), (15, 35), (34, 36), (26, 46), (54, 34), (65, 45), (57, 55), (45, 65), (75, 55), (74, 54), (54, 56), (47, 45), (66, 46), (52, 54), (32, 52), (34, 32), (14, 34), (45, 47), (73, 53), (62, 42), (54, 52), (51, 53), (53, 33), (41, 43), (22, 42), (34, 32), (13, 33), (43, 23), (31, 33), (23, 43), (43, 41)])
True
>>> p29.coups()
['4,6:S', '2,5:E', '3,7:S', '4,5:W', '1,5:E', '3,4:N', '2,6:E', '5,4:W', '6,5:W', '5,7:S', '4,5:E', '7,5:W', '7,4:W', '5,4:N', '4,7:S', '6,6:W', '5,2:N', '3,2:E', '3,4:S', '1,4:E', '4,5:N', '7,3:W', '6,2:W', '5,4:S', '5,1:N', '5,3:W', '4,1:N', '2,2:E', '3,4:S', '1,3:E', '4,3:W', '3,1:N', '2,3:E', '4,3:S']

Enoncé et solution de E.Lucas

p30

Charger le problème et afficher l'objectif⚓︎

>>> p30 = Solitaire("EL30")
>>> p30.goal()

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ○  ○          
6        ●  ●  ●  ●  ●            6        ○  ○  ○  ○  ○       
5     ●  ●  ●  ●  ●  ●  ●         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ●  ●  ●  ●         4     ○  ○  ○  ○  ○  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ○  ○  ○  ○  ○  ○  ○    
2        ●  ●  ●  ●  ●            2        ○  ○  ○  ○  ○       
1           ●  ●  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

Tester la solution de E. Lucas⚓︎

>>> p30.solution([(53, 51), (73, 53), (65, 63), (62, 64), (75, 73), (54, 52), (51, 53), (43, 63), (73, 53), (23, 43), (25, 23), (45, 25), (47, 45), (31, 33), (33, 35), (13, 33), (43, 23), (22, 24), (14, 34), (35, 33), (15, 35), (45, 25), (26, 24), (37, 35), (66, 46), (41, 43), (43, 23), (23, 25), (25, 45), (45, 65), (65, 63), (63, 43), (43, 45), (45, 47), (57, 37)])
True
>>> p30.coups()
['5,3:S', '7,3:W', '6,5:S', '6,2:N', '7,5:S', '5,4:S', '5,1:N', '4,3:E', '7,3:W', '2,3:E', '2,5:S', '4,5:W', '4,7:S', '3,1:N', '3,3:N', '1,3:E', '4,3:W', '2,2:N', '1,4:E', '3,5:S', '1,5:E', '4,5:W', '2,6:S', '3,7:S', '6,6:W', '4,1:N', '4,3:W', '2,3:N', '2,5:E', '4,5:E', '6,5:S', '6,3:W', '4,3:N', '4,5:N', '5,7:W']

Ces problèmes mettent à mal l'heuristique du nombre relatif d'encoches bloquées car :

certains offrent un motif final particulier où le pourtour du tablier reste plein,
les derniers demandent de ne laisser que 1 à 3 encoches pleines et sont donc fortement combinatoires.

Il faudrait trouver une autre heuristique pour les problèmes qui justement laissent des encoches pleines sur le pourtour du solitaire. Et pour aller encore plus loin, il serait probablement nécessaire de passer à une implémentation en C et trouver d'autres optimisations, comme par exemple les symétries dont fait état E. Lucas dans son ouvrage.

Notons que le beam search permet de résoudre les problèmes classiques de Solitaire :

P30Solitaire anglaisVariante de P30

Rappel de l'objectif⚓︎

---------- Initial -----------     ----------- Final ------------
8                                 8                            
7           ●  ●  ●               7           ●  ○  ○          
6        ●  ●  ●  ●  ●            6        ○  ○  ○  ○  ○       
5     ●  ●  ●  ●  ●  ●  ●         5     ○  ○  ○  ○  ○  ○  ○    
4     ●  ●  ●  ●  ●  ●  ●         4     ○  ○  ○  ○  ○  ○  ○    
3     ●  ●  ●  ●  ●  ●  ●         3     ○  ○  ○  ○  ○  ○  ○    
2        ●  ●  ●  ●  ●            2        ○  ○  ○  ○  ○       
1           ●  ●  ○               1           ○  ○  ○          
0                                 0                            
   0  1  2  3  4  5  6  7  8        0  1  2  3  4  5  6  7  8

La solution⚓︎

>>> p30.explored
15380
>>> p30.coups()
['3,1:E', '4,3:S', '6,3:W', '6,5:S', '4,5:E', '2,2:E', '3,4:S', '1,3:E', '4,7:S', '2,6:E', '7,3:W', '4,3:E', '5,1:N', '5,4:W', '3,4:N', '3,7:S', '6,6:S', '7,4:W', '6,2:N', '4,1:N', '4,3:E', '5,7:S', '5,4:N', '6,3:N', '7,5:W', '1,5:S', '3,2:N', '2,5:S', '1,3:E', '4,5:W', '3,3:N', '2,5:E', '5,6:W', '5,5:W', '3,5:N']

Trace complète

--- motif 1/36 None:
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ●  ●  ●  ●
4     ●  ●  ●  ●  ●  ●  ●
3     ●  ●  ●  ●  ●  ●  ●
2        ●  ●  ●  ●  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 2/36 (3, 1):E
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ●  ●  ●  ●
4     ●  ●  ●  ●  ●  ●  ●
3     ●  ●  ●  ●  ●  ●  ●
2        ●  ●  ●  ●  ●
1           ○  ○  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 3/36 (4, 3):S
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ●  ●  ●  ●
4     ●  ●  ●  ●  ●  ●  ●
3     ●  ●  ●  ○  ●  ●  ●
2        ●  ●  ○  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 4/36 (6, 3):W
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ●  ●  ●  ●
4     ●  ●  ●  ●  ●  ●  ●
3     ●  ●  ●  ●  ○  ○  ●
2        ●  ●  ○  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 5/36 (6, 5):S
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ●  ●  ○  ●
4     ●  ●  ●  ●  ●  ○  ●
3     ●  ●  ●  ●  ○  ●  ●
2        ●  ●  ○  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 6/36 (4, 5):E
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ○  ○  ●  ●
4     ●  ●  ●  ●  ●  ○  ●
3     ●  ●  ●  ●  ○  ●  ●
2        ●  ●  ○  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 7/36 (2, 2):E
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ○  ○  ●  ●
4     ●  ●  ●  ●  ●  ○  ●
3     ●  ●  ●  ●  ○  ●  ●
2        ○  ○  ●  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 8/36 (3, 4):S
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ○  ○  ●  ●
4     ●  ●  ○  ●  ●  ○  ●
3     ●  ●  ○  ●  ○  ●  ●
2        ○  ●  ●  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 9/36 (1, 3):E
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ○  ○  ●  ●
4     ●  ●  ○  ●  ●  ○  ●
3     ○  ○  ●  ●  ○  ●  ●
2        ○  ●  ●  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 10/36 (4, 7):S
8
7           ●  ○  ●
6        ●  ●  ○  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ●  ○  ●  ●  ○  ●
3     ○  ○  ●  ●  ○  ●  ●
2        ○  ●  ●  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 11/36 (2, 6):E
8
7           ●  ○  ●
6        ○  ○  ●  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ●  ○  ●  ●  ○  ●
3     ○  ○  ●  ●  ○  ●  ●
2        ○  ●  ●  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 12/36 (7, 3):W
8
7           ●  ○  ●
6        ○  ○  ●  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ●  ○  ●  ●  ○  ●
3     ○  ○  ●  ●  ●  ○  ○
2        ○  ●  ●  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 13/36 (4, 3):E
8
7           ●  ○  ●
6        ○  ○  ●  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ●  ○  ●  ●  ○  ●
3     ○  ○  ●  ○  ○  ●  ○
2        ○  ●  ●  ●  ●
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 14/36 (5, 1):N
8
7           ●  ○  ●
6        ○  ○  ●  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ●  ○  ●  ●  ○  ●
3     ○  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ○  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 15/36 (5, 4):W
8
7           ●  ○  ●
6        ○  ○  ●  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ●  ●  ○  ○  ○  ●
3     ○  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ○  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 16/36 (3, 4):N
8
7           ●  ○  ●
6        ○  ●  ●  ●  ●
5     ●  ●  ○  ●  ○  ●  ●
4     ●  ●  ○  ○  ○  ○  ●
3     ○  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ○  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 17/36 (3, 7):S
8
7           ○  ○  ●
6        ○  ○  ●  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ●  ○  ○  ○  ○  ●
3     ○  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ○  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 18/36 (6, 6):S
8
7           ○  ○  ●
6        ○  ○  ●  ●  ○
5     ●  ●  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ○  ●  ●
3     ○  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ○  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 19/36 (7, 4):W
8
7           ○  ○  ●
6        ○  ○  ●  ●  ○
5     ●  ●  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ○  ○
3     ○  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ○  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 20/36 (6, 2):N
8
7           ○  ○  ●
6        ○  ○  ●  ●  ○
5     ●  ●  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ○
3     ○  ○  ●  ○  ●  ○  ○
2        ○  ●  ●  ○  ○
1           ○  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 21/36 (4, 1):N
8
7           ○  ○  ●
6        ○  ○  ●  ●  ○
5     ●  ●  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ○
3     ○  ○  ●  ●  ●  ○  ○
2        ○  ●  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 22/36 (4, 3):E
8
7           ○  ○  ●
6        ○  ○  ●  ●  ○
5     ●  ●  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ○
3     ○  ○  ●  ○  ○  ●  ○
2        ○  ●  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 23/36 (5, 7):S
8
7           ○  ○  ○
6        ○  ○  ●  ○  ○
5     ●  ●  ●  ●  ●  ○  ●
4     ●  ●  ○  ○  ●  ●  ○
3     ○  ○  ●  ○  ○  ●  ○
2        ○  ●  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 24/36 (5, 4):N
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ●  ●  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ○  ●  ○
3     ○  ○  ●  ○  ○  ●  ○
2        ○  ●  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 25/36 (6, 3):N
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ●  ○  ○  ○  ○  ○
3     ○  ○  ●  ○  ○  ○  ○
2        ○  ●  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 26/36 (7, 5):W
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ●  ●  ●  ●  ●  ○  ○
4     ●  ●  ○  ○  ○  ○  ○
3     ○  ○  ●  ○  ○  ○  ○
2        ○  ●  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 27/36 (1, 5):S
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ○  ●  ●  ●  ●  ○  ○
4     ○  ●  ○  ○  ○  ○  ○
3     ●  ○  ●  ○  ○  ○  ○
2        ○  ●  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 28/36 (3, 2):N
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ○  ●  ●  ●  ●  ○  ○
4     ○  ●  ●  ○  ○  ○  ○
3     ●  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 29/36 (2, 5):S
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ○  ○  ●  ●  ●  ○  ○
4     ○  ○  ●  ○  ○  ○  ○
3     ●  ●  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 30/36 (1, 3):E
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ○  ○  ●  ●  ●  ○  ○
4     ○  ○  ●  ○  ○  ○  ○
3     ○  ○  ●  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 31/36 (4, 5):W
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ○  ●  ○  ○  ●  ○  ○
4     ○  ○  ●  ○  ○  ○  ○
3     ○  ○  ●  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 32/36 (3, 3):N
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ○  ●  ●  ○  ●  ○  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 33/36 (2, 5):E
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ○  ○  ○  ●  ●  ○  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 34/36 (5, 6):W
8
7           ○  ○  ○
6        ○  ●  ○  ○  ○
5     ○  ○  ○  ●  ●  ○  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 35/36 (5, 5):W
8
7           ○  ○  ○
6        ○  ●  ○  ○  ○
5     ○  ○  ●  ○  ○  ○  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 36/36 (3, 5):N
8
7           ●  ○  ○
6        ○  ○  ○  ○  ○
5     ○  ○  ○  ○  ○  ○  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8

Rappel de l'objectif⚓︎

---------- Initial ----------     ----------- Final -----------
8                                 8
7           ●  ●  ●               7           ○  ○  ○
6           ●  ●  ●               6           ○  ○  ○
5     ●  ●  ●  ●  ●  ●  ●         5     ○  ○  ○  ○  ○  ○  ○
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○
3     ●  ●  ●  ●  ●  ●  ●         3     ○  ○  ○  ○  ○  ○  ○
2           ●  ●  ●               2           ○  ○  ○
1           ●  ●  ●               1           ○  ○  ○
0                                 0
   0  1  2  3  4  5  6  7  8         0  1  2  3  4  5  6  7  8

La solution⚓︎

>>> ang.explored
1704
>>> ang.coups()
['4,6:S', '2,5:E', '3,3:N', '4,4:N', '6,5:W', '5,7:S', '5,4:N', '5,2:N', '7,3:W', '3,7:E', '3,6:S', '3,1:N', '3,4:S', '1,3:E', '4,3:W', '1,5:S', '1,3:E', '3,2:N', '7,5:S', '4,1:N', '4,3:E', '5,7:S', '7,3:W', '4,5:E', '6,5:S', '5,4:S', '5,1:N', '2,4:E', '6,3:W', '4,3:N', '4,6:S']

Trace complète

--- motif 1/32 None:
8
7           ●  ●  ●
6           ●  ●  ●
5     ●  ●  ●  ●  ●  ●  ●
4     ●  ●  ●  ○  ●  ●  ●
3     ●  ●  ●  ●  ●  ●  ●
2           ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 2/32 (4, 6):S
8
7           ●  ●  ●
6           ●  ○  ●
5     ●  ●  ●  ○  ●  ●  ●
4     ●  ●  ●  ●  ●  ●  ●
3     ●  ●  ●  ●  ●  ●  ●
2           ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 3/32 (2, 5):E
8
7           ●  ●  ●
6           ●  ○  ●
5     ●  ○  ○  ●  ●  ●  ●
4     ●  ●  ●  ●  ●  ●  ●
3     ●  ●  ●  ●  ●  ●  ●
2           ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 4/32 (3, 3):N
8
7           ●  ●  ●
6           ●  ○  ●
5     ●  ○  ●  ●  ●  ●  ●
4     ●  ●  ○  ●  ●  ●  ●
3     ●  ●  ○  ●  ●  ●  ●
2           ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 5/32 (4, 4):N
8
7           ●  ●  ●
6           ●  ●  ●
5     ●  ○  ●  ○  ●  ●  ●
4     ●  ●  ○  ○  ●  ●  ●
3     ●  ●  ○  ●  ●  ●  ●
2           ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 6/32 (6, 5):W
8
7           ●  ●  ●
6           ●  ●  ●
5     ●  ○  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ●
3     ●  ●  ○  ●  ●  ●  ●
2           ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 7/32 (5, 7):S
8
7           ●  ●  ○
6           ●  ●  ○
5     ●  ○  ●  ●  ●  ○  ●
4     ●  ●  ○  ○  ●  ●  ●
3     ●  ●  ○  ●  ●  ●  ●
2           ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 8/32 (5, 4):N
8
7           ●  ●  ○
6           ●  ●  ●
5     ●  ○  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ○  ●  ●
3     ●  ●  ○  ●  ●  ●  ●
2           ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 9/32 (5, 2):N
8
7           ●  ●  ○
6           ●  ●  ●
5     ●  ○  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ●
3     ●  ●  ○  ●  ○  ●  ●
2           ●  ●  ○
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 10/32 (7, 3):W
8
7           ●  ●  ○
6           ●  ●  ●
5     ●  ○  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ●
3     ●  ●  ○  ●  ●  ○  ○
2           ●  ●  ○
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 11/32 (3, 7):E
8
7           ○  ○  ●
6           ●  ●  ●
5     ●  ○  ●  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ●
3     ●  ●  ○  ●  ●  ○  ○
2           ●  ●  ○
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 12/32 (3, 6):S
8
7           ○  ○  ●
6           ○  ●  ●
5     ●  ○  ○  ●  ○  ○  ●
4     ●  ●  ●  ○  ●  ●  ●
3     ●  ●  ○  ●  ●  ○  ○
2           ●  ●  ○
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 13/32 (3, 1):N
8
7           ○  ○  ●
6           ○  ●  ●
5     ●  ○  ○  ●  ○  ○  ●
4     ●  ●  ●  ○  ●  ●  ●
3     ●  ●  ●  ●  ●  ○  ○
2           ○  ●  ○
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 14/32 (3, 4):S
8
7           ○  ○  ●
6           ○  ●  ●
5     ●  ○  ○  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ●
3     ●  ●  ○  ●  ●  ○  ○
2           ●  ●  ○
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 15/32 (1, 3):E
8
7           ○  ○  ●
6           ○  ●  ●
5     ●  ○  ○  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ●
3     ○  ○  ●  ●  ●  ○  ○
2           ●  ●  ○
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 16/32 (4, 3):W
8
7           ○  ○  ●
6           ○  ●  ●
5     ●  ○  ○  ●  ○  ○  ●
4     ●  ●  ○  ○  ●  ●  ●
3     ○  ●  ○  ○  ●  ○  ○
2           ●  ●  ○
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 17/32 (1, 5):S
8
7           ○  ○  ●
6           ○  ●  ●
5     ○  ○  ○  ●  ○  ○  ●
4     ○  ●  ○  ○  ●  ●  ●
3     ●  ●  ○  ○  ●  ○  ○
2           ●  ●  ○
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 18/32 (1, 3):E
8
7           ○  ○  ●
6           ○  ●  ●
5     ○  ○  ○  ●  ○  ○  ●
4     ○  ●  ○  ○  ●  ●  ●
3     ○  ○  ●  ○  ●  ○  ○
2           ●  ●  ○
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 19/32 (3, 2):N
8
7           ○  ○  ●
6           ○  ●  ●
5     ○  ○  ○  ●  ○  ○  ●
4     ○  ●  ●  ○  ●  ●  ●
3     ○  ○  ○  ○  ●  ○  ○
2           ○  ●  ○
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 20/32 (7, 5):S
8
7           ○  ○  ●
6           ○  ●  ●
5     ○  ○  ○  ●  ○  ○  ○
4     ○  ●  ●  ○  ●  ●  ○
3     ○  ○  ○  ○  ●  ○  ●
2           ○  ●  ○
1           ○  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 21/32 (4, 1):N
8
7           ○  ○  ●
6           ○  ●  ●
5     ○  ○  ○  ●  ○  ○  ○
4     ○  ●  ●  ○  ●  ●  ○
3     ○  ○  ○  ●  ●  ○  ●
2           ○  ○  ○
1           ○  ○  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 22/32 (4, 3):E
8
7           ○  ○  ●
6           ○  ●  ●
5     ○  ○  ○  ●  ○  ○  ○
4     ○  ●  ●  ○  ●  ●  ○
3     ○  ○  ○  ○  ○  ●  ●
2           ○  ○  ○
1           ○  ○  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 23/32 (5, 7):S
8
7           ○  ○  ○
6           ○  ●  ○
5     ○  ○  ○  ●  ●  ○  ○
4     ○  ●  ●  ○  ●  ●  ○
3     ○  ○  ○  ○  ○  ●  ●
2           ○  ○  ○
1           ○  ○  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 24/32 (7, 3):W
8
7           ○  ○  ○
6           ○  ●  ○
5     ○  ○  ○  ●  ●  ○  ○
4     ○  ●  ●  ○  ●  ●  ○
3     ○  ○  ○  ○  ●  ○  ○
2           ○  ○  ○
1           ○  ○  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 25/32 (4, 5):E
8
7           ○  ○  ○
6           ○  ●  ○
5     ○  ○  ○  ○  ○  ●  ○
4     ○  ●  ●  ○  ●  ●  ○
3     ○  ○  ○  ○  ●  ○  ○
2           ○  ○  ○
1           ○  ○  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 26/32 (6, 5):S
8
7           ○  ○  ○
6           ○  ●  ○
5     ○  ○  ○  ○  ○  ○  ○
4     ○  ●  ●  ○  ●  ○  ○
3     ○  ○  ○  ○  ●  ●  ○
2           ○  ○  ○
1           ○  ○  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 27/32 (5, 4):S
8
7           ○  ○  ○
6           ○  ●  ○
5     ○  ○  ○  ○  ○  ○  ○
4     ○  ●  ●  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ●  ○
2           ○  ○  ●
1           ○  ○  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 28/32 (5, 1):N
8
7           ○  ○  ○
6           ○  ●  ○
5     ○  ○  ○  ○  ○  ○  ○
4     ○  ●  ●  ○  ○  ○  ○
3     ○  ○  ○  ○  ●  ●  ○
2           ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 29/32 (2, 4):E
8
7           ○  ○  ○
6           ○  ●  ○
5     ○  ○  ○  ○  ○  ○  ○
4     ○  ○  ○  ●  ○  ○  ○
3     ○  ○  ○  ○  ●  ●  ○
2           ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 30/32 (6, 3):W
8
7           ○  ○  ○
6           ○  ●  ○
5     ○  ○  ○  ○  ○  ○  ○
4     ○  ○  ○  ●  ○  ○  ○
3     ○  ○  ○  ●  ○  ○  ○
2           ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 31/32 (4, 3):N
8
7           ○  ○  ○
6           ○  ●  ○
5     ○  ○  ○  ●  ○  ○  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2           ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 32/32 (4, 6):S
8
7           ○  ○  ○
6           ○  ○  ○
5     ○  ○  ○  ○  ○  ○  ○
4     ○  ○  ○  ●  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2           ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8

Rappel de l'objectif⚓︎

---------- Initial ----------     ----------- Final -----------
8                                 8
7           ●  ●  ●               7           ○  ○  ○
6        ●  ●  ○  ●  ●            6        ○  ○  ○  ○  ○
5     ●  ●  ●  ●  ●  ●  ●         5     ○  ○  ○  ●  ○  ○  ○
4     ●  ●  ●  ●  ●  ●  ●         4     ○  ○  ○  ○  ○  ○  ○
3     ●  ●  ●  ●  ●  ●  ●         3     ○  ○  ○  ○  ○  ○  ○
2        ●  ●  ●  ●  ●            2        ○  ○  ○  ○  ○
1           ●  ●  ●               1           ○  ○  ○
0                                 0
   0  1  2  3  4  5  6  7  8         0  1  2  3  4  5  6  7  8

La solution⚓︎

>>> p30variante.explored
937
>>> p30variante.coups()
['4,4:N', '2,4:E', '6,5:W', '6,3:N', '4,3:E', '5,1:N', '2,6:S', '4,5:W', '1,4:E', '2,2:N', '4,7:S', '6,6:W', '7,5:W', '7,3:N', '4,5:E', '7,5:W', '5,4:N', '5,7:S', '3,4:E', '6,3:W', '4,3:W', '1,3:E', '3,2:E', '6,2:W', '4,1:N', '5,4:N', '3,7:S', '5,6:W', '3,6:S', '3,4:S', '3,1:N', '1,5:E', '4,3:W', '2,3:N', '2,5:E']

Trace complète

--- motif 1/36 None:
8
7           ●  ●  ●
6        ●  ●  ○  ●  ●
5     ●  ●  ●  ●  ●  ●  ●
4     ●  ●  ●  ●  ●  ●  ●
3     ●  ●  ●  ●  ●  ●  ●
2        ●  ●  ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 2/36 (4, 4):N
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ○  ●  ●  ●
4     ●  ●  ●  ○  ●  ●  ●
3     ●  ●  ●  ●  ●  ●  ●
2        ●  ●  ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 3/36 (2, 4):E
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ○  ●  ●  ●
4     ●  ○  ○  ●  ●  ●  ●
3     ●  ●  ●  ●  ●  ●  ●
2        ●  ●  ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 4/36 (6, 5):W
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ●  ○  ○  ●
4     ●  ○  ○  ●  ●  ●  ●
3     ●  ●  ●  ●  ●  ●  ●
2        ●  ●  ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 5/36 (6, 3):N
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ○  ○  ●  ●  ○  ●
3     ●  ●  ●  ●  ●  ○  ●
2        ●  ●  ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 6/36 (4, 3):E
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ○  ○  ●  ●  ○  ●
3     ●  ●  ●  ○  ○  ●  ●
2        ●  ●  ●  ●  ●
1           ●  ●  ●
0
   0  1  2  3  4  5  6  7  8
--- motif 7/36 (5, 1):N
8
7           ●  ●  ●
6        ●  ●  ●  ●  ●
5     ●  ●  ●  ●  ○  ●  ●
4     ●  ○  ○  ●  ●  ○  ●
3     ●  ●  ●  ○  ●  ●  ●
2        ●  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 8/36 (2, 6):S
8
7           ●  ●  ●
6        ○  ●  ●  ●  ●
5     ●  ○  ●  ●  ○  ●  ●
4     ●  ●  ○  ●  ●  ○  ●
3     ●  ●  ●  ○  ●  ●  ●
2        ●  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 9/36 (4, 5):W
8
7           ●  ●  ●
6        ○  ●  ●  ●  ●
5     ●  ●  ○  ○  ○  ●  ●
4     ●  ●  ○  ●  ●  ○  ●
3     ●  ●  ●  ○  ●  ●  ●
2        ●  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 10/36 (1, 4):E
8
7           ●  ●  ●
6        ○  ●  ●  ●  ●
5     ●  ●  ○  ○  ○  ●  ●
4     ○  ○  ●  ●  ●  ○  ●
3     ●  ●  ●  ○  ●  ●  ●
2        ●  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 11/36 (2, 2):N
8
7           ●  ●  ●
6        ○  ●  ●  ●  ●
5     ●  ●  ○  ○  ○  ●  ●
4     ○  ●  ●  ●  ●  ○  ●
3     ●  ○  ●  ○  ●  ●  ●
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 12/36 (4, 7):S
8
7           ●  ○  ●
6        ○  ●  ○  ●  ●
5     ●  ●  ○  ●  ○  ●  ●
4     ○  ●  ●  ●  ●  ○  ●
3     ●  ○  ●  ○  ●  ●  ●
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 13/36 (6, 6):W
8
7           ●  ○  ●
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ●  ○  ●  ●
4     ○  ●  ●  ●  ●  ○  ●
3     ●  ○  ●  ○  ●  ●  ●
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 14/36 (7, 5):W
8
7           ●  ○  ●
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ●  ●  ○  ○
4     ○  ●  ●  ●  ●  ○  ●
3     ●  ○  ●  ○  ●  ●  ●
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 15/36 (7, 3):N
8
7           ●  ○  ●
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ●  ●  ○  ●
4     ○  ●  ●  ●  ●  ○  ○
3     ●  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 16/36 (4, 5):E
8
7           ●  ○  ●
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ○  ●  ●
4     ○  ●  ●  ●  ●  ○  ○
3     ●  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 17/36 (7, 5):W
8
7           ●  ○  ●
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ●  ○  ○
4     ○  ●  ●  ●  ●  ○  ○
3     ●  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 18/36 (5, 4):N
8
7           ●  ○  ●
6        ○  ●  ●  ●  ○
5     ●  ●  ○  ○  ○  ○  ○
4     ○  ●  ●  ●  ○  ○  ○
3     ●  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 19/36 (5, 7):S
8
7           ●  ○  ○
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ●  ○  ○
4     ○  ●  ●  ●  ○  ○  ○
3     ●  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 20/36 (3, 4):E
8
7           ●  ○  ○
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ●  ○  ○
4     ○  ●  ○  ○  ●  ○  ○
3     ●  ○  ●  ○  ●  ●  ○
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 21/36 (6, 3):W
8
7           ●  ○  ○
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ●  ○  ○
4     ○  ●  ○  ○  ●  ○  ○
3     ●  ○  ●  ●  ○  ○  ○
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 22/36 (4, 3):W
8
7           ●  ○  ○
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ●  ○  ○
4     ○  ●  ○  ○  ●  ○  ○
3     ●  ●  ○  ○  ○  ○  ○
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 23/36 (1, 3):E
8
7           ●  ○  ○
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ●  ○  ○
4     ○  ●  ○  ○  ●  ○  ○
3     ○  ○  ●  ○  ○  ○  ○
2        ○  ●  ●  ○  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 24/36 (3, 2):E
8
7           ●  ○  ○
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ●  ○  ○
4     ○  ●  ○  ○  ●  ○  ○
3     ○  ○  ●  ○  ○  ○  ○
2        ○  ○  ○  ●  ●
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 25/36 (6, 2):W
8
7           ●  ○  ○
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ●  ○  ○
4     ○  ●  ○  ○  ●  ○  ○
3     ○  ○  ●  ○  ○  ○  ○
2        ○  ○  ●  ○  ○
1           ●  ●  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 26/36 (4, 1):N
8
7           ●  ○  ○
6        ○  ●  ●  ○  ○
5     ●  ●  ○  ○  ●  ○  ○
4     ○  ●  ○  ○  ●  ○  ○
3     ○  ○  ●  ●  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ●  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 27/36 (5, 4):N
8
7           ●  ○  ○
6        ○  ●  ●  ●  ○
5     ●  ●  ○  ○  ○  ○  ○
4     ○  ●  ○  ○  ○  ○  ○
3     ○  ○  ●  ●  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ●  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 28/36 (3, 7):S
8
7           ○  ○  ○
6        ○  ○  ●  ●  ○
5     ●  ●  ●  ○  ○  ○  ○
4     ○  ●  ○  ○  ○  ○  ○
3     ○  ○  ●  ●  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ●  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 29/36 (5, 6):W
8
7           ○  ○  ○
6        ○  ●  ○  ○  ○
5     ●  ●  ●  ○  ○  ○  ○
4     ○  ●  ○  ○  ○  ○  ○
3     ○  ○  ●  ●  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ●  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 30/36 (3, 6):S
8
7           ○  ○  ○
6        ○  ○  ○  ○  ○
5     ●  ●  ○  ○  ○  ○  ○
4     ○  ●  ●  ○  ○  ○  ○
3     ○  ○  ●  ●  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ●  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 31/36 (3, 4):S
8
7           ○  ○  ○
6        ○  ○  ○  ○  ○
5     ●  ●  ○  ○  ○  ○  ○
4     ○  ●  ○  ○  ○  ○  ○
3     ○  ○  ○  ●  ○  ○  ○
2        ○  ●  ○  ○  ○
1           ●  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 32/36 (3, 1):N
8
7           ○  ○  ○
6        ○  ○  ○  ○  ○
5     ●  ●  ○  ○  ○  ○  ○
4     ○  ●  ○  ○  ○  ○  ○
3     ○  ○  ●  ●  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 33/36 (1, 5):E
8
7           ○  ○  ○
6        ○  ○  ○  ○  ○
5     ○  ○  ●  ○  ○  ○  ○
4     ○  ●  ○  ○  ○  ○  ○
3     ○  ○  ●  ●  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 34/36 (4, 3):W
8
7           ○  ○  ○
6        ○  ○  ○  ○  ○
5     ○  ○  ●  ○  ○  ○  ○
4     ○  ●  ○  ○  ○  ○  ○
3     ○  ●  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 35/36 (2, 3):N
8
7           ○  ○  ○
6        ○  ○  ○  ○  ○
5     ○  ●  ●  ○  ○  ○  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8
--- motif 36/36 (2, 5):E
8
7           ○  ○  ○
6        ○  ○  ○  ○  ○
5     ○  ○  ○  ●  ○  ○  ○
4     ○  ○  ○  ○  ○  ○  ○
3     ○  ○  ○  ○  ○  ○  ○
2        ○  ○  ○  ○  ○
1           ○  ○  ○
0
   0  1  2  3  4  5  6  7  8

Certains problèmes ne sont pas solubles⚓︎

Il existe une preuve élégante basée sur le typage des encoches en 3 types : A, B, C. L'idée serait de Hans Zantema mais impossible de trouver une référence à cette preuve.

Bien sûr le typage ne doit pas se faire n'importe comment car on souhaite conserver l'invariant suivant : à chaque coup 2 des types diminuent de 1 et le 3e augmente de 1. Ainsi la parité de chaque type change à chacun des coups.

Un balayage de haut en bas et de gauche à droite en alternant A, B et C (en réalité 0, 1 et 2) convient :

typer

class Solitaire:
    # ...
    def typer(self):
        self.types = {}
        d_tmp = {}
        typ = -1
        for y in range(self.h):
            typ = 0 if typ == -1 else (d_tmp[0, y-1] + 1) % 3
            for x in range(self.w):
                d_tmp[x, y] = typ
                if self.inside(x, y):
                    self.types[x, y] = typ
                typ = (typ + 1) % 3

Voici ce que donne ce typage sur un solitaire européen³ :

Signature Solitaire européen

>>> impossible = Solitaire('No37')
>>> impossible.signature(True)

8
7           B  C  A
6        C  A  B  C  A
5     A  B  C  A  B  C  A
4     C  A  B  C  A  B  C
3     B  C  A  B  C  A  B
2        B  C  A  B  C
1           B  C  A
0
   0  1  2  3  4  5  6  7  8

Dès lors on peut typer un motif par :

la parité du nombre de coups simples depuis le motif initial
le triplet des quantités d'encoches de type A, B et C

Signature d'un motif

class Motif:
    # ...
    def signature(self):
        parite = (sum(self.solitaire.initial.encoches.values()) - sum(self.encoches.values())) % 2
        sig = [0, 0, 0]
        for x, y in self.encoches:
            if self.encoches[x, y] == PLEIN:
                sig[self.solitaire.types[x,y]] += 1
        return parite, sig

>>> impossible.goal()

---------- Initial ----------     ----------- Final -----------
8                                 8
7           ●  ●  ●               7           ○  ○  ○
6        ●  ●  ●  ●  ●            6        ○  ○  ○  ○  ○
5     ●  ●  ●  ●  ●  ●  ●         5     ○  ○  ○  ○  ○  ○  ○
4     ●  ●  ●  ○  ●  ●  ●         4     ○  ○  ○  ●  ○  ○  ○
3     ●  ●  ●  ●  ●  ●  ●         3     ○  ○  ○  ○  ○  ○  ○
2        ●  ●  ●  ●  ●            2        ○  ○  ○  ○  ○
1           ●  ●  ●               1           ○  ○  ○
0                                 0
   0  1  2  3  4  5  6  7  8         0  1  2  3  4  5  6  7  8

>>> impossible.initial.signature()
(0, [12, 12, 12])
>>> impossible.final.signature()
(1, [0, 0, 1])

A chaque coup simple, la parité de chacun des types A, B et C change. Ainsi, on peut prévoir en fonction de la signature des motifs initial et final et de la parité du nombre de coups nécessaire pour passer du premier au second que le problème est insoluble. Attention, ne pas répondre True à la question de l'insolubilité du problème ne garantit pas qu'on puisse répondre True.

nopath

class Motif:
    # ...

    def nopath(self, m):
        p1, s1 = self.signature()
        p2, s2 = m.signature()
        s1 = parite(s1)
        s2 = parite(s2)
        if (p1 == p2 and s1 != s2) or (p1 == (not p2) and s1 != non(s2)):
            return True

class Solitaire:
    # ...
    def nopath(self):
        if self.initial.nopath(self.final):
            return True

Commencer avec l'encoche vide au centre et terminer avec l'encoche pleine au même endroit est impossible :

>>> impossible.nopath()
True

Téléchargement⚓︎

Le script (à l'état de brouillon) est disponible ici : Solitaire.zip. Cette version ne code que le parcours en largeur.
une version 2 avec parcours en profondeur et beam search, permettant de jouer avec la signature d'un solitaire et d'un motif, la symétrie etc. est disponible ici : Solitaire2.zip.

n.m. petit bâton servant de marque (source : Larousse en ligne) ↩
Extrait de gravure Dame de qualité jouant au Solitaire ↩
Disponible dans la version 2 à télécharger ↩

Le jeu du Solitaire⚓︎

Introduction⚓︎

Historique⚓︎

Objectif⚓︎

Les problèmes d'Édouard Lucas⚓︎

Modéliser les motifs de départ et d'arrivée⚓︎

Résoudre un problème⚓︎

Modéliser un problème⚓︎

La classe Solitaire⚓︎

La classe Motif⚓︎

Manipulations d'un Motif⚓︎

La classe Encoche⚓︎

Résolution automatique : principe général⚓︎

Un parcours de graphe⚓︎

Solution 1 : le parcours en largeur⚓︎

La file⚓︎

Solution 2 : le parcours en profondeur⚓︎

Résolution automatique : les diverses opérations⚓︎

Jouer un coup⚓︎

Coup simple⚓︎

Coup composé⚓︎

Mouvements⚓︎

solve : le coeur de la résolution⚓︎

Premiers résultats et amélioration nécessaire⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Notre solution⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Notre solution⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Notre solution⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Notre solution⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Notre solution⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Notre solution⚓︎

Explosion combinatoire⚓︎

Solution 3 : limiter la largeur de l'arbre⚓︎

Solution 3 bis : le beam search⚓︎

Les problèmes 7 à 12⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Suite des problèmes : de 13 à 30⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

Tester la solution de E. Lucas⚓︎

Charger le problème et afficher l'objectif⚓︎

La classe `Solitaire`⚓︎

La classe `Motif`⚓︎

Manipulations d'un `Motif`⚓︎

La classe `Encoche`⚓︎

`solve` : le coeur de la résolution⚓︎