This assignment is due Thursday, May 8, at the start of section. You are to do this assignment individually .
Write a prolog program for map coloring, specialized to the US. You may restrict attention to the "Western States". (washington, oregon, california, idaho, nevada, arizona, utah, newMexico, colorado, wyoming, montana).
My program uses a tuple called color to keep track of colors of states. The trick used to print out the list of states along with their colors is to match the color vector with a tuple of colors and state names (of course, prolog does have IO facilities. This was done declaring
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)).
Here is a sample run of my coloring program -
This is a four color version. The three color version fails - although
if you allow Utah and Nevada to be the same color, then there is a
3 coloring of the western states.
Script started on Tue Apr 29 10:21:05 1997
lynx% prolog
Quintus Prolog Release 3.1 (DECstation, Ultrix 4.x)
Copyright (C) 1990, Quintus Corporation. All rights reserved.
2100 Geng Road, Palo Alto, California U.S.A. (415) 813-3800
| ?- [map].
% compiling file /Sucia/staff/anderson/plog/map
% map compiled in module user, 0.350 sec 2,472 bytes
yes
/* Check if there is a valid coloring - there are lots of them! */
| ?- valid(CV).
CV = color(red,blue,red,green,yellow,blue,red,red,blue,yellow,blue) ;
CV = color(red,blue,red,green,yellow,blue,red,green,blue,yellow,blue) ;
CV = color(red,blue,red,green,yellow,blue,red,yellow,blue,yellow,blue) ;
CV = color(red,blue,red,green,yellow,blue,red,red,green,yellow,blue) ;
CV = color(red,blue,red,green,yellow,blue,red,yellow,green,yellow,blue) ;
CV = color(red,blue,red,green,yellow,blue,red,red,green,blue,red) ;
CV = color(red,blue,red,green,yellow,blue,red,yellow,green,blue,red)
/* List state names as well */
| ?- valid(CV), colorList(CV, CL).
CV = color(red,blue,red,green,yellow,blue,red,red,blue,yellow,blue),
CL = cList(washington,red,oregon,blue,california,red,idaho,green,nevada,yellow,arizona,blue,utah,red,newMexico,red,colorado,blue,wyoming,yellow,montana,blue)
/* Is there a coloring with washington blue? */
| ?- valid(CV), color(washington, blue, CV).
CV = color(blue,red,blue,green,yellow,red,blue,blue,green,red,blue)
/* what about oregon - red, california - green,
arizona - yellow, utah - blue? */
| ?- valid(CV), color(oregon, red, CV), color(california, green, CV),
color(arizona, yellow, CV), color(utah, blue, CV).
no
| ?- valid(CV), color(oregon, red, CV), color(california, green, CV),
colorList(CV, CL).
CV = color(blue,red,green,green,blue,red,yellow,green,blue,red,blue),
CL = cList(washington,blue,oregon,red,california,green,idaho,green,nevada,blue,arizona,red,utah,yellow,newMexico,green,colorado,blue,wyoming,red,montana,blue)
| ?-
| ?- halt.
lynx%
script done on Tue Apr 29 10:28:15 1997
The merge sort algorithms is
MergeSort (S) =
if |S| <= 1 return S
split S into to sets S1 and S2 of (roughly) equal size.
S1 = MergeSort(S1), S2 = MergeSort(S2)
return Merge(S1, S2)
Begin by writing a routine called split, which divides S into S1 and S2.
One very minor hint: in prolog, <= is =<.
Here is a script showing my solution.
Script started on Tue Apr 29 11:40:04 1997
Quintus Prolog Release 3.1 (DECstation, Ultrix 4.x)
Copyright (C) 1990, Quintus Corporation. All rights reserved.
2100 Geng Road, Palo Alto, California U.S.A. (415) 813-3800
| ?- [merge].
% compiling file /Sucia/staff/anderson/plog/merge
% merge compiled in module user, 0.117 sec 892 bytes
yes
| ?- mergesort([3, 5, 6, 1, 2, 8, 2, 11, 5, 6]), A).
A = [1,2,2,3,5,5,6,6,8,11]
| ?- mergesort([], A).
A = []
| ?- mergesort([1, 2, 3 , 4, 5], B).
B = [1,2,3,4,5]
| ?- merge([1, 2, 3, 4], [2, 3, 4, 5], C).
C = [1,2,2,3,3,4,5]
(* It would be cool if Merge went backwards - but something
goes wrong. I wonder if mergesort goes backwards . . .*)
| ?- merge(A, B, [1, 2, 3, 4]).
A = [1,2,3,4],
B = [] ;
A = [],
B = [1,2,3,4] ;
! Instantiation error in argument 1 of =< /2
! goal: _9084=<_9085
(* Here is the split routine - note the order that it
splits - I think this is easier than putting the
first half in A and second half in B *)
| ?- split([1, 2, 3, 4, 5, 6, 7, 8], A, B).
A = [1,3,5,7],
B = [2,4,6,8]
| ?- split([1, 2, 3, 4, 5, 6, 7], A, B).
A = [1,3,5,7],
B = [2,4,6]
| ?- split(A, [1, 2, 3], [4, 5]).
A = [1,4,2,5,3] ;
no
| ?- split(A, B, [1, 2]).
A = [_9355,1,_9361,2],
B = [_9355,_9361] ;
A = [_9355,1,_9361,2,_9367],
B = [_9355,_9361,_9367] ;
no
script done on Tue Apr 29 11:46:07 1997