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.

To the right is an instance of this problem for size n = 4. Some of the squares have known values.

Let’s formulate this puzzle as a CSP. We will use 4² variables, one for each cell, with X_ij 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. X₃₄ = 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₁₄ and X₂₄. 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? 

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₃₂ = 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.

Transcribed Image Text:

1,1 ㅁ 2,1 3,1 4,1 1,2 2,2 V 다. 3,2 < 4,2 1,3 ㅅ 2,3 3,3 4,3 2 1.4 더 2,4 3,4 3 4