This code requires the Simulated Annealing package.
/* * Graceful Tree Labelling using Simulated Annealing * * The labelling of a tree of N nodes is an assignment of the numbers 0 to N-1 * to its nodes. A labelling is graceful if the N-1 differences of the adjacent * labels are distinct. * * Ringel-Kotzig Conjecture: Every tree admits a graceful labelling. */ graceful(N, Edges0):- nodes(Edges0, [], Nodes), edges(Edges0, Nodes, Edges), retractall(size(_)), retractall(the_nodes(_)), retractall(the_edges(_)), asserta(size(N)), asserta(the_nodes(Nodes)), asserta(the_edges(Edges)), anneal. /* perturb(Xs, Ys) is true if the list Xs is a permutation of the integers */ /* 0 to Size-1, and Ys is the same as Xs except that two pseudo-randomly */ /* selected elements have been exchanged. */ perturb(Xs, Ys):- size(Size), random(Size, I), repeat, random(Size, J), I =\= J, !, subst(Xs, I, -1, Xs1), subst(Xs1, J, I, Xs2), subst(Xs2, -1, J, Ys). /* subst(Ls, X, Y, Ms) is true if the list Ms is the same as the list Ls */ /* except that the first occurrence of the element X is replaced by Y. */ subst([X|Ls], X, Y, Ms):-!, Ms=[Y|Ls]. subst([L|Ls], X, Y, [L|Ms]):-subst(Ls, X, Y, Ms). % Given the alphabetic edges generates the alphabetic nodes nodes([], Nodes0, Nodes):- reverse(Nodes0, Nodes). nodes([[A,B]|Xss], Nodes0, Nodes):- \+ member(A, Nodes0), \+member(B, Nodes0), !, nodes(Xss, [B,A|Nodes0], Nodes). nodes([[A,_]|Xss], Nodes0, Nodes):- \+ member(A, Nodes0), !, nodes(Xss, [A|Nodes0], Nodes). nodes([[_,B]|Xss], Nodes0, Nodes):- \+ member(B, Nodes0), !, nodes(Xss, [B|Nodes0], Nodes). nodes([[_,_]|Xss], Nodes0, Nodes):- nodes(Xss, Nodes0, Nodes). % Given the alphabetic edges and the alphabetic nodes generates the numeric % edges edges([], _, []). edges([[A,B]|Xss], Nodes, [[I,J]|Edges]):- nth(Nodes, I, A), nth(Nodes, J, B), !, edges(Xss, Nodes, Edges). % The energy is N-1-(the number of distinct differences of adjacent labels) energy(Labels, Energy):- the_edges(Edges), size(N), !, N1 is N - 1, energy_1(Edges, Labels, [], N1, Energy). energy_1([], _, _, Energy, Energy). energy_1([[I,J]|Edges], Labels, Xs, Energy0, Energy):- nth(Labels, I, K), nth(Labels, J, L), X is abs(K - L), \+ member(X, Xs), !, Energy1 is Energy0 - 1, energy_1(Edges, Labels, [X|Xs], Energy1, Energy). energy_1([_|Edges], Labels, Xs, Energy0, Energy):- energy_1(Edges, Labels, Xs, Energy0, Energy). output(optimal, Labels, 0):- % Solution found the_nodes(Nodes), !, output_1(Nodes, Labels). output(iterations, _, _):- write(`Solution not found - all iterations performed`), nl. output(nochanges, _, _):- write(`Solution not found - no changes made at a given temperature`), nl. output_1([], []):-nl. output_1([Node|Nodes], [Label|Labels]):- write(Node), write('='), write(Label), write(' '), output_1(Nodes, Labels). /* nth(+Xs, ?N, ?X) is true if X is the N-th (base 0) element of the list Xs.*/ nth(Xs, N, X):-nth_1(Xs, X, 0, N). nth_1([X|_], X, N, N). nth_1([_|Xs], X, N0, N):- N1 is N0 + 1, nth_1(Xs, X, N1, N). /* member(X, Ys) is true if the element X is contained in the list Ys. */ % member(X, [X|_]). % member(X, [_|Ys]):-member(X, Ys). /* reverse(Xs, Ys) is true if Ys is the result of reversing the order of the */ /* elements in the list Xs. */ %reverse(Xs, Ys):-reverse_1(Xs, [], Ys). %reverse_1([], As, As). %reverse_1([X|Xs], As, Ys):-reverse_1(Xs, [X|As], Ys). /* * Sample data */ % Gives, for example: % a=5 b=0 d=4 g=1 c=2 e=6 f=3 % Gives, for example: % a=2 b=7 c=13 g=1 h=10 i=9 d=3 e=0 f=4 k=5 q=12 m=6 n=8 p=11 go_14:- Edges=[[a,b],[a,c],[a,g],[a,h],[a,i],[c,d],[c,e],[c,f],[d,k],[e,q],[q,m], [q,n],[n,p]], graceful(14, Edges). % Gives, for example: % a=19 b=11 c=0 d=4 e=8 f=18 g=9 h=16 i=17 j=12 k=13 l=1 m=15 n=10 o=14 p=7 % q=6 r=5 s=2 t=3 go_20:- Edges=[[a,b],[a,c],[b,d],[b,e],[c,f],[c,g],[c,h],[d,i],[e,j],[f,k],[f,l], [g,m],[g,n],[h,o],[i,p],[i,q],[i,r],[i,s],[i,t]], graceful(20, Edges).