Homework answers / question archive / Assignment 1 Write a lisp program to colour a map of m countries with a minimum number of colours, such that no two adjacent countries have the same colour

Assignment 1 Write a lisp program to colour a map of m countries with a minimum number of colours, such that no two adjacent countries have the same colour

Computer Science

Share With

---

Assignment 1

Write a lisp program to colour a map of m countries with a minimum number of colours, such that no two adjacent countries have the same colour.

For convenience, let the input to the program be

(1) A representation of the map as a list of lists each of whose car is the name of a country with the cdr containing all the countries adjacent to this country.

For example,

((A B C F)

 (B A C D E F)

 (C A B F D)

 (D B C F E)

 (E B D F)

 (F B E D C A))

 Is input to represent a map of six countries A, B,...,F.

(2) A list of colours available for use.  For example,

 (W G Y R)

The program can output either

(a) A valid colouring of the map using the minimum of colours as a list of two element lists :

((country colour)

 (country colour)

 .....)

OR

(b) NIL in case there is no solution.

For the above example, one valid output is

((A Y)

 (B R)

 (C G)

 (D Y)

 (E G)

 (F W))

The search strategy and evaluation function can be formulated by you.  Different search strategies can be tried out.