Yes it is arc consistent, as there are vowels in the 1st, 3rd and 5th positions in the words.

fever can be removed from W as there is no vowel in the 1st, 3rd or 5th position of the word fever.

See 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 for a representation in the applet of the arc consistent network.

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

Let's first eliminate 1a: We get the constraint on <1d, 2d> with the elements {<haste, eta>, <sound, one>, <think, her>}.

Eliminate 3a, gives the relation on <1d, 2d> with elements: {<haste, eta>, <sound, one>, <think, her>}. These combine to the same relation on <1d, 2d>.

We can now eliminate 2d, which creates a relation on <1d, 4a> with domain {<haste, usage>, <sound, fuels>, <think, first>}. 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: {<easy, usage>, <else, usage>, <desk, fuels>}.

If we eliminate 5d, we create a relation on <6a, 4a> with domain: {<desk, fuels>, <easy, fuels>, <else, fuels>, <kind, first>}.

These last two can be combined giving their intersection: {<desk, fuels>, <kind, first>}.

This is then only relation left and there are two solutions on <6a, 4a>. Each of these gives rise to a unique solution.

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.

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

• Initial constraint graph:
• Arc consistent graph:

You can try to split the domain of D. There are two cases, D = 2 and D = 3.