Discussion :

[yacc22300]

Bonjour à tous,

Retraite et confinement obliges, j'occupe une partie de mon temps sur un livre d'énigmes logiques (La Bible des énigmes logique, de J.M. Maman, editions ESI) et je suis tombé sur un problème que Prolog pourrait peut-être facilement traiter (voir l'image jointe, les chiffres dans les cases sont pour les identifier, pas une tentative de solution!)
Je ne connais ce langage que par des publications (je sais que dans ma boîte, il avait été expérimenté il y a une vingtaine d'années, pour tenter de résoudre des problèmes de configuration et d'installation d'équipements télécom, mais sans suite)
De métier informaticien (essentiellement en VBasic), j'ai tenté de m'y mettre mais j'ai vite déchanté! On ne rentre pas dans ce langage la fleur au fusil. Impatient d'avoir une solution (sur les 12 possibles mais qui sont toutes liées, de par les propriétés de symétrie - rotation et miroir -), j'ai développé un programme en Python - que je ne connaissais pas- d'environ 300 lignes. En cherchant à minimiser la combinatoire, ce programme me retourne une solution en environ 1 heure
J'aimerais soumettre aux experts Prolog (qui je pense sont aussi des bêtes en mathématiques) deux questions :
1) y a-t-i une solution mathématique à ce problème? (j'ai tenté de le mettre en équations, la contrainte de somme à 38 s'appliquant à 15 lignes, pour 19 inconnues, je n'ai pas abouti. Il existe d'autres contraintes mais sous forme d'inégalités - par exemple si on ne considère que les deux lignes L1 et L5, il faut que case 1 + case 19 < 33) C'est ce type d'inégalités que j'ai appliqué dans le programme Python pour exclure des lignes entre elles.
2) une programmation Prolog est-elle envisageable, pour une complexité et un temps de réponse équivalents, voire meilleurs que dans un langage classique interprété?

Si l'un d'entre vous a un peu de temps (de loisir) à consacrer, je le remercie d'avance
Cordialement

[Trap D]

Ce programme donne la réponse en 0,172 seconde sur ma machine :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
:-use_module(library(clpfd)).
 
solve(Lst) :-
    Lst = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S],
    Lst ins 1..19,
    all_distinct(Lst),
 
        A + B + C     #= 38,
      D + E + F + G   #= 38,
    H + I + J + K + L #= 38,
      M + N + O + P   #= 38,
        Q + R + S     #= 38,
 
        A + D + H     #= 38,
      B + E + I + M   #= 38,
    C + F + J + N + Q #= 38,
      G + K + O + R   #= 38,
        L + P + S     #= 38,
 
        C + G + L     #= 38,
      B + F + K + P   #= 38,
    A + E + J + O + S #= 38,
      D + I + N + R   #= 38,
        H + M + Q     #= 38,
 
    labeling([ff], Lst),
    affiche(Lst).
 
affiche(Lst) :-
    Lst = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S],
    format('      ~d + ~d + ~d~n', [A,B,C]),
    format('   ~d + ~d + ~d + ~d~n', [D,E,F,G]),
    format('~d + ~d + ~d  + ~d + ~d~n', [H,I,J,K,L]),
    format('   ~d + ~d + ~d + ~d~n', [M,N,O,P]),
    format('      ~d + ~d + ~d~n', [Q,R,S]).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 ?- time(solve(L)).
      3 + 17 + 18
   19 + 7 + 1 + 11
16 + 2 + 5  + 6 + 9
   12 + 4 + 8 + 14
      10 + 13 + 15
% 1,515,100 inferences, 0.172 CPU in 0.187 seconds (92% CPU, 8815127 Lips)
L = [3, 17, 18, 19, 7, 1, 11, 16, 2|...] ;
      3 + 19 + 16
   17 + 7 + 2 + 12
18 + 1 + 5  + 4 + 10
   11 + 6 + 8 + 13
      9 + 14 + 15
% 1,168,895 inferences, 0.188 CPU in 0.203 seconds (92% CPU, 6234107 Lips)
L = [3, 19, 16, 17, 7, 2, 12, 18, 1|...]

La bibliothèque clpfd est très puissante !
Il n'y a aucune recherche mathématique (équation ou autre), la librairie se contente de tester (très rapidement) toutes les combinaisons possibles.
PS Si vous êtes passionné par la résolutions d'énigmes logiques, intéressez-vous aussi à la bibliothèque clp, écrite aussi par Markus Triska.

[yacc22300]

Bonjour,
Total respect mais là je ne comprends pas (en fait si ,voir plus bas) pourquoi votre programme donne effectivement la réponse en moins de la seconde, alors que celui que j'avais écrit, sur la base de l'exemple donné sur votre site pour le sudoku, de P. Caboche :
https://pcaboche.developpez.com/arti...og/clp/sudoku/, et qui ressemble quand même beaucoup au votre, ne répond pas, même après plusieurs heures (SWI-Prolog 64bits version 8.2.3), et qui m'avait fait partir sur un autre langage.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
:- use_module(library(clpfd)).
 
atomeInfernal(Vars) :-
Vars =
 [
    A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,
    A10,A11,A12,A13,A14,A15,A16,A17,A18
 ],
 
 Vars ins 1..19,
 
 all_distinct([A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,A18]),
 
 label(Vars),
 
 
    sum([A0,A1,A2], #=, 38),
    sum([A3,A4,A5,A6], #=, 38),
    sum([A7,A8,A9,A10,A11], #=, 38),
    sum([A12,A13,A14,A15], #=, 38),
    sum([A16,A17,A18], #=, 38),
    sum([A0,A3,A7], #=, 38),
    sum([A1,A4,A8,A12], #=, 38),
    sum([A2,A5,A9,A13,A16], #=, 38),
    sum([A6,A10,A14,A17], #=, 38),
    sum([A11,A15,A18], #=, 38),
    sum([A2,A6,A11], #=, 38),
    sum([A1,A5,A10,A15], #=, 38),
    sum([A0,A4,A9,A14,A18], #=, 38),
    sum([A3,A8,A13,A17], #=, 38),
    sum([A7,A12,A16], #=, 38).

En fait, je comprends que c'est la position du prédicat "label" qui est mauvaise. En le positionnant à la fin, effectivement, les performances sont toutes autres.
Il en faut donc peu pour abandonner une voie!
Merci donc pour m'avoir redonné l'envie d'aller plus loin avec Prolog.
Merci aussi pour le conseil concernant la bibliothèque

Bien cordialement