Assignment 2 Solution

This assignment includes both conceptual and code questions. It must be completed individually. You may not collaborate with other students, share code, or exchange partial answers. Questions involving answers or code must be emailed to the instructor or TAs directly or discussed during o ce hours. Your answers to the conceptual questions must be uploaded to Moodle as a pdf le titled \Assign2 UnityID.pdf". Your sourcecode must be submitted as a self-contained zip. All code must be clear, readable, and well-commented. Note: The code will be tested on the NCSU VCL system(\CSC520 VCL"). You are advised to test your code there before submission.


Question 1 (10 pts)

Use the lexicon:

n { A student can log in the Mypack website.

r { A student can go inside Hunt Library .

i { A student has an NCSU ID card with him/her.

g { The students will get a NCSU ID card

q { The NCSU student.

oc { A student who lives on campus.

ic { A student who lives o    campus

ad { A student can go inside dorms

p { Peter is a student .

For all the students of NCSU, they get a NCSU Student ID card. All the students from NCSU can log in the Mypack website.

NCSU Students can go inside Hunt Library only if they have am NCSU ID card with them.

All of the NCSU students live on or o  campus.

The students who live on campus can enter dorms only if they take their NCSU ID cards with them, while others who live o campus cannot.

Peter is an NCSU student.

Peter lives on campus. But he cannot go inside the dorms and Hunt Library as he has lost his card.

Peter cannot log in the Mypack website.

    a. (5 pts) Use propositional logic to determine if the speci cation is consistent. If the sentences are not consistent, use resolution to derive a contradiction. If they are consistent, use the truth-table method to show at least one model.

1
b. (5 pts) What if anything changes if Peter can log in the Mypack website? Be speci c in showing what’s di erent.


Question 2 (50 pts)

You have been given three text les that describe binary constraint problems. The rst line of each le is VARS following that line is a list of variable names followed by their respective values. Variable names are represented by sequences of characters and are separated from values by a : Values are represented by integers. The list will end with a single line stating ENDVARS. Following the variable declarations there will be a set of constraints starting with the line CONSTRAINTS and ending with the line ENDCONSTRAINTS Constraints are represented line by line using pre x notation. The rst symbols in each line represents the constraint function which must hold over the arguments. Following the constraint symbol there will be a sequence of variable names or values separated by whitespace. The constraints apply to all of the variables listed. NOTE: Apart from != and = most will be binary constraints.

!= Not equal or Alldi = equal or Allmatch < value less than.

> value greater than. <1 value one less than.
>1 value one greater than.

<>1 value one less or one greater than. The problems are described brie y here:

Map Coloring: You have been given two maps. One Map v.txt which represents a partial map of southeastern states of USA consists of Alabama, Mississippi, Georgia, Tennessee, Florida. The variables are initials of each state A, M, G, T, F. Neighboring states should have di erent colors and speci ed in the constraint le. Allowable colors are numbered as f1; 2; 3g Initially all states have the domain of f1; 2; 3g The other of which represents the contiguous 48 US states and expands the range of values to 5.

Sudoku: A Sudoku puzzle has 81 variables, one for each square. The variable names follow the convention of textbook Figure 6.4. Rows are numbered from A1 through A9 for the top row (left to right), down to I1 through I9 for the bottom row. The empty squares have the domain f1; 2; 3; 4; 5; 6; 7; 8; 9g and the pre lled squares have a domain consisting of a single value. In addition, there are 27 di erent constraints de ned in the constraint le.

Class Assignment: You have to assign classes for N subjects, S1; S2; ; SN to k Professors. A Professor can teach one or multiple classes. The domain of the variable Si, i 2 f1; Ng speci es the Professors who can teach the subject Si. The constraint are speci ed in Si 6= Sj format, indicating that these two courses have overlapping time slots and Professors.

Zebras: As described in class you have ve houses with an owner, a pet, a drink, a cigarette, and a color of each. We will do assignment over each house.


2
Your task in this assignment is to implement two solver algorithms for the constraint problems: BACKTRACKING, and MIN-CONFLICTS as described in the lecture and textbook. Both algo-rithms should be implemented as part of a single package that takes as input a problem le and an argument specifying the algorithm to use and as output returns a le specifying a complete and satisfactory assignment of values to the variables or a nal assignment with con icts noted if no solution is found. You should use a max steps parameter of 20. When run with MIN-CONFLICTS your code must print out the number of steps taken to nd the assignment. When run with back-tracking search your code must print out the number of backtrack steps taken. As always your code must be clear, readable and well documented. For this assignment you are permitted to use third party libraries for graph data structures as necessary. In your report you should compare and contrast your algorithms and problems. Which approach worked better for each of the problems and how could they be improved.





















































3