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

Exercice 2

Cet exercice porte sur la mise au point de programme, la gestion des bugs et les graphes.

Le taquin est un jeu qui se joue avec 15 tuiles numérotées dans une grille de 4 lignes et 4 colonnes pouvant en contenir 16. La tuile manquante permet de déplacer les tuiles adjacentes en les faisant glisser. Par exemple dans la grille de gauche de la figure 1, il est possible de déplacer les tuiles 12 et 15, et dans celle de droite, il est possible de déplacer les tuiles 14, 15 ou 3.

Le but du jeu, partant d'une grille mélangée, est de ranger la grille en procédant à des glissements successifs afin de remettre les tuiles comme sur la grille de gauche sur la figure 1. Une grille mélangée pour laquelle cela est possible est dite résoluble.

On souhaite dans cet exercice écrire des fonctions permettant de mélanger une grille de taquin tout en s'assurant que la grille mélangée est résoluble.

Partie A: Mélange aléatoire

Une grille de taquin est représentée en machine par une liste Python contenant quatre sous-listes de quatre entiers. Chacune des sous-listes contient des valeurs entières de façon à ce que chaque entier entre 1 et 16 apparaisse une unique fois. La valeur 16 représente la tuile vide. La grille rangée ci-dessus est ainsi représentée par:

rangee = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] On suppose que la liste melangee représente la grille mélangée de droite sur la figure 1.

Partie C: Mélange réaliste

On souhaite désormais utiliser une méthode de mélange garantissant que la grille obtenue est résoluble. Pour ce faire, on va effectuer des déplacements réalistes en échangeant, à plusieurs reprises, la tuile vide avec une de ses tuiles voisines. On effectue ces échanges directement sur la liste de valeurs aplatie.

Pour représenter les déplacements réalisables, on définit un graphe dans lequel les sommets sont les indices des cases dans la liste aplatie. Deux sommets $i$ et $j$ sont reliés par une arête s'il est possible, lorsque la tuile vide est sur l'indice $i$, de l'échanger avec la tuile d'indice $j$. On représente ce graphe en machine par une liste d'adjacence graphe sous la forme d'une liste Python dans laquelle la valeur à l'indice $i$ contient la liste des indices des cases avec lesquelles on peut échanger la tuile d'indice $i$.

On fournit ci-dessous, à titre d'exemple, le graphe des déplacements réalisables pour une grille de taquin de 3 lignes et 3 colonnes (soit 9 tuiles au total).

On suppose que graphe_3_3 représente ce graphe par sa liste d'adjacence. Ainsi graphe_3_3[8] vaut [5, 7] ou [7, 5].

11.

Donner une valeur possible de graphe_4_4[9] en supposant que graphe_4_4 est la liste d'adjacence représentant le graphe associé à une grille à 4 lignes et 4 colonnes.

12.

La fonction melange_graphe prend en paramètre un nombre entier nb_dep, un entier n et une liste d'adjacence graphe représentant un graphe de déplacements sur un taquin à n lignes et n colonnes et effectue nb_dep déplacements successifs de la tuile vide. Ces déplacements sont choisis aléatoirement parmi ceux enregistrés dans le graphe grâce à la fonction random.choice qui renvoie un élément pioché aléatoirement dans la liste passée en paramètre.

Recopier et compléter les lignes 7 à 10 de la fonction melange_graphe.

1 from random import choice

2

3 def melange_graphe(nb_dep, n, graphe):

4 valeurs = [i for i in range(n*n)] #liste aplatie rangée

5 num_tuile_vide = n * n

6 actuelle = num_tuile_vide - 1 #position de la tuile vide

7 for k in range(

):

8 prochaine = choice(

)

9 valeurs[actuelle] = valeurs[

]

10 valeurs[prochaine] =

11 actuelle = prochaine

12 return en_grille(valeurs, n)