Corrigé bac NSI 2026 Métropole jour 2 — Exercice 2 : Le taquin : mise au point, grille résoluble et mélange par graphe

Sujet officiel du baccalauréat, spécialité numérique et sciences informatiques, session 2026. Corrigé rédigé par Ibrahim Alame.

Travailler ce sujet sur Adloun Sujet officiel (PDF) Corrigé complet (PDF)

Énoncé

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.

Figure 1. Une grille rangée, à gauche, et mélangée, à droite.

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.

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

On décide dans un premier temps d'obtenir une grille mélangée en utilisant la démarche suivante :

on crée une liste valeurs contenant les entiers entre 1 et 16. Dans la suite du sujet, cette liste sera appelée liste aplatie ;
on mélange la liste aplatie en utilisant la fonction random.shuffle de Python ;
on convertit la liste aplatie ainsi mélangée en une liste de listes afin d'obtenir la grille.

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.

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

La liste aplatie valeurs étant désormais correctement créée, on la mélange à l'aide de la fonction random.shuffle. La documentation de Python indique que random.shuffle(x), mélange la séquence x sans créer de nouvelle instance (« en place »).

On saisit donc :


>>> from random import shuffle
>>> valeurs = shuffle(valeurs)
>>> print(valeurs)
None

On constate que la variable valeurs est désormais affectée à None.

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

La fonction en_grille donnée ci-dessous prend en paramètres une liste d'entiers valeurs et un entier n. Cette fonction permet de transformer la liste valeurs (contenant $n \times n$ éléments) en une liste de n listes contenant chacune n entiers.


def en_grille(valeurs, n):
    assert ...
    grille = [[0 for j in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            grille[i][j] = valeurs[j * n + i]
    return grille

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

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

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

Partie B : Grille résoluble

Certaines grilles obtenues par la méthode précédente ne sont pas résolubles. Pour savoir si une grille est résoluble, on doit calculer :

le nombre d'inversions présentes dans la liste aplatie ;
la distance, mesurée en nombre de déplacements, séparant la tuile vide de sa position finale en bas à droite de la grille.

Une inversion dans une liste aplatie valeurs est un couple d'indices (i, j) vérifiant i < j et valeurs[i] > valeurs[j]. Par exemple, la liste valeurs = [6, 9, 7, 8] compte 2 inversions : les couples (1, 2) (car 9 > 7) et (1, 3) (car 9 > 8).

La distance séparant la tuile vide de sa position finale est égale à la somme du nombre de lignes et du nombre de colonnes séparant la tuile vide et le coin inférieur droit de la grille. Dans la grille de droite de la figure 1 cette distance vaut 5. En effet, la tuile vide est séparée de 3 lignes et de 2 colonnes de sa position finale.

On admet que la grille est résoluble si et seulement si la somme du nombre d'inversions et de la distance est un nombre pair.

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]]

On propose ci-dessous la fonction compte_inversions qui permet de compter les inversions dans une liste aplatie passée en paramètre.


def compte_inversions(valeurs):
    total = 0
    for i in range(len(valeurs)):
        for j in range(len(valeurs)):
            if valeurs[i] > valeurs[j]:
                total = total + 1
    return total

On remarque que la grille non mélangée de 2 lignes et 2 colonnes compte 0 inversion, ainsi on peut tester cette fonction, en exécutant le test suivant :


assert compte_inversions([1, 2, 3, 4]) == 0

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.

On propose désormais la fonction distance_tuile_vide qui prend en paramètre une liste de listes et un entier n, où la liste représente une grille de taquin de n lignes et n colonnes, et qui renvoie la distance séparant la tuile vide de sa position finale.


def distance_tuile_vide(grille, n):
    num_tuile_vide = n * n
    for i in range(n):
        for j in range(n):
            if grille[...][...] == ...:
                return ...

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

La fonction est_resoluble prend en paramètre la liste aplatie valeurs et un entier n, où la liste valeurs a $n \times n$ éléments, et renvoie le booléen indiquant si la grille de taquin qu'elle représente est résoluble ou non.


def est_resoluble(valeurs, n):
    grille = en_grille(valeurs, n)
    inv = ...(...)
    dis = ...(...)
    return (... + ...) ... == ...

10. Recopier et compléter cette fonction afin qu'elle renvoie la valeur attendue. On rappelle que 7 % 2 est égal à 1 alors que 8 % 2 est égal à 0.

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).

Figure 2. Le graphe des déplacements pour un taquin à 3 lignes et 3 colonnes

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.

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.


from random import choice

def melange_graphe(nb_dep, n, graphe):
    valeurs = [i for i in range (n*n)]#liste aplatie rangée
    num_tuile_vide = n * n
    actuelle = num_tuile_vide - 1#position de la tuile vide
    for k in range(...):
        prochaine = choice(...)
        valeurs[actuelle] = valeurs[...]
        valeurs[prochaine] = ...
        actuelle = prochaine
    return en_grille(valeurs, n)

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

Corrigé

Partie A : Mélange aléatoire

1. La grille de droite de la figure 1 se lit ligne par ligne :


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

(la tuile vide est codée 16). Les indices commencent à 0 : melangee[2] est la troisième sous-liste, [2, 10, 9, 4], et son élément d'indice 1 est le deuxième. Donc melangee[2][1] vaut 10.

2. range(16) produit les entiers de 0 à 15 (la borne supérieure est exclue) : la liste obtenue est [0, 1, ..., 15], elle contient un 0 et pas de

Il faut décaler d'un cran, en donnant à range sa borne de départ :


valeurs = [k for k in range(1, 17)]

On peut aussi écrire valeurs = [k + 1 for k in range(16)] ; les deux instructions donnent exactement [1, 2, ..., 16] (vérifié).

3. La fonction shuffle mélange la liste en place : elle modifie directement l'objet qu'on lui passe et ne renvoie rien, c'est-à-dire None. En écrivant valeurs = shuffle(valeurs), on remplace donc la liste (bien mélangée) par la valeur de retour None. La correction consiste à ne pas affecter le résultat :


shuffle(valeurs)

Après cette ligne, valeurs est toujours la même liste, mais ses éléments ont été mélangés (exécuté : shuffle(v) renvoie None et v contient ensuite les 16 entiers dans un ordre aléatoire).

4. La précondition à vérifier est que la liste contient $n \times n$ éléments ; on l'exprime par une assertion (avec un message facultatif) :


    assert len(valeurs) == n * n, "la liste doit contenir n*n éléments"

Si la condition est fausse, une exception AssertionError est levée et le programme s'arrête, ce qui vaut mieux qu'un résultat faux : en_grille([1, 2, 3], 2) déclenche bien l'assertion (vérifié).

5. L'élément situé à la ligne i et à la colonne j de la grille est précédé, dans la liste aplatie, de i lignes complètes de n éléments puis de j éléments : son indice est i n + j. La ligne 6 du sujet utilise j n + i, qui échange les rôles de la ligne et de la colonne (la grille obtenue est la transposée de la grille attendue, d'où [[1, 3], [2, 4]]). Correction :


            grille[i][j] = valeurs[i * n + j]

Trace pour en_grille([1, 2, 3, 4], 2) : $(i, j) = (0, 0)$ lit l'indice 0, soit 1 ; $(0, 1)$ lit l'indice 1, soit 2 ; $(1, 0)$ lit l'indice $1 \times 2 + 0 = 2$ , soit 3 ; $(1, 1)$ lit l'indice 3, soit 4. La fonction renvoie bien [[1, 2], [3, 4]], et en_grille([1, ..., 16], 4) renvoie la grille rangee (vérifié).

Partie B : Grille résoluble

6. La liste aplatie correspondante est [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 15, 14]. Les treize premiers éléments sont dans l'ordre croissant et plus petits que tous les suivants : ils ne créent aucune inversion. Il reste les couples d'indices parmi 13, 14 et 15 :

(13, 14) : $16 > 15$ , inversion ;
(13, 15) : $16 > 14$ , inversion ;
(14, 15) : $15 > 14$ , inversion.

Le nombre d'inversions vaut 3. La tuile vide (16) est en ligne 3, colonne 1 ; sa position finale est la ligne 3, colonne 3 : elle est séparée de $0$ ligne et de $2$ colonnes, la distance vaut 2. La somme $3 + 2 = 5$ est impaire : d'après le critère admis, la grille n'est pas résoluble.

Ce que le correcteur attend : compter les inversions sur la liste aplatie avec la valeur 16 (la tuile vide compte), et donner la parité de la somme.

7. Le sujet fournit lui-même une liste de quatre éléments à deux inversions, [6, 9, 7, 8] ; le test s'écrit :


assert compte_inversions([6, 9, 7, 8]) == 2

Tout autre exemple convient, par exemple assert compte_inversions([2, 1, 4, 3]) == 2 (inversions (0, 1) et (2, 3)).

8. Dans la fonction proposée, la boucle intérieure parcourt tous les indices j, y compris ceux qui sont inférieurs à i : la condition i < j de la définition n'est pas respectée. Pour deux valeurs distinctes, l'une des deux comparaisons valeurs[i] > valeurs[j] ou valeurs[j] > valeurs[i] est toujours vraie : la fonction compte donc toutes les paires, soit $(2 4) = 6$ pour n'importe quelle liste de quatre éléments distincts. Exécutée, elle renvoie 6 pour [1, 2, 3, 4] (au lieu de 0), 6 pour [6, 9, 7, 8] (au lieu de 2) : aucun des deux tests ne passe. Il suffit de faire démarrer j à i + 1 :


def compte_inversions(valeurs):
    total = 0
    for i in range(len(valeurs)):
        for j in range(i + 1, len(valeurs)):
            if valeurs[i] > valeurs[j]:
                total = total + 1
    return total

Les tests compte_inversions([1, 2, 3, 4]) == 0, compte_inversions([6, 9, 7, 8]) == 2, compte_inversions([4, 3, 2, 1]) == 6 et compte_inversions([]) == 0 passent tous (exécutés). La fonction reste de complexité quadratique : pour une liste de longueur $p$ , on effectue $p (p - 1) /2$ comparaisons, soit $O (p^{2})$ .

9. On cherche la case contenant la valeur num_tuile_vide (soit $n \times n$ , c'est-à-dire 16 pour le taquin classique). Si elle est en ligne i et colonne j, la position finale étant la ligne n - 1 et la colonne n - 1, la distance vaut (n - 1 - i) + (n - 1 - j) :


            if grille[i][j] == num_tuile_vide:
                return (n - 1 - i) + (n - 1 - j)

Vérifications exécutées : pour melangee (tuile vide en $(0, 1)$ ) la fonction renvoie $3 + 2 = 5$ , la valeur annoncée par le sujet ; pour la grille rangée elle renvoie 0 ; pour la grille de la question 6 elle renvoie 2.

10. On calcule le nombre d'inversions sur la liste aplatie, la distance sur la grille, puis on teste la parité de leur somme avec l'opérateur % :


def est_resoluble(valeurs, n):
    grille = en_grille(valeurs, n)
    inv = compte_inversions(valeurs)
    dis = distance_tuile_vide(grille, n)
    return (inv + dis) % 2 == 0

Exécutée, est_resoluble renvoie False pour la liste de la question 6 (somme 5), True pour la grille rangée (somme 0) et True pour la grille mélangée de la figure 1 (73 inversions, distance 5, somme 78 paire).

Ce que le correcteur attend : compte_inversions reçoit la liste aplatie valeurs, distance_tuile_vide reçoit la grille et n ; ne pas inverser les deux arguments.

Partie C : Mélange réaliste

11. Dans une grille $4 \times 4$ , l'indice k de la liste aplatie correspond à la ligne k // 4 et à la colonne k % 4 : l'indice 9 est en ligne 2, colonne 1, c'est-à-dire une case intérieure de la grille qui possède quatre voisines : au-dessus (ligne 1, colonne 1, indice $9 - 4 = 5$ ), à gauche (indice $9 - 1 = 8$ ), à droite (indice $9 + 1 = 10$ ) et au-dessous (ligne 3, colonne 1, indice $9 + 4 = 13$ ). Une valeur possible est donc


graphe_4_4[9] = [5, 8, 10, 13]

dans n'importe quel ordre. (Vérifié par construction du graphe complet : graphe_3_3[8] redonne bien [5, 7] par la même règle.)

12. À chaque tour de boucle, on tire au hasard une case prochaine voisine de la case actuelle de la tuile vide (dans graphe[actuelle]), on fait glisser la tuile qui s'y trouve vers la case actuelle, puis on place la tuile vide en prochaine :


def melange_graphe(nb_dep, n, graphe):
    valeurs = [i for i in range (n*n)]#liste aplatie rangée
    num_tuile_vide = n * n
    actuelle = num_tuile_vide - 1#position de la tuile vide
    for k in range(nb_dep):
        prochaine = choice(graphe[actuelle])
        valeurs[actuelle] = valeurs[prochaine]
        valeurs[prochaine] = num_tuile_vide
        actuelle = prochaine
    return en_grille(valeurs, n)

L'ordre des lignes 9 et 10 est essentiel : on copie d'abord la tuile voisine dans la case de la tuile vide, puis seulement on écrase la case voisine avec num_tuile_vide ; dans l'ordre inverse, la tuile voisine serait perdue.

Ce que le correcteur attend : range(nb_dep) et non range(n), et choice appliqué à la liste des voisins de la case courante, graphe[actuelle], pas à graphe tout entier.

Remarque sur la ligne 4. Telle qu'elle est écrite dans le sujet, [i for i in range (nn)] contient les entiers de 0 à $n^{2} - 1$ , alors que la convention de l'exercice (et la valeur num_tuile_vide = n n) suppose la liste rangée [1, ..., nn] : c'est la même erreur de borne qu'à la question 2. Avec range(1, nn + 1), la fonction complétée a été exécutée sur 2 000 mélanges (grilles $2 \times 2$ , $3 \times 3$ et $4 \times 4$ , de 0 à 200 déplacements) : elle renvoie chaque fois une permutation de $1$ à $n^{2}$ que est_resoluble déclare résoluble. C'est attendu : chaque échange est un glissement légal, donc la suite des glissements inverses ramène la grille rangée.

Poser une question au tuteur sur ce sujet