Programming Assignment 2

Due: Oct. 26

Overview

In this assignment, you are to implement the Davis-Putnam algorithm and use it to solve a simple form of an adventure game.

The puzzle is as follows: You are given (1) a maze with treasures at particular nodes; (2) a list of treasures to get; (3) a maximum number of steps. The object is to find a path through the maze that collects all these treasures in at most the given number of steps.

Example: Suppose that the maze is as follows:

If the task is "GOLD, RUBY" in 2 steps, then a solution is "START, C, F". If the task is "GOLD, WAND, RUBY" in 4 steps, then a solution is "START,C,D,C,F". If the task is "GOLD,RING" in two steps, then there is no solution.

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 maze problem and outputs a set of clauses that can be input to (1).
  3. A back end, which takes as input the output of (1) and translates it into a solution to the original problem.

Compiling the maze puzzle to propositional logic

The MAZE puzzle can be expressed propositionally as follows: There are two kinds of atoms: There are 8 kinds of propositions.
  1. The player is only at one place at a time. For any time I, for any two distinct nodes M and N, ~(AT_M_I ^ AT_N_I), or in CNF ~AT_M_I V ~AT_N_I.
    For example, ~AT_C_2 V ~AT_F_2.
  2. The player must move on edges. Suppose that node N is connected to M1 ... Mk. For any time I, if the player is at node N at time I, then the player either remains at N or moves to M1 or to M2 ... at time I+1.
    Thus AT_N_I => AT_N_(I+1) V AT_M1_(I+1) V ... V AT_Mk_(I+1);
    in CNF, ~AT_N_I V AT_N_(I+1) V AT_M1_(I+1) V ... V AT_Mk_(I+1).
    For example, ~AT_C_2 V AT_C_3 V AT_START_3 V AT_D_3 V AT_F_3
  3. Suppose that treasure T is at node N. If the player is on node N at time I, then the player has T at time I. AT_N_I => HAS_T_I, or in CNF ~AT_N_I V HAS_T_I.
    For instance, ~AT_F_3 V HAS_RUBY_3.
  4. If the player has treasure T at time I, then he has treasure T at time I+1, then he has treasure T at time I+1. HAS_T_I => HAS_T_(I+1), or in CNF, ~HAS_T_I V HAS_T_(I+1). For example, ~HAS_GOLD_3 V HAS_GOLD_4.
  5. Suppose that treasure T is located at nodes N1, N2 ... Nk. If the player does not have treasure T at time I-1, and does have treasure T at time I, then at time I he must be either at N1 or at N2 ... or at Nk.
    [~HAS_T_(I-1)] ^ HAS_T_(I+1)] => AT_N1_I V AT_N2_I V ... V AT_Nk_T
    In CNF, HAS_T_(I-1)] V ~HAS_T_(I+1) V AT_N1_I V AT_N2_I V ... V AT_Nk_T
    For example, HAS_GOLD_2 V ~HAS_GOLD_3 V AT_B_3 V AT_C_3.
  6. The player is at START at time 0. AT_START_0.
  7. If T is a treasure that is not at START, then the player does not have T at time 0. If the treasures not at START are T1 ... Tk then we have ~HAS_T1_0 ^ ~HAS_T2_0 ^ ... ^ ~HAS_Tk_0;
    In CNF this is the separate clauses:
    ~HAS_T1_0.
    ~HAS_T2_0.
    ...
    ~HAS_Tk_0.
    For instance, in the example problem we have
    ~HAS_GOLD_0.
    ~HAS_RUBY_0.
    ~HAS_WAND_0.
    ~HAS_RING_0.
  8. At the time limit, the player has all the required treasures. For instance, in the first problem above, we have
    HAS_GOLD_2.
    HAS_RUBY_2.

Specifications

Input / Output.

All three programs take their input from a text file produce their output to a text file. (If you want, you may use standard input and 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 ~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 V Q V R. 
~Q V R. 
~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 EXACT SET COVER program.

You may assume that there are no more than 1000 atoms and no more than 10,000 clauses.

Front end

The front end takes as input a specification of a maze and a problem and generates as output a set of clauses to be satisfied.

The format of the input contains the following elements:

Thus, the first problem above would be encoded in the following input:
START A B C D E F G H
GOLD WAND RUBY RING
2 GOLD RUBY
START NONE A C
A NONE START B D
B GOLD A D E
C GOLD START D F
D WAND A B C E
E GOLD B D G H
F RUBY C G
G NONE E F H
H RING E G
You may assume that the input is correctly formatted. You do not have to do any error checking on the input. The output consists of

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 the path that solves the problem. If the input indicates that the clauses have no solution, the back end should output the message "NO SOLUTION".

Another example for Davis-Putnam

The following is the input-output pair just for the Davis-Putnam module --- not the front and back ends --- corresponding to the example in the class notes.

A Simpler Maze Example

It would be a mistake to begin your testing using the above example, with its 39 propositional atoms and hundreds of propositions. Rather, I would suggest that you start by working on the following maze, with the problems, "Get the GOLD in 1"; "Get the GOLD and the WAND in 2" and "Get the GOLD and the RUBY in 3".

The clauses for the first of these is shown here

Obvious Optimizations for Front End

There are a couple of easy optimizations that can be made in the front end which eliminate a substantal number of the atoms. For instance, or one can eliminate all the treasures that are not to be collected and their associated atoms since they obviously don't make any difference to the solution. Or you can eliminate all the nodes that are not reachable from START in K steps (or, even better, eliminate all the atoms AT_N_I where node N is not reachable from START in I steps.) As we'll discuss in class, that is not an optimization that Davis-Putnam can find. Whether you want to implement these is up to you; it is quite likely that they will make the system run noticeably faster.

Deliverable

You should submit by email (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 35%; the back end is worth 5%. 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.