This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get help from the TAs or the instructor. You are encouraged to use the LMS Discussions page to post problems so that other students can also answer/see the answers.

Constraint Solving and Natural Language Processing with Prolog

Part 1. Puzzle Solving.

In the image presented above, there are nine circles. Each circle must be assigned a number between 1-9 exactly once. Find the satisfying assignment of numbers such that the sum of the numbers across each side and the horizontal is 17. For example, the sum of the numbers filled in circles a, b, and d must add up to 17. Likewise, the sum of the numbers filled in circles d, e, and f must add up to 17.

Your final solution should have a one argument predicate called puzzle. The predicate's argument should represent the number assignments for each slot in the puzzle. The ordering of the list should be [A,B,C,D,E,F,G,H,I], where the letters represent the slots in the above image.

By entering the following Prolog query, your program should return a valid solution to the puzzle:

?- puzzle(Solution).
Solution=[...]

Hitting semicolon should return alternate solutions.

Your code should be placed in a file called puzzle.pl.

Part 2. Sentence Parsing.

Here, you will create a grammar the accepts a set of sentences. You will then use this grammar to output a parse tree for a given input.

Below is the set of sentences that your grammar must be able to accept.

• the train flew.
• a bike flew.
• a flight left.
• a train arrived.
• every train left.
• the bike stayed.
• a train stayed.
• the flight flew.
• a flight stayed.
• the train arrived.
• every train flew.
• a person arrived.
• every bike stayed.
• a flight flew.
• a bike left.
• the person stayed.
• the person left.
• every bike left.
• a bike stayed.
• a train left.
• every bike flew.
• every person arrived.
• the flight arrived.
• a person left.
• the person flew.
• the bike left.
• every train arrived.
• a train flew.
• a flight arrived.
• every flight stayed.
• every person left.
• the bike arrived.
• every bike arrived.
• the person arrived.
• every flight arrived.
• the train left.
• the bike flew.
• the flight left.
• a person stayed.
• a person flew.
• every flight left.
• a bike arrived.
• every person flew.
• every train stayed.
• the flight stayed.
• every person stayed.
• the train stayed.
• every flight flew.

You will create a predicate called loop to allow the user to continuously input sentences and receive the resulting parse tree.

Example:

?- loop.
|: a train flew.
s(np(det(a),nom(noun(train))),vp(verb(flew)))
|: every train arrived.
s(np(det(every),nom(noun(train))),vp(verb(arrived)))

To assist you with this part, we have provided you with the read_line predicate, which can be found in read_line.pl.

UPDATE 2/5/2015: To provide further assistance with Part 2 and Part 3, we have provided sample code, which can be found in parse_example.pl. This example program will show you how to load code from a separate file and how to use DCG syntax to accept a grammar and generate a simple parse tree.

The parse tree generated by your program must use the following predicates:

• s/2 - represents overall sentence; expects np and vp
• np/2 - represents noun phrase; expects det and nom
• vp/1 - represents verb phrase; expects verb
• det/1 - represents determiner; expects a word
• nom/1 - represents nominal; expects noun
• noun/1 - expects a word
• verb/1 - expects a word

Your code should be placed in a file called parse.pl.

Extra Credit (Up to 10% bonus)

Given an input parse tree, output the sentence formed from the tree.

Part 3. Simple DB.

For this part, you will be extending your grammar from Part 2 to simulate a simple database. You will write a loop predicate that will continuously prompt the user to enter a command or query. The program should output a 'yes' or 'no' in response to entering a query.

Commands to the database must take the following forms:

the <noun> _ <verb>.
the <noun> _ did not <pres_verb>.

<noun> is one of the nouns from Part 2.

<verb> is one of the verbs from Part 2.

<pres_verb> is either leave,fly, arrive, or stay.

_ is any word.

Example:

the person jane left.
the person jack did not leave.

did a <noun> <pres_verb>?
did every <noun> <pres_verb>?

Example:

did a train arrive?
did every bike stay?

Example:

?- loop.
|: the person john left.
|: the person jane left.
|: did a person leave?
yes
|: did every person leave?
yes
|: the person jake did not leave.
|: did a person leave?
yes
|: did every person leave?
no
|: did a train arrive?
no
|: did every train arrive?
yes

Your code should be placed in a file called db.pl.

Extra Credit (Up to 15% bonus)

Due Date:
 

Received Time	Grade Modification
before Tuesday, 02/17, 6:00PM	+10%
before Wednesday, 02/18, 6:00PM	no modification (on time)
before Thursday 02/19, 6:00PM	-10%
before Saturday, 02/21, 6:00PM	-25%
after Saturday, 02/21, 6:01PM	not accepted

Grading: The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor (comment, comment, comment!).  See the professor or TAs, if you have ideas for other extensions for this assignment and would like extra credit for implementing them.

Submission Requirements: Please submit a ZIP file with your code, including a README file. In the README file, place the names of each group member (up to two). Your README file should also have a list of specific features / bugs in your solution. Your ZIP file should be named with your LMS user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair via LMS.