Devoir Maison Révisions – CPGE TSI1 – À rendre le mercredi 30 avril 2025

La résolution d’une grille de Sudoku est une gymnastique du cerveau qui peut être assimilée à un décodage
correcteur d'effacement. En effet, à partir d'une grille presque vide, il est possible (pour une grille bien faite) de
la compléter d'une manière unique. L'objectif de cet exercice est de mettre en œuvre deux méthodes permet-
tant de compléter une grille de Sudoku, l'une native, et l'autre par backtracking.
Une grille de Sudoku est une grille de taille 9 × 9 découpée en 9 carrés de taille 3 × 3. Le but est de la remplir
de chiffres entre 1 et 9, de sorte que chaque ligne, chaque colonne et chacun des carrés de taille 3 × 3 contienne
une et une seule fois chaque entier de 1 à 9. On dira alors que la grille est bien remplie. En pratique, certaines
cases sont déjà remplies et on fera l'hypothèse que le Sudoku qui nous intéresse est bien écrit, c'est-à-dire qu'il
possède une unique solution. 6 2 5
On représente en Python une grille de Su- 4 9 2 1
doku par une liste de taille 9 × 9, c'est-à-dire 7 8 1
une liste de 9 listes de taille 9, dans laquelle 5 9
les cases non remplies sont associées au 6 4 7 3
chiffre 0. Ainsi, la grille suivante est repré-
1 4
sentée par la liste ci-contre :
3 7 6
1 4 6 2
2 6 1

Les 9 carrés de taille 3 × 3 sont numérotés du haut à gauche jusqu'en bas à droite. Ainsi, sur cette grille, le carré
0, en haut à gauche, contient les chiffres 6, 4 et 7 ; le carré 1, en haut au milieu, contient les chiffres 9, 2, 1 et
8 ; le carré 8 contient les chiffres 6, 2 et 1.
Rappels
 Les lignes du Sudoku sont alors les éléments de L accessibles par L[0], ... , L[8].
 L'élément de la case (𝑖; 𝑗) est accessible par L[i][j].
Remarques
 On fera bien attention, dans l'ensemble du sujet, aux indices des listes !
 Les lignes, ainsi que les colonnes et les carrés, sont indicées de 0 à 8 inclus !
Partie 1 [11 points]– Généralités et fonctions annexes

⚠ On rappelle que l’opérateur in d’appartenance à une liste est interdit, mais on peut utiliser ce mot clé dans
les autres contextes (par exemple dans une boucle for).
1 [0,5 point] Écrire une fonction recherche qui prend en arguments une Exemple
liste L et un entier elt, qui renvoie l’une des positions de l’élément elt
>>> recherche(3,[1,7,3,4])
dans la liste L. Si l’élément n’est pas trouvé dans la liste, la fonction devra
2
retourner −1. Cette fonction sera utile par la suite dans de nombreuses >>> recherche(6,[1,7,3,4])
questions. -1
2 [0,75 point] Montrer que si une grille de Sudoku est complète, alors pour chacune des lignes, chacune des
colonnes et chacun des carrés de taille 9 × 9, la somme des chiffres fait 45. La réciproque est-elle vraie ?
On va commencer par écrire des fonctions permettant de vérifier si un Sudoku est bien rempli. On rappelle que L
est la grille complète (liste de listes) représentant le Sudoku dont on pourra extraire des lignes, des colonnes ou
des carrés.

1
 Devoir Maison Révisions – CPGE TSI1 – À rendre le mercredi 30 avril 2025

3 [0,25 point] Quelle commande permet d’accéder à la ligne i du Sudoku représenté par la grille L ?

4 [1 point] Écrire une fonction ligneBienRemplie qui prend en argument une liste du Sudoku L et un entier i
entre 0 et 8, et renvoie True si la ligne est bien rempli et False sinon. On rappelle que la ligne i est bien remplie
si elle contient exactement les chiffres de 1 à 9 (on pourra utiliser ou pas la fonction recherche).

5 [0,5 point] Comment sont notés les neuf éléments de la colonne j du Sudoku représenté par la grille L ?

6 [1 point] Écrire de même une fonction colonneBienRemplie pour la colonne j.

7 [1 point] Écrire de même une fonction carreBienRempli(L,i) pour le carré i.

8 [1 point] Écrire une fonction bienRempli qui prend en paramètre une liste de Sudoku L, et qui renvoie True
si la grille est bien remplie, False sinon.

9 [1 point] Recopier et compéter avec une couleur différente la fonction ci-

contre ligne qui prend en arguments une liste L et deux entiers i et j, et qui
renvoie la liste des nombres compris entre 1 et 9 qui apparaissent sur la ligne
d’indice i en ne tenant pas compte de L[i][j].
Ainsi avec la grille donnée dans l’énoncé, on doit obtenir : Exemple
10 [1 point] On définit de la même manière, la fonction colonne(L,i,j) qui >>> ligne(L,0,0)
[6,2,5]
renvoie la liste des nombres comprise entre 1 et 9 qui apparaissent dans la co-
>>> ligne(L,0,1)
lonne j excepté L[i][j] (on ne demande pas d’écrire le code de la fonction
[2,5]
colonne). Que devrait renvoyer la commande colonne(L,6,3).

11 [1,5 point] On se donne une case (𝑖, 𝑗) avec (𝑖, 𝑗) dans Exemple
{0, … , 8}2 . On admet que la case en haut à gauche du carré Le carré n° 8 (en bas à droite) auquel appar-
3 × 3 auquel appartient la case (𝑖, 𝑗) a pour coordonnées : tient la case de coordonnées (7,8) a pour case
𝑖 𝑗 de coin en haut à gauche :
(3 × ⌊ ⌋ , 3 × ⌊ ⌋) où ⌊𝑥⌋ représente la partie entière de 𝑥.
3 3
7 8
Recopier alors et compléter (avec une couleur différente) la (3 × ⌊ ⌋ , 3 × ⌊ ⌋) = (6,6)
3 3
fonction carre qui prend en arguments une liste L et deux
entiers i et j, et qui renvoie la liste des Exemples
nombres compris entre 1 et 9 qui apparais-
>>> carre(L,4,6)
sent dans le carré 3 × 3 auquel appartient la [9,7,3]
case (𝑖, 𝑗) toujours sans tenir compte de la >>> carre(L,4,7)
case (𝑖, 𝑗). On rappelle que si x et y sont des [9,3]
entiers, alors x//y renvoie le quotient de la
division euclidienne de x par y. Ainsi, avec la grille donnée dans l’énoncé, on doit obtenir :

12 [0,5 point] Déduire des trois questions précédentes une fonction conflit qui prend en arguments une liste
L et deux entiers i et j, et qui renvoie la liste des chiffres que l’on ne peut pas écrire en case (𝑖, 𝑗) sans contredire
les règles du jeu. La liste envoyée peut très bien comporter des redondances. On ne prendra toujours pas en
compte la valeur de L[i][j].

13 [1 point] Recopier et compléter avec une

couleur différente la fonction chiffresOk qui Exemple
prend en arguments une liste L et deux entiers >>> chiffresOk(L,4,2)
i et j, et qui renvoie la liste des chiffres que l’on [2,5,8,9]
peut écrire en case (𝑖, 𝑗).

2
 Devoir Maison Révisions – CPGE TSI1 – À rendre le mercredi 30 avril 2025
On pourra dans la suite du sujet utiliser librement les fonctions annexes définies précédemment comme si elles
avaient été implémentées correctement.
Partie 2 [2,5 points]– Algorithme naïf
Naïvement, on commence par compléter les 2 9 3
cases n’ayant qu’une seule possibilité. Nous 1 9 8 7 4
prendrons dans la suite comme Sudoku la 8 4 6 2
grille ci-contre. 5 9 6 2 1
1 [0,5 point] À partir des fonctions écrites 2 7 1 6
dans la partie 1, écrire une fonction nbPos- 5 7 4 9 3
sible qui prend en arguments une liste L et 8 5 9 7
deux entiers i et j, et qui renvoie le nombre 9 3 5 8 4
de chiffres possibles à la case (𝑖, 𝑗). 2 6 1
2 [1 point] On souhaite disposer de la fonction unTour qui prend en argument une liste L et qui parcourt l’en-
semble des cases du Sudoku et qui complète les cases dans le cas où il n’y a qu’un chiffre possible, et renvoie
True s’il y a eu un changement, et False sinon. La liste L est alors modifiée par effet de bords.

Par exemple, on propose la fonction ci-contre :

Recopier ce code en corrigeant les erreurs (avec une couleur
différente).

3 [1 point] Écrire une fonction complete qui prend en argu-

ment une liste L et qui exécute la fonction unTour tant qu’elle
modifie la liste, et renvoie True si la grille est complète et False sinon.
Partie 3 [6,5 points] – Backtracking
La deuxième idée est de résoudre la grille par
"Backtracking" ou "retour en arrière". L’objec- 2 5 4 9 6 3
tif est d’essayer de compléter la grille de Su-
1 9 8 7 4
doku en testant les combinaisons, en com-
8 4 6 2
mençant par la première case, et jusqu’à la
dernière. Si on obtient un conflit avec les 5 9 6 2 1
règles, ou est obligé de revenir en arrière. 2 7 1 6
5 7 4 9 3
On va compléter la grille en utilisant l’ordre
8 5 9 7
lexicographique, c’est-à-dire les cases (0 , 0),
(0 , 1), …, (0 , 8), puis (1 , 0), (1 , 1), … ,(1 , 8), 9 3 5 8 4
(2 , 0), …, (8 , 8). Considérons pour cette par- 2 6 1
tie le Sudoku ci-contre.
1 [1 point] Écrire une fonction caseSuivante qui prend en argument une liste pos qui est le couple des coor-
données de la case et renvoie le couple des coordonnées de la case suivante en utilisant l’ordre lexicographique.
Elle devra renvoyer [9,0] si pos=[8,8]. Par exemple :

Exemples
>>> caseSuivante([1,3]) >>> caseSuivante([1,8]) >>> caseSuivante([8,8])
[1,4] [2,0] [9,0]

3
 Devoir Maison Révisions – CPGE TSI1 – À rendre le mercredi 30 avril 2025
La fonction principale va avoir la structure ci-contre où la fonction récursive backtracking(L,pos) doit ren-
voyer True s’il est possible de compléter la grille à partir des hypothèses faites sur les cases qui précèdent la
case pos, et False dans le cas contraire. Ainsi,
◼ Si pos est la liste [9,0], alors la grille est complétée
et on renvoie True (cas d’arrêt).
◼ Si la case est déjà remplie (donnée initiale du Su-
doku), on passe à la case suivante via un appel récursif.
◼ Sinon, on affecte un des chiffres possibles à la case,
et on passe à la case suivante par un appel récursif.
2 [4 points] Compléter le squelette de la fonction
backtracking(L,pos) selon les règles précédentes.

3 [0,5 point] On suppose qu’au départ, il y a 𝑝 cases

déjà remplies. Montrer qu’au maximum la fonction
backtracking est appelée 981−𝑝 fois.

4 [0,5 point] Que renvoie la fonction solution_sudoku(L) si le Sudoku L admet plusieurs solutions ? et si L
est le sudoku rempli de 0 ?

5 [0,5 point] Dans le programme précédent, on parcourt l’ensemble des cas dans l’ordre lexicographique. Com-
ment améliorer celui-ci pour limiter le nombre d’appels à la variable pos ?

***** Fin du sujet *****