12.11 Corrigés des exercices
bool Ids ( in t ordre ) {
in t i , j ;
}
Domainelntervalle *d = choisitVariable (i , j );
if (d == NUL L) return true;
in t val [TailleMax ], nb_vals =
enumereValeurs (i , j, val );
i f ( ordre == 0) {
}
if ( trylds ( i, j, val [0] , ordre ))
ret urn true;
else {
}
for (in t k = 1; k < nb_vals; k++ ) {
}
if (trylds (i , j, val [k] , ordre - 1))
return true ;
if (nb_ vals > 0)
if ( trylds (i , j, val [0] , ordre ))
ret urn true ;
return false;
bool id_lds () {
}
for (in t ordre = O; ordre < taille * taille; ordre++) {
if (Ids (ordre ))
ret urn true;
}
return false;
215
On peut tester que pour des Sudokus de taille 25x25, la recherche avec déviations
limitées trouve une grille en 10 secondes alors que le forward checking met beaucoup
plus de temps. Le succès de la méthode n'est pas seulement dû à un bon ordonnancement
des valeurs puisque dans ce cas, elles sont ordonnées Iexicographiquement.
12.11.7 La recherche Monte-Carlo imbriquée
La recherche Monte-Carlo imbriquée trouve instantanément un Sudoku de taille
25x25 :
#include< stdlib .h>
class Move {
public :
in t _i , _j , _value;
Move ( in t i = 0 , in t j = 0 , in t va 1 u e = 0) {