Marcel Délèze

SUDOKU, ensemble des solutions

Mode d'emploi

1.	Modifier la grille des données (recopier la grille vierge sur la grille de données et entrer les données).
2.	Exécuter le programme Mathematica (Noyau / Evaluer le cahier).
3.	Vérifier que la grille des données soit correcte.
4.	Prendre connaissance des résultats.
	Usuellement, il devrait y avoir une et une seule grille dans l'ensemble des solutions.
	Si l'ensemble des solutions est {}, le problème n'a pas de solution.
	Si l'ensemble des solutions contient plusieurs grilles, il y a plusieurs solutions.

Entrée des données

Grille vierge (à recopier sur la grille "donnee" pour entrer une nouvelle grille):

({{\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}});

Grille de données (à remplir):

donnee=({{\[Placeholder], 5, \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], 3, \[Placeholder], \[Placeholder], 2, \[Placeholder], 8, \[Placeholder], \[Placeholder]}, {\[Placeholder], 1, 8, 7, \[Placeholder], \[Placeholder], \[Placeholder], 4, \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], 3, \[Placeholder], 2, \[Placeholder], 7, \[Placeholder]}, {\[Placeholder], \[Placeholder], 7, \[Placeholder], 4, \[Placeholder], 9, \[Placeholder], \[Placeholder]}, {\[Placeholder], 9, \[Placeholder], 6, \[Placeholder], 5, \[Placeholder], \[Placeholder], \[Placeholder]}, {\[Placeholder], 7, \[Placeholder], \[Placeholder], \[Placeholder], 9, 5, 8, \[Placeholder]}, {\[Placeholder], \[Placeholder], 2, \[Placeholder], 6, \[Placeholder], \[Placeholder], 3, \[Placeholder]}, {\[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], \[Placeholder], 2, \[Placeholder]}});

Représentation interne des grilles:

donnee=Apply[sdk,donnee/.{\[Placeholder]->Null}]

Affichage d'une grille:

affiche[grille_sdk]:=FrameBox[GridBox[Apply[List,grille]/.{Null->"·"},RowLines->{False,False,True,False,False,True,False,False},ColumnLines->{False,False,True,False,False,True,False,False}]]//DisplayForm

affiche[g_List]:=Map[affiche,g]

affiche[donnee]

Résolution

Détermination des chiffres possibles

Extractions de lignes, de colonnes et de carrés:

ligne[grille_sdk,i_]:=grille[[i]]

colonne[grille_sdk,j_]:=Transpose[Apply[List,grille]][[j]]

carre[grille_sdk,i_,j_]:=Module[{ib,jb,ic,jc},ib=3Quotient[i-1,3]+1;jb=3Quotient[j-1,3]+1;Flatten[Table[grille[[ib+ic,jb+jc]],{ic,0,2},{jc,0,2}],1]]

Pour une case vide, les chiffres possibles (qu'on pourrait essayer) sont ceux qui ne se trouvent ni dans la ligne, ni dans la colonne, ni dans le carré:

case[grille_sdk,i_,j_]:=grille[[i,j]]/;IntegerQ[grille[[i,j]]]

case[grille_sdk,i_,j_]:=Complement[Range[1,9],ligne[grille,i],colonne[grille,j],carre[grille,i,j]]

possible[grille_sdk]:=Apply[sdk,Table[case[grille,i,j],{i,1,9},{j,1,9}]];

affiche[possible[donnee]]

Détermination des grilles qui comportent un chiffre de plus

Tester les impasses.
Former la grille suivante, ou plusieurs grilles lorsqu'il y a plusieurs possibilités, comme suit:
*	choisir une case pour laquelle la liste des chiffres à essayer est de longueur minimale;
*	pour chaque chiffre à essayer, former une grille comportant ce chiffre

suivant[grille_sdk]:=Module[{e1,li,lj,nPoss,i,j,k},e1=possible[grille];
If[MemberQ[e1,{},{2}],{},
nPoss=10;
Do[If[1≤Length[e1[[i,j]]]<nPoss,
li=i;lj=j;nPoss=Length[e1[[i,j]]]],
{i,1,9},{j,1,9}];
Table[ReplacePart[grille,e1[[li,lj]][[k]],{li,lj}],{k,1,nPoss}]]]

suivant[g_List]:=Flatten[Map[suivant,g]]

Itération

resous[grille_]:=Nest[suivant,donnee,81-Count[donnee,_Integer,{2}]]

affiche[resous[donnee]]