L'intelligence humaine est supérieure à celle d'un algorithme
22/06/2023
Le développement présenté dans l'article précédent aura été l'occasion de découvrir une difficulté intéressante. Le sudoku avec les contraintes suivantes n'a pas de solution !
Seulement voilà, il faut 1 873 812 290 itérations au programme écrit en C appliquant l'algorithme présenté dans l'article comparant différents langages pour aboutir à cette conclusion. Plus d'un milliard d'itérations n'est pas un problème en soit pour un ordinateur mais le souci est que le serveur de numerunique met plus de 47 secondes pour les exécuter. Et 47 secondes c'est un temps infini pour un utilisateur qui aura déjà décidé au bout de 2 secondes que le programme est planté.
D'où la nécessité d'optimiser le traitement de recherche automatique d'une solution d'un sudoku. Le nouvel algorithme, inspiré de la stratégie implicitement proposée à l'utilisateur du sudoku proactif, trouve une solution en 1 447 itérations au sudoku choisi comme exemple pour la comparaison des différents langage alors que 1 453 557 itérations sont nécessaires pour l'ancien algorithme. Dans cet exemple, le temps de traitement passe de 0.05 s à 0.02 s ; plus de deux fois plus rapide.
Mais pour le cas particulier considéré ci-dessus c'est la catastrophe !
Le nouvel algorithme, "optimisé", trouve qu'il n'y a pas de solution en seulement 26 440 176 itérations mais met plus de 2 minutes à rendre sont résultat :-((
Le problème est contourné en décidant d'un nombre maximal d'itérations choisi arbitrairement pour laisser la place à la découverte d'une solution si elle existe mais renoncer à décider qu'il n'y a pas de solution si cela était trop long pour le confirmer. L'utilisateur est alors informé de la situation par un message tel que :
"Il reste 248 alternatives… mais une solution improbable."
Ainsi aidé par la machine, l'intelligence humaine prendra la bonne décision.
Le corolaire de cette histoire est que l'optimisation d'un algorithme est une démarche complexe…