RECHERCHE :
Bienvenue sur le site de Michel VOLLE
Powered by picosearch  


Vous êtes libre de copier, distribuer et/ou modifier les documents de ce site, à la seule condition de citer la source.
 GNU Free Documentation License.

Résoudre un Sudoku

31 mars 2006

Pour lire un peu plus :

- Le programme sudoku.scm
- La programmation comme hobby
- The Little Schemer
- Télécharger DrScheme

Pour me remettre à la programmation, j’ai écrit un programme qui résout les Sudokus. Pour l'utiliser il faut disposer d'un interpréteur Scheme (Scheme est le plus connu des dialectes de LISP ; on peut télécharger DrScheme, c'est gratuit).

Après avoir ouvert le programme (par exemple par copier-coller vers DrScheme), il faut y saisir le tableau sous le format suivant qui parle de lui-même :

(define tableau
  '((()(6)()()(8)(7)()(2)(1))
    (()()()()()()(8)(6)())
    (()()(8)()()()()(3)())
    ((4)(3)()()()(6)()()(7))
    (()()()(2)()(9)(4)()())
    (()(1)()()()()()()(2))
    ((1)(5)()()(7)()()()(3))
    (()()(7)(5)()()(1)()())
    (()()()(3)()()()()())))

Le Sudoku ci-dessus est l'un de ceux qui sont classés au niveau 6 et que leur éditeur qualifie de  « diaboliques » - mais si l'on clique sur le bouton Execute de DrScheme la solution s’affiche après une fraction de seconde :

((9 6 3 4 8 7 5 2 1)
 (5 7 1 9 2 3 8 6 4)
 (2 4 8 6 1 5 7 3 9)
 (4 3 2 1 5 6 9 8 7)
 (7 8 5 2 3 9 4 1 6)
 (6 1 9 7 4 8 3 5 2)
 (1 5 6 8 7 4 2 9 3)
 (3 9 7 5 6 2 1 4 8)
 (8 2 4 3 9 1 6 7 5))

*    *

Ayant passé les six derniers mois à composer De l’Informatique, j’avais perdu l’habitude de programmer. Pour m’y remettre j’ai relu attentivement The Little Schemer de Friedman et Felleisen. C’est un livre très sympathique mais pas vraiment pédagogique, quoi qu'on en dise !

Après quoi j’étais armé pour programmer de nouveau en Scheme. J’ai retrouvé les difficultés familières : comme je suis habitué à écrire f(x) pour noter les fonctions alors qu’il convient en Scheme d’écrire (f x), je commets de fréquentes erreurs que le déboguage révèle heureusement. L'écriture du programme m'a pris deux jours, sa vérification et son édition (mise en ordre, commentaires, élagage des fonctions inutiles) deux autres jours.

*    *

Je m’y étais préparé en résolvant quelques Sudokus à la main. Comment fait-on pour trouver le chiffre qu’il convient d’inscrire dans une case ? Chaque case doit obéir à trois contraintes simultanées : par ligne, par colonne et par bloc, en nommant « bloc » chacun des neuf pavés de neuf cases. On peut associer à chaque case la liste des valeurs possibles sous ces contraintes. Si cette liste se réduit à un seul chiffre, ou si la case est la seule pour laquelle un chiffre soit possible, il faut le lui assigner.

Le tableau se remplit ainsi progressivement. Les nouveaux chiffres créent de nouvelles contraintes, ce qui réduit le nombre des valeurs possibles. La démarche est donc récursive, et progresse jusqu'à ce que toutes les cases du tableau contiennent un chiffre. Scheme, dans lequel il est facile de programmer une récursion, devait donc a priori être bien adapté. Une fois définies les fonctions idl? et iter, le programme aboutit en effet à une récursion des plus simples :

(define sol
   (lambda (t)
      (cond ((idl? (iter t) t) t)
      (else (sol (iter t))))))

Je n’ai traité que les Sudokus de forme classique (avec des chiffres, sur un tableau 9 sur 9 divisé en neuf blocs carrés), mais le programme pourrait être adapté sans difficulté à tous les types de Sudokus. Si vous trouvez un Sudoku (de forme classique) qui lui résiste, dites-le moi !

*      *

L’ordinateur est-il plus intelligent que moi ?

Oui, puisqu'il résout en une fraction de seconde un Sudoku qui m’aurait demandé plusieurs heures.

Non, parce qu’il ne fait qu’exécuter le programme que j’ai écrit et qu’il aurait été incapable de l’écrire lui-même.

De ces deux réponses, laquelle choisirez-vous ? Pour ma part, je choisis la deuxième : ce n'est pas parce qu'un programme permet à l'ordinateur de calculer à toute vitesse les valeurs possibles pour les diverses cases alors que je le fais lentement, qu'il mérite d'être qualifié d'« intelligent ».

*      *

Quel est l’intérêt de ce programme, me dit-on, puisque le charme du Sudoku réside dans la recherche manuelle de la solution ?

Comme ce programme me permet de résoudre un Sudoku sans réfléchir, ce jeu a il est vrai perdu à mes yeux tout son attrait. Sachant qu’une machine peut le traiter plus vite que moi, parce qu’elle est en mesure de parcourir très vite toutes ses cases pour évaluer et comparer les valeurs possibles, je ne parviens plus à m’y intéresser ! La magie du jeu s’est évaporée.

Mais était-ce une magie ou un faux-semblant ?  En perdant le goût du Sudoku, ai-je perdu quelque chose de précieux ou me suis-je débarrassé d’une occupation qui aurait pu devenir une manie ? Le temps que j’aurais consacré au Sudoku ne sera-t-il pas mieux employé par des activités que l’ordinateur ne peut pas réaliser à ma place – à la lecture, par exemple ?

*     *

Le programme qui serait vraiment utile, me dit-on, c'est celui qui serait capable de produire des Sudokus classés selon leur niveau de difficulté. Je suppose que les éditeurs y ont réfléchi ! Mais je vais tout de même tenter de produire automatiquement de nouveaux Sudokus, et de les classer par ordre de difficulté. Le générateur de nombres au hasard de Scheme sera mis à contribution, ainsi que le compteur qui m'indiquera le nombre d'itérations nécessaires pour résoudre un Sudoku. 

*     *

Post-Sriptum : un des lecteurs de volle.com m'a aimablement communiqué un Sudoku du niveau expert qu'il a trouvé sur le site http://njussien.e-constraints.net/sudoku/jouer.html et qui semblait résister à mon programme. Le tableau initial est :

(define tableau
 '((()(2)()()()()()(1)(4))
   ((8)()()(5)()()(7)()())
   (()()(1)()()()(3)()(6))
   (()(5)()()()()()()(1))
   ((7)()()()()(5)(4)()(2))
   (()(1)()()(4)(3)()()())
   (()(3)()(8)(7)()()(4)())
   (()()(8)(4)()(1)()()())
   (()()()(6)(5)()()()())))

et le programme donne un résultat incomplet :

((() 2 5 3 () 7 8 1 4)
 (8 () 3 5 1 () 7 2 9)
 (() 7 1 () () () 3 5 6)
 (3 5 4 () () () () () 1)
 (7 8 () 1 () 5 4 3 2)
 (() 1 () () 4 3 5 () 8)
 (() 3 () 8 7 () () 4 5)
 (5 () 8 4 3 1 2 () 7)
 (() () 7 6 5 () () 8 3))

J'ai cependant trouvé la solution en utilisant quelques-unes des fonctions que comporte le programme. La voici :

((6 2 5 3 9 7 8 1 4)
 (8 4 3 5 1 6 7 2 9)
 (9 7 1 2 8 4 3 5 6)
 (3 5 4 7 2 8 9 6 1)
 (7 8 9 1 6 5 4 3 2)
 (2 1 6 9 4 3 5 7 8)
 (1 3 2 8 7 9 6 4 5)
 (5 6 8 4 3 1 2 9 7)
 (4 9 7 6 5 2 1 8 3))

Il faudra que je perfectionne le programme, car il aurait dû arriver automatiquement à la solution... Je remercie Philippe Caille, qui m'a fait apercevoir une erreur de raisonnement dans une version antérieure de cette page.