Overview

There is a famous proven conjecture in graph theory that any map divided into countries can be colored with 4 colors such that no two adjacent countries have the same color. We'll call this the "no same colors share a border" rule. We are going to write a Prolog program that produces all such colorings for the countries of the European Union, using red, yellow, blue, and green.

Generate and Test

A standard paradigm for Prolog programs is called generate and test. This means that we write a Prolog program (i.e., a set of rules) that searches a space of possible solutions, generates a candidate solution and then tests that this candidate has the right properties to be an acceptable solution of our problem. The backtracking execution of Prolog allows us to do this in a very simple, but not always efficient, fashion. For example, say we want to calculate all pairs of distinct numbers that we can form from the numbers {1 2 2 3}. First, we might generate all pairs as candidate solutions: (1,2) (1,3) (2,2) (2,3) and then test if each of these is a pair of distinct numbers. Only (1,2) (1,3) and (2,3) pass our test; these are the three acceptable solutions. This is an inefficient way of doing the job, as it would have been better to have seen at pair generation time that (2,2) is not a valid pair and thus to have avoided generating it. For problems with a large candidate solution space relative to the acceptable solution space, this inefficiency can make the Prolog program take much more time than is necessary to solve the problem. In Prolog, usually it is very easy to code the naive generation solution procedure; with some effort we can get the better solution procedure as well.

A substantial example of using (naive) generate and test can be found in N queens program. This program places N queens on an N by N chessboard, so that no queen can attack any other queen. Our solution solves this problem for 4 queens on an 4 by 4 chess board. Try running this program with the query: queens(X). and observe the solutions generated.

Assignment Definition

This assignment has two parts. In the first part, you will run the code we give you in naive_color.pl and euadjacent.pl which uses the naive generate and test approach described above to color the countries of the European Union (i.e., EU) whose adjacencies are given as facts in euadjacent.pl. For example,

 adj(fr,sp). 

A coloring is a list of country/color pairs. For example, the Prolog list [(fr,red),(sp,blue)] stands for the coloring where France is red and Spain is blue. The Prolog clauses in our files naive_coloring.pl and euadjacent.pl use the naive approach of generating a coloring for an entire list of countries and then checking that this coloring is valid for all adjacencies. The rule is that no two adjacent countries can have the same color; that is, the list [(fr,red),(sp,red)] is an illegal coloring.

In the second part, you will write a smart coloring predicate, which prevents colorings from being generated which violate the "no same colors share a border" rule, and thus incorporates the test as part of the candidate solution generation. You can use any predicates from the N queens program (mentioned above) that you think may be useful, (e.g., not).

Specifics

• Do the following experiments with predicate coloring(CTRY,COL), in file naive_coloring.pl. Create a file called readme to contain the answers to these questions. Be sure to include your NAME and STUDENT NUMBER in the text in this file.
  • Execute the query coloring([sp,po],C). and always respond with a ";" in order to generate all the possible colorings. Answer the following questions about this execution:
    • How does this program form the possible colorings of Spain and Portugal? Essentially, what is the algorithm used by this Prolog program?
    • Why are the same colorings returned a multiple number of times?
    • What if Luxembourg and the Netherlands were the countries on the list input to coloring (that is, what if we called coloring([ne,lu],C).? How many duplicate solutions would be generated?
  • The predicate coloring is invertible if it also has the following functionality: given a coloring COL that could be a valid coloring, it produces the corresponding list of countries CTRY whose coloring it might be. Explain whether or not this predicate is invertible and show examples.
  • Finally, perform the following experiment to test the coloring predicate with subsets of the EU countries, in order to observe the exponential nature of the algorithm. Form a list of length k of the countries in the order in which they appear as the first term in the adj facts in file euadjacent.pl. For example, for k=1, [po]; for k=2, [po,sp]; for k=3, [po,sp,fr]. (Make sure you don't include duplicates in your list. Why not?)
    • Then test the coloring predicate using each of these lists as its first argument and a variable as its second argument (to obtain a coloring for that list of countries) until the time to obtain the first answer for a list exceeds 1 minute, using elapsed time as measured by your watch. What is that list?
    • Once the Prolog program obtains an answer, can you explain why obtaining the next answer does not take so long?
    • *****DELETE THIS PARAGRAPH
      Run the coloring predicate on all the list containing all the countries. How long does it take to obtain an answer? ****END OF DELETE
      
• Write a smart coloring predicate to create country colorings for lists of EU countries. This predicate will check for the colors that are already used by neighbors of a country, before picking a color for that country. Call this predicate smart_coloring(CTRY, COL). (Note: you can define any helper predicates that you may need as well.)
  • Test your predicate on a pair of adjacent EU countries. Record in your readme file the countries you use in your test. Does it generate as many duplicates as coloring did? Why or why not?
  • Now try your predicate with all 15 EU countries in the input list. Can you obtain an answer more quickly than with coloring? Why or why not?

  To Hand In

  You will hand in two files: readme and proj4.pl. All of your predicates (i.e., helpers too, if any were defined) should be included in the Prolog file. Note, you do NOT need to include the rules from euadjacent.pl in proj4.pl, but your file proj4.pl must be executable when we input it to Prolog with our copy of euadjacent.pl. Both readme and proj4.pl files will be submitted electronically using the handin program.

  Your solution will be graded on correctness and appropriate use of Prolog.

  last updated 10:00pm, December 3, 2002 by BGR