chemin — Recherche du score maximal d’un jeu

Usage

Solve a game (see documentation for the game description).

usage: chemin [-h] [-v] [-j JOBS]

Named Arguments

-v, --version show program’s version number and exit
-j, --jobs

Number of jobs to run simultaneously.

Default: 4

Two arrays are displayed: the resulting array, and the array of the steps used to build this resulting array.

Description du jeu

Dans un carré 3x3, on remplit une à une les 9 cases, avec la règle suivante :
  • si toutes les cases entourant la case sont vides, inscrire 1 ;
  • sinon, inscrire la somme des nombres présents dans toutes les cases adjacentes (diagonales incluses).

Le jeu se termine lorsque toutes les cases sont pleines, et le score est la plus grande valeur écrite dans le tableau.

Voici un exemple de jeu, avec un score de 33 :

  1. \[\begin{split}\begin{array}{|c|c|c|} \hline \color{red}{1} & ~~ & \\ \hline & & ~~\\ \hline & & \\ \hline \end{array}\end{split}\]
  2. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & & ~~\\ \hline & \color{red}{1} & \\ \hline & & \\ \hline \end{array}\end{split}\]
  3. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & \color{red}{2} & ~~\\ \hline & 1 & \\ \hline & & \\ \hline \end{array}\end{split}\]
  4. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & 2 & \color{red}{3} \\ \hline & 1 & \\ \hline & & \\ \hline \end{array}\end{split}\]
  5. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline & 1 & \color{red}{6} \\ \hline & & \\ \hline \end{array}\end{split}\]
  6. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline & 1 & 6 \\ \hline & & \color{red}{7} \\ \hline \end{array}\end{split}\]
  7. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline & 1 & 6 \\ \hline & \color{red}{14} & 7 \\ \hline \end{array}\end{split}\]
  8. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline & 1 & 6 \\ \hline \color{red}{15} & 14 & 7 \\ \hline \end{array}\end{split}\]
  9. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline \color{red}{33} & 1 & 6 \\ \hline 15 & 14 & 7 \\ \hline \end{array}\end{split}\]

La question que l’on se pose est : quel est le score maximal possible ?

Recherche de solution optimale

Premières propriétés

Cette partie manque un peu de rigueur, c’est la raison pour laquelle les démonstrations ne sont présentées que comme des ébauches.

Définition 1 (Solutions)
  • On appelle solution l’ordre dans lequel on remplit la grille.
  • On dit qu’une solution est (strictement) supérieure à une autre si le score de la première est (strictement) supérieur au score de la seconde.
  • On appelle solution maximale une solution supérieure à toutes les solutions possibles.
  • Une case réalisant le score d’une solution est une case de la grille complétée contenant la plus grande valeur de la grille (donc le score).

Dans la méthode Solution.score(), la valeur de la dernière case remplie est prise comme le score de cette grille. Deux questions se posent alors.

  • Le score maximal calculé risque-t-il d’être faux, si le score maximal n’est jamais atteint par la dernière case ?
  • Si le score maximal est atteint par la dernière case dans au moins une des grilles, des grilles maximales risquent-elles d’être oubliées, si la case remplissant leur score maximale n’est pas la dernière case remplie ?

Heureusement, la réponse est non :

Propriété 2
Une solution dont la dernère case remplie ne réalise pas le score n’est pas maximale.
Démonstration (Preuve (ébauche))

Supposons qu’il existe une solution \(S\), maximale, dont la dernière case remplie ne réalise pas le score.

Soit \(S'\) la nouvelle solution, identique à \(S\), sauf que les cases remplies après la (ou les) cases réalisant le score sont cette fois ci remplies en premier. Appellons \(p'\) la première case remplie de \(S'\), \(m\) la case de \(S\) réalisant le score maximal, et \(d'\) la dernière case de \(S'\) remplie (qui correspond donc à \(m\)).

Vu la taille de la grille, \(p'\) et \(d'\) sont soit adjacentes, soient séparées par une case.

  • Si \(p'\) et \(d'\) sont adjacentes, alors la valeur de \(d'\) est supérieure ou égale à la valeur de \(m\), à laquelle on ajoute la valeur \(p'\) (soit 1). La valeur de \(p'\) est donc strictement supérieure à \(m\), et le score de \(S'\) est strictement supérieur au score de \(S\), qui n’est donc pas maximal, ce qui est contraire à l’hypothèse de départ.
  • Si \(p'\) et \(d'\) sont séparées par une case \(c'\). Alors avec un raisonnement similaire, on montre que la valeur de cette case dans \(S'\) est strictement supérieure à la valeur de la case correspondante dans \(S\), donc que la valeur de \(p'\) est strictement supérieure à celle de \(m\), donc que le score de \(S'\) est strictement supérieur à celui de \(S\), et donc que \(S\) n’est pas maximale, ce qui est contraire à l’hypothèse de départ.

L’hypothèse de départ est donc fausse, et une solution dont la dernière case remplie ne réalise pas le score n’est pas possible.

Donc l’approximation faite dans la méthode Solution.score(), en considérant comme score la valeur de la dernière case remplie, même tout de même à un résultat correct en ce qui concerne les grilles maximales.

Algorithme

Étude de l’espace des solutions

Une approche naïve pour résoudre ce problème est de tester toutes les solutions possibles : il y a 9 cases possibles au départ, 8 ensuite, 7 ensuite, etc. Cela fait donc au total \(9!\) solutions, soit 362880. Ça n’est pas si grand que ça : mon ordinateur, qui est loin d’être une bête de course, devrait pouvoir tester tout cela en moins d’une minute, mais nous allons pouvoir améliorer cela.

En énumérant toutes les solutions possibles, certaines solutions sont étudiées plusieurs fois. Par exemple, considérons les débuts de solutions suivantes (où les numéros indiquent l’ordre de remplissage).

  1. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & 3 & \\ \hline & 2 & ~~\\ \hline & & \\ \hline \end{array}\end{split}\]
  2. \[\begin{split}\begin{array}{|c|c|c|} \hline 1 & & ~~\\ \hline 3 & 2 & \\ \hline & & \\ \hline \end{array}\end{split}\]
  3. \[\begin{split}\begin{array}{|c|c|c|} \hline & & ~~\\ \hline 3 & 2 & \\ \hline 1 & & \\ \hline \end{array}\end{split}\]
  4. \[\begin{split}\begin{array}{|c|c|c|} \hline ~~ & 3 & 1 \\ \hline & 2 & \\ \hline & & \\ \hline \end{array}\end{split}\]
  • La seconde solution correspond à une symétrie de la première par rapport à la diagonale ;
  • la troisième à une rotation de la première d’angle \(\frac{\pi}{2}\) ;
  • la quatrième à une symétrie de la première par rapport à une droite verticale ;
  • et d’autres transformations sont encore possibles.

Finalement, ces quatre solutions (et les autres, non décrites ici) sont redondantes, et c’est une perte de temps que de toutes les étudier.

Réduction de l’espace

Il y a \(9!\) solutions possibles. Pour chacune de ces solutions, il y a les transformations suivantes, qui donnent une solution équivalente.

  • l’identité (ne rien changer) ;
  • symétrie par une des deux diagonales ;
  • rotation de plus ou moins \(\frac{\pi}{2}\) (un quart de tour à droite ou à gauche) ;
  • symétrie centrale (qui peut être vue comme une rotation de \(\pi\), ou encore d’un demi tour) ;
  • symétrie par un axe horizontal ou vertical passant par le centre.

Cela fait 8 solutions équivalents et différentes pour chaque solution possible, soit un nombre de solutions intéressantes de \(\frac{9!}{8}=45360\).

En ignorant ces solutions équivalentes, nous pouvons donc nous contenter de recherche parmi huit fois moins de solutions.

Mise en œuvre algorithmique

On définit une classe chemin.Solution, et on s’intéresse ici à la méthode chemin.Solution.solve() et l’attribut chemin.Solution.classes :

  • chemin.Solution.classes est un dictonnaire dont les clefs sont les indices des cases, et les valeurs sont les classes de solution à laquelle va appartenir l’objet une fois que ladite case aura été complétée.

  • chemin.Solution.solve() est une méthode qui recherche toutes les solutions possibles à partir de la solution courante, en utilisant chemin.Solution.classes.

    1
    2
    3
    4
    5
    6
    7
        def solve(self):
            "Renvoit la liste des objets Solution, après remplissage d'une case."
            return [
                self.classes[i](self).fill(i)
                for i in range(9)
                if ((not self.array[i]) and (i in self.classes))
            ]
    

Des sous-classes particulières font varier l’attribut chemin.Solution.classes.

Par exemple, la classe SolutionVide représente une solution qui n’a pas encore été complétée. Les cases qu’il est utile de compléter sont la case centrale, la case supérieure gauche, et la case en bas au milieu. Les autres cases mèneront à des solutions identiques à transformation près.

1
2
3
4
5
6
class SolutionVide(Solution):
    """Solution, vide."""

    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.classes = {0: SolutionDiagonale, 4: SolutionCentrale, 7: SolutionVerticale}

De même, à partir d’une SolutionCentrale, qui représente une solution dont seule la case centrale est remplie, on peut remplir les cases supérieure gauche et médiane basse, pour les même raisons que précédemment.

1
2
3
4
5
6
class SolutionCentrale(Solution):
    """Solution, dont seule la case centrale est remplie."""

    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.classes = {0: SolutionDiagonale, 7: SolutionVerticale}

L’exécution de ce programme donne un score maximal de 57, et quatre solutions qui donnent ce score.

Amélioration possible

Parmi les solutions optimales trouvées, on trouve les deux suivante (l’ordre de remplissage est donné à droite, et la grille correspondante à gauche).

  • Solution 1

    1 | 57 | 27       0 | 8 | 7
    2 |  7 | 20       2 | 4 | 6
    1 |  3 | 10       1 | 3 | 5
    
  • Solution 2

    1 |  3 | 10       0 | 3 | 5
    2 |  7 | 20       2 | 4 | 6
    1 | 57 | 27       1 | 8 | 7
    

Ces deux solutions apparaissent comme le symétrique l’une de l’autre par un axe horizontal médian. Pourquoi notre algorithme donne-t-il les deux solutions ?

C’est parce que si on regarde l’ordre de remplissage, on s’aperçoit que ce sont bien deux solutions différentes : la symétrie des trois premières cases remplies fait que deux alternatives possibles pour la suite donnent deux résultats différents si l’on regarde l’ordre de remplissage, mais identiques (à une symétrie près) si l’on regarde le résultat final.

Une amélioration possible de notre algorithme serait de prendre en compte ce genre de similarités, pour étudier encore moins de solutions.

Pour aller plus loin

Cet exercice est plutôt simple, et l’espace des solutions (composé de 362880 éléments), n’est finalement pas si grand que ça pour nos ordinateurs contemporains. Ces optimisations n’étaient donc pas forcément nécessaires.

Il serait intéressant de se demander dans quelle mesure il peut être adapté à un problème plus gros, comme la résolution d’une partie de solitaire. De remarques me viennent alors.

  • Dans cet algorithme, il n’est jamais nécessaire de deviner dans quelle configuration on se trouve (grille vide, seule une diagonale remplie, seul le centre rempli, etc.). Ceci a pu être fait car l’espace des solutions étant petit, il était plus simple de coder cela à la main dans les attributs Solution.classes plutôt que de le recalculer. Pour un solitaire, je pense qu’il serait nécessaire de faire le calcul.
  • L’amélioration évoquée dans la partie précédante devra peut-être être prise en compte.

Enfin, il est également possible que ma méthode ne s’applique pas à des problèmes plus gros… Mais je n’en ai aucune idée…