Ce travail consiste à faire un programme Prolog qui résout le casse tête suivant:
Trouver un nombre:
Etape 1: exprimer qu'un nombre est divisible par un autre.
% X divise Y si...
divise(X,Y) :- ...
Etape 2: exprimer que ce nombre s'écrit avec une liste de
chiffres donnée: X divise le nombre qui s'écrit avec les chiffres
Chiffres si...
diviseChif(X,Chiffres)
:- ..., divise(X,Y).
Etape 3: exprimer que ce nombre résulte de l'ajout (la
concaténation) d'un chiffre à un autre nombre: X divise le
nombre qui s'écrit en ajoutant le chiffre Ch à la liste
Chiffres si...
diviseAvecChiffre(X,[Ch],Chiffres) :- ..., diviseChif(X,Chiffres).
Etape 4: exprimer que, en plus, ce chiffre est choisi dans une liste de
chiffres donnée, et effacé de cette liste: X divise un nombre
qui s'écrit en ajoutant à la liste Chiffres un chiffre de
la liste AutresChiffres si...
diviseSelect(X,Chiffres, AutresChiffres) :- ..., diviseAvecChiffre(X,[Ch],Chiffres).
Etape 5: exprimer que l'on cherche ensuite une solution avec un
diviseur augmenté de 1 et les chiffres qui restent.
cassetete(X,Chiffres, AutresChiffres,S) :- ..., diviseAvecChiffre(X,[Ch],Chiffres),...
Etape 6: exprimer que la solution est atteinte lorsqu'il ne reste
plus de chiffres à sélectionner.
cassetete(X,Chiffres,[],S) :- ...
Pour finir, la résolution sera lancée par la
requête Prolog:
cassetete(1,[],"123456789",Solution).
La réponse à cette requête est hélas un échec. Pourtant, il existe une solution, que nous obtenions l'an dernier en utilisant un autre interpréteur Prolog appelé Open Prolog (qui ne fonctionne que sous Mac OS 9), qui donnait Solution=381654729.
Pour comprendre pourquoi cela ne fonctionne pas en GnuProlog (celui qui est utilisé cette année), on peut lancer la requête divise(9,381654729) ou 0 is 381654729 mod 9 et obtenir la réponse faux. C'est donc un problème lié au fait que l'entier 381654729 n'est pas géré en GnuProlog car trop grand. On peut s'en convaincre en lançant la requête X is 38165 * 10000 + 4729, pour laquelle on obntient X = -155216183.
Nous allons donc réduire nos ambitions et reformuler notre casse-tête:
Trouver un nombre:
Ce nouveau problème, lui, est résolu par la requête cassetete(1,[],"12345678",Solution), qui renvoie bien Solution=38165472. Si nous généralisons notre casse-tête aux nombres composés des n premiers chiffres non nuls, par quelles requête pouvons nous trouver pour quelles valeurs de n il existe des solutions?
Un corrigé est proposé: ne le regardez pas tout de suite ;-)
Mise à jour 9/03/05 0:01