Exercice 2 - Partie A · 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 A: représentation binaire des configurations

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

1.

Justifier que le nombre total de configurations possibles est $2^9$.

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.

2.

Indiquer en justifiant si la séquence de coups suivante, jouée depuis la configuration donnée en figure 1, permet de mener à la victoire: ligne 1, ligne 2, colonne 2.

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.

3.

En détaillant le calcul, donner l'entier représentant la configuration illustrée en figure 1.

4.

Implémenter une fonction representant prenant en paramètre une liste de 0 et de 1 et renvoyant l'entier correspondant.

Dans la suite on considère à disposition une fonction binaire prenant réciproquement en paramètre un entier et renvoyant son écriture en binaire sous forme d'une liste de neuf 0 ou 1.

L'opérateur ou exclusif, noté $\oplus$, a pour table de vérité:

X

Y

X ⊕ Y

0 · 0 · 0

0 · 1 · 1

1 · 0 · 1

1 · 1 · 0

La fonction xor définie ci-dessous prend en paramètres deux bits b1, b2 (de type int) et renvoie le résultat de b1 ⊕ b2.

def xor(b1, b2):

if b1 == b2:

return 0

else:

return 1

L'opérateur $\oplus$ peut être appliqué sur deux listes de même longueur l_x et l_y contenant plusieurs bits: pour chaque indice de ces listes, on applique le $\oplus$ aux deux bits positionnés à cet indice. Par exemple, si l_x = [1, 1] et l_y = [0, 1], alors l_x ⊕ l_y vaut [1, 0], puisque $1 \oplus 0$ vaut 1, et $1 \oplus 1$ vaut 0.

5.

Implémenter une fonction xor_etendu qui prend en paramètre deux listes de bits de même longueur l_x et l_y et renvoie la liste l_x ⊕ l_y.

On peut observer que pour un bit X donné, l'opération $X \oplus 1$ a pour résultat l'inverse de X et l'opération $X \oplus 0$ a pour résultat X.

Si X représente un jeton, alors $X \oplus 1$ le retourne et $X \oplus 0$ le laisse inchangé.

Appliquer un coup à une configuration revient à lister les jetons retournés et les jetons non-retournés. On peut donc représenter chaque coup par une liste de bits. Par exemple le coup "ligne 1" est représenté par la liste [1, 1, 1, 0, 0, 0, 0, 0, 0] et l'appliquer à la configuration 67 revient à calculer [0, 0, 1, 0, 0, 0, 0, 1, 1] ⊕ [1, 1, 1, 0, 0, 0, 0, 0, 0].

La figure 3 illustre les 8 coups possibles de la même manière au moyen du $\oplus$.

On suppose à disposition le dictionnaire coups_possibles qui énumère chaque coup représenté de la sorte:

coups_possibles = {

"ligne 1": [1, 1, 1, 0, 0, 0, 0, 0, 0],

"ligne 2": [0, 0, 0, 1, 1, 1, 0, 0, 0],

"ligne 3": [0, 0, 0, 0, 0, 0, 1, 1, 1],

"colonne 1": [1, 0, 0, 1, 0, 0, 1, 0, 0],

"colonne 2": [0, 1, 0, 0, 1, 0, 0, 1, 0],

"colonne 3": [0, 0, 1, 0, 0, 1, 0, 0, 1],

"diagonale 1": [1, 0, 0, 0, 1, 0, 0, 0, 1],

"diagonale 2": [0, 0, 1, 0, 1, 0, 1, 0, 0]

}

On souhaite implémenter une fonction qui prend en paramètre un entier config représentant une configuration et qui renvoie la liste des entiers correspondant à toutes les configurations accessibles en un seul coup.

def configurations_suivantes(config):

config_bin =...

voisins = []

for... in...:

... # ligne facultative

... = xor_etendu(...,...)

voisins.append(representant(...))

return voisins

6.

Recopier et compléter la fonction configurations_suivantes.