vertex(1).
vertex(2).
vertex(3).
vertex(4).
color(1).
color(2).
color(3).
edge(1,2).
edge(1,3).
edge(1,4).
edge(2,4).
edge(3,4).
edge(X,Y):-edge(Y,X).
getelement(1,[Z|_],Z).
getelement(X,[Z|Zs],M):-K is X-1,getelement(K,Zs,M).
check(Z):-edge(X,Y),getelement(X,Z,M),getelement(Y,Z,N),M=:=N,!,fail.
getcolor(1,red).
getcolor(2,blue).
getcolor(3,green).
colorit([A,B,C,D]):-color(A),color(B),color(C),color(D),write([A,B,C,D]),check([A,B,C,D]),write([A,B,C,D]).
This is my code. The problem it is not getting terminated. But the logic in code is clear, if you find where problem exists please help me to correct.
input:- colorit(Z).
output:- [1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]
[1, 1, 3, 1]
[1, 1, 3, 2]
[1, 1, 3, 3]
[1, 2, 1, 1]
[1, 2, 1, 2]
[1, 2, 1, 3]
[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]
it came till here, [1,2,2,3] which is the true solution it is in loop and not terminating by returning true.There's just a small correction that need to be made. Please help me out.
Some notes on your code:
The rule edge(X,Y):-edge(Y,X).
creates an infinite search tree.
Instead use hasEdge(X,Y) :- edge(X,Y) ; edge(Y,X).
This means hasEdge(X,Y)
is true when edge(X,Y)
or edge(Y,X)
is true.
Then replace the usage of edge
in your check
predicate by hasEdge
.
Your definition of check provides no positive case. You say: When there is an edge between the vertices X
and Y
such that the X
th and Y
th element of the coloring list Z
are equal, then fail. But you provide no way for check
to be true when this condition does not hold, so this path will also fail. For this, add a check(Z).
declaration after your check
rule (analogous to how yo would define the not
predicate, see here). Even shorter, you could remove the fail path altogether and just use not
in your definition of colorize
.
Based on these observations, your program could be rewritten to (I'm skipping the facts):
hasEdge(X,Y):-edge(X,Y) ; edge(Y,X).
getelement(1,[Z|_],Z).
getelement(X,[Z|Zs],M):-K is X-1,getelement(K,Zs,M).
check(Z):-hasEdge(X,Y),getelement(X,Z,M),getelement(Y,Z,N),M=:=N,!,fail.
check(Z).
colorit([A,B,C,D]):-color(A),color(B),color(C),color(D),check([A,B,C,D]).
Or using not
:
hasEdge(X,Y):-edge(X,Y) ; edge(Y,X).
getelement(1,[Z|_],Z).
getelement(X,[Z|Zs],M):-K is X-1,getelement(K,Zs,M).
check(Z):-hasEdge(X,Y),getelement(X,Z,M),getelement(Y,Z,N),M=:=N.
colorit([A,B,C,D]):-color(A),color(B),color(C),color(D),not(check([A,B,C,D])).