On the Density of Solutions in Equilibrium Points for the Queens Problem

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Constraint Satisfaction

There has been recent, interest in applying hill-climbing 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.