Hybrid backtrack/lookahead search technique for constraint-satisfaction problems

摘要

A method of solving a constraint-satisfaction problem with a data processor includes the steps of (a) providing a search tree structure (10) representing a plurality (N) of variables (X), the search tree structure having a plurality of levels; (b) searching (L) shallow levels of the search tree structure by employing a backtrack search method wherein (L) is less than or equal to a specified value H; and (c) searching (M) remaining, deeper, levels of the search tree structure by employing a lookahead search method. The step of searching (L) shallow levels of the search tree structure includes a step of binding a set of X₁ through X_H variables each to an element from its domain such that no constraints are violated. The step of searching (M) remaining, deeper, levels of the search tree structure includes the steps of, given the bindings for the set of variables X₁ through X_H, determining for each variable X_i, H i ≦ N a list of feasible values any one of which could be assigned to X_i; and storing the lists of feasible values in a Feasible_-Value table data structure.