Conclusions
The cause of the paradoxical phenomenon (problems with fewer solutions are easier than problems with more solutions for hill-climbing algorithms) was clarified:
- the number of local-minima decreases.
- basins are divided into smaller regions.
Similar results are obtained for graph-coloring problems.