  Relation between problem hardness and solution space structure is an
important research aspect. Model d-k-CSP generates very hard instances when
$r=1$ and $r$ is near 1, where $r$ represents normalized constraint density. We
find that when $r$ is below and close to 1, the solution space contains many
widely distributed well-separated small cluster-regions (a cluster-region is a
union of some clusters), which should the reason that the generated instances
are hard to solve.
