Constraint satisfaction problems: simple Sudoku This problem asks you to solve a simplified version of a Sudoku puzzle. The board is a 4-by-4 square, and each box can have a number from 1 through 4. One number can only appear once in each row and column. Furthermore, in each group of 2-by-2 boxes outlined with a solid border, each of the 4 numbers may only appear once as well. For example, in the boxes a, b, e, and f, each of the numbers 1 through 4 may only appear once. Note that the diagonals do not necessarily need to have each of the numbers 1 through 4. Notice that the board already has some boxes filled out: Box b = 4, c = 2, g = 3,1 = 2, and o= 1. а b 4 с 2 d
e f g 3 h
i j k l 2
m n 0 1 p
We represent this simple Sudoku puzzle as a CSP with the following constraints:
1. Each box can only take on values 1, 2, 3, or 4.
2. 1, 2, 3, and 4 may only appear once in each row.
3. 1, 2, 3, and 4 may only appear once in each column.
4. 1, 2, 3, and 4 may only appear once in each set of 2-by-2 boxes with solid borders.
5. b = 4, c = 2, g = 3,1=2, and o = 1.
1. Write down the math representation for the constraint "value 1 must and must only appear once in the first row". You may use the variables a, b, c,...,p and logical connectors (1, V, -, etc) to represent the constraint. To give some hints, the constraint "value 1 must appear in the first row" can be represented as "a = 1Vd=1".
2. Write down the math representation for the constraint "value 3 must and must only appear once in the first column". You may use the variables a, b, c, ... ,p and logical connectors (^, V, 7, etc) to represent the constraint.
3. Write down the math representation for the constraint "value 2 must and must only appear once in the first group of 2-by-2 boxes". You may use the variables a, b, c, ... ,p and logical connectors (A, V, -, etc) to represent the constraint.
4. Consider a naive backtracking algorithm using only forward checking. Assume that the backtracking algorithm solves the board from left to right, top to bottom, and enforces all unary constraints along the way (e. g., b is assigned to 4 already, etc). In the first step, 3 is assigned to box a. Using forward checking, what are the boxes whose domains will be affected by the assignment of box a? (In this problem, d, e, f,...,p are the variables represent the values assigned to boxes. You do not need to include the boxes whose values are already fixed in the answer.)
5. Following the last question, what are the possible value assignments of each affected box?