Q2. (20 Points, 3 points a to e, 5 points for f) Futoshiki is a Sudoku-like Japanese logic puzzle that is very simple, but can be quite challenging. You are given

an n x n grid, and must place the numbers 1,...., n in the grid such that every row and column has exactly one of each. Additionally, the assignment must satisfy the inequalities placed between some adjacent squares. The inequalities apply only to the two adjacent squares, and do not directly constrain other squares in the row or column. Below is an instance of this problem, for size n = 4. Some of the squares have known values./n1.1 1.2 1,3 1,4 2.1 2.2 2,3 Λ Λ 2,4 3.1 3.2 3.3 3,4 4,1 4.2 Λ 2 3 Let's formulate this puzzle as a CSP. We will use 42 variables, one for each cell, with Xij as the variable for the cell in the ith row and jth column. The only unary constraints will be those assigning the known initial values to their respective squares (e.g. X34 = 3). a. Complete the formulation of the CSP. Describe the domains of the variables, the two unary constraints, and all binary constraints you think are necessary. You can describe the constraints using concise mathematical notation. Do not use general n-ary con- straints (such as alldiff). b. After enforcing unary constraints, consider the binary constraints relating X14 and X24- Enforce arc consistency on just these constraints and state the resulting domains for the two variables. c. Suppose we enforced unary constraints and ran are consistency on this CSP, pruning the domains of all variables as much as possible. After this, what is the maximum possible domain size for any variable? Hint: consider the least constrained variable(s); you should not have to run every step of arc consistency to answer this. d. Suppose we enforced unary constraints and ran are consistency on the initial CSP in the figure above. What is the maximum possible domain size for a variable adjacent to an inequality? e. By inspection of column 2, we find it is necessary that X32 = 1, despite not having found an assignment to any of the other cells in that column. Would running are con- sistency find this requirement? Explain why or why not. f. Provide a solution to this puzzle by assigning values to the variables. Answer: