Exercice 2 - Partie A · Bac Numérique et Sciences Informatiques Polynésie 2026 (jour 2)

EXERCICE 2 (6 points)

Cet exercice porte sur la programmation Python, les structures de données, les graphes et la recherche de motif dans un texte.

Cet exercice comporte 2 parties qui peuvent être traitées indépendamment.

Le jeu du taquin consiste à déplacer des tuiles adjacentes à la case vide jusqu’à arriver à mettre tous les nombres dans l’ordre. Voici un exemple de positions pour un jeu du taquin de dimension 3 x 3 soit 9 cases.

Partie A

Dans un premier temps, on s’intéresse au jeu du taquin sur 4 cases. Voici une figure qui représente les 12 positions que l’on peut atteindre à partir de la position finale en déplaçant les tuiles. Deux positions sont reliées si on peut passer de l’une à l’autre en un seul coup, c’est-à-dire en déplaçant une tuile.

Partie A

Dans un premier temps, on s'intéresse au jeu du taquin sur 4 cases. Voici une figure qui représente les 12 positions que l'on peut atteindre à partir de la position finale en déplaçant les tuiles. Deux positions sont reliées si on peut passer de l'une à l'autre en un seul coup, c'est-à-dire en déplaçant une tuile.

1.

Représenter une position des 3 tuiles qui n'est pas accessible depuis la position finale.

2.

Nommer, en justifiant, la structure de données la plus adaptée pour modéliser, dans ce jeu, les passages d'une position à une autre.

On s'intéresse maintenant au jeu du taquin sur 9 cases.

On représente, en Python, une position de taquin par une liste qui contient les nombres présents de gauche à droite puis de haut en bas. La case vide est représentée par le nombre 0. Par exemple, les positions de jeu du taquin de dimension 3 x 3 de la Figure 1 sont représentées respectivement par:

[3, 1, 2, 7, 5, 0, 4, 6, 8] et [0, 1, 2, 3, 4, 5, 6, 7, 8].

3.

Étant donnée une liste pos représentant une position du taquin, donner une instruction, basée sur l'instruction assert, qui permet d'interrompre le programme si la taille de la liste pos n'est pas correcte (c'est-à-dire différente de 9).

4.

Recopier et compléter la fonction est_finale qui prend en paramètre une position représentée par une liste pos et qui renvoie un booléen valant True si la position correspond à la position finale et False sinon.

def est_finale(pos):

for i in range(len(pos)):

if...:

return...

return...

5.

Compléter, en utilisant autant de lignes que nécessaire, la fonction case_vide qui prend en paramètre une liste d'entiers pos et qui renvoie l'indice de 0.

Si la liste pos ne contient pas 0, ou contient plusieurs 0, case_vide(pos) renvoie -1.

def case_vide(pos):

res =...

for i in range(9):

...

return res

6.

Si la case vide se trouve en indice i dans une grille de 9 cases, donner les 4 indices qui sont susceptibles de désigner les tuiles qui peuvent être déplacées sur la case vide (sans chercher à éliminer ceux qui sont invalides au niveau des bords).

On suppose que l'on a à disposition une fonction voisins qui prend en paramètre une position représentée par une liste pos et qui renvoie la liste des positions que l'on peut atteindre en déplaçant une tuile. On écrit la fonction est_possible pour parcourir toutes les positions du taquin atteignables à partir d'une position donnée afin de déterminer si la position finale est accessible depuis cette position.

def est_possible(pos):

if est_finale(pos):

return True

# Liste pour retenir les positions déjà rencontrées

visites = []

for v in voisins(pos):

if v not in visites:

visites.append(v)

if est_possible(v):

return True

Lorsqu'on teste la fonction, l'exécution ne semble pas se terminer.

7.

Expliquer le problème et proposer une solution (sans la programmer).