Apprendre Maple Solveur de Sudoku

 
  Page d'accueilPage d'accueil   RechercherRechercher   Forum de discussionForum de discussion   ContactContact   SommaireSommaire 
  Cours MapleCours Maple   Travaux dirigésTravaux dirigés   Thèmes d'activitésThèmes d'activités   Thèmes d'activitésMaplets
Ecran MapleEcran Maple  TéléchargementTéléchargement  BibliographieBibliographie  LiensLiens  

 

 

Page d'accueil   Thèmes d'activités   << Thème précédent   Thème suivant >>

 

Une grille de Sudoku se compose de neuf blocs carrés 3x3 comportant chacun 9 cases, soit au total 81 cases.
Le but du jeu est de compléter la grille (certaines des cases contenant initialement un chiffre) afin que chaque ligne,
chaque colonne et chaque bloc 3x3 contienne une fois et une seule chacun des chiffres de 1 à 9.
Chaque case de la grille pourra être caractérisée, comme on le voit dans la grille ci-dessous:

- par sa ligne : nombre entier entre 0 et 8.

- par sa colonne : nombre entier entre 0 et 8.

- par son index :  nombre entier entre 0 et 80.

Ainsi, la case grisée de la grille est en ligne 3, colonne 5 et a pour index 32.
 

[Maple OLE 2.0 Object]

Une grille de Sudoku  sera représentée par un tableau sudoku à une dimension, dont les indices évolueront de 0 à 80.

Exemple :

>    sudoku:=array(0..80,[
 3, 0, 0, 1, 0, 0, 0, 0, 0,
 0, 5, 7, 0, 0, 3, 1, 0, 0,
 9, 0, 6, 0, 5, 0, 0, 0, 8,
 4, 0, 0, 6, 0, 0, 9, 5, 1,
 0, 0, 5, 8, 0, 0, 0, 0, 6,
 0, 0, 0, 0, 0, 7, 0, 0, 0,
 8, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 4, 2,
 0, 0, 0, 0, 7, 1, 0, 0, 0
]):

représentera la grille de Sudoku  ci-dessous.
Les cases contenant initialement un chiffre seront appelées cases fixées  et seront représentées dans le tableau
sudoku par ce chiffre. Tandis que les cases vides seront représentées dans le tableau sudoku par la valeur 0: ces
cases seront appelées pour la suite des cases modifiables  du tableau.

[Maple Plot]

1° Ecrire une procédure afficher (T::array) qui affiche une grille de Sudoku, à partir de sa représentation sous
    forme de tableau. Prévoir de bien délimiter les blocs 3x3 en utilisant un trait plus épais, comme ci-dessous:   

>    afficher(sudoku);

[Maple Plot]

2° Ecrire les procédures suivantes, i étant de type nonnegint:
a) index_debut_ligne (i) donne pour résultat l'index de la case située au début de la ligne à laquelle appartient la case d'index i.
b) index_debut_colonne (i) donne pour résultat l'index de la case située au début de la colonne à laquelle appartient la case d'index i.
c) ligne (i) donne pour résultat le numéro de la ligne à laquelle appartient la case d'index i.
d) colonne (i) donne pour résultat le numéro de la colonne à laquelle appartient la case d'index i  (identique à index_debut_colonne (i)).
e) index_debut_bloc (i) donne pour résultat l'index de la première case du bloc 3x3 auquel appartient la case d'index i.

Exemples :

>    index_debut_ligne(32);

27

>    index_debut_colonne(32);

5

>    ligne(32);

3

>    colonne(32);

5

>    index_debut_bloc(32);

30

3° En utilisant les procédures définies dans la question 2°, écrire les procédures suivantes:
a) OK_ligne (T::array,v::posint,i::nonnegint) donne pour résultat une valeur booléenne true  ou false  selon que le chiffre v figure
déjà ou non sur la ligne de la case d'index i du tableau T.
Exemple : on peut placer un 7 en ligne dans la case d'index 32, mais pas un 5 (car un 5 figure déjà sur cette ligne, dans la case d'index 34)

>    OK_ligne(sudoku,7,32),OK_ligne(sudoku,5,32);

true, false

b) OK_colonne (T::array,v::posint,i::nonnegint) donne pour résultat une valeur booléenne true  ou false  selon que le chiffre v figure
déjà ou non sur la colonne de la case d'index i du tableau T.
Exemple : on peut placer un 5 en colonne dans la case d'index 32, mais pas un 1 (car un 1 figure déjà sur cette colonne, dans la case d'index 77)

>    OK_colonne(sudoku,5,32),OK_colonne(sudoku,1,32);

true, false

c) OK_bloc (T::array,v::posint,i::nonnegint) donne pour résultat une valeur booléenne true  ou false  selon que le chiffre v figure
déjà ou non dans le bloc de la case d'index i du tableau T.
Exemple : on peut placer un 3 dans le bloc de la case d'index 32, mais pas un 8 (car un 8 figure déjà dans ce bloc, dans la case d'index 39)

>    OK_bloc(sudoku,3,32),OK_bloc(sudoku,8,32);

true, false

d) OK (T::array,v::posint,i::nonnegint) donne pour résultat   false si i=81 et sinon donne pour résultat une valeur booléenne true  ou false
selon que le chiffre v peut être placé ou non dans la case d'index i du tableau T, conformément à la règle du jeu de Sudoku .
Pour cela, on utilisera les 3 procédures précédentes.
Exemple : on peut placer un 2 dans la case d'index 32, car 2 ne figure ni dans la ligne, ni dans la  colonne, ni dans le bloc auquel
appartient cette case. Par contre, on ne peut y placer 1 qui figure déjà (à la fois en ligne et en colonne)

>    OK(sudoku,2,32),OK(sudoku,1,32);

true, false

4° Ecrire une procédure suivant (T::array,i::nonnegint) donnant pour résultat :

 i si la case d'index i du tableau T est modifiable, ou sinon l'index de la prochaine case modifiable suivant la case d'index i du tableau T.

(prévoir dans ce dernier cas que le résultat pourra valoir 81, dans le cas où les dernières cases de la grille ne sont pas modifiables)  
Exemple : la case d'index 32 est vide, les cases d'index 33,34,35 contiennent respectivement 9,5,1, la case d'index 36 est vide.
 

>    suivant(sudoku,32),suivant(sudoku,33);

32, 36

5°   Ecrire une   procédure index_fixes (T::array) donnant pour résultat la liste des index des cases fixées du tableau T.

Exemple : les cases contenant initialement un chiffre sont les cases d'index  0,3,10,...,76,77.

>    index_fixes(sudoku);

[0, 3, 10, 11, 14, 15, 18, 20, 22, 26, 27, 30, 33, 34, 35, 38, 39, 44, 50, 54, 70, 71, 76, 77]

6° Ecrire une   procédure  solution (T::array) donnant pour résultat la solution du sudoku T.

La procédure fonctionnera sur un algorithme de retour arrière ( backtracking ) et utilisera les procédures index_fixes ,
suivant , et OK .

On passera en revue toutes les possibilités offertes de chiffres candidats pour les différentes cases modifiables:

- si le chiffre convient, on passe à la case modifiable suivante.

- si on a épuisé tous les chiffres candidats pour une case, on revient en arrière sur la case modifiable précédente et on y

teste un nouveau chiffre candidat.

Ainsi de suite ... jusqu'à atteindre la fin du tableau T  (c'est à dire lorque index = 81 ).

Exemple : voici le fonctionnement de l'algorithme sur les premières cases de l'exemple précédent

`index ` = 1, `chiffre ` = 2

`index ` = 2, `chiffre ` = 4

`index ` = 4, `chiffre ` = 6

`index ` = 5, `chiffre ` = 8

`index ` = 6, `chiffre ` = 5

`index ` = 7, `chiffre ` = 7

`index ` = 8, `chiffre ` = 9

`retour arrière: index` = 8

`retour arrière: index` = 7

`index ` = 7, `chiffre ` = 9

`index ` = 8, `chiffre ` = 7

`retour arrière: index` = 8

`retour arrière: index` = 7

`retour arrière: index` = 6

`index ` = 6, `chiffre ` = 7

`index ` = 7, `chiffre ` = 9

`index ` = 8, `chiffre ` = 5

`retour arrière: index` = 8

`retour arrière: index` = 7

`retour arrière: index` = 6

`retour arrière: index` = 5

`---------- etc --------------`

 

>    afficher(solution(sudoku));

[Maple Plot]

Correction :
 

>    restart;
>    sudoku:=array(0..80,[
 3, 0, 0, 1, 0, 0, 0, 0, 0,
 0, 5, 7, 0, 0, 3, 1, 0, 0,
 9, 0, 6, 0, 5, 0, 0, 0, 8,
 4, 0, 0, 6, 0, 0, 9, 5, 1,
 0, 0, 5, 8, 0, 0, 0, 0, 6,
 0, 0, 0, 0, 0, 7, 0, 0, 0,
 8, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 4, 2,
 0, 0, 0, 0, 7, 1, 0, 0, 0
]):
 

1° afficher () affiche la grille de Sudoku correspondant au tableau T des 81 nombres:

>    with(plots): 
Warning, the name changecoords has been redefined
>    afficher:=proc(T::array)
local L,e,texte,lig,col;
L:=NULL: texte:=NULL:
for lig from 0 to 9 do
  if (lig mod 3=0) then e:=5 else e:=1 end if;
  L:=L,plot([t,9-lig,t=0..9],thickness=e);
  for col from 0 to 9 do
    if (col mod 3=0) then e:=5 else e:=1 end if;
    L:=L,plot([col,t,t=-0.05..9.05],thickness=e):
    if lig<9 and col<9 and T[9*lig+col]>0 then texte:=texte,textplot([col+0.5,9-lig-0.5,T[9*lig+col]],font=[HELVETICA,BOLD,32]) end if;
  end do;
end do:
display([L,texte],axes=none)
end proc:

 
>    afficher(sudoku);

[Maple Plot]

2°a) index_debut_ligne (i) donne pour résultat l'index de la case située au début de la ligne à laquelle appartient la case d'index i:

>    index_debut_ligne:=proc(i::nonnegint)
  9*iquo(i,9)
end proc:
 

2°b) index_debut_colonne (i) donne pour résultat l'index de la case située au début de la colonne à laquelle appartient la case d'index i:

>    index_debut_colonne:=proc(i::nonnegint)
  irem(i,9)
end proc:
 

2°c) ligne (i) donne pour résultat le numéro de la ligne à laquelle appartient la case d'index i:

>    ligne:=proc(i::nonnegint)
  iquo(i,9)
end proc:
 
   

2°d) colonne (i) donne pour résultat le numéro de la colonne à laquelle appartient la case d'index i  (identique à index_debut_colonne (i)):

>    colonne:=proc(i::nonnegint)
  irem(i,9)  # identique à index_debut_colonne(i)
end proc:
 

2°e) index_debut_bloc (i) donne pour résultat l'index de la première case du bloc 3x3 auquel appartient la case d'index i:

>    index_debut_bloc:=proc(i::nonnegint)
  27*iquo(ligne(i),3)+3*iquo(colonne(i),3)
end proc:
 

 

3°a)   OK_ligne (T::array,v::posint,i::nonnegint) donne pour résultat une valeur booléenne true  ou false  selon que le chiffre v figure
déjà ou non sur la ligne de la case d'index i du tableau T.

>    OK_ligne:=proc(T::array,v::posint,i::nonnegint)
local id,x;
id:=index_debut_ligne(i):
for x from id to id+8 do
  if T[x]=v then return false end if
end do:
true
end proc:
 
>    OK_ligne(sudoku,7,32),OK_ligne(sudoku,5,32);

true, false

3°b) OK_colonne (T::array,v::posint,i::nonnegint) donne pour résultat une valeur booléenne true  ou false  selon que le chiffre v figure déjà ou non sur la colonne de la case d'index i du tableau T.  

>    OK_colonne:=proc(T::array,v::posint,i::nonnegint)
local id,x;
id:=index_debut_colonne(i):
for x from id to id+72 by 9 do
  if T[x]=v then return false end if
end do:
true
end proc:
 
>    OK_colonne(sudoku,5,32),OK_colonne(sudoku,1,32);

true, false

3°c) OK_bloc (T::array,v::posint,i::nonnegint) donne pour résultat une valeur booléenne true  ou false  selon que le chiffre v figure
déjà ou non dans le bloc de la case d'index i du tableau T.

>    OK_bloc:=proc(T::array,v::posint,i::nonnegint)
local id,x,y;
id:=index_debut_bloc(i):
for x from 0 to 2 do
  for y from 0 to 2 do
     if T[id+9*x+y]=v then return false end if
  end do
end do:
true
end proc:
 
>    OK_bloc(sudoku,3,32),OK_bloc(sudoku,8,32);

true, false

3°d) OK (T::array,v::posint,i::nonnegint) donne pour résultat   false si i=81 et sinon donne pour résultat une valeur booléenne true  ou false selon que le chiffre v peut être placé ou non dans la case d'index i du tableau T, conformément à la règle du jeu de Sudoku .

 

>    OK:=proc(T::array,v::posint,i::nonnegint)
if i=81 then return false
else OK_ligne(T,v,i) and OK_colonne(T,v,i) and OK_bloc(T,v,i) end if
end proc:
 
>    OK(sudoku,2,32),OK(sudoku,4,32);

true, false

4° suivant (T::array,i::nonnegint) donne pour résultat:

 i si la case d'index i du tableau T contient 0, ou sinon

 l'index de la prochaine case modifiable suivant la case d'index i du tableau T:

>    suivant:=proc(T::array,i::nonnegint)
local id;
id:=i;
while T[id]<>0 do
  if id<80 then id:=id+1 else return 81 end if
end do:
id
end proc:
 
>    suivant(sudoku,32), suivant(sudoku,33);

32, 36

5° index_fixes (T) donne pour résultat la liste des index des cases fixées du tableau T:

>    index_fixes:=proc(T::array)
local k,f;
f:=NULL;
for k from 0 to 80 do
  if T[k]>0 then f:=f,k end if
end do;
[f]
end proc:
 
>    index_fixes(sudoku);

[0, 3, 10, 11, 14, 15, 18, 20, 22, 26, 27, 30, 33, 34, 35, 38, 39, 44, 50, 54, 70, 71, 76, 77]

6° solution (T) donne pour résultat la solution du sudoku T ; la procédure fonctionne sur un algorithme de retour arrière ( backtracking ) :

>    solution:=proc(T::array)
local index,valeur,fixes;

index:=0: valeur:=0: fixes:=index_fixes(T):   
while index<81 do  
  index:=suivant(T,index):
  valeur:=valeur+1:
  if OK(T,valeur,index) then
     T[index]:=valeur: valeur:=0:
  else
    if valeur=9 then
     valeur:=0:
     do
       T[index]:=0:
       index:=index-1:
       while member(index,fixes) do
         index:=index-1
       end do:
       if index<0 then
         error "Pas de solution trouvée pour ce sudoku."
       end if;
       if T[index]<9 then
         valeur:=T[index]: T[index]:=0:
         break
       end if:
     end do
    end if
  end if:
end do:
eval(T)
end proc:
 
>    afficher(solution(sudoku));

 

[Maple Plot]

Autres exemples:
 

 

>    sudoku:=array(0..80,[
8,0,0,6,9,0,1,0,2,
4,0,9,5,1,3,0,0,6,
0,0,0,0,0,7,0,0,4,
0,5,0,9,0,1,0,2,0,
2,0,0,0,0,0,0,0,0,
0,0,0,0,3,0,0,0,0,
0,0,0,0,4,0,0,0,8,
6,0,4,0,0,2,0,5,0,
7,0,1,0,0,0,0,0,0]):
 
>    afficher(sudoku);

[Maple Plot]

>    afficher(solution(sudoku));

[Maple Plot]

>    sudoku:=array(0..80,[
0,0,5,0,0,0,4,8,2,
9,0,4,6,0,0,0,0,3,
0,7,0,0,4,1,0,0,0,
0,1,0,0,0,0,3,5,0,
0,0,8,0,2,0,1,0,0,
0,3,7,0,0,0,0,2,0,
0,0,0,7,5,0,0,6,0,
3,0,0,0,0,4,2,0,9,
0,0,0,0,0,0,5,0,0]):
 
>    afficher(sudoku);

[Maple Plot]

 

>    afficher(solution(sudoku));

[Maple Plot]

>    sudoku:=array(0..80,[
6,0,5,0,9,1,2,4,0,
0,4,0,5,3,0,0,0,0,
3,2,0,0,0,6,0,7,0,
0,0,6,3,1,0,7,0,0,
0,1,0,0,0,0,9,0,0,
8,0,0,0,0,4,0,0,0,
0,0,3,8,0,0,0,0,0,
0,0,0,0,6,0,0,0,1,
0,5,0,0,7,0,0,0,0]):
 
>    afficher(sudoku);

[Maple Plot]

>    afficher(solution(sudoku));

[Maple Plot]

 

>    sudoku:=array(0..80,[
0,8,1,0,0,0,0,0,6,
9,0,4,3,0,6,0,0,8,
0,3,0,0,0,4,2,0,0,
0,0,8,9,0,0,7,1,0,
1,0,3,5,0,0,0,0,0,
0,0,7,0,2,0,0,0,0,
8,0,0,7,0,0,0,0,4,
0,0,5,0,0,0,8,9,0,
6,0,9,0,1,0,0,0,0]):
 
>    afficher(sudoku);

[Maple Plot]

>    afficher(solution(sudoku));

 

[Maple Plot]

 

haut de cette page

 

 


©  - Alain Le Stang - Navigation optimisée pour une résolution 1024 x 768.