|
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. |
