Homework 1: CSG 270 Due: Jan. 17, 2007 ==================================================== In the course project we will build a tool similar to the CSP Solver in CISpace: http://www.cs.ubc.ca/labs/lci/CIspace/Version4/Constraint/ http://www.cs.ubc.ca/labs/lci/CIspace/Version4/Constraint/help/tutorial1.html The homeworks prepare you for the project. Part 1: Verifier =================================================================== Write a program that solves: Input: A Boolean CSP instance F using any of the 256 relations of rank 3. An assignment I of 0 or 1 to all the variables of F. Output: Does I satisfy F? In other words, is F(I) true or false? This verifier will be very useful to verify the outputs of your CSP solver. Suggested method to be used: Use Relation class in materials/relation. The method: static public int reduce(int relationNumber,int variableNumber,int value) takes as first argument a relation number between 0 and 255. The second argument is a variable position between 0 and 2 and the third argument is 0 or 1, the value of the variable. Keep reducing the relations and if we get unsat (R0) at any stage then the assignment is not satisfying. What you learn: Should you reuse or build? Understanding CSP. Good opportunity to learn schema-binding method What to turn in: Your program with 3 test cases and outputs. Part 2: Testing, Modeling ========================================================================= Model 4x4 Sudoku as a Boolean CSP problem using only relations of rank 3: Example: 1 2 | 3 4 3 4 | 2 1 --------- 2 1 | 4 3 4 3 | 1 2 The rules are: In each row, column and region each number appears exactly once. Suggestion: There are 16 variables with domain 1..4 which translates to 32 Boolean variables. Write all constraints for one row. It will be similar for the other rows, columns and regions. What you learn: How to think outside the box. Really understanding Boolean CSP. Translation between leanguages. Language design. What to turn in: The CSP instance (for the first row only): 1 | 3 4 | 1 --------- 2 | 4 3 | 2 given in the input language for Part 1.