CSE 341, Prolog Assignment

This assignment is due Thursday, May 8, at the start of section. You are to do this assignment individually .

  1. Write a prolog program for coloring a map of the United States.
  2. Implement the mergesort algorithm in prolog.

Details:

Problem 1, Map coloring.

The map coloring problem is to assign colors to regions, while using as few colors as possible. It is known that any planar map can be colored with four colors, and that certain maps (such as a map of the US), cannot be colored with three colors.

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

Problem 2. Merge Sort

Write a prolog program to sort two lists using the merge sort algorithm. Your algorithm should be "efficient".

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