Algorithmes de Résolution des SUDOKUS

Progammation par contraintes

Principe

La programmation par contraintes est utilisée pour résoudre des problèmes combinatoires de grandes tailles tel que les problèmes de planification et d'ordonnancement.

On peut distinguer deux choses dans la programmation par contraintes :
  -> La représentation du problème selon les CSP (Problème de satisfaction de contraintes),
  -> La résolution du problème: propagation des contraintes pour réduire l'espace de solution

Définition d'une contrainte:

Une contrainte est définie en trois varibles : X, D, C.
   X = ensemble de variable du problèmes,
   D = ensemble des domaines variables,
   C = ensemble des contraintes.

Il existe un certain nombre de solveurs de contraintes libres :
  -> AbsCon
  -> Choco
  -> Google OR Tools

Application au Sudoku

Représentation de la contraintes appliqué au Sudoku

X correspond à l'ensemble des variables du problèmes. Les variables associés au Sudoku correspondent aux cases de la grille.
Soit X vaut : {
X1,1 ; X1,2 ; ... ; X1,9
X2,1 ; X2,2 ; ... ; X2,9
    .    ;    .    ; ... ;   .
X9,1 ; X9,2 ; ... ; X9,9 }

D correspond à l'ensemble des domaines variables, soit l'ensemble des valeurs que peut prendre une variables. Dans le cas générale D vaut {1,...,n&sub2;}.
Appliqué aux grilles du Sudoku les plus communes, il vaut D = {1, 2, 3, 4, 5, 6, 7, 8, 9}.

Enfin C correspond à l'ensemble des contraintes.
On cherche que toutes les variables présentes sur une même ligne soient différentes, que toutes les variables présentes sur une même colonne soit différentes, et enfin que toutes les variables présentes dans un même bloc soit différentes, et ça pour toutes les lignes, colonnes et blocs de la grille.
On modélise la contraintes de la façon suivante :

  

Pour les lignes:

allDifferent(x11, x12, x13, x14, x15, x16, x17, x18, x19),
allDifferent(x21, x22, x23, x24, x25, x26, x27, x28, x29),
...
allDifferent(x91, x92, x93, x94, x95, x96, x97, x98, x99)

  

Pour les colonnes:

allDifferent(x11, x21, x31, x41, x51, x61, x71, x81, x91),
allDifferent(x12, x22, x32, x42, x52, x62, x72, x82, x92),
...
allDifferent(x19, x29, x39, x49, x59, x69, x79, x89, x99)

  

Pour les blocs:

allDifferent(x11, x12, x13, x21, x22, x23, x31, x32, x33),
allDifferent(x14, x15, x16, x24, x25, x26, x34, x35, x36),
...
allDifferent(x77, x78, x79, x87, x88, x89, x97, x98, x99)