sudokus Et Algorithmes De Recuit - 3 1 5 6 8 2 7 9 7 2 6 3 4 1 9 5 8 5 8 4 6 2 9 3 1 7 ... du problme, ici le nombre de cases de la grille. Concernantlesecondpoint,onsait[10],pourunpro-

  • Published on
    23-Apr-2018

  • View
    213

  • Download
    0

Embed Size (px)

Transcript

  • Sudokus et algorithmes de recuit

    par Renaud Sirdey

    Nous prsentons un algorithme de recuit simul pour une application ludique dactualit : la rsolution deSudokus. Dans un prochain numro, nous prsenterons une mthode base sur la programmation linaire.

    Introduction

    Le Sudoku (est-il encore besoin de le prsenter ?)semble tre le casse-tte du moment. Dans la mesureo il cache un problme combinatoire redoutable, ilest fort tentant de sen servir pour illustrer, de manireludique, lart de concevoir des algorithmes de rsolu-tion de problmes combinatoires. Cest ce que nousfaisons ici avec la mthode dite du recuit simul.

    I Rgles du jeu

    Un Sudoku consiste en la donne dune grille car-re de 81 cases divise en 9 sous-carrs de 3 casesde ct et partiellement remplie avec des chiffres de1 9. Le but du jeu est de complter le remplissagede la grille avec des chiffres de 1 9 de manire cequaucun chiffre napparaisse deux fois dans la mmeligne, dans la mme colonne ou dans le mme sous-carr. En rgle gnrale, il ny a quune seule faonde complter la grille.

    Le tableau I donne un exemple de grillecomplte.

    Comme le fait remarquer Jean-Paul Delahaye [3],complter un Sudoku est quivalent complter le 9-coloriage dun graphe G = (V, E) dont les sommetssont les cases de la grille et o deux sommets sont re-lis par une arte sils appartiennent la mme ligne, la mme colonne ou au mme sous-carr. Rappelonsquun 9-coloriage est une application f : V 7 {1, 9}telle que f (v) , f (w) ds lors que {v, w} E.

    Notons aussi que le problme qui consiste dci-der si un Sudoku (de taille arbitraire) peut tre com-plt ou non est NP-complet [17]. Ceci justifie une ap-proche heuristique, si tant est, bien videmment, queles algorithmes rsultants soient polynomiaux.

    *renauds@nortel.com

    Tableau I. Exemple de Sudoku diabolique complet. Leschiffres encadrs indiquent les donnes du problme.

    6 5 9 4 1 3 7 8 2

    3 1 7 2 8 5 4 9 62 4 8 7 9 6 5 3 1

    9 6 5 1 7 2 8 4 3

    8 7 2 9 3 4 1 6 54 3 1 5 6 8 2 7 9

    7 2 6 3 4 1 9 5 85 8 4 6 2 9 3 1 7

    1 9 3 8 5 7 6 2 4

    II Le recuit simul

    La mthode du recuit simul a t propose dansles annes 80 [2, 9] et, lorigine, justifie par ana-logie avec la technique dite du recuit utilise par lesphysiciens afin de conduire certains systmes phy-siques dans un tat de basse nergie. Il sagit dunemtaheuristique [4], autrement dit dun principe g-nral de construction dalgorithmes de rsolution ap-proche pour les problmes doptimisation difficile,en particulier combinatoire. Ses avantages sont dtrerelativement bien comprise sur le plan thorique et deconduire des algorithmes assez simples. Elle a parailleurs t utilise avec succs dans le cadre dappli-cations industrielles (voir [14] pour un exemple), et ce de nombreuses reprises.

    Soit un problme doptimisation combinatoirequi consiste, tant donn un ensemble de solutions = {1, . . . , N} ainsi quune fonction conomiquec : 7 {e1, . . . , eP}, trouver un lment tel que e1 = c() c() eP, pour tout .De manire usuelle, c() sappelle la valeur de la so-lution . Aussi, on suppose donne une fonction devoisinage V : 7 2.

  • 10 Quadrature n 62

    La mthode est alors trs simple noncer. Au d-part on commence avec une solution arbitraire. Soit la solution courante. chaque itration, une solutioncandidate est choisie uniformment dans le voi-sinage de la solution courante et accepte avec une

    probabilit gale min(

    1, ec()c()

    T

    )

    . Le paramtre T

    sappelle la temprature et tend vers 0, de maniremonotone, selon une fonction appele loi de dcrois-sance de la temprature. La meilleure solution ren-contre durant lexcution de lalgorithme est mmo-rise et crite lorsque la condition darrt choisie estvrifie.

    Bien que ce schma converge en probabilit versune solution optimale sous des conditions assez peurestrictives (symtrie de la fonction de voisinage i.e. j V(i) i V( j) et forte connexitdu graphe orient induit), ce nest quau prix dunedcroissance de la temprature extrmement (com-prendre prohibitivement) lente [6]. Qui plus est, onsait quil existe des instances du problme du cou-plage de cardinalit maximum (problme polynomial)et du problme de 3-coloriage dun graphe dont larsolution ncessite un nombre exponentiel ditra-tions [11, 13].

    Ces rsultats ngatifs ne doivent pas obscurcir letableau outre mesure : la pertinence pratique de la m-thode reste remarquable !

    Gnralement, la mise en uvre dun algorithmede recuit simul passe par ltude de la chane deMarkov qui modlise lalgorithme lorsque la tempra-ture reste constante et dont la matrice des probabilitsde passage est donne par [1, 10, 16] :

    Ai j(T ) =

    0 si j < V(i)1

    |V(i)|si j V(i) et c( j) c(i)

    ec(i)c( j)

    T

    |V(i)|si j V(i) et c( j) > c(i)

    1

    j: jV(i)Ai j(T ) si i = j

    .

    Sous les hypothses de rgularit (cest--dire,dans le prsent contexte, de forte connexit dugraphe orient induit par la fonction de voisinage) etdapriodicit, cette chane admet une unique loi sta-tionnaire exprime comme suit

    ()i (T ) =

    ec(i)T

    Nj=1 e

    c( j )

    T

    (1)

    Aussi,

    limT0()i (T ) = limT0

    1N

    j=1 ec(i)c( j)

    T

    =

    {

    0 si c(i) > e11| |

    sinon,

    o = { : c() = e1}.

    III Rsolution de Sudokus

    Nous lavons vu, la mthode du recuit simulpermet de sattaquer des problmes doptimisa-tion (ici, combinatoire). Pour lutiliser afin de r-soudre des Sudokus, il convient dassocier un pro-blme doptimisation chaque instance. Pour ce faire,nous procdons de la manire suivante : lensembledes solutions, , est lensemble des grilles carres dect 9 dont les cases contiennent un chiffre de 1 9 quelconque, ceci lexception des cases fixes quidfinissent linstance. Sil y a m telles cases, on aN = || = 981m. Soit , i j dnotant le contenude la case dont la ligne est i et la colonne j. On noteci j() le nombre doccurences du chiffre i j dans lazone dfinie par lunion de la ligne i, de la colonnej et du sous-carr contenant la case i j, cette der-nire ntant pas comprise ; la fonction conomiqueest alors dfinie par

    c() =12

    9

    i=1

    9

    j=1

    ci j().

    Il est clair quune solution de valeur nulle respecte lesrgles du jeu et rsout donc le Sudoku.

    La fonction de voisinage, quant elle, est dfiniecomme suit. Deux grilles sont voisines lune de lautresi lune peut sobtenir partir de lautre en changeantle chiffre contenu dans une et une seule case (non fixebien sr). La forte connexit du graphe orient induitpar cette relation de voisinage est vidente.

    Il convient ensuite de chercher simuler avec uneprcision acceptable la loi stationnaire une tempra-ture suffisamment faible pour avoir de bonnes chancesde tirer une solution optimale. Pour ce faire, lideconsiste dmarrer lalgorithme une tempraturerelativement leve, temprature laquelle la conver-gence vers la loi stationnaire est extrmement rapide1,et faire dcrotre la temprature de telle manire que

    1 Rappelons que la convergence vers la loi stationnaire est go-mtrique et que la vitesse de convergence dpend de la valeur ab-solue de la deuxime plus grande valeur propre de la matrice desprobabilits de passage [8, 12]. Malheureusement, celle-ci est ex-trmement faible basse temprature.

  • OctobreDcembre 2006 11

    les lois stationnaires associes deux valeurs succes-sives soient proches. Typiquement [1], on choisira

    Tk+1 =Tk

    1 + log(1+)eP+1 Tk, (2)

    ce qui garantit que

    |()i (Tk)

    ()i (Tk+1)| ,

    o est un petit rel positif. En consquence, il estraisonnable descompter quaprs avoir fait dcrotrela temprature il suffit dun petit nombre ditrationspour se rapprocher de la nouvelle loi stationnaire, demanire satisfaisante. Bien entendu, ce raisonnementest de nature heuristique et il existe dautres faons deprocder [15].

    Reste fixer le nombre ditrations par palier et savoir quand sarrter lorsque lalgorithme tarde fournir une solution de valeur nulle. Concernant lepremier point, on choisit gnralement un nombreditrations proportionnel la taille naturelle du problme, ici le nombre de cases de la grille.Concernant le second point, on sait [10], pour un pro-blme doptimisation combinatoire quelconque, queles solutions issues de la loi stationnaire la tempra-ture

    T f =

    log N log(1 )(3)

    ont une valeur infrieure ou gale e1 + avec uneprobabilit dau moins . Afin de sen convaincre, ilsuffit de remarquer que

    1 =

    i:ei>e1+

    N(i)eeiT

    K(T )

    e

    e1+T

    K(T )

    i:ei>e1+

    N(i)

    N

    NeT

    ee1T

    K(T )

    1

    NeT ,

    o N(i) est le nombre de solutions dont la valeur estgale ei et o

    K(T ) =N

    j=1

    ec( j )

    T .

    Pour le prsent problme, on choisira, par exemple, = 12 , dans la mesure o la fonction conomique est valeurs entires. Lquation (3) se rcrit alors

    T f =0.5

    (81 m) log 9 log(1 )

    En pratique, on pourra lui prfrer la valeur

    T f =0.5

    81 log 9 log(1 )

    qui fournit les mmes garanties tout en ayant lavan-tage dtre indpendante de linstance considre.

    Par exemple, si lalgorithme atteint la tempra-ture 0,002 738 52 il est raisonnable de conclure quuneproximit suffisante la loi stationnaire na pas pu tremaintenue car, dans le cas contraire, il y avait plus de99 % de chances de tirer une solution de valeur nulle.Il convient alors dabandonner et, par exemple, de re-lancer lalgorithme dans lespoir de faire mieux.

    Lencadr suivant donne lnonc de lalgorithme.

    nonc de lalgorithme

    Poser = 0.1, eP = 16202 et faire T eP.

    Choisir arbitrairement et faire c c().

    Tant que T 0.00273852 faire

    Palier : pour k = 1 81 faire

    Choisir i et j uniformment dans {1, 9}tant que la case i j est fixe.

    Faire t i j et c1 ci j().

    Choisir i j uniformment dans {1, 9}tant que i j = t.

    Faire c2 ci j() et c c c1 + c2.

    Choisir u uniformment dans [0, 1].

    Si u eccT alors faire c c (acceptation).

    Sinon faire i j t (rejet).

    Si c = 0 alors crire et sarrter.

    Fin.

    Faire T T1+ log(1+)eP+1

    T

    Fin.

    IV Rsultats empiriques

    Pour fixer les ides, nous avons essay lalgo-rithme sur quatre Sudokus de niveau diabolique donns dans les tableaux I, II, III et IV.

    Ces quatres Sudokus ont respectivement 23, 26,25 et 24 cases fixes et il faut, en moyenne2, respecti-vement 7,69, 2,28, 3,85 et 2,38 essais3 pour en venir bout. Notons que lalgorithme ne parvient rsoudrele Sudoku diabolique donn dans [3] (23 casesfixes) quau prix de 11,11 essais, en moyenne.

    2 Estime sur 100 essais.3 Un essai requiert de lordre de trois secondes sur un ordina-

    teur portable des plus moyens.

  • 12 Quadrature n 62

    Tableau II. Un Sudoku de niveau diabolique .

    5 4 9 1 7 2 3 8 66 8 3 4 5 9 1 7 22 7 1 3 8 6 5 9 4

    3 2 4 5 9 7 6 1 87 6 5 8 2 1 4 3 99 1 8 6 4 3 2 5 7

    1 9 7 2 6 5 8 4 34 5 6 9 3 8 7 2 18 3 2 7 1 4 9 6 5

    Tableau III. Un autre Sudoku de niveau diabolique .

    9 5 2 1 4 7 6 3 81 7 6 8 9 3 2 4 5

    4 8 3 2 5 6 7 1 9

    6 1 4 7 3 8 9 5 27 2 9 5 6 1 4 8 35 3 8 4 2 9 1 7 6

    3 4 5 9 7 2 8 6 12 6 1 3 8 4 5 9 78 9 7 6 1 5 3 2 4

    Tableau IV. Encore un autre Sudoku de niveau diabo-lique .

    7 9 8 6 4 2 3 1 5

    4 1 5 9 7 3 6 2 83 6 2 1 8 5 9 7 4

    6 7 4 5 2 8 1 9 35 2 1 7 3 9 4 8 68 3 9 4 6 1 7 5 2

    9 4 3 8 5 7 2 6 1

    1 8 6 2 9 4 5 3 72 5 7 3 1 6 8 4 9

    Aussi, prcisons que lorsque lalgorithme narrivepas rsoudre un Sudoku, il termine gnralementavec une solution de valeur trs faible (typiquement 2)ce qui est excellent sur le plan de loptimisation, bienquinutile pour le Sudoku (rappelons toutefois quilny a thoriquement quune et une seule solution devaleur nulle, ce qui complique la tche de lalgo-rithme).

    Enfin, il convient dinsister sur le fait que nous neprtendons ni que notre algorithme est comptitif avecles meilleurs algorithmes de rsolution de Sudokus niquil nexiste pas de manire plus ingnieuse dappli-quer la mthode du recuit simul ce problme (enparticulier, de nombreux travaux traitent de lappli-cation de la mthode au problme du coloriage, par

    exemple [7], et, ce titre, sont dun intrt certainpour le prsent problme).

    V Gnralisation et complexit

    Le Sudoku, tout comme notre algorithme, se g-nralise aisment. Soit n le ct des sous-carrs. Unn-Sudoku consiste en la donne dune grille carre den4 cases divise en n2 sous-carrs de n cases de ctet partiellement remplie avec des nombres de 1 n2

    (rappelons que le nombre chromatique dun graphe Gest suprieur ou gal la cardinalit maximale duneclique deG [5], or, pour notre problme, un sous-carrdfinit une clique de cardinalit n2 contenue dans legraphe colorier).

    Considrons que T0, , et sont fixs et com-menons par quantifier le nombre de paliers de tem-prature rencontrs par lalgorithme. Il est ais devrifier que la loi de dcroissance de la tempraturedonne par lquation (2) est telle que

    Tk+l =Tk

    1 + l log(1+)eP+1 Tk

    Il suit que le nombre de paliers de temprature ren-contrs, not , est la solution de lquation

    T0

    1 + log(1+)eP+1 T0=

    logN log(1 ),

    soit

    =(1 + eP)(log N log(1 ))

    log(1 + )

    1 + ePT0 log(1 + )

    Notons quavec T0 = eP le second terme de lqua-tion ci-dessus est approximativement gal 1log(1+) ,ds que eP est suffisamment grand.

    Pour un n-Sudoku, eP est en O(n6), le nombre depaliers rencontrs est donc en O(n10 log n), dans lamesure o N n2n

    4. Puisque lon ralise n4 itrations

    pour chaque valeur de la temprature et que le calculde la valeur de la solution candidate est en O(n2), lacomplexit de lalgorithme est en O(n16 log n), doncpolynomiale. Toutefois, la taille naturelle du pro-blme est plutt le nombre de cases de la grille. Soitp = n4, lalgorithme est alors en O(p4 log p).

    Ce dernier rsultat ne doit nanmoins pas masquerle fait que lalgorithme, bien qu complexit polyno-miale, reste relativement gourmand : les constan-tes caches dans le O sont loin dtre ngligeables.Afin damliorer lefficacit pratique de la mthode,on pourra ajouter une condition darrt ad hoc consis-tant abandonner ds lors que la valeur de la meilleuresolution rencontre ne sest pas amliore durant unnombre suffisamment grand (typiquement 10 000) depaliers de temprature.

  • OctobreDcembre 2006 13

    Rfrences

    [1] E.H.L. Aarts et P.J.M. van Laarhoven, Statistical cooling : a general approach tocombinatorial optimization problems , PhilipsJ. Res. 40 (4) (1985) 193226.

    [2] V. Cerny, Thermodynamical approach to thetraveling salesman problem : an efficient simu-lation algorithm , J. Optimiz. Theory App. 5 (1)(1985) 4151.

    [3] J.-P. Delahaye, Le tsunami du Sudoku , Pourla Science (dcembre 2005).

    [4] J. Dro, A. Ptrowski, P. Siarry et . Taillard,Mtaheuristiques pour loptimisation difficile,Algorithmes, Eyrolles, 2003.

    [5] M. Gondran et M. Minoux, Graphes et algo-rithmes, tome 37 de Collection de la Directiondes tudes et Recherches dlectricit deFrance, Eyrolles, troisime dition, 1995.

    [6] B. Hajek, Cooling schedule for optimal annea-ling , Math. Oper. Res. 13 (1988) 311329.

    [7] D.S. Johnson, C.R. Aragon, L.A. McGeogh etC. Schevon, Optimization by simulated annea-ling an experimental evaluation part. II : graphcoloring and number partitioning , Oper. Res.39 (1991) 378406.

    [8] J.G. Kemeny et J.L. Snell, Finite MarkovChains, The University Series in UndergraduateMathematics, D. van Nostrand Company,Princeton, New Jersey, 1960.

    [9] S. Kirkpatrick, C.D. Gelatt Jr et M.P. Vecchi, Optimization by simulated annealing ,Science (1983).

    [10] M. Lundy et A. Mees, Convergence of an an-nealing algorithm , Math. Program. 34 (1986)111124.

    [11] A. Nolte et R. Schrader, Simulated annealingand its problems to colo...

Recommended

View more >