Abstract
In the early 1990s, empirical research demonstrated that local search algorithms could solve the $n$-queens problem for millions of queens in remarkably short timeframes. However, a theoretical explanation for this success remained elusive, particularly regarding why simple hill-climbing often failed while refined heuristics succeeded. This paper provides an analytic bridge between these empirical results and the mathematical landscape of the problem. By distinguishing between "tight" and "loose" constraints and analyzing the density of solutions within local optima (equilibrium points), the author proves that for large $n$, the search space becomes an "amphitheatre" where almost every 2-step local optimum is a global solution.
Introduction
The $n$-queens problem—placing $n$ queens on an $n \times n$ board such that no two queens attack each other—was long considered a benchmark for backtracking search. The discovery that simple local search techniques, such as the Min-Conflicts heuristic, could solve instances with $n > 1,000,000$ challenged the prevailing understanding of the problem's complexity. Despite this empirical success, there was a significant gap in the theory: simple hill-climbing (SHC) frequently became trapped in local optima, while algorithms that allowed "sideways" moves or used specific preprocessing succeeded with near-certainty. This paper sets out to provide the mathematical "why" behind this phenomenon.
Theoretical Framework: Tight vs. Loose Constraints
The core of the paper's analysis lies in the distinction between different types of constraints within the $n$-queens problem:
- Tight Constraints: These are constraints where the number of available slots is equal to the number of items to be placed. In $n$-queens, the column constraints are "tight" because there are exactly $n$ columns for $n$ queens. Violating one column constraint almost inevitably leads to the violation of another.
- Loose Constraints: These are constraints where the available slots significantly outnumber the items. The diagonal constraints are "loose" because there are approximately $4n$ diagonals. For a large board, a queen has many potentially "safe" diagonal positions.
Morris argues that successful algorithms effectively "factor out" the tight constraints. By restricting the search space to permutations (where each queen is assigned to a unique column), the algorithm only needs to resolve the loose diagonal constraints.
The Amphitheatre Landscape
When the tight column constraints are factored out, the resulting search space takes on a specific geometric character that Morris describes as an "amphitheatre." In this landscape, solutions are located at the bottom, surrounded by "stairs" or plateaus of width 2.
This geometry explains the discrepancy between different local search variants. A "1-step" local optimum (where no single move improves the state) is often a "pit" that is not a solution. However, a "2-step" equilibrium point (where no sequence of two moves improves the state) is almost always a global solution. If an algorithm has the capacity to traverse these 2-step plateaus—either through lookahead or by allowing moves that do not immediately improve the cost—it will almost inevitably fall into a solution.
Analytic Results
Morris employs a probabilistic approach to calculate the limit of solution density as $n$ tends toward infinity. He breaks the problem into sub-components ($n$-rooks and $n$-bishops) to build toward the full $n$-queens proof:
- Theorems 1 & 2: In the simplified $n$-rooks and $n$-bishops problems, the density of solutions among local optima approaches 1 as $n$ increases.
- Theorem 3: In the full $n$-queens problem, the density of solutions in 2-step equilibrium points approaches 1. This provides the theoretical justification for the success of algorithms like Min-Conflicts and QS1, which can navigate the 2-step plateaus of the amphitheatre landscape.
- Theorem 4: Conversely, for 1-step Simple Hill-Climbing (SHC), the solution density tends toward 0 as $n$ grows. This explains why naive hill-climbing fails on large-scale problems despite the overall abundance of solutions.
Empirical Validation
To support the theoretical findings, Morris conducted experiments on the 1000-queens problem. The results were stark: Simple Hill-Climbing failed to find a solution in 100 trials, while algorithms designed to account for the 2-step nature of the landscape (allowing for sideways moves or using a "head-start" preprocessing) achieved near-perfect success rates. These results align with the empirical data from Minton et al. (1990) and Sosic & Gu (1991).
Conclusion and Implications
The paper concludes that the success of local search on $n$-queens is not a fluke of the specific problem, but a result of the mathematical relationship between tight and loose constraints. By identifying and factoring out tight constraints, the search space is transformed into a manageable landscape where local optima are likely to be global solutions. Morris suggests that this principle can be generalized to other Constraint Satisfaction Problems (CSPs), such as scheduling, providing a roadmap for designing more effective local search heuristics in other domains.
Summary updated