Go backward to Solution to part (c)
Go up to 7 Solving a CSP via backtracking, arc consistency, hillclimbing

## Solution to part (c)

Show how hill climbing can be used for the problem. Suppose a neighbor is obtained by increasing or decreasing the value of one of the variables by 1, the heuristic function to be maximized is the number of satisfied constraints, and you always choose a neighbor with the maximal heuristic value.
1. There are many variants. Here is one:
 A B C D E h 1 1 1 1 1 1 1 1 2 1 1 4 1 2 2 1 1 5 1 3 2 1 1 6 1 3 2 2 1 6 1 3 2 3 1 6 1 4 2 3 1 7
Here is another:
 A B C D E h 1 1 1 1 1 1 1 1 2 1 1 4 1 2 2 1 1 5 1 2 3 1 1 5 1 3 3 1 1 5 1 3 3 2 1 6 1 4 3 2 1 7
2. Again there are many variants:
 A B C D E h 3 3 2 1 4 4 4 3 2 1 4 5 4 4 2 1 4 5 4 3 2 1 4 5
This can meander for a long time, but it never gets out of the local minima. Here is another run:
 A B C D E h 3 3 2 1 4 4 3 3 2 1 3 5 3 4 2 1 3 5
Again we can't go anywhere except alternate between the last two assignments. This is a small plateau.
3. A better heuristic would be to notice that if we have a constraint X>Y that increasing X, even if it doesn't make it greater than Y is a useful move. Hence one heuristic is to count a the achievement of X>Y by 1, but a violation of X>Y by the value X-Y (which could be negative). This would allow us to avoid the second local minima we found. Another may be to count the inequality and the even/odd constraints as less important on the grounds that they it is often useful to violate them temporarily, and they are easy to achieve (by moving a value by one).

Computational Intelligence online material, ©David Poole, Alan Mackworth and Randy Goebel, 1999