Sujet du CAPES 2017, épreuve d'informatique¶
Problème 1 - Sudoku¶
Source: http://www4.ac-nancy-metz.fr/capesmath/data/uploads/EP1_Info_2017.pdf
N.B.: Ceci ne représente ni LA solution ni LE corrigé de cette épreuve mais uniquement la façon avec laquelle je répondrais à une telle série d'exercices.
Partie A - Généralités¶
Question 2¶
Écrire une fonction ligne_complete(L,i) qui prend une liste Sudoku L et un entier i entre 0 et 8,
et renvoie True si la ligne i du Sudoku L vérifie les conditions de remplissage d’un Sudoku, et False
sinon.
On définit de même (on ne demande pas de les écrire) les fonctions colonne_complete(L,i) pour
la colonne i et carre_complet(L,i) pour le carré i.
# Q.2
def ligne_complete(L, i, debug=False):
""" Renvoie True si la ligne *i* du sudoku *L* vérifie les
conditions de remplissage d'un sudoku. """
ligne = L[i] # la ligne qui nous intéresse
if debug:
print(ligne)
if sum(ligne) == 45:
# si la ligne rempli la condition, la somme doit faire 45
# ce test n'est pas vraiment utile mais c'est pour faire un
# lien avec la question 1
for n in range(1, 10):
if n not in ligne:
return False
else:
return False
return True
# fonction non demandée mais nécessaire pour tester l'ensemble
def colonne_complete(L, i, debug=False):
""" Renvoie True si la colonne *i* du sudoku *L* vérifie les
conditions de remplissage d'un sudoku. """
col = [ligne[i] for ligne in L] # on construit/extrait la colonne
if debug:
print(col)
if sum(col) == 45:
# si la colonne remplit la condition, la somme doit faire 45
for n in range(1, 10):
if n not in col:
return False
else:
return False
return True
# fonction non demandée mais nécessaire pour tester l'ensemble
def carre_complet(L, i, debug=False):
""" Renvoie True si le carré *i* du sudoku *L* vérifie les
conditions de remplissage d'un sudoku. """
# on construit/extrait les valeurs du carré
carre = [L[n][m] for n in range((i//3) * 3, (i//3) * 3 + 3) for m in range((i%3)*3, (i%3)*3 + 3)]
# pour un carré *i*, on cherche l'indice de "méta-ligne" (ligne "d'épaisseur" 3) donné par I=i//3
# ainsi les lignes concernées sont la I*3, la I*3 + 1 et la I*3 + 2,
# par exemple pour le carré 4, les lignes 3, 4 et 5
# pour les colonnes, on fait un raisonnement similaire sauf que cette fois I est donné par I=i%3
# dans la question 6, on autre approche a été proposée
if debug:
print(carre)
if sum(carre) == 45:
# si le carre rempli la condition, la somme doit faire 45
for n in range(1, 10):
if n not in carre:
return False
else:
return False
return True
Question 3¶
Écrire une fonction complet(L) qui prend une liste Sudoku L comme argument, et qui renvoie True
si la grille est complète, False sinon.
# Q.3
def complet(L):
""" Renvoie True si le sudoku *L* est entièrement remplit en respectant les contraintes
inhérentes au sudoku. """
for i in range(9):
if not (ligne_complete(L, i) and colonne_complete(L, i) and carre_complet(L, i)):
return False
return True
# Premier exemple d'une grille incomplète
L= [
[0,6,0,0,0,0,2,0,5],
[4,0,0,9,2,1,0,0,0],
[0,7,0,0,0,8,0,0,1],
[0,0,0,0,0,5,0,0,9],
[6,4,0,0,0,0,0,7,3],
[1,0,0,4,0,0,0,0,0],
[3,0,0,7,0,0,0,6,0],
[0,0,0,1,4,6,0,0,2],
[2,0,6,0,0,0,0,1,0]
]
# on teste les fonctions définies précédemment
ligne_complete(L, 1, True)
colonne_complete(L, 2, True)
carre_complet(L, 8, True)
complet(L)
Question 4¶
Compléter la fonction suivante ligne(L,i), qui renvoie la liste des nombres compris entre 1 et 9 qui
apparaissent sur la ligne d’indice i.
def ligne(L,i):
chiffre = []
for j in ....:
if ( ....) :
chiffre.append(L[i][j])
return chiffre
Ainsi, avec la grille donnée dans l’énoncé, on doit obtenir :
>>> ligne(L,0)
[6, 2, 5]
On définit alors, de la même manière, la fonction colonne(L,j) qui renvoie la liste des nombres
compris entre 1 et 9 qui apparaissent dans la colonne j (on ne demande pas d’écrire son code).
# Q.4
def ligne(L, i):
""" Renvoie la liste des nombres compris entre 1 et 9 qui apparaissent sur la ligne *i*
"""
chiffre = []
for j in range(9):
if (0 < L[i][j] < 10):
chiffre.append(L[i][j])
return chiffre
# Autre façon de faire plus "pythonique"
def ligne_bis(L, i):
return [n for n in L[i] if n != 0]
ligne(L, 0)
# fonction non demandée mais utile pour la suite (version pythonique)
def colonne(L, i):
""" Renvoie la liste des nombres compris entre 1 et 9 qui apparaissent sur la ligne *i*
"""
return [l[i] for l in L if l[i] != 0]
colonne(L, 0)
Question 6¶
Compléter alors la fonction carre(L,i,j), qui renvoie la liste des nombres compris entre 1 et 9 qui
apparaissent dans le carré 3 × 3 auquel appartient la case (i, j).
def carre(L,i,j):
icoin = 3*(i//3)
jcoin = 3*(j//3)
chiffre = []
for i in range (....):
for j in range (....):
if (....):
chiffre.append(L[i][j])
return chiffre
On rappelle que si x et y sont des entiers, 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 :
>>> carre(L,4,6)
[9, 7, 3]
>>>carre(L,4,5)
[5, 4]
# Q6
def carre(L, i, j, debug=False):
""" Renvoie la liste des nombres compris entre 1 et 9 qui apparaissent dans le carré 3 × 3
auquel appartient la case (i,j). """
icoin = 3 * (i // 3)
jcoin = 3 * (j // 3)
if debug:
print(icoin, jcoin)
chiffre = []
for i in range(icoin, icoin + 3):
for j in range (jcoin, jcoin + 3):
if debug:
print(i, j, L[i][j])
if (0 < L[i][j] < 10):
chiffre.append(L[i][j])
return chiffre
carre(L, 4, 6, True)
carre(L, 4, 5, True)
Question 7¶
Déduire des questions précédentes une fonction conflit(L,i,j) renvoyant la liste des chiffres que
l’on ne peut pas écrire en case (i,j) sans contredire les règles du jeu. La liste renvoyée peut très bien
comporter des redondances. On ne prendra pas en compte la valeur de L[i][j].
# Q:7
def conflit(L, i, j):
""" Renvoie la liste des chiffres que l'on ne peut pas écrire en case (i,j). """
conf = ligne(L, i) # les conflits par rapport à la ligne *i*
conf.extend(colonne(L, j)) # les conflits par rapport à la colonne *j*
conf.extend(carre(L, i ,j)) # les conflits par rapport au carré contenant la case
return list(set(conf)) # petit passage par les ensembles uniquement pour enleves les redondances
conflit(L, 5, 5)
Question 8¶
Compléter enfin la fonction chiffres_ok(L,i,j) qui renvoie la liste des chiffres que l’on peut écrire
en case (i, j).
def chiffres_ok(L,i,j):
ok = []
conflit = conflit(L,i,j)
for k in ....:
if ....:
ok.append(k)
return ok
Par exemple, avec la grille initiale :
>>> chiffres_ok(L,4,2)
[2, 5, 8, 9]
# Q.8
# Attention, ici il y avait une erreur dans le sujet: une variable locale et une fonction portait
# le même nom:
# conflit = conflit(L,i,j)
# cf. résolution de la portée des variables/fonctions, et les notions de polymorphisme/surcharge
# qui n'existent pas en Python
def chiffre_ok(L, i ,j):
""" Renvoie la liste des chiffres qu'il est possible de placer dans la case (i,j) """
ok = []
conflit_list = conflit(L, i, j)
for k in range(1, 10):
if k not in conflit_list:
ok.append(k)
return ok
# une autre façon de faire en passant par les ensembles
def chiffre_ok_bis(L, i, j):
return set(range(1, 10)) - set(conflit(L, i, j))
# une façon de faire en gardant les listes mais plus pythonique
def chiffre_ok_ter(L, i, j):
return [n for n in range(1, 10) if n not in conflit(L, i, j)]
chiffre_ok(L, 4, 2)
chiffre_ok_bis(L, 4 ,2)
chiffre_ok_ter(L, 4, 2)
Partie B - Algorithme naïf¶
# Second exemple de grille incomplète
M= [[2, 0, 0, 0, 9, 0, 3, 0, 0],
[0, 1, 9, 0, 8, 0, 0, 7, 4],
[0, 0, 8, 4, 0, 0, 6, 2, 0],
[5, 9, 0, 6, 2, 1, 0, 0, 0],
[0, 2, 7, 0, 0, 0, 1, 6, 0],
[0, 0, 0, 5, 7, 4, 0, 9, 3],
[0, 8, 5, 0, 0, 9, 7, 0, 0],
[9, 3, 0, 0, 5, 0, 8, 4, 0],
[0, 0, 2, 0, 6, 0, 0, 0, 1]]
Question 9¶
A partir des fonctions annexes, écrire une fonction nb_possible(L,i,j), indiquant le nombre de
chiffres possibles à la case (i, j).
# Q.9
def nb_possible(L, i ,j):
""" Renvoie le nombre de chiffres possibles en case (i,j) """
return len(chiffre_ok(L, i ,j))
nb_possible(L, 4, 2)
Question 10¶
On souhaite disposer de la fonction un_tour(L) qui parcourt l’ensemble 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, en partant de la grille initiale M :
>>> un_tour(M)
True
>>> M
[[2, 0, 0, 0, 9, 0, 3, 0, 0],
[0, 1, 9, 0, 8, 0, 5, 7, 4],
[0, 0, 8, 4, 0, 0, 6, 2, 9],
[5, 9, 0, 6, 2, 1, 4, 8, 7],
[0, 2, 7, 0, 3, 8, 1, 6, 5],
[0, 6, 1, 5, 7, 4, 2, 9, 3],
[0, 8, 5, 0, 0, 9, 7, 3, 0],
[9, 3, 6, 0, 5, 0, 8, 4, 2],
[0, 0, 2, 0, 6, 0, 9, 5, 1]]
On propose la fonction suivante :
def un_tour(L):
changement = False
for i in range(1,9):
for j in range(1,9):
if (L[i][j] = 0):
if (nb_possible(L,i,j) = 1):
L[i][j] = chiffres_ok(L,i,j)[1]
return changement
Recopier ce code en en corrigeant les erreurs.
# Q.10
def un_tour(L):
""" Parcours l'ensemble des cases du sudoku et remplit les cases n'ayant qu'une seule possibilité.
Renvoie True si au moins une case a été remplie, False sinon.
"""
changement = False
for i in range(0, 9):
for j in range(0, 9):
if L[i][j] == 0:
if nb_possible(L, i ,j) == 1:
L[i][j] = chiffre_ok(L, i ,j)[0]
changement = True
return changement
un_tour(M)
M
Question 11¶
Écrire une fonction complete(L) qui exécute la fonction un_tour tant qu’elle modifie la liste, et
renvoie True si la grille est complétée, et False sinon.
# Q.11
def complete(L):
""" Essaie de compléter la grille en remplissant itérativement les cases n'ayant qu'une seule possibilité.
Renvoie True si la grille finale est complète, False sinon. """
while un_tour(L):
pass
return complet(L)
complete(M)
M
Partie C - Backtracking¶
Question 12¶
Écrire une fonction case_suivante(pos) qui prend une liste pos du couple des coordonnées de la
case, et renvoie la liste du couple d’indices de la case suivante en utilisant l’ordre lexicographique, et
qui renvoie [9,0] si pos=[8,8]. Par exemple :
>>> case_suivante([1,3])
[1, 4]
>>> case_suivante([8,8])
[9, 0]
# Q.12
def case_suivante(pos):
""" Renvoie la case suivante dans la grille. """
x = pos[0] + (pos[1] + 1) // 9
y = (pos[1] + 1) % 9
return [x, y]
case_suivante([1,3])
case_suivante([8, 8])
Question 13¶
Compléter le squelette de la fonction backtracking(L,pos) selon les règles précédentes.
def backtracking(L,pos):
"""
pos est une liste désignant une case du sudoku,
[0,0] pour le coin en haut à gauche.
"""
if (pos==[9 , 0]):
.....
i,j = pos[0],pos[1]
if L[i][j] != 0:
return .....
for k in ....:
L[i][j] = ....
if ....:
return ....
L[i][j] = ....
return ....
# Q.13
nb_appel = 0 # sert uniquement pour le debuggage pour que chaque appel à la fonction ait un numéro unique
def backtracking(L, pos, debug=False):
"""
pos est une liste désignant une case du sudoku,
[0, 0] pour le coin en haut à gauche.
"""
global nb_appel # sert uniquement pour suivre le debuggage
appel = nb_appel # idem
nb_appel += 1 # idem
if debug:
print("enter backtrack niveau " + str(appel))
print("pos: " + str(pos) + " ", end='')
if pos == [9, 0]:
return True
i, j = pos[0], pos[1]
if debug:
print(L[i][j])
if L[i][j] != 0:
return backtracking(L, case_suivante(pos), debug)
if debug:
print(chiffre_ok(L, i, j))
for k in chiffre_ok(L, i, j):
if debug:
print(k)
L[i][j] = k
if backtracking(L, case_suivante(pos), debug):
return True
L[i][j] = 0
if debug:
print("exit backtrack niveau " + str(appel))
return False
# juste un rappel de la seconde grille initiale
M= [[2, 0, 0, 0, 9, 0, 3, 0, 0],
[0, 1, 9, 0, 8, 0, 0, 7, 4],
[0, 0, 8, 4, 0, 0, 6, 2, 0],
[5, 9, 0, 6, 2, 1, 0, 0, 0],
[0, 2, 7, 0, 0, 0, 1, 6, 0],
[0, 0, 0, 5, 7, 4, 0, 9, 3],
[0, 8, 5, 0, 0, 9, 7, 0, 0],
[9, 3, 0, 0, 5, 0, 8, 4, 0],
[0, 0, 2, 0, 6, 0, 0, 0, 1]]
# Les affichages de cet appel sont long, c'est à cause du mode debuggage pour illustrer et bien comprendre
# cette fonction
backtracking(M, [0, 0], True)
# on vérifie la grille obtenue
complet(M)
M
Question 15¶
Que renvoie la fonction solution_sudoku(L) si le sudoku L admet plusieurs solutions ? Et si L est
le sudoku rempli de 0 ?
# Q.15
# on créé une grille vide
N = [[0]*9 for _ in range(9)]
N
backtracking(N, [0, 0])
N
Question 16¶
Dans l’algorithme précédent, on parcourt l’ensemble des cas dans l’ordre lexicographique. Comment améliorer celui-ci pour limiter le nombre d’appels à la variable pos ?
# Q.16
# Sans doute en parcourant les cases d'abord par carré puis par ligne, puis par colonne