On the density of solutions in equilibrium points for the queens problem
Paul H. Morris · National Conference on Artificial Intelligence · 1992
There has been recent interest in applying hillclimbing or iterative improvement methods to constraint satisfaction problems. An important issue for such methods is the likelihood of encountering a non-solution equilibrium (locally optimal) point. We present analytic techniques for determining the relative densities of solutions and equilibrium points with respect to these algorithms. The analysis explains empirically observed data for the n-queens problem, and provides insight into the potential effectiveness of these methods for other problems.