On rappelle qu'un Sudoku consiste en la donnée d'une grille carrée divisée en 9 sous-carrés de 3 cases de côté, et partiellement remplie avec des nombres de 1 à 9.
Le but du jeu consiste à compléter la grille avec les chiffres de 1 à 9, de sorte qu'aucun chiffre n'apparaisse deux fois dans la même ligne, dans la même colonne ou dans le même sous-carré
En général, il n'existe qu'une seule manière de compléter la grille.
On peut prouver que compléter un Sudoku est équivalent à compléter le 9-coloriage d'un graphe :
Le problème qui consiste à décider si un Sudoku peut être complété ou non est NP-complet.
La méthode du recuit simulé a été proposée dans les années 80, par analogie avec une technique dite du recuit, utilisée par les physiciens.
Il s'agit d'un principe général de construction d'algorithmes pour résoudre des problèmes d'optimisation difficiles.
Cette métaheuristique est assez bien comprise, d'un point de vue théorique, et permet la création d'algorithmes relativement simples.
Soit un problème d'optimisation combinatoire qui consiste, étant donnés :
à trouver un élément $w* \in \Omega$ tel que $e_1 = c(w*) \leqslant c(w) \leqslant e_p$, pour tout $w \in \Omega$.
$c(w)$ s'appelle la valeur de la solution $w$.
Au départ, on commence avec une solution arbitraire $w$.
A chaque itération, une solution candidate $w'$ est choisie uniformément dans le voisinage de la solution courante. Elle est acceptée avec une probabilité égale à $min \left(1, e^{-\frac{c(w')-c(w)}{T}}\right)$, et remplace la meilleure solution mémorisée.
Le paramètre $T$ ci-dessus s'appelle la température. Il doit tendre vers 0, de manière monotone, selon une fonction appelée loi de décroissance de la température.
On a convergence (en probabilité) vers une solution optimales, sous des conditions peu restrictives (concernant la fonction de voisinage, et la forte connexité du graphe induit).
Cependant, si la convergence est assurée sous ces hypothèses, la décroissance de la température (donc la vitesse de convergence) peut s'avérer être beaucoup trop lente.
Il reste que cette méthode a donnée de bons résultats sur un certain nombre de cas pratiques.
L'ensemble des solutions $\Omega$ est l'ensemble des grilles carrées de côté 9 dont les cases contiennent un chiffre de 1 à 9 quelconque, ceci à l'exception des cases fixées par l'énoncé.
S'il y a $m$ cases fixées, le nombre d'éléments de $\Omega$ est égal à $N = 9^{81-m}$.
Soient alors :
La fonction économique est alors naturellement définie par $c(w) = \frac{1}{2} \sum_{i=1}^9 \sum_{j=1}^9 c_{ij}(w)$
Notons dès à présent qu'une solution de fonction économique nulle respecte les règles du Sudoku.
La fonction de voisinage est définie ainsi : deux grilles sont voisines l'une de l'autre si l'une peut s'obtenir à partir de l'autre en changeant un et un seul chiffre (non fixé).
Il reste à définir l'évolution de la température, et le nombre d'itérations à cette température. Les discutions pour les trouver étant un peu techniques, on se contentera de donner leurs formules. Signalons seulement qu'elles ont été choisies de sorte que :
La formule de la température :
$T_0 = 810, T_{k+1} = \frac{T_k}{1 + \frac{log(1+\delta)}{811} T_k}$
Reste à fixer le nombre d'itérations par palier, et à savoir quand s'arrêter.
L'ensemble des réflexions précédantes mène à l'algorithme :
Poser $\delta = 0.1$, et $T = 810$ Choisir $w$ arbitrairement, et faire $c = c(w)$ Tant que $T \geqslant 0.00273852$, faire (Palier) Pour k=1 à 81, faire Choisir $i$ et $j$ uniformément dans [1,9] tant que la case ij est fixée Faire $t = w_{ij}$, et $c_1 = c_{ij}(w)$ Choisir $w_{ij}$ uniformément dans [1,9] tant que $w_{ij} = t$ Faire $c_2 = c_{ij}(w)$ et $c' = c-c_1+c_2$ Choisir $u$ uniformément dans [0,1] Si $u \leqslant e^{-\frac{c'-c}{T}}$, alors faire $c = c'$ (acceptation) Sinon faire $w_{ij} = t$ (rejet) Si $c = 0$, alors écrire $w$ et s'arrêter. Fin Faire $T = \frac{T}{1+\frac{log(1+\delta)}{811}T}$ Fin