Saute-Mouton

Présentation

Le jeu du saute-mouton est une variante du jeu du Solitaire à une ligne. Comme pour le Solitaire classique, il s'agit d'atteindre une configuration finale en partant d'une configuration initiale.

Les états du jeu saute-mouton

État initialÉtat final

Règles

1. Les moutons blancs ne peuvent avancer que vers la droite ; les noirs vers la gauche
2. Un mouton peut aller sur l'unique case vide qui si elle se trouve juste devant lui ou alors
3. il peut sauter par-dessus un mouton de la couleur opposée pour atterir dans la case vide

Le jeu est intéressant à modéliser dans un contexte d'initiation à la programmation et à l'algorithmique. En effet, sans être vraiment difficile à résoudre, il n'est pas trivial et permet d'aborder divers aspects de programmation.

C. Declercq propose par exemple une version instrumentée permettant à l'élève de mettre en oeuvre l'utilisation d'une structure de pile pour l'implémentation d'une fonction undo ¹

Ici, nous proposons d'explorer une version objet, jouable dans un notebook en utilisant une interface utilisateur minimaliste :

• Une visualisation des "moutons" par l'utilitaire ipythonblocks :

• 4 méthodes :
  • jeu.show() : pour visualiser l'état de la partie
  • jeu.white() : pour déplacer le seul mouton blanc qui pourrait bouger
  • jeu.black() : idem mais avec les moutons noirs
  • jeu.undo() : pour annuler le dernier déplacement

La modélisation

Dans la présentation précédente, jeu référence un objet Moutons que nous allons décrire.

La classe Moutons doit permettre de créer une instance du jeu, en choisissant le nombre de moutons blancs (il y aura la même quantité de moutons noirs) :

[1]: jeu = Moutons(3)
[2]: jeu.show()

La classe devra embarquer 3 attributs :

• board : tableau de taille \(2n + 1\) initialisé avec les moutons blancs à gauche, les noirs à droite, une case vide centrale les séparant ;
• moves : une pile des coups joués
• view qui sera un BlockGrid de la bonne dimension

Modéliser les moutons

Comment modéliser un mouton ? Il y a plusieurs possibilité. L'une d'elle simplifie ensuite le déplacement des moutons : on choist de modéliser un mouton blanc par l'entier 1 et un noir par l'entier -1.

Pourquoi ?

Pour les déplacements. Si c représente l'indice de la case où se trouve le mouton alors c + couleur représente la case voisine dans la direction où doit se déplacer le mouton.

Modéliser les coups

On modélise les coups par un couple d'indices de cases :(depart, arrivee). Ainsi, lorsque ce coup sera mémorisé dans la pile des coups, le undo consistera à dépiler le couple (depart, arrivee) et à réaliser le déplacement arrivee vers depart.

Questions

Trouver la case d'arrivée

Si on donne une case depart, alors, si cette case est bien dans les limites du tableau et non vide, on peut calculer la case d'arrivée si elle existe. Cette case sera soit celle juste devant (dans le sens du déplacement du mouton), soit celle d'après encore.

Écrire une méthode destination qui prend l'indice d'une case de départ et qui calcule et renvoie l'indice de la case d'arrivée si elle existe et None sinon.

Solution

def destination(self, depart):
    """depart est une case non vide du tableau"""
    arrivee = None
    color = self.board[depart]
    next_case = depart + color # (1)
    next_next_case = next_case + color # (2)

    if self.empty(next_case):
        arrivee = next_case
    elif self.board[next_case] == -color and self.empty(next_next_case):
        arrivee = next_next_case

    return arrivee

1. la case suivante... vers la droite pour un mouton blanc, vers le gauche pour un noir
2. la case d'après encore

Réaliser un déplacement

Écrire une méthode move qui prend deux cases depart et arrivee en paramètres ainsi qu'un troisième booléen et qui réalise le déplacement du mouton depuis depart vers arrivee. Si de plus le 3e paramètre est à True une mémorisation du couple de cases est effectuée dans la pile moves.

Solution

def move(self, depart, arrivee, memorize=True):
    color = self.board[depart]
    self.board[arrivee] = color
    self.board[depart] = Moutons.EMPTY
    self.update_view(depart, arrivee, color)
    if memorize: # (1)
        self.moves.append((depart, arrivee))

1. si True, on ajoute le coup dans la pile des coups

L'interface

Finalement coder les quatre méthodes de l'interface.

Solution

whiteblackundo

Trouve, s'il existe, l'unique mouton blanc qui peut bouger, ordonne son déplace et renvoie True, renvoie False sinon.

def white(self):
    for depart in range(self.size):
        if self.is_white(depart):
            arrivee = self.destination(depart)
            if arrivee is not None:
                self.move(depart, arrivee)
                return True
    return False

Similaire à white

def black(self):
    for depart in range(self.size):
        if self.is_black(depart):
            arrivee = self.destination(depart)
            if arrivee is not None:
                self.move(depart, arrivee)
                return True
    return False            

Il s'agit de dépiler le dernier coup joué. Et de le rejouer à l'envers, sans mémoriser.

def undo(self):
    if self.moves:
        depart, arrivee = self.moves.pop()
        self.move(arrivee, depart, memorize=False)
        return True
    return False        

Télécharger le Notebook complet

Notebook moutons.ipynb

---

1. Découverte de la nécessité de la pile pour la résolution d’un jeu de solitaire, C. Declercq, IREMI de la Réunion, 2022. ↩