Théorème à quatre couleurs dans Prolog (utilisant un prédicat dynamique)

Question

Je travaille sur la coloration d'une carte selon le théorème à quatre couleurs (http://en.wikipedia.org/wiki/Four_color_theorem) avec SWI-Prolog. Jusqu'à présent, mon programme ressemble à ceci:

colour(red). 
colour(blue). 

map_color(A,B,C) :- colour(A), 
     colour(B), 
     colour(C), 
     C \= B, 
     C \= A. 

(le progamme réel serait plus complexe, avec 4 couleurs et plus de champs, mais je pensais que je commencerais avec un cas simple)

Maintenant, Je veux éviter les solutions doubles qui ont la même structure. Par exemple. pour une carte avec trois champs, la solution "rouge, rouge, bleu" aurait la même structure que "bleu, bleu, rouge", juste avec des noms de couleurs différents, et je ne veux pas les deux affichés. J'ai donc pensé que j'aurais une solution de prédicat dynamique/3, et j'appellerais affirmer (solution (A, B, C)) à la fin de mon prédicat map_color. Et puis, pour chaque solution, vérifiez si elles existent déjà comme solution/3 fait. Le problème est que je devrais affirmer quelque chose comme solution (Color1, Color1, Color2), c'est-à-dire avec des variables afin de faire un contrôle d'unification. Et je ne peux pas penser à un moyen d'y parvenir. Donc, la question est, quelle est la meilleure façon d'affirmer une solution trouvée et ensuite faire un test d'unification de sorte que "rouge, rouge, bleu" serait unifier avec "bleu, bleu, rouge"?

Answer 1

Pour construire relation entre les variables:

mask_helper(_, _, [], []). 
mask_helper(A, B, [A|_], [B|_]):- !. 
mask_helper(A, B, [X|Xs], [_|Ys]):- 
    A \= X, 
    mask_helper(A, B, Xs, Ys). 

mask([], []). 
mask([X|Xs], [Y|Ys]):- 
    mask_helper(X,Y,Xs,Ys), 
    mask(Xs, Ys). 

et vous pouvez construire votre masque:

?- mask([red,red,blue],X). 
X = [_G300, _G300, _G306] . 

mais:

?- mask([red,red,blue],X), mask([blue,red,red],Y), X=Y. 
X = [_G27, _G27, _G27], 
Y = [_G27, _G27, _G27]. 

à savoir il n'y a aucune relation sur Color1 \= Color2 si vous utiliserez assert (sans le corps de la règle).

Vous pouvez envisager somethin comme ordre d'attribution des couleurs (approche assez populaire):

colour(red). colour(green). colour(blue). 

colour_order(red, red). 
colour_order(red, green). 
colour_order(red, blue). 
colour_order(green, green). 
colour_order(green, blue). 

colour_code([]). 
colour_code([X]):- colour(X). 
colour_code([X|[Y|T]]):- 
    colour_order(X,Y), 
    colour_code([Y|T]). 

map_color(A,B,C):- 
    colour_code([A,B,C]), 
    C \= B, C \= A. 

Mais encore une fois, vous ne serez jamais obtenir le résultat « rouge, bleu, rouge » si vos conditions seront A \= B, B \= C.

méditer:

unify([], [], _). 
unify([X|Xs], [Y|Ys], M):- 
    member((X=Z), M), !, 
    Z = Y, 
    unify(Xs, Ys, M). 

unify([X|Xs], [Y|Ys], M):- 
    % X is not assigned yet 
    not(member((_=Y),M)), % Y is not used as well 
    unify(Xs, Ys, [(X=Y)|M]). 

que vous pouvez comparer:

?- unify([red,red,blue],[blue,blue,red],[]). 
true. 

?- unify([red,red,blue],[blue,blue,blue],[]). 
false. 

?- unify([red,red,blue],[blue,red,red],[]). 
false. 

Answer 2

Je pense que la solution la plus simple est de dire que A a toujours la couleur rouge (par exemple).