Exercices de programmation pour classes préparatoires
Écrire une fonction resoudre_sudoku(grille) qui prend une grille de Sudoku 9x9 (liste de 9 listes de 9 entiers) et renvoie la grille résolue. Les cases vides sont représentées par des 0.
Le Sudoku doit respecter les regles suivantes : - Chaque ligne contient les chiffres de 1 a 9 exactement une fois. - Chaque colonne contient les chiffres de 1 a 9 exactement une fois. - Chaque sous-grille 3x3 contient les chiffres de 1 a 9 exactement une fois.
On utilisera un algorithme de backtracking : pour chaque case vide, essayer les chiffres de 1 a 9 ; si un chiffre est valide (pas de conflit ligne/colonne/sous-grille), le placer et passer a la case suivante ; sinon revenir en arriere.
La fonction renvoie la grille complétée (une nouvelle liste de listes).
| Appel | Résultat attendu |
|---|---|
| resoudre_sudoku([[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]) | [[5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9]] |
| resoudre_sudoku([[2,9,5,7,4,3,8,6,1],[4,3,1,8,6,5,9,0,7],[8,7,6,1,9,2,5,4,3],[3,8,7,4,5,9,2,1,6],[6,1,2,3,8,7,4,9,5],[5,4,9,2,1,6,7,3,8],[7,6,3,5,2,4,1,8,9],[9,2,8,6,7,1,3,5,4],[1,5,4,9,3,8,6,0,2]]) | [[2, 9, 5, 7, 4, 3, 8, 6, 1], [4, 3, 1, 8, 6, 5, 9, 2, 7], [8, 7, 6, 1, 9, 2, 5, 4, 3], [3, 8, 7, 4, 5, 9, 2, 1, 6], [6, 1, 2, 3, 8, 7, 4, 9, 5], [5, 4, 9, 2, 1, 6, 7, 3, 8], [7, 6, 3, 5, 2, 4, 1, 8, 9], [9, 2, 8, 6, 7, 1, 3, 5, 4], [1, 5, 4, 9, 3, 8, 6, 7, 2]] |
Connectez-vous pour soumettre du code.