

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

when looking at the H(n,d,4.0) case. Here almost all instances in the phase-transition region and many instances in the mostly insoluble region are path-consistent, though only a few of them are consistent.

For the following evaluation of the different heuristics we will randomly generate instances with an average degree between d = 2 and d = 18 in the A( n, d, 4.0) case and between d = 4 and d = 20 in the H ( n, d, 4.0) case. This covers a large area around the phase-transition. We expect the instances in the phase-transition region of H ( n, d, 4.0) to be particularly hard which makes them very interesting for comparing the quality of the different heuristics.

## 6. Empirical Evaluation Of The Heuristics

In this section we compare the different heuristics by running them on the same randomly generated instances. For the instances of A(n,d,4.0) we ran all 20 different heuristics