DEV Community

Ayedoun Châ-Fine ADEBI
Ayedoun Châ-Fine ADEBI

Posted on • Edited on

Résoudre le Puzzle Coulissant en Python : Implémentation de Problem et Node 🧩🐍

Les puzzles coulissants ne sont pas seulement des casse-têtes amusants, ils sont aussi parfaits pour booster nos compétences en intelligence artificielle ! Dans cet article, on va vous emmener à travers la résolution d'un puzzle coulissant en Python avec une petite touche de fun 🎉. On va utiliser des algorithmes de recherche non informée et implémenter les classes abstraites Problem et Node.


C'est Quoi un Puzzle Coulissant ? 🤔

Imaginez un plateau 5x4 avec des pièces que vous devez déplacer pour amener une pièce rouge (2x2) à sa place cible. Les autres pièces sont de tailles différentes, et vous devez les déplacer dans l'ordre :

  • Pièces verticales (2x1)
  • Pièces horizontales (1x2)
  • Pièces uniques (1x1)

Exemple de départ et de cible 🎯

État initial :

2 1 1 3
2 1 1 3
0 A A 0
4 6 7 5
4 8 9 5
Enter fullscreen mode Exit fullscreen mode

Objectif à atteindre :

. . . .
. . . .
. . . .
. 1 1 .
. 1 1 .
Enter fullscreen mode Exit fullscreen mode

L'Approche Algorithmique 🧠💻

On va utiliser deux classes principales pour modéliser ce problème : Problem et Node.

1. Classe Problem – La Base du Puzzle

Cette classe définit tout ce qu'il faut pour résoudre notre puzzle :

  • initial : L'état de départ du puzzle (où tout commence).
  • goal : L'état à atteindre (c'est la cible !).
  • actions(state) : Retourne les mouvements possibles à partir d'un état donné.
  • result(state, action) : Applique une action et obtient le nouvel état.
  • goal_test(state) : Vérifie si l'état actuel est l'objectif.

2. Classe Node – Le Héros du Parcours

Chaque Node représente un état dans notre arbre de recherche :

  • state : L'état actuel.
  • parent : Le parent du nœud (pour tracer le chemin).
  • action : L'action qui a permis d'atteindre cet état.

La méthode expand crée les "enfants" du nœud courant en appliquant toutes les actions possibles. Magique, non ? ✨


- Get the full code on my github

Le Code Python – Magic Mode On 🧙‍♂️

Voici le code qui fait tout le travail :

Classe Problem

class Problem:
    def __init__(self, initial, goal):
        self.initial = initial
        self.goal = goal

    def actions(self, state):
        # Logic to find possible actions
        pass

    def result(self, state, action):
        # Apply an action and return the new state
        pass

    def goal_test(self, state):
        return state == self.goal
Enter fullscreen mode Exit fullscreen mode

Classe Node

class Node:
    def __init__(self, state, parent=None, action=None, path_cost=0):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost

    def expand(self, problem):
        return [
            Node(problem.result(self.state, action), self, action)
            for action in problem.actions(self.state)
        ]
Enter fullscreen mode Exit fullscreen mode

Stratégies de Recherche – Choisissez Votre Arme 🛠️

Il existe plusieurs techniques pour explorer l'arbre des états. On en a testé deux :

Recherche en largeur (BFS) 🌊

  • Avantages : Trouve toujours la solution optimale (profondément, pas de raccourcis !).
  • Inconvénients : Mange beaucoup de mémoire (ça devient un peu lourd...).

Recherche en profondeur (DFS) 🏊‍♂️

  • Avantages : Utilise peu de mémoire (tout va bien !).
  • Inconvénients : Parfois, ça fait des boucles infinies et ça n'aboutit à rien... Pas top ! 🙄

Résultats – Testons Cela ! 📊

Après avoir lancé nos tests sur différentes instances du puzzle, voici ce qu'on a observé :

  • BFS a trouvé la solution à chaque fois, mais à un coût mémoire assez élevé.
  • DFS a parfois échoué, bloqué dans des boucles infinies. Pas cool. 😅

Conclusion – Mission Accomplie ✅

Voilà comment on a résolu le puzzle coulissant en utilisant des algorithmes de recherche non informée et en modélisant notre problème avec des classes Python. 🎉 N'hésitez pas à tester votre propre implémentation et à nous faire part de vos idées pour améliorer cette approche. Qui sait, vous pourriez résoudre des puzzles encore plus complexes ! 😎


Références 📚

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

Imagine monitoring actually built for developers

Billboard image

Join Vercel, CrowdStrike, and thousands of other teams that trust Checkly to streamline monitor creation and configuration with Monitoring as Code.

Start Monitoring

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay