Map Coloring Prolog

user_17740557 0
Viewed 45

I wrote this code to solve the map coloring problem using prolog:

coloring([A,B,C,D,E,F]):-
    maplist(=\=(A),[B,C,D,E]),
    maplist(=\=(B),[C,D,F]),
    C=\=D,
    maplist(=\=(D),[E,F]),
    E=\=F.

I try to get solutions using the query:

?- coloring(Cs), Cs ins [1,2,3,4], Cs = [1|_].

but I always get the error "Arguments not sufficiently instantiated", how to fix this?

clpfd prolog
1 Answers

Use #\=/2 instead of =\=/2, and fix the domain in ins/2:

:- use_module(library(clpfd)).

coloring([A,B,C,D,E,F]):-
    maplist(#\=(A),[B,C,D,E]),
    maplist(#\=(B),[C,D,F]),
    C#\=D,
    maplist(#\=(D),[E,F]),
    E#\=F.

Sample runs:

?- coloring(Cs), Cs ins 1..4, Cs=[1|_].
Cs = [1, _A, _B, _C, _D, _E],
_A in 2..4,
_A#\=_E,
_A#\=_C,
_A#\=_B,
_B in 2..4,
_B#\=_C,
_C in 2..4,
_C#\=_E,
_C#\=_D,
_D in 2..4,
_D#\=_E,
_E in 1..4.

with labeling:

?- coloring(Cs), Cs ins 1..4, Cs=[1|_], label(Cs).
Cs = [1, 2, 3, 4, 2, 1] ;
Cs = [1, 2, 3, 4, 2, 3] ;
Cs = [1, 2, 3, 4, 3, 1] ;
Cs = [1, 2, 4, 3, 2, 1] ;
Cs = [1, 2, 4, 3, 2, 4] ;
  ...
user_4632430
Related