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. sub.1 through X.sub.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.sub.1 through X.sub.H, determining for each variable X.sub.i, H i≦N a list of feasible values any one of which could be assigned to X.sub.i ; and storing the lists of feasible values in a Feasible.sub.-- Value table data structure.