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

Paul Morris

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.