Patent ID: 8849741

Claim:
A system for determining an efficient solution to a constraint satisfaction problem (CSP), comprising: a non-transitory computer-readable storage medium storing executable computer program instructions comprising instructions for: initializing the CSP and constructing a binary tree using the CSP, the CSP modeling a real world problem in an application domain, the CSP comprising a plurality of variables, a plurality of states, and one or more constraints determining which states each variable is permitted to be assigned to in a CSP solution, the CSP solution modeling a real world solution to the real world problem; iteratively searching the binary tree to determine an efficient solution to the CSP, the searching comprising starting a new iteration of the search of the binary tree when a search depth is less than a restart depth, the restart depth based on a deepest depth previously searched minus a restart value, wherein the search depth is the depth measured when backtracking up the binary tree after reaching a leaf node of the binary tree, and a new iteration of the search is a search that begins at the root node of the binary tree and reporting the efficient solution; a processor for executing the computer program instructions.