Abstract: This paper introduces a hybrid search strategy, IC2, which integrates stochastic local search with systematic backtracking to solve complex Constraint Satisfaction Problems (CSPs). By leveraging the strengths of both methods, the approach successfully navigates highly structured search spaces, leading to the resolution of several open problems in quasigroup design theory.
Introduction
In the field of automated reasoning, two primary methodologies traditionally dominate the landscape of search: systematic backtracking and stochastic local search. Backtracking is a complete method that explores a search tree, making it ideal for proving unsatisfiability; however, it often falters in massive search spaces. Conversely, local search is an incomplete, stochastic method that excels at finding solutions in dense problem spaces (such as the N-Queens problem) but struggles with "structured" problems where solutions are sparse and mathematically dependent.
The gap between these methods is most evident in problems like Quasigroups—algebraic structures similar to Sudoku puzzles. In these domains, the search space is vast, yet the constraints are highly structured, requiring a level of logical inference that pure local search lacks, while remaining too large for pure backtracking to navigate efficiently.
The IC2 Procedure
The authors propose a new procedure called IC2, a two-phase incomplete search strategy designed to bridge this gap:
- Phase 1 (Initialization): Rather than starting with a random full assignment or an empty set, the algorithm generates a "good" partial interpretation. It assigns values to a specific subset of variables, defined by the parameter $MaxD$. This initialization can be achieved through random selection, greedy local search, or constraint propagation.
- Phase 2 (Extension): This partial solution is then handed to a systematic backtracking solver (such as SEM or SATO). The solver attempts to complete the assignment using logical inference and pruning.
To prevent the backtracking phase from becoming trapped in a massive, unsatisfiable branch, the authors implement a "Safety Valve" parameter ($MaxBr$). This limits the number of branches explored; if a solution is not found within this limit, the algorithm restarts Phase 1 to generate a new stochastic "jump" into a different region of the search space.
Datasets and Problem Domains
The researchers evaluated the IC2 method on several difficult benchmarks, ranging from classic puzzles to complex algebraic structures:
- N-Queens Problem: A standard benchmark for search efficiency.
- Random 3SAT: Propositional satisfiability problems.
- Algebraic Structures: Finding finite models for Groups, Rings, and Non-commutative Groups (NCG).
- Quasigroup Problems: Specifically, "holey quasigroups" (Latin squares with empty subsquares), including types QG2, QG4, and QG50.
Key Results and Insights
The hybrid approach proved significantly more effective than either parent method for structured problems. By maintaining logical dependencies during the backtracking phase, the solver avoided the "search traps" that typically plague pure backtracking.
Solving Open Problems
Most notably, the IC2 method solved four open problems in design theory regarding the existence of specific holey quasigroups (e.g., $QG2(1^{27}, 4^1)$). These problems had remained unsolved by previous systematic or local search methods.
Efficiency Gains
Empirical testing demonstrated substantial performance improvements. For instance, on Non-commutative Groups (NCG) of size 20, the hybrid method found a solution in 170 seconds, whereas standard backtracking solvers often failed to terminate within reasonable time limits. The strategy's versatility was further proven by its successful integration into both SEM (first-order logic) and SATO (propositional logic) solvers.
Limitations and Future Work
While powerful, the IC2 method is inherently incomplete. Because it utilizes a stochastic starting point and limits backtracking depth, it cannot prove that a problem is unsatisfiable. It is designed to find "needles in haystacks" rather than prove the haystack is empty. Additionally, the method struggles with problems that have extremely few solutions, where random jumps are unlikely to land near a valid starting configuration. Future research will focus on the automatic tuning of parameters like $MaxD$ and $MaxBr$ to optimize performance across diverse problem sets.
Summary updated