Discussion :

[Trap D]

Bonjour

J'ai écrit cet article/ tutoriel d'utilisation qui permet de résoudre des Kuromasu en Prolog avec la librairie des contraintes clpfd.
Le module de résolution permet la résolution dans les deux sens :
A partir de la liste des contraintes, on obtient la grille solution.
A partir d'une grille on peut obtenir la liste des contraintes.

J'attends toute vos remarques et questions.
Merci

Trap D.

[luckyvae]

Je ne connaissais pas du tout ce type de jeu, j'ai donc trouvé cet article très intéressant. Je n'ai pas encore eu le temps de regarder en détail le code source, mais je pense le faire par la suite.

Merci pour cet article

[luckyvae]

C'est à nouveau moi et je n'ai toujours pas regardé l'entièreté du code, mais je me pose la question suivante: dans le code que tu fournis, tu utilises "labeling" avec l'option activant la stratégie "first fail", tandis que dans l'article tu utilises "label". Pourquoi?

Il me semble que ce serait intéressant pour les lecteurs que tu parles de "labeling" plutôt que de "label" afin de mettre en évidence que le choix des options pour "labeling" peut faire gagner énormément de temps dans certains cas.

[Trap D]

Effectivement, dans le texte j'utilise le mot "labeling" et dans le code "label".
La phase de labeling, comme tu le sais sans doute, est le moment où on lance le mécanisme d'attribution de valeurs aux variables déclaréees pour les contraintes. J'utilise ce mot dans le sens général.
Dans mon code, comme je n'impose pas d'option particulière pour ce labeling, j'utilise le raccourci Prolog label(S) qui est équivalent à labeling([], S).
Mais tu as raison, il peut être intéressant de faire un petit développement sur l'utilité des différentes options du labeling.

[edit] En relisant attentivement l'article, j'ai vu que effectivement, dans le code fourni dans le zip, j'utilise labeling(options, Solution).

je vais corriger tout celà

Merci !

[/edit]

[luckyvae]

Je viens de tester en vrac différentes options possibles pour labeling en utilisant le code fournit avec l'article. Les résultats ne sont pas fort différents (solve-console, grille 43b)

Code :

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

1
2
3
4
5
6
7
8
9
#inférences   options
152,363,905   ffc,bisect
152,363,896   ffc
152,372,323   max
152,372,317   min
151,905,542   leftmost
152,280,664   ff
151,905,551   leftmost, enum
151,905,551   leftmost, bisect

Donc je me dis que dans le cadre de cet article, ça pourrait être chouette de signaler qu'il existe différentes options de recherche.

Par contre, je me dit que ce serait chouette de faire un article à part qui parle de ces différentes options ou de manière plus générale de différentes méthodes de recherche. Je veux bien faire une ébauche si tu le souhaites en me basant sur deux trois trucs que j'ai déjà lu...

[Trap D]

Par contre, je me dit que ce serait chouette de faire un article à part qui parle de ces différentes options ou de manière plus générale de différentes méthodes de recherche. Je veux bien faire une ébauche si tu le souhaites en me basant sur deux trois trucs que j'ai déjà lu...

Pas de problème au contraire, tu peux rédiger un article la-dessus.

Il y a des options qui sont simples à mettre en oeuvre, (up, down, min(Expr) max(Expr)), mais d'autres sont plus difficiles à utiliser (bisect, ff, ffc) il faudrait arriver à trouver des exemples vraiment parlant.

Par exemple pour min(Exp) et down:

26 ?- X in 3..7, E #= X*X - 10 * X + 25, labeling([min(E), down], [X]).
X = 5,
E = 0 ;
X = 6,
E = 1 ;
X = 4,
E = 1 ;
X = 7,
E = 4 ;
X = 3,
E = 4 ;
false.

27 ?- X in 3..7, E #= X*X - 10 * X + 25, labeling([min(E)], [X]).
X = 5,
E = 0 ;
X = 4,
E = 1 ;
X = 6,
E = 1 ;
X = 3,
E = 4 ;
X = 7,
E = 4 ;
false.

On voit les différentes méthodes de recherches (par défaut c'est up).

[Trap D]

Je viens de trouver un exemple ou l'option ff est spectaculaire.
j'ai repris le code du Sudoku de pcaboche
J'ai un peu modifé le code pour ajouter des options de labeling :

11 ?- time(sudokuExemple(Vars, [])).

===================
|8,7,4|6,5,1|2,3,9|
|2,3,9|8,4,7|1,6,5|
|1,6,5|3,9,2|8,4,7|
===================
|6,5,7|1,2,4|9,8,3|
|9,4,2|5,3,8|7,1,6|
|3,1,8|7,6,9|5,2,4|
===================
|5,2,1|4,7,3|6,9,8|
|7,8,3|9,1,6|4,5,2|
|4,9,6|2,8,5|3,7,1|
===================
|
% 1,107,581 inferences, 0.406 CPU in 0.439 seconds (93% CPU, 2726353 Lips)
Vars = [8, 7, 4, 6, 5, 1, 2, 3, 9|...].

12 ?- time(sudokuExemple(Vars, [ff])).

===================
|8,7,4|6,5,1|2,3,9|
|2,3,9|8,4,7|1,6,5|
|1,6,5|3,9,2|8,4,7|
===================
|6,5,7|1,2,4|9,8,3|
|9,4,2|5,3,8|7,1,6|
|3,1,8|7,6,9|5,2,4|
===================
|5,2,1|4,7,3|6,9,8|
|7,8,3|9,1,6|4,5,2|
|4,9,6|2,8,5|3,7,1|
===================
|
% 326,751 inferences, 0.125 CPU in 0.154 seconds (81% CPU, 2614008 Lips)
Vars = [8, 7, 4, 6, 5, 1, 2, 3, 9|...].

C'est plus de trois fois plus rapide !

[luckyvae]

Ce qui montre bien que la méthode de recherche est un point crucial pour le temps de calcul ;-)

Le fait que ça aille trois fois plus vite est simple à expliquer: au lieu d'assigner une valeur aux différentes variables en fonction de l'ordre de la liste, la variable possédant le moins de possibilités d'assignations est choisie. De ce fait, ça va plus vite car comme le nom l'indique, les appels échoueront plus vite et donc l'arbre de recherche s'en retrouve fortement réduit.

[Trap D]

A ce sujet, je viens de recevoir un mail de Markus Triska qui m'a conseillé pour la rédaction de l'article, je le livre tel quel :

regarding labeling options, take for example N-queens as a great example for the difference between
ff and leftmost:

http://www.logic.at/prolog/queens/queens.html

Try for example:

?- n_queens(80, Qs), time(labeling([], Qs)).
%@ Action (h for help) ? abort
%@ % 8,237,652 inferences, 1.510 CPU in 4.564 seconds (33% CPU, 5455399 Lips)
%@ % Execution Aborted

(run it as long as you want)

and:

?- n_queens(80, Qs), time(labeling([ff], Qs)).
%@ % 714,139 inferences, 0.150 CPU in 0.430 seconds (35% CPU, 4760927 Lips)
%@ Qs = [1, 3, 5, 44, 42, 4, 50, 7, 68|...].

Il a ajouté, ce qui explique bien le fait que l'option ff ne change rien pour les Kuromasus :

With binary variables, "ff" cannot make a difference: Either the variable is still unknown, or its value is fixed. There cannot be a case where some elements could be pruned but the variable is still unbound, because each variable only has two possible values. This is why you do not see much difference in the Kuromasu example. This is one possible problem of binary models - it is hard to see for the constraint solver where the search space gets "tight".

[SpiceGuid]

C'est assez rare un article Prolog comme celui-ci qui montre la puissance de la programmation logique en particulier et non pas seulement de la programmation déclarative en général.

Le module de résolution permet la résolution dans les deux sens :
A partir de la liste des contraintes, on obtient la grille solution.
A partir d'une grille on peut obtenir la liste des contraintes.

Je trouve fascinante l'idée qu'un code soit réversible.
C'est une faiblesse de la programmation déclarative qu'elle est souvent moins équationnelle qu'on le souhaiterait, on écrit souvent une transformation là où en fait on voudrait une égalité.
En tout cas cette solution Prolog est incroyablement efficace et tord le cou à la réputation du prolog "1000 x plus lent que le C".