different(red, blue). different(red, green). different(red, yellow). different(blue, red). different(blue, green). different(blue, yellow). different(green, blue). different(green, red). different(green, yellow). different(yellow, blue). different(yellow, green). different(yellow, red). color(washington, C, color(C,_,_,_,_,_,_,_,_,_,_)). color(oregon, C, color(_,C,_,_,_,_,_,_,_,_,_)). color(california, C, color(_,_,C,_,_,_,_,_,_,_,_)). color(idaho, C, color(_,_,_,C,_,_,_,_,_,_,_)). color(nevada, C, color(_,_,_,_,C,_,_,_,_,_,_)). color(arizona, C, color(_,_,_,_,_,C,_,_,_,_,_)). color(utah, C, color(_,_,_,_,_,_,C,_,_,_,_)). color(newMexico, C, color(_,_,_,_,_,_,_,C,_,_,_)). color(colorado, C, color(_,_,_,_,_,_,_,_,C,_,_)). color(wyoming, C, color(_,_,_,_,_,_,_,_,_,C,_)). color(montana, C, color(_,_,_,_,_,_,_,_,_,_,C)). colorList(color(C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11), cList(washington, C1, oregon, C2, california, C3, idaho, C4, nevada, C5, arizona, C6, utah, C7, newMexico, C8, colorado, C9, wyoming, C10, montana, C11)). differentColor(S1, S2, CV) :- color(S1, C1, CV), color(S2, C2, CV), different(C1, C2). valid(CV) :- differentColor(washington, oregon, CV), differentColor(washington, idaho, CV), differentColor(oregon, idaho, CV), differentColor(oregon, california, CV), differentColor(oregon, nevada, CV), differentColor(california, nevada, CV), differentColor(california, arizona, CV), differentColor(idaho,montana, CV), differentColor(idaho,wyoming, CV), differentColor(idaho,utah, CV), differentColor(idaho,nevada, CV), differentColor(montana, wyoming, CV), differentColor(utah, arizona, CV), differentColor(utah, colorado, CV), differentColor(utah, wyoming, CV), differentColor(utah, nevada, CV), differentColor(wyoming, colorado, CV), differentColor(colorado, newMexico, CV), differentColor(newMexico, arizona, CV), differentColor(arizona, nevada, CV). split([], [], []). split([X], [ X], []). split([X1, X2 | L1], [X1 | L2], [X2 | L3]) :- split(L1, L2, L3). merge(L, [], L). merge([], L, L). merge([X1 | L1], [X2 | L2], [Z | L3]) :- X1 =< X2, X1 = Z, merge(L1, [X2 | L2], L3). merge([X1 | L1], [X2 | L2], [Z | L3]) :- X2 =< X1, X2 = Z, merge([X1 |L1], L2, L3). mergesort([], []). mergesort([X], [X]). mergesort(L1, L2) :- split(L1, A, B), mergesort(A, A1), mergesort(B, B1), merge(A1, B1, L2).