Introduction
This research addresses a fundamental inefficiency in how logic programming languages like Prolog handle complex combinatorial puzzles and scheduling tasks. Historically, these systems relied on a "generate and test" strategy, which leads to significant performance bottlenecks. This paper proposes a shift from "blind searching" to "active pruning" by introducing explicit variable domains into the logic engine.
The Problem: Passive Constraints and Pathological Backtracking
Standard logic programming is notoriously inefficient at solving Constraint Satisfaction Problems (CSPs), such as Sudoku or industrial scheduling. The culprit is the "a posteriori" approach: the solver picks a value for a variable and only afterward checks if it violates any constraints. If a violation occurs, the system backtracks, often repeatedly rediscovering the same failures. This "pathological backtracking" makes many real-world problems computationally intractable without complex meta-interpreters that add significant overhead.
Methodology: Active Pruning via Domains
The authors propose three primary extensions to the logic programming framework to transform constraints from passive tests into active filters:
- Domain Declarations (d-variables): Variables are explicitly tied to a finite set of constants (e.g.,
domain(X) = {1, 2, 3, 4, 5}). - Modified Unification: The core engine's unification algorithm is updated to calculate the intersection of domains. If the intersection is empty, the match fails immediately, preventing the exploration of invalid branches.
- Active Built-in Predicates: Standard predicates like $\neq, \leq,$ and $>$ are redefined to be "active." Instead of just returning a boolean value, these predicates actively remove impossible values from a variable's domain as soon as they are encountered.
Key Insights and Heuristics
- Active vs. Passive Constraints: By treating a constraint as a filter rather than a test, the system prunes the search tree before assignment, implementing "forward checking" naturally.
- The "First Fail" Principle: With access to domain sizes, the solver can dynamically prioritize the "most constrained" variable (the one with the smallest domain). This heuristic often leads to finding a solution—or identifying a failure—much faster.
- Data-Driven Computation: When combined with delay mechanisms, constraints act as "demons" that trigger automatically as domains narrow, creating a highly reactive and efficient solver.
Evaluation and Results
The approach was evaluated using classic combinatorial benchmarks, including the N-Queens problem and complex logic puzzles.
In the 5-queens problem, the system found solutions with only two choices and zero backtracking. In more complex scenarios, such as the "Tennis Match" puzzle, the domain reduction was so effective that the system could occasionally solve the entire problem through constraint propagation alone, without needing to make any speculative "guesses."
Conclusion and Future Work
While the initial implementation of certain inequality predicates was noted as suboptimal, this work marked a pivotal moment in the evolution of logic programming. By integrating domain reasoning directly into the unification engine, the authors laid the groundwork for modern Constraint Logic Programming (CLP) languages, enabling declarative languages to tackle industrial-scale combinatorial challenges.
Summary updated