Approfondissement

Le problème du cavalier est un problème de logique dans lequel on souhaite faire se déplacer un cavalier sur un échiquier avec la contrainte suivante : le cavalier est initialement positionné sur une case de l'échiquier, et il doit effectuer une suite de déplacements de telle sorte qu'il visite chaque case et ne visite jamais une case deux fois.

On représente un échiquier de taille \(n \in \mathbb{N}^{*}\) par un tableau de tableaux, rectangulaire de taille \(n \times n\). On repère la position d'un cavalier par le couple (abscisse, ordonnee). Si \(n\) est la taille de l'échiquier, alors les positions possibles pour le cavalier sont les couples \((i, j)\), avec \(0 \leq i < n\) et \(0 \leq j < n\).

Par exemple, pour \(n = 8\), le cavalier de la figure ci-dessous se trouve à la position \((2, 3)\). On rappelle que le cavalier peut se déplacer "en L" aux cases indiquées.

img

On considérera que la position de départ du cavalier est toujours \((0, 0)\). Un parcours du cavalier sera représenté par une pile, constituée des différentes positions du cavalier au cours du parcours (la dernière position du cavalier se trouvant au sommet de la pile).

  1. Soit \(n = 3\). Faire le schéma d'un échiquier de taille \(3 \times 3\) puis numéroter les cases de l'échiquier dans l'ordre dans lequel elles sont visitées par le cavalier lors du parcours correspondant à la pile pile_parcours:

    [Sommet] (1, 2) (2, 0) (0, 1) (2, 2) (1, 0) (0, 2) (2, 1) (0, 0)

  2. Le problème du cavalier possède-t-il une solution lorsque \(n = 3\) ? Expliquer.

On utilisera dans la suite des questions les variables globales suivantes. Les fonctions pourront directement modifier la variable plateau.

1
2
3
4
5
n = 5
plateau = [ [-1 for i in range(n)]
           for j in range(n)]
deplacements = [(2, 1), (1, 2), (-1, 2), (-2, 1),
                (-2, -1), (-1, -2), (1, -2), (2, -1)]

  1. Écrire une fonction est_dans qui étant donné une position pos détermine si celle-ci est une position compatible avec la taille de l'échiquier.

    1
2
3
4
    def est_dans(pos):
    """ (int, int) -> bool
    Détermine si la position pos = (x, y) appartient au plateau  """
    pass

  2. On souhaite obtenir la liste de tous les déplacements à tester à partir d'une position donnée. Il s'agit de toutes les cases accessibles par le cavalier, sans celles par lesquelles le cavalier est déjà passé. On décide d'affecter la valeur 1 à la case d'indice (i ,j) de plateau si le cavalier est passé par cette case lors de son parcours. Sinon, cette case stocke -1.

    1. Écrire une fonction est_visitee qui renvoie True si et seulement si la case pos a été visitée par le cavalier.

      1
2
3
4
      def est_visitee(pos):
    """ (int, int) -> bool
    Détermine si la position pos = (x, y) a déjà été visitée """
    pass

    2. En déduire une fonction a_partir_de qui renvoie une pile constituée des positions accessibles par le cavalier depuis la position pos (dans l'état courant de la variable plateau). On calculera pour cela toutes les cases atteignables par le cavalier à l'aide de la variable deplacements et on empilera uniquement celles qui appartiennent au plateau et qui n'ont pas encore été visitées par le cavalier. 

      1
2
3
4
5
      def a_partir_de(pos):
    """ (int, int) -> Pile
    Renvoie une pile constituée des éléments accessibles depuis pos
    avec l'état courant du plateau. '"""
    pass

La structure de pile peut être utilisée pour "revenir en arrière". Par exemple, si pile_parcours est la pile représentant le chemin du cavalier jusqu'à l'étape actuelle, on peut "revenir en arrière" à l'aide de l'instruction pile_parcours.depiler() : après exécution de cette instruction pile_parcours représente alors le chemin du cavalier sans la dernière étape.

L'idée de l'algorithme permettant de déterminer un parcours possible du cavalier est la suivante :

  • on maintient deux piles :
    • pile_parcours : la pile correspondant au parcours du cavalier ;
    • pile_essais : qui représente la liste des positions à explorer par le cavalier. Si pos est la valeur au sommet de pile_parcours (la position actuelle du cavalier), alors la valeur au sommet de pile_essais est une pile constituée des positions restantes à explorer à partir de pos, dans l'état actuel de l'échiquier.
  • tant que la longueur du chemin du cavalier n'est pas \(n^2\) (le cavalier est alors passé par toutes les cases) :
    • soient pos et accessibles les valeurs présentes au sommet des piles pile_parcours et pile_accessibles :
      • si aucune position n'est accessible depuis pos (le chemin suivi par le cavalier abouti à une impasse) : alors il faut revenir en arrière. On indique que la position pos est à nouveau accessible, puis on dépile pile_parcours et pile_accessibles. On décrémente également la longueur du chemin.
      • sinon : la nouvelle position est la valeur qui se trouve au sommet de la pile accessibles : on la dépile afin de la supprimer de la pile des positions à explorer. Puis on indique que la nouvelle position ne sera plus accessible par la suite (car on s'y rend). On met à jour la longueur du chemin. On empile dans la pile pile_parcours la nouvelle position ainsi que la liste des positions à explorer à partir de cette nouvelle position selon l'état actuel du plateau.
    • si à un moment pile_parcours est vide, c'est que l'on a échoué à trouver une solution en testant toutes les possibilités : il n'y a donc pas de solution au problème.

Répondre aux questions suivantes dans le cas \(n = 3\).

  1. Initialement pile_parcours est constituée d'un seul élément, (0,0).
    1. Décrire la constitution de la pile_essais correspondante.
    2. Décrire la constitution du plateau correspondant.
  2. Le cavalier se rend à la position au sommet de la pile au sommet de pile_essais. On supprime cette valeur de la pile correspondante en la dépilant.
    1. Quelle est la position du cavalier ?
    2. Donner la composition de pile_parcours, pile_essais, et plateau correspondants à cette situation.
    1. Suivre l'exécution de cet algorithme jusqu'au premier dépilement de pile_parcours.
    2. Quelle est la prochaine valeur empilée sur pile_parcours ?

  4. Compléter le code ci-dessous afin d'implémenter l'algorithme décrit dans l'énoncé. Vérifier que le chemin trouvé pour \(n = 5\) est une solution au problème du cavalier.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
    def cavalier():
    """ () -> Pile
    Renvoie une pile constituée des mouvements à effectuer pour
    obtenir un chemin de cavalier passant par toutes les cases du plateau. """

    pos = (0,0)
    # le sommet de la pile parcours contient
    # la position courante
    pile_parcours = Pile()
    pile_parcours.empiler(pos)
    # initialement le chemin est de longueur 1
    longueur_chemin = 1
    # le sommet de la pile essais contient
    # les positions à explorer à partir de la position courante
    pile_essais = Pile()
    pile_essais.empiler(...)
    # on indique la position courante comme visitée
    plateau[...][...] = 1
    while longueur_chemin < n**2:
        # on récupère l'état courant du cavalier :
        # sa position se trouve au sommet de la pile parcours
        # et ses mouvements à explorer au sommet de la pile essais
        pos = pile_parcours.sommet.valeur
        accessibles = pile_essais.sommet.valeur
        # Dans le cas où il est possible de visiter une
        # case à partir de la position courante
        if ...:
            # on choisit la première position à explorer
            # il ne sera plus nécessaire de l'explorer
            # par la suite, on la supprime de accessibles
            pos = ...
            # on indique que la case pos a été visitée
            plateau[...][...] = ...
            longueur_chemin = ...
            # on met à jour les piles de parcours et d'essais
            pile_parcours.empiler(...)
            pile_essais.empiler(...)
        else:
            # la position courante est un cul de sac
            # on met à jour le plateau (la case courante
            # redevient accessible)
            ...
            # on revient à la dernière configuration connue qui
            # ne menait pas à un cul de sac en dépilant les piles
            # parcours et essais
            ...
            ...
            # on met à jour la longueur du chemin
            ...
        # si jamais la pile du parcours est vide
        # c'est qu'il n'y a pas de solution au problème
        if ...:
            raise IndexError("Pas de solution trouvée au problème")
    return pile_parcours