Programming Assignment 2
Assigned: Feb. 9
Due: Mar. 9
The "map-coloring problem" is the problem of coloring a map with K colors
in such a way that no two neighboring countries have the same color.
In this assignment, you are to implement the Davis-Putnam procedure
and use it to solve the map-coloring problem.
Specifically: You will write three programs.
- 1. An implementation of the Davis-Putnam procedure, which takes
as input a set of clauses and outputs either a satisfying valuation,
or a statement that the clauses cannot be satisfied.
- 2. A front end, which takes as input a map to be colored and
a set of colors and outputs a set of clauses that can be input to (1).
- 3. A back end, which takes as input the output of the (1) and
translates it into a coloring of the map.
Input / Output.
All three programs take their input from standard input and
produce their output in standard output.
The input to the Davis-Putnam procedure has the following form:
An atom is denoted by a natural number: 1,2,3 ... The literal P
is the same number as atom P; the literal not P is the negative.
A clause is a line of text containing the integers of the corresponding
literals. After all the clauses have been given, the next line is the
single value 0; anything further in the file is ignored in the
execution of the procedure and reproduced at the end of the output file.
(This is the mechanism we will use to allow the front end to communicate
to the back end.)
The output from the Davis-Putnam procedure has the following form:
First, a list of pairs of atom (a natural number) and truth value
(either T or F). Second, a line containing the single value 0. Third,
the back matter from the input file, reproduced.
Example: Given the input
1 2 3
This is a simple example with 3 clauses and 3 atoms.
Davis-Putnam will generate the output
This corresponds to the clauses
This is a simple example with 3 clauses and 3 atoms.
P or Q or R.
not Q or R.
If the clauses have no solution, then Davis-Putnam outputs a single
line containing a 0, followed by the back-matter in the input file.
Note: Your implementation of Davis-Putnam must work on _any_ set of clauses,
not just those that are generated by the map coloring program
You may assume that there are no more than 1000 atoms and no more than 10,000
Your implementation of Davis-Putnam should include the following
two heuristics for dealing with branch-points (that is, points where
the algorithm has to "guess" a variable assignment)
For example, in the example in the class notes, in the set of clauses
S1, variables Q, R and U appear in 4 clauses; P appears in 3 clauses;
and X appears in two clauses. Therefore, you should choose either Q, R,
or U to assign to. Suppose you choose Q. Q appears twice positively,
and twice negatively, so the order of truth assignments doesn't matter
(you can do TRUE then FALSE, or FALSE then TRUE).
- Choose the atom A which appears in the greatest number of clauses.
(Ties can be resolved arbitrarily.)
- If atom A appears more often in negative form than in positive form,
then try first assigning it FALSE, then TRUE. Otherwise, try first
TRUE and then FALSE.
Another example: Suppose S is the set of clauses
not P or Q or R
Q appears in 4 clauses whereas P and R appear in 3 each, so choose P to
assign to. Q appears 3 times negatively and only once positively, so
try the assignment Q=FALSE before Q=TRUE.
P or not Q
not Q or not R
not P or not Q
The front end takes as input a representation of a map and generates as
output a set of clauses to be satisfied.
The format of the input contains the following elements:
Thus, the problem of coloring the map of New England + New York in three
colors is expressed in the following input file.
- A list of the colors, in a single line. A color is a character string
of up to 20 characters. The colors are separated by white space.
- A list of
the names of the countries. These are character strings of up to 20
characters, separated by white space. The list of countries is terminated
by an asterisk.
- A list of pairs of countries that border one another.
There is one pair per line.
RED BLUE YELLOW
The output consists of
MAINE VERMONT NEW-HAMPSHIRE MASSACHUSETTS
RHODE-ISLAND CONNECTICUT NEW-YORK *
Click below for the files illustrating the steps in one possible solution
of the problem:
- 1. A set of clauses suitable for inputting to Davis-Putnam.
The clauses that you need for this problem are
Note that you can directly output the constraints in
clausal form (CNF) and therefore you do not have to implement
a program to translate arbitrary Boolean formulas to CNF.
- A. For each country, a clause saying that the country has one of the
- B. For each country, and for each pair of colors, a clause saying that
the country does not have both colors. (I.e. each country has a unique color).
- C. For each pair of countries A,B that border one another and for each
color X, a clause stating that A and B are not both colored X.
- 2. A key for translating the numbers used for propositional atoms in
the clauses into pairs of countries and colors. This is to allow the
front end to communicate to the back end. The format of this is up to you.
My suggestion would be a sequence of lines of the form "number, country,
You may assume that there are no more than 10 colors and 100 countries.
The back end takes as input the output that Davis-Putnam generates when run
on the output of the front end. It generates as output a coloring of
the map. The format is pairs of the form "country color", one pair per line.
For example, one possible output for the above example would be
If the input indicates that the clauses have no solution, the back end
should output the message "NO COLORING POSSIBLE".
Another example for Davis-Putnam
The following is the input-output pair just for the Davis-Putnam module ---
not the map-coloring modules --- corresponding to the example
in the class notes.
You should email to the TA.
(a) the source code; (b) instructions for running it,
if there's anything at all non-obvious about it. Nothing else.
The Davis-Putnam program is worth 60% of the grade; the front end is worth
30%; the back end is worth 10%. In each of these, a program that does
not compile will get a maximum of 10%; a correct program
will get 90%; the remaining 10% is for being well-written and