====== Solutions to the CSP lab ======
===== 4.2 =====
==== (a) ====
Yes it is arc consistent, as there are vowels in the 1st, 3rd and 5th positions in the words.
==== (b) ====
//fever// can be removed from W as there is no vowel in the 1st, 3rd or 5th position of the word //fever//.
===== 4.3 =====
==== (a) ====
See [[https://www.cs.ubc.ca/~poole/aibook/figures/ch04/cross2cn.xml|https://www.cs.ubc.ca/~poole/aibook/figures/ch04/cross2cn.xml]] for a representation in the applet.
See [[https://www.cs.ubc.ca/~poole/aibook/figures/ch04/cross2ac.xml|https://www.cs.ubc.ca/~poole/aibook/figures/ch04/cross2ac.xml]] for a representation in the applet of the arc consistent network.
==== (b) ====
Number the squares on the intersections of words s1-s9 (s1 is the square with a 1 in it, s2 has a 2 in it and s8 has a 6 in it). The arc consistent form has:
s1: h,s,t
s2: e,h,o
s3: a,h,o
s4: e,n,t
s5: i,s,u
s6: a,e,r
s7: g,l,s
s8: d,e,k
s9: n,s,v
==== (c) ====
Let's first eliminate 1a: We get the constraint on //<1d, 2d>// with the elements {//, , //}.
Eliminate 3a, gives the relation on //<1d, 2d>// with elements: {//, , //}. These combine to the same relation on //<1d, 2d>//.
We can now eliminate 2d, which creates a relation on //<1d, 4a>// with domain {//, , //}. Again this provides no more constraints than the previous relation on //<1d, 4a>//.
We can now eliminate 1d and create a relation on //<6a, 4a>// with domain: {//, , //}.
If we eliminate 5d, we create a relation on //<6a, 4a>// with domain: {//, , , //}.
These last two can be combined giving their intersection: {//, //}.
This is then only relation left and there are two solutions on //<6a, 4a>//. Each of these gives rise to a unique solution.
==== (d) ====
If you eliminate 1d (or 4a) first, you create a relation on 3 variables which is much more complicated and less efficient. So that elimination ordering does affect efficiency.
===== 4.5 =====
==== (a) ====
There is a solution tree based on the variable ordering //C, D, A, B, E// at [[https://www.cs.ubc.ca/~poole/aibook/figures/ch04/schedSearchTree.txt|https://www.cs.ubc.ca/~poole/aibook/figures/ch04/schedSearchTree.txt]]
==== (b) ====
* Initial constraint graph: {{:teaching:is:csp-lab-solution-graph-before.png?400|initial constraint graph}}
* Arc consistent graph: {{:teaching:is:csp-lab-solution-graph-after.png?400|arc consistent graph}}
==== (c) ====
You can try to split the domain of D. There are two cases, D = 2 and D = 3.