(Solved): 3. Constraint Satisfaction I ( 20 points total) Consider a constraint satisfaction problem where th ...

3. Constraint Satisfaction I ( 20 points total) Consider a constraint satisfaction problem where there are four variables A, B, C, and D. $\mathrm{A},\mathrm{B}$, and $\mathrm{C}$ each have domain $\{1,2,3,4\}$, whereas $\mathrm{D}$ 's domain is $\{3\}$. There are three constraints: $\mathrm{A}=\mathrm{B},\mathrm{B}=\mathrm{C}$, and $\mathrm{C}>\mathrm{D}$. (a) Show how backtracking can be used to solve this problem. To select variables, use the most constrained variable heuristic, breaking ties using the most constraining variable heuristic. If ties still exist, break them alphabetically. To select values, use the least constraining value heuristic. Indicate the first 30 branches visited in the search tree (or stop when the solution is reached). Write them in text form with each branch on one line. (b) Show how forward checking can be used to solve this problem. To select variables, use the most constrained variable heuristic, breaking ties using the most constraining variable heuristic. If ties still exist, break them alphabetically. To select values, use the least constraining value heuristic. Indicate the first 30 branches visited in the search tree (or stop when the solution is reached). 4. Constraint Satisfaction II (10 points total) (a) Explain why it is a good heuristic for a constraint satisfaction search to choose the variable that is most constrained. (b) Explain why it is a good heuristic for a constraint satisfaction search to choose the value that is least constraining. 5. Problem Encoding ( 20 points total) Consider a clique on $\mathrm{N}$ nodes. (A clique is a graph with an edge between each pair of nodes.) To color the graph, one must assign a color from a given set of colors to each of the nodes in the graph such that any two nodes connected by an edge have different colors. Consider coloring the clique using a set of $\mathrm{N}-1$ colors. Give the CSP formulation of the problem. Use $N^2$ variables, where variable $x_{ik}$ is true if and only if node $\mathrm{i}$ is colored with color $\mathrm{k}$. Each clause (or set of clauses) you encode should be accompanied by an English description.