Exercice 2 - Mise au point de programmes et tests · 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 A: Mélange aléatoire

1.

Donner la valeur de melangee[2][1].

2.

Afin de créer la liste aplatie valeurs on saisit tout d'abord l'instruction valeurs = [k for k in range(16)]. On constate que les valeurs ne sont pas celles attendues.

Réécrire cette instruction en la corrigeant pour que la liste valeurs contienne bien les entiers de 1 à 16.

3.

On constate que la variable valeurs est désormais affectée à None après l'instruction valeurs = shuffle(valeurs).

Proposer une modification de la ligne valeurs = shuffle(valeurs) afin de corriger cette erreur.

4.

Recopier et compléter la ligne 2 de la fonction en_grille afin qu'elle vérifie que la liste passée en paramètre contient le bon nombre d'éléments.

5.

L'appel en_grille([1, 2, 3, 4], 2) renvoie [[1, 3], [2, 4]] au lieu de [[1, 2], [3, 4]].

Recopier et modifier la ligne 6 de la fonction en_grille afin de corriger cette erreur.

Partie B: Grille résoluble

6.

Indiquer si la grille représentée en machine par la liste suivante est résoluble ? Justifier.

[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 16, 15, 14]]

7.

Proposer un test faisant intervenir une liste aplatie de quatre éléments et comptant deux inversions permettant de vérifier que la fonction compte_inversions renvoie le résultat attendu.

8.

La fonction proposée ne passe pas les tests. Proposer une correction de la fonction compte_inversions (indiquer la ligne modifiée ou la boucle corrigée).

9.

Recopier et compléter les lignes 5 et 6 de la fonction distance_tuile_vide afin qu'elle renvoie la distance attendue.

10.

Recopier et compléter la fonction est_resoluble (lignes 3, 4 et 5) afin qu'elle renvoie la valeur attendue.