Exercice 2 - Partie B · Bac Numérique et Sciences Informatiques Métropole 2026 (sujet 1)

Exercice 2 (6 points)

Cet exercice porte sur le binaire, les graphes, la récursivité.

Le jeu du Recto-Verso, de la famille des solitaires, se compose de neuf jetons disposés sur un plateau carré. Le plateau a 3 lignes et 3 colonnes. Chaque jeton possède une face Recto, dessinée en couleur noire sur les figures, et une face Verso, dessinée en blanc.

Partie A: représentation binaire des configurations

On appelle configuration l'état du plateau. La figure 1 illustre un exemple de configuration.

Le but du jeu est, depuis une configuration quelconque, de retourner tous les jetons sur leur face Recto (noire). Pour ce faire, le seul type d'opération autorisé est de choisir une ligne ou une colonne ou une diagonale, et d'en retourner tous les jetons. On appelle une telle opération un coup. La figure 2 illustre les huit différents coups possibles à partir d'une configuration donnée.

Une configuration est représentée, ligne par ligne et de haut en bas, par une liste de bits en considérant les jetons Recto comme des 1 et les jetons Verso comme des 0. Ainsi on lit la configuration initiale de la figure 2 comme la liste [0, 0, 1, 0, 0, 0, 0, 1, 1].

On peut aussi lire la liste de bits d'une configuration comme l'écriture binaire d'un nombre entier. Pour l'exemple de la figure 2, la configuration initiale est donc aussi représentée par l'entier 67.

Partie B: graphe des configurations

On constate qu'il semble impossible d'atteindre la victoire depuis la configuration représentée par l'entier 4. On appelle configuration perdante toute configuration pour laquelle il n'existe aucune suite de coups menant à la victoire (c'est-à-dire à tous les jetons côté Recto). Inversement, on appelle configuration gagnante toute configuration qui n'est pas perdante.

La configuration représentée par l'entier 4 est effectivement perdante. Pour s'en convaincre on construit le graphe des configurations du jeu Recto-Verso.

Les sommets de ce graphe sont les différentes configurations possibles et il existe une arête $s_1 \to s_2$ d'un sommet $s_1$ vers un sommet $s_2$ si et seulement s'il est possible de passer de la configuration $s_1$ à la configuration $s_2$ en jouant un coup autorisé.

7.

Montrer que s'il existe une arête $x \to y$ dans le graphe, alors il existe également une arête $y \to x$.

En Python, on choisit de représenter ce graphe par un dictionnaire construit grâce à la fonction configurations_suivantes:

graphe = {

0: [...],

...

67: [387, 123, 68, 359, 209, 10, 338, 23],

...

}

8.

Une représentation par matrice d'adjacence aurait aussi pu être envisagée. Justifier le choix du dictionnaire en comparant pour les deux structures le nombre d'entiers nécessaires pour stocker en mémoire le graphe des configurations. On pourra laisser ce nombre écrit sous la forme d'une puissance de 2.

La fonction parcours_profondeur ci-dessous implémente un parcours en profondeur d'abord. Elle prend en paramètres la représentation d'un graphe, un entier configuration qui indique le sommet que l'on est en train de visiter, et une liste vus de sommets déjà visités par le parcours. Cette fonction effectue le parcours en rajoutant les sommets visités à la liste vus.

1 def parcours_profondeur(graphe, configuration, vus):

2 vus.append(...)

3 for s in...:

4 if s not in vus:

5 parcours_profondeur(...,...,...)

9.

Recopier et compléter la fonction parcours_profondeur.

10.

En utilisant la fonction parcours_profondeur, écrire en Python une suite d'instructions permettant de vérifier que la configuration représentée par l'entier 4 est bien perdante.

11.

Indiquer et justifier quel parcours de graphe (en largeur ou en profondeur) est le plus approprié pour trouver un chemin partant d'une configuration gagnante et menant à la victoire en un minimum de coups.