Discussion :

[Nathanelnak]

Bonjour a tous!

Je sollicite votre aide car je bloque completement sur un exercice PROLOG.
Je souhaite écrire un prédicat qui va lister toutes les permutations possible d'une liste composé de pions noirs (n) ou blancs (b).
Par exemple, le predicat affecte(3, 2, L) doit retourner toutes les listes L possibles de taille 3 ou figurent 2 pions noirs exactement, soit:

L = [b, n, n]
L = [n, b, n]
L = [n, n, b]

J'ai pour l'instant ceci qui n'est pas du tout fonctionnel.

Code :

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

1
2
3
4
5
affecte_ligne(0, _, L):-
    length(L, R).
 
affecte_ligne(Nn, N, L):-
    (N == 0 -> N1 is Nn-1, affecte_ligne(N1, N, [b|L])).

Merci pour votre aide,

[Trap D]

Bonjour
Une possibilité est celle-ci :

Code :

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

1
2
3
4
5
6
7
8
affecte_ligne(L) :-
    nth0(_,L, b),
    select(b, L, [n,n]).
 
 
affecte(Lst) :-
    length(L, 3),
    bagof(L, affecte_ligne(L), Lst).

Le principe est le suivant :
On définit le pattern recherché dans la clause affecte_ligne, ici une liste composée d'un élément b positionné "au hasard" avec le prédicat nth0/3, le reste de la liste n'est composé que de n, on le force à l'aide du prédicat select/3.
Ensuite on dit à Prolog de trouver toutes les listes de longueur 3 qui suivent ce pattern, c'est bagof/3 qui fait cette recherche

[EDIT] On peut se passer de la clause nth0(_,L, b),.

Code :

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

1
2
3
4
5
6
7
affecte_ligne(L) :-
    select(b, L, [n,n]).
 
 
affecte(Lst) :-
    length(L, 3),
    bagof(L, affecte_ligne(L), Lst).

Avec pour résultat

?- affecte(L).

L = [[b, n, n], [n, b, n], [n, n, b]].


Finalement, si on regarde bien le code, la clause length(L,3) ne sert à rien puisque le select(b, L, [n,n]) implique que la longueur de L est 3.
Le code final est tout simple

Code :

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

1
2
3
4
5
affecte_ligne(L) :-
    select(b, L, [n,n]).
 
affecte(Lst) :-
    bagof(L, affecte_ligne(L), Lst).

[laurentcp]

Bonjour,

Vous devez créer le prédicat affecte(N, M, L), qui crée la liste L de longueur N constituée de M 'n' et de (N-M) 'b'.

Je vous recommande de créer quatre clauses pour ce prédicat. Deux clauses pour traiter les cas particuliers où M = 0 et M = N, les deux autres pour créer les deux cas récursifs : la liste L commence par 'b', la liste L commence par 'n'.

A noter que vous n'avez besoin d'aucun prédicat prédéfini de Prolog excepté 'is', mais vous pouvez utiliser 'length' pour faciliter la création des listes de 'b' et de 'n'.

Code :

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

1
2
3
4
affecte(N, 0, L) :- ...
affecte(N, N, L) :- ...
affecte(N, M, [n|L]) :- ... affecte(?, ?, L) ...
affecte(N, M, [b|L]) :- ... affecte(?, ?, L) ...

[Trap D]

Bonjour
Ça fait plaisir de voir que je ne suis plus seul à m'intéresser à Prolog sur ce site !
J'ai une petite remarque à faire sur ce que vous avez écrit : "A noter que vous n'avez besoin d'aucun prédicat prédéfini de Prolog excepté 'is', mais vous pouvez utiliser 'length' pour faciliter la création des listes de 'b' et de 'n'."
Personnellement, je ne pense pas que ce soit une bonne idée d'ignorer les prédicats prédéfinis de Prolog car, dans ce cas on utilise l'approche connue de programmation qui est en général l’approche impérative et ce n’est surement pas ce qu’on recherche lorsqu’on fait du Prolog.
Vous proposez de généraliser le problème à une liste de longueur quelconque avec un nombre quelconque de « m » et de « n ».
Voici l’approche que je propose qui n’est absolument pas efficace, je le reconnais, mais qui est basée sur l’observation des résultats recherchés (une autre façon de programmer, sans utiliser les sempiternelles boucles et les compteurs).
D’abord, je crée un pattern initial (une liste de N ’n’ et M ’m’) :

Code :

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

1
2
3
4
5
6
7
8
9
10
set_value(C,C).
 
cree_liste(N, C, L) :-
    length(L, N),
    maplist(set_value(C), L).
 
cree_pattern(N, Cn, M, Cm, L) :-
    cree_liste(N, Cn, Ln),
    cree_liste(M, Cm, Lm),
    append(Ln,Lm,L).

Ensuite je montre à Prolog comment créer une combinaison quelconque à partir du pattern fourni, donc on utilise à haute dose select/3 et la récursivité :

Code :

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

1
2
3
4
5
6
7
8
9
affecte_une_combinaison([H|T], Tmp):-
    select(H, Tmp, Tmp1),
    affecte_une_combinaison(T, Tmp1).
 
affecte_une_combinaison([], []).
 
cree_une_combinaison(Pattern, L):-
    same_length(Pattern, L),
    affecte_une_combinaison(Pattern, L).

Enfin je demande à Prolog de rechercher toutes les combinaisons possibles, en utilisant le backtrack et en éliminant les doublons, inévitables suivant la méthode de création (setof/3)

Code :

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

1
2
3
toutes_les_combinaisons(N, Cn, M, Cm, L) :-
    cree_pattern(N, Cn, M, Cm, Pattern),
    setof(Tmp, cree_une_combinaison(Pattern, Tmp), L).

Vous remarquerez qu'il n'y a absolument aucun cas particulier.