Patent US 5,249,261

Method and apparatus for improving an efficiency of solution of constraint-satisfaction type problems performed with a digital computer. A method includes the steps of creating a data structure having storage allocated for a plurality of entries, each of the entries having a plurality of attribute fields, including a Binding.sub.-- set attribute, a Potential.sub.-- savings attribute and an Accumulated.sub.-- savings attribute. The method further includes a step of inserting entries into the data structure in response to an occurrence of a failure path identified during a backtrack search of a search tree structure. The method also includes a step of examining the entries of the data structure during a backtrack search in order to avoid paths of the tree structure that are repetitively identified to be failure paths. The step of examining occurs before a forward move from a node of the search tree and determines if a value of a current set of bindings associated with a path from a root node to a current node is already present within the Binding.sub.-- set attribute of an entry in the data structure. If present, the search backtracks to a father node of the current node thereby avoiding a previously identified failure path.