Programming Assignment 2

Assigned: Feb. 9
Due: Mar. 9

Overview

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.

Specifications

Input / Output.

All three programs take their input from standard input and produce their output in standard output.

Davis-Putnam

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
-2 3
-3
0
This is a simple example with 3 clauses and 3 atoms.






Davis-Putnam will generate the output
1 T
2 F
3 F
0
This is a simple example with 3 clauses and 3 atoms.
This corresponds to the clauses
P or Q or R.
not Q or R.
not 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 clauses.

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).

Another example: Suppose S is the set of clauses

not P or Q or R
P or not Q
not Q or not R
not P or not Q
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.

Front end

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.
RED BLUE YELLOW
MAINE VERMONT NEW-HAMPSHIRE MASSACHUSETTS
RHODE-ISLAND CONNECTICUT NEW-YORK *
MAINE NEW-HAMPSHIRE
NEW-HAMPSHIRE VERMONT
NEW-HAMPSHIRE MASSACHUSETTS
VERMONT MASSACHUSETTS
VERMONT NEW-YORK
MASSACHUSETTS NEW-YORK
MASSACHUSETTS RHODE-ISLAND
MASSACHUSETTS CONNECTICUT
RHODE-ISLAND CONNECTICUT
CONNECTICUT NEW-YORK
The output consists of Click below for the files illustrating the steps in one possible solution of the problem:

You may assume that there are no more than 10 colors and 100 countries.

Back-end

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
MAINE RED
VERMONT RED
NEW-HAMPSHIRE BLUE
MASSACHUSETTS YELLOW
RHODE-ISLAND BLUE
CONNECTICUT RED
NEW-YORK BLUE
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.

Deliverable

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.

Grading

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 well commented.