Q$2.(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 $nn$ grid, and must place the numbers $1,$dots.,$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.

Let's formulate this puzzle as CSP$.$ We will use $4^2$ variables, one for each cell, with $x_{ij}$ as the variable for the cell in the $i$ th row and $j$ th column. The only unary constraints will be those assigning the known initial values to their respective squares $($e$.$g$.x_{34}=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 constraints $($such as alldiff$).$

b$.$ After enforcing unary constraints, consider the binary constraints relating $x_{14}$ and $x_{24}.$ Enforce arc consistency on just these constraints and state the resulting domains for the two variables.

c$.$ Suppose we enforced unary constraints and ran arc 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 arc 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 $x_{32}=1,$ despite not having found an assignment to any of the other cells in that column. Would running arc consistency find this requirement? Explain why or why not.

f$.$ Provide a solution to this puzzle by assigning values to the variables.

Answer:

$($Need Particular help with c$-$f$)$