====== TP 0.5 ======
Pour aller plus loin que le TP0. En est la suite directe.
===== Sudoku Incomplet =====
On remplacera par des 0 les nombres inconnus. La variable ci-après est par exemple un sudoku incomplet de la grille précédente :
grille_1 = [0, 0, 0, 0, 0, 0, 0, 4, 0,
0, 0, 8, 4, 0, 2, 0, 5, 7,
0, 0, 4, 8, 0, 3, 2, 1, 0,
7, 4, 0, 0, 0, 5, 0, 9, 0,
2, 0, 3, 1, 0, 6, 4, 0, 5,
0, 8, 0, 7, 0, 0, 0, 6, 2,
0, 3, 2, 5, 0, 7, 9, 0, 0,
9, 6, 0, 2, 0, 8, 5, 0, 0,
0, 5, 0, 0, 0, 0, 0, 0, 0]
Ecrivez 3 méthodes permettant de rendre pour une ligne, une colonne ou une sous-matrice particulière un ensemble de valeurs manquantes.
Ainsi, les commandes :
print("valeurs manquantes ligne 5", valeurs_manquantes_ligne(5, grille_1))
print("valeurs manquantes colonne 5", valeurs_manquantes_colonne(5, grille_1))
print("valeurs manquantes sous-matrice issue de 5, 5", valeurs_manquantes_matrice(5, 5, grille_1))
Affichent chez moi :
valeurs manquantes ligne 5 {1, 3, 4, 5, 9}
valeurs manquantes colonne 5 {1, 9, 4}
valeurs manquantes sous-matrice issue de 5, 5 {8, 9, 2, 3, 4}
==== Valeurs manquantes ====
En déduire une méthode permettant de donner les valeurs possibles pour une case donnée (en ne prenant en compte que les valeurs manquantes). Par exemple :
print("possible en 5, 5:", possible_sudoku(5, 5, grille_1))
Affiche :
possible en 5, 5: {9, 4}
==== Complète ce qui est unique ====
Il n'y a qu'une seule possibilité pour la case (3, 3), Laquelle ? Ecrivez une méthode qui remplit toutes les cases à une unique possibilité. Cette méthode doit rendre un sudoku que l'on espère complet, ou au pire qui ne contient que des valeurs incomplètes ayant plus d'un choix.
Chez moi :
grille_1_complet_1_possible = rempli_sudoku_possible(grille_1)
affiche_sudoku(grille_1_complet_1_possible)
print("valeurs manquantes (3, 2)", possible_sudoku(3, 2, grille_1_complet_1_possible))
print("valeurs manquantes (3, 6)", possible_sudoku(3, 6, grille_1_complet_1_possible))
print("valeurs manquantes (3, 8)", possible_sudoku(3, 8, grille_1_complet_1_possible))
Affiche :
020 000 040
018 402 057
074 803 210
740 325 090
293 186 475
080 700 062
032 507 980
960 208 530
050 000 020
valeurs manquantes (3, 2) {1, 6}
valeurs manquantes (3, 6) {8, 1}
valeurs manquantes (3, 8) {8, 1}
Ce n'est donc pas fini, mais on a un peu avancé.
===== Sudoku Incomplet v2=====
Améliorez votre remplisseur de sudoku. Je n'ai utilisé qu'une règle supplémentaire pour le résoudre complètement. En regardant la ligne 3 par exemple on voit qu'il y a 3 "trous", mais que 6 n'est disponible que pour la case (3, 2). C'est donc un nouveau type d'élément unique, et l'on est assuré que la case (3, 2) contient le nombre 6.
En ne rajoutant que ce test sur les lignes, le code suivant :
soluce = rempli_sudoku_possible_v2(grille_1)
affiche_sudoku(soluce)
print(soluce == grille_1_complete)
Affiche :
529 671 843
318 492 657
674 853 219
746 325 198
293 186 475
185 749 362
432 567 981
967 218 534
851 934 726
True
===== Résolution complète =====
Le code écrit précédemment ne permet que de résoudre des sudoku très simples. Pour résoudre tout les sudokus possibles, il faut mettre en place des techniques de [[https://fr.wikipedia.org/wiki/Retour_sur_trace|backtracing]].
Vous n'êtes pas censé lire ceci, car il y a suffisamment à faire en 2 heures ci-avant. Mais si effectivement vous avez tout fait jusqu'à présent, attelez vous à ce problème (pour accélérer le backtracking, on pourra choisir à chaque étape l'élément ayant le moins de possibilité).
De mon côté, j'ai :
grille_vide = [0] * (9 * 9)
soluce = rempli_sudoku_backtracking(grille_vide)
affiche_sudoku(soluce)
qui affiche :
123 489 567
489 567 123
567 123 894
238 954 671
971 638 245
645 271 938
892 345 716
356 712 489
714 896 352
sudoku correct ? True